[Theory] Parsing Techniques 读书笔记（七）：非经典的解析技术

非经典的解析技术（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解析的非经典方法。

如果当前无法识别为唯一的非终结符，则表示为一个集合，继续往后识别。

等到可以决定的时候，再回来消除这种不确定性。

广义确定性解析器（Generalized Deterministic Parser）：结合了确定性解析技术（解析表），与（广度优先）搜索技术（当遇到不充分状态（inadequate state）时）的解析器。

GLR解析器（Generalized LR Parsers）：借用了LR自动机，但是当出现不充分状态，对状态栈拷贝进行广度优先搜索。

GLL解析器（Generalized LL Parsers）：在进行LL非终结符推导时，同时推导非终结符的多种可能（广度优先，或者深度优先）。

GLR解析器，可以进行一些优化：

（1）在拷贝状态栈的时候，合并后缀

（2）对合并了的状态站，合并前缀或中缀

经过状态栈合并，多个广度优先搜索的状态栈，就变成了一个有向无环图，称为图结构的栈（graph-structured stack，GSS）。

包含左递归和空串规则（ε-rules）的文法，会使状态栈包含环。

简单的GLR解析器的算法复杂度是指数时间的，标准GLR的算法复杂度是多项式时间的，多项式的次数与文法中的最长产生式相关。

LR(1)自动机包含了太多的状态，GLR(1)需要拷贝大量的状态，因此反而不是最好的选择。

更好的选择是基于LALR(1)，会比LR(0)好一点点，5%-10%。

子串解析（Substring Parsing）：对不完整字符串的解析技术，主要包括两种：片段，后缀。

语言L的后缀语言（suffix language）：删除语言L中字符串的某些前缀，最后得到的语言。

文法可以用有限的描述，生成字符串的无穷集。

解析则是判断给定的字符串是否可以由特定的文法生成。

后缀解析涉及到了两种数据结构：最大化的解析森林（maximally supported parse forest），最小化的解析树（minimally completed parse tree）。

上下文无关语言的后缀语言，仍然是上下文无关语言。

新语言的文法，可以由原语言的文法构造出来。

通用的后缀语言解析方法，也包括了定向解析（directional）的和非定向的（non-directional）。

CYK算法只能识别非终结符生成的完整字符串，不能识别不全的字符串。

一个后缀是由识别出的非终结符，加上无法识别的字符串组成的，这就形成了一个后缀开始序列（suffix start sequences）。

后缀的开始序列的集合称为根集（root set），开始序列的文法称为根集文法（root set grammar）。

根集文法是正则文法，可以用有限状态自动机来解析。

定向解析方法，通过调整Earley解析器来实现，时间复杂度是立方级的。

线性复杂度的后缀解析方法，还比较少，Earley-on-LL(1)解析器，GLR后缀解析器。

LL(1)文法的后缀文法，不是LL(k)的。

上下文无关语言与正则语言的交集，还是上下文无关语言。

交集算法

（1）把输入字符串理解为一个有限状态自动机，每个输入一个字符跳转到一个新状态。

（2）对上下文无关文法中的终结符和非终结符添加后缀，枚举所有可能性，表示当前匹配让自动机从哪个状态切换到了哪个状态。

（3）对结果文法进行清理，得到交集的文法。

这样生成的文法，和解析森林文法（parse-forest grammars）非常相似。

上下文无关语言与正则语言求交集后，还可以再与另一个正则语言求交集。

通过求交集的技术，可以枚举出符合文法的包含未知字符的所有字符串。

还可以用来进行子字符串解析。

Parsing Techniques

根据你说的情况看，你是想编辑一个注册表修改文件，也就是 REG 后缀的文件；

REG注册表这样的文件，采用文败仔本编辑器都可以做，不用c语言的，c语言的一种编察租汪程语言。

给你一个百度型搜百科链接，你看看吧，说的非常详细的！！

http://baike.baidu.com/link?url=4AU4QigllJ6LxF7JkjMA8EiT-mWQW7GFcBHBFD_jxB7BmBejZxZhX-c8hLUqf4OW

---