编译原理实验之 LL(1) 语法分析器设计

编译原理第二个实验是 LL(1)语法分析，这里我来写一下关于 LL(1)的内容，虽然书上都有，但是总结一遍，应该印象更加深刻的，也有助于写代码。目前 LL(1)实验已全部完成，项目地址：http://115.159.147.250:666/LL1/，代码地址：https://github.com/netcan/compilingTheory，效果图：

我写这篇博文写了好几天了，描述比较凌乱，建议大家还是看书吧，或者直接看我 程序设计部分 。一定要搞懂 集和 集的求法，不然写程序也会遇到困难的，这里有篇不错的关于求 和集的论文，推荐看看：https://www.cs.virginia.edu/~weimer/2008-415/reading/FirstFollowLL.pdf

LL(1)文法主要是求 集和 集，个人觉得 集比较麻烦点，然后就是用这两个集合求预测分析表。

集

集就是求文法符号串 的开始符号集合，例如有以下文法：

用例子还是比较好说明的，很容易求出各非终结符的 集。

这里给出 集的一般描述。

也就是说，如果非终结符 有产生式，那么它们，这个不难理解，因为我（）能推出你（），你又能推出它（开始符号，终结符），那我们都能推出它。

集的作用是，当用来匹配开头为 的文本时，有产生式 ，若，则选择候选式，若，选择，说了那么多，我只想说，不是用 这个来匹配 ，而是用它的候选式 或者 来匹配。

用上面的例子来说，匹配 ，因为，应该选择 这个候选式。

集

集比较抽象，它用来解决这个问题的，如果非终结符 的含有，那么选择会不确定，比如说，

很容易求得

匹配开头为 ，因为，选择 产生式，匹配开头为 ，因为，选择 产生式。然而当我匹配 时，因为 ，这时候就不知道选择哪个产生式了，但是因为，且，应该选择 的，这说明了 集的不足，从而引进 集。

给出定义，即为非终结符 后面可能接的符号集。

至于怎么求，我就直接摘抄 PPT 的定义吧，然后在说明。

连续使用下面的规则，直至每个 不再增大为止。

• 对于文法的开始符号 ，置 #于 中。
• 若 是一个产生式，则把 加至 中；
• 若 是一个产生式，或 是一个产生式而 ，则把 加至 中。

第三条规则可以这么理解，因为 后面啥都没，又能推出 ，所以应该把 后面的符号（）加入 中。需要注意的是，集不含。

所以要求某个非终结符的 集，只要在 产生式右边 中找，然后根据它后面一个 符号 按照上述规则计算就行了。

预测分析表

求得 集和 集后，求分析表就比较容易了。这里简单说下构建方法。

对文法的每个产生式，执行下面步骤。

• 对 的每个 终结符 ，将候选式 加入
• 如果 ，把 的每个 终结符 （包括 #），把 加入。

程序设计

代码的核心部分就是求 集和 集了，这也是程序的精髓所在。

首先我约定字符 @代表，因为键盘上没那个符号，所以随便找了个合适的符号代替。约定单个大写字母代表非终结符，小写字母或某些符号代表终结符。

然后设计一个叫做产生式的类 Prod，它的构造函数接受一个字符串，字符串描述了一个产生式。然后分割字符串，把它的非终结符存入noTerminal 成员中，候选式存入 selection 集合中。

接着设计一个叫 LL1 的类，也就是核心部分了，它提供了求 first、follow、分析表等方法。因为first 集和 follow 集可能会求未知表达式的 first 集和 follow 集，比如说A->B，B->C，欲求first(A)，需求first(B)，欲求first(B)，需求first(C)，从而确定了这两种集合求法只能用递归来求，这也是我所能想到的最简单求法，可以参考我代码。

然而现在（2016/10/21）补充下，经过反复调教，first集都重写了 5 次，而 follow 集是 不能用递归 来求的，因为有可能出现这种情况：

求 follow(A) 需要 first(S) 和follow(S)，递归求 follow(S) 需要follow(A)，然而这样就进入了死递归。所以最后我改写成 5 个循环搞定。

求出了 first 和follow，剩下的就好办了。至于图形界面，和 上次 一样，套了个 php，通过php 传 json 数据到前端，前端输入数据取数据，渲染页面。那颗语法树的画法，通过前序遍历画得。