语法分析器
实验题目：语法分析程序设计与实现
一．实验内容：
编写语法分析程序，实现对算数表达式的语法分析。要求所分析算数表达式由如下的文法产生。
E->E+T|E-T|T
T->T*F|T/F|F
F->id|(E)|num
二．实现要求：
在对输入表达式进行分析的过程中，输出所采用的产生式。 方法2：编写LL （1）语法分析程序，要求如下。
（1） 编写实现算法4.2，为给定文法自动构造预测分析表。
（2） 编写实现算法4.1，构造LL （1）预测分析程序。
三．程序设计说明
1. 对一个文法如果要进行LL(1)语法分析，首先必须确保该文法没有左递归，所以程序首先进行了消递归。该过程中考虑到文法是通过字符串数组存储的，故分析过程是一个字符一个字符进行的，所以如果消递归过程出现类似E ’,T ’，num,id 多个字符构成一个整体的形式，难以处理，程序中对于这种情况采取只取第一个字符的方式处理，也就是用A 代替E ’,B 代替T ’,n 代替num,i 代替id 。此外在求FIRST 和FOLLOW 集时，将->省去利于处理。
在前面所述思想下，消递归后的输出文法是：
2. 求FIRST 和FOLLOW 集合。
1）求FIRST 集合，首先找到每个生成式的首字符。
如果是终结符，就加入左部符号的FIRST 集合中；
如果是非终结符，将该非终结符的FIRST 集除空以外的元素加入，若该非终结符FIRST 集中有空，继续看它的下一个元素；
若生成式右边的符号均能推出空，则把空加入。
2）求FOLLOW 集合
在起始符的FOLLOW 集中加入＄；
从生成式最后向前遍历，找第一个非终结符；
如果生成式最右边第一个就是非终结符，将生成式左边符号的FOLLOW 集中元素加入该非终结符的FOLLOW 集中；
如果非终结符后有符号，且是终结符, 直接把该终结符加入该非终结符的FOLLOW 集中；
如果非终结符后还是非终结符，将后一个非终结符的FIRST 集加入。
输出结果如下：
3. 根据FIRST 和FOLLOW 集构建分析表
根据算法4.2构造出来的预测分析表如下：
4. 根据算法4.1，构造LL （1）预测分析程序。
5. 输出格式
在对输入表达式进行分析的过程中，输出所采用的产生式。如果输入表达式是错误的，给出错误提示，并且停止分析。