2.4 少许理论知识——LL（1）与LALR（1）

2.3.2节中手写的解析器会对记号进行预读，并按照语法图的流程读入所有记号。这种类型的解析器叫作LL（1）解析器。LL（1）解析器所能解析的语法，叫作LL（1）语法。

采用LL（1）语法，当然能制作出对应的编程语言来。比如Pascal的语法就是LL（1）。

但是看了代码清单2-9就能明白，LL（1）解析器在语法上需要非终结符与解析器内部的函数一一对应。也就是说，只看第一个进入的记号，还无法判断需不需要继续往下读取，也不能知道当前非终结符究竟是什么。

比如在Pascal中，goto语句使用的标签只能是数字，这样限制的原因是，如果像C语言一样允许英文字母作为标识符的话，读入第一个记号时，就没有办法区分这个记号究竟是赋值语句的一部分，还是标签语句的一部分。因为无论赋值语句还是标签语句，开始的标识符是一样的。由此可知，LL（1）语法所做出的解析器都比较简单，语法能表达的范围比较狭窄。

那么，在把计算器的BNF改写为语法图的过程中，一些敏锐的读者可能已经有了这样的疑问：

不管是用BNF还是语法图，都应该只是表面上有区别，语法实现部分应该是一样的啊。但你写的代码怎么连算法都不一样？我有种上当了的感觉。

实际上确有此事，在把BNF置换为图2-5所示的语法图时，我运用了一个小手法。在BNF中语法规则是这样的：

      expression /＊ 表达式的规则 ＊/
              | expression ADD term /＊ 或 表达式 + 项目 ＊/

而在实现递归下降分析时，如果仍然按这个规则在parse_expression（）刚开始就调用parse_expression（），会造成死循环，一个记号也读不了。

BNF这样的语法称为左递归，原封照搬左递归的语法规则，是无法实现递归下降分析的。

所以yacc生成的解析器称为LALR（1）解析器，这种解析器能解析的语法称为LALR（1）语法。LALR（1）解析器是LR解析器的一种。

LL（1）的第一个L，代表记号从程序源代码的最左边开始读入。第二个L则代表最左推导（Leftmost derivation），即读入的记号从左端开始置换为分析树。而与此相对的LR解析器，从左端开始读入记号与LL（1）解析器一致，但是发生归约时（参看2.2.3节图2-3），记号从右边开始归约，这称为最右推导（Rightmost derivation），即LR解析器中R字母的意思。

递归下降分析会按自上而下的顺序生成分析树，所以称作递归“下降”解析器或递归“向下”解析器。而LR解析器则是按照自下而上的顺序，所以也称为“自底向上”解析器。

此外，LL（1）、LALR（1）等词汇中的（1），代表的是解析时所需前瞻符号（lookahead symbol），即记号的数量。

LALR（1）开头的LA两个字母，是Look Ahead的缩写，可以通过预读一个记号判明语法规则中所包含的状态并生成语法分析表。LALR也是由此得名的。

本章中实际制作的计算器是采用LL（1）语法作为解析器的，因为比较简单，所以适合手写。如果是LALR（1）等LR语法的话，则更适合用yacc等工具自动生成（这话可能已经说了太多遍了）。不过，最近像ANTLR、JavaCC等一些采用LL（k），即预读任意个记号的LL解析器也开始普及起来。

      Hoge ＊hoge_p = NULL;