[Theory] Parsing Techniques 读书笔记

10. Non-Canonical Parsers

名词定义

非经典的解析技术（Non-canonical paring methods）：通过延迟决策，采取了比较自由的节点构建顺序。

分部LL解析（Partitioned LL）提取了所有可能推导的公共前缀，先进行处理下去，而不是因为有歧义而报错。
分部LR解析（Partitioned LR）是一种自底向上的，延迟LR解析的非经典方法。

一般化的非经典解析（General Non-Canonical Parsing），引入了一种称为头部文法（head grammar）的概念，
在编写文法时，可以标记哪个非终结符包含了关键信息，从这里开始推导。

内容总结

自顶向下解析器使用先序（pre-order）方式构建解析树，先识别父节点，再识别子节点，最终模拟了最左推导（left-most derivation）过程。
自底向上解析器使用后序（post-order）方式构建解析树，先识别子节点，再识别父节点，最终模拟了最右推导（right-most derivation）过程。

非经典解析技术的好处是，一大堆文法不加修改，就可以用线性复杂度的方式来解决了。

有三种非经典的自顶向下解析：
（1）左下角解析（left corner parsing）
（2）消除解析（cancellation parsing）
（3）分部LL解析（Partitioned LL）

左下角解析（left corner parsing）从开始符号开始，不断的推导，得到最终能匹配到终结符的形式。
这会产生一个有限状态自动机，称为产生式链自动机（production chain automaton），这个自动机描述了开始符号的所有最左推导。
通过对这个自动机的推导顺序进行逆转，我们就得到了一个有效的识别方式，只有读取自动机中标注字符，才可以反向回到开始符号。
这样得到的解析器，称为LC(1)解析器（left corner parser）。

左下角解析器最终识别节点的顺序是中序的（infix order），因此要想得到解析树，还要再进行一遍后处理。
LC(1)文法的处理过程，可用于将LC(1)文法，转换为LL(1)。
对于任意的上下文无关文法，如果转换过后的文法是LL(1)的，则原文法就是LC(1)的。

分部LL解析（Partitioned LL）提取了所有可能推导的公共前缀，先进行处理下去，而不是因为有歧义而报错。
这样得到的解析器称为分部解析器（Partitioned LL(1)），或简称为PLL(1)。

自底向上解析，延迟了子树的识别过程，允许对非终结符进行前瞻。
所谓延迟识别就是先往下进行，而不是报错。

NSLR(1)解析算法思路：
（1）将非终结符也加入到FOLLOW集中。
（2）用前瞻字符，不断的过滤所有可能的解析，即使有歧义也往下进行
（3）直到最后剩下一种可能

LR(k,∞)解析算法思路：
（1）k表示前瞻长度，∞表示可被延迟的决策数
（2）除了前瞻输入字符串之外，还要计算文法中非终结符的当前识别位置的前瞻产生式（dot look-aheads）
（3）前瞻的k个字符串，会对所有可能的推导进行过滤
（4）最后剩下一种可能时，再回溯确定之前的所有决策

LR(k,∞)文法是不可判定的，只有到解析器的运行时，我们才能决定某个文法是不是LR(k,∞)。
它是迄今为止所知道的，能力最强大的，可以处理有歧义文法的线性时间解析算法。
LR(k,∞)解析算法有一些小问题，例如所有可能的推导集可能会指数级暴涨，可以采用将这个集合转换为正则表达式描述来解决。
LR(k,∞)有时也称为NLR(k)（Non-canonical LR(k)）。

LR(k,∞)的缺点是不可判定性，为此我们可以限制可延迟决定的步数为t，LR(k,t)。
这样就得到了一个确定性算法，且在解析器生成时，就可以判定文法是否LR(k,t)。

分部LR解析（Partitioned LR）是一种自底向上的，延迟LR解析的非经典方法。
如果当前无法识别为唯一的非终结符，则表示为一个集合，继续往后识别。
等到可以决定的时候，再回来消除这种不确定性。

参考

Parsing Techniques