美文网首页Theory
[Theory] Parsing Techniques 读书笔记

[Theory] Parsing Techniques 读书笔记

作者: 何幻 | 来源:发表于2019-08-28 12:39 被阅读0次

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

相关文章

网友评论

    本文标题:[Theory] Parsing Techniques 读书笔记

    本文链接:https://www.haomeiwen.com/subject/mbupectx.html