语法分析_lr1到lalr1

到了一定程度，为了提升对程序设计的认知深度，了解编译原理是无法回避的MidStone。编程语言种类繁乱多样，不同的专业领域都有某一具体语言的拥趸，并且彼此间往往当成梗一样的彼此取笑逗乐，如静态语言和动态语言优劣之争，Python、Perl和Ruby的脚本之王争论，Ocmal和Scheme函数式编程简洁之争……

但抛去具体使用场景而谈论编程语言的优劣，无疑是浅薄且不负责任的，无益于方案设计和功能实现。因为编程学习是自学入门，自己沉迷多种编程语言学习打卡已久，如今幡然醒悟，希望以这一系列的文章记录并告诫自己曾今走过的弯路。

任何高级语言最终都会归结到某一具体机器上的具体机器码序列，编译器便是中间的译者，这便决定了任何语言的高级特征都是对应的语言编译器构造的外在体现。有人说，生活从来都不轻松，如果你感觉轻松，说明有人在为你负重前行。这句话同样适用于高级语言和编译器或解释器之间的关系。本系列文章是读者学习初级编译原理的随笔，更多的想法是倒逼自己输出，以达到更深的理解，若有理解偏颇，还望批评指正。

编译器按构造方法和功能可分为：一遍编译器、多遍编译器、装入并执行编译器、调试编译器、优化编译器等。 编译器的阶段划分： 词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成。实际上编译的各个阶段都可以看成完成一定的翻译工作：词法分析是将代码文件的字符流翻译成单词流（ 空格和注释将在这一阶段被滤过），语法阶段是将单词流按照语言语法规则翻译成语法树，语义分析则是在语法树的基础上按照语义规则完成语义操作（ 类型检查、一致性检查、类型转换以及标识符符号表管理等工作）。

语法分析是程序设计语言有限的规则空间和程序实现的无限功能空间映射的关键（用有限数目的规则把语言的全部可能语句描述出来，是用有穷的集合映射无穷空间）。语法分析的输出结果是语法树，故而“树”结构（还有图）是语法分析过程最为直观的表达形式。在初级编译原理中，可以通过对比LL(1)自顶向下分析法、算符优先分析法、LR(0)、SLR(1)、LALR(1)、LR(1)等语法分析方法构建语法树的过程，初窥语法分析原理和程序语言的特征设计。

1. 1 LL(1)自顶向下分析法
   LL(1)自顶向下分析法是从语法规则出发，从文法的开始符号出发企图通过不断的试探往下构建语法树，直到推出和输入的目标单词串完全匹配的句子，是不断“分枝”的过程。在每个非终结符节点根据当前target character终结符确定后续延伸的分支。LL(n)中的n是需要在目标单词串当前位置向后整体搜集n个字符作为匹配集才能唯一确定后续延伸分支，LL(1)显然表示只需要在目标单词串当前位置向后提取1个字符便可唯一确定后续延伸分支。这种限制极大地缩减了待搜索的状态空间，但是这种搜索便捷性是以牺牲设计语言的语义功能为代价的，极大地限制设计语言的适用范围。

2. 2 算法优先分析法
   算符优先分析法属于自底向上分析，核心的特征是忽略单非终结符之间的优先关系，只规定算符（非终极符）之间的优先关系，所以在规约过程中所有的非终结符都用同一标号代表，故而可能会出现将错误的语句规约成功。算符优先分析虽然对文法有一定限制，但是在实际应用中一般用于算数表达式的规约。
   

   

3. 3 LR分析法
   LR(K)分析法括号中K表示向右查看的当前比较集字符集数目。LR(K)分析法比LL(K)和算法优先对文法限制要少得多，对于大多无二义上下文无关文法描述的语言都可以用LR语法分析器解析。LR分析器还具有分析速度快、能准确即时地指出error place，但主要的缺点是对于一个实用语言文法的分析器的构造工作量相当大，K越大构造工作量越大。LR分析法主要是依旧图结构，配置符号栈和状态栈，以及动作表和状态迁移表实现表示文法解析步骤的图结构绘制，用该解析图指导语法分析。

   3.1 LR(0)
   LR(0)在同一项目集上进行的移进或规约动作（两种动作不能同存 )和下一输入符无关，在LR(0)的图网络拓扑是“直肠子网络拓扑结构，一进一出”,网络拓扑完全静态下，无环无递归，编程过程毫无动态性可言。

   3.2 SLR(1)
   在LR(0)基础上，将LR(0)无法处理的同一项目中移进-规约冲突根据当前非终结符A的follow(A)和该项目集移进面临的终结符号集合不相交来做出移进或规约的操作，产生了简单的分路选择空间（多输出），增加了网络拓扑的动态性：多进多出，节点复用，单输出时选择旁路的标准要求极为严格，网络拓扑的粗糙性讲被转移到文法设计的限制上，如同一项目集中的follow集合不应该和可能待移进的符号集合出现相交，这对文法要求太死，基本上断绝了文法设计某些动态特性的可能性。

   3.3 LR(1)
   LR(1)认为SLR(1)在做移进或规约操作时过于死脑筋，讲很多本应该可以可以区分的分支结构，通过follow(A)这一过强范围约束给锁死了选择空间，这是不合理的，故而LR(1)为每个项目集定制属于本项目特有的向前搜索符号集合，从而在SLR(1)基础上做到了更细腻的区分，但这也导致了LR(1)网络节点将比SLR(1)膨胀很多，导致存储容量需求急剧增加。

   3.4 LALR(1)
   LALR(1)则是在LR(1)基础上采用合并同心集的方法，来针对LR(1)节点膨胀问题。同心集是指心相同，只是超前搜索符集合合并为各同心集的超前搜索符集合的和集。合并同心集后对某些错误的发现时间可能会产生推迟现象，但错误的出现位置仍是准确的，即相比与LR(1)可能进行了多几步的规约操作，但是错误不会被忽略。

总结：语法分析是程序设计语言利用有限的规则空间和程序实现的无限功能空间进行映射的步骤，关键是在尽可能快地判断某一语句是否属于目标语言可规约约束的语言，若可以，则在完成规约成功的同时，将语法树予以补全，以供后续语义操作（或者语义分析和语法分析同步交替进行），若规约失败，则根据移进-规约失败节点的环境进行判断并提供compiler error信息，供程序员调试。