发布时间 : 星期二 文章编译原理课程设计说明书--词法分析，语法分析，语义分析更新完毕开始阅读
桂林电子科技大学编译原理课程设计说明书 第7页
白（0）f_删 白 (0,3) f_改 非白 (除0) f_回 0 1 0 非‘\\r’（除3）f_删 ‘/’(1) f_删 ‘\\r’（3）f_改 ‘/’（1）f_删 2 3 0 *（2）f_删 ‘/’（1）f_改 非* (除2)f__删 4 10 *(2)f_删 非‘/’非* （除1除2）f_补 *(2)f_删 非‘/’（除1）f_删 5 0 _，l，d（4,5,6）f_留 _，l（4）f_留 6 1-9（5）f_留 其他（除4，5, 6） f_读 0 0-9（5,6）f_留 7 （除4）f_读 非_非l 0 _, l,d(4,5,6)f_错 9 非_, l,d (除4,5,6)f_回 _, l （4）f_错 0 0（6）f_留 8 u 0-9（5,6）f_错9 0 11 其他（除5,6） f_读 运算符（2，7，9） f_留 10 =（9）f_留 全部f_读 0 非=（除9）f_读 0 界符（8）f_留2 0 非“”（除10）f_留 “（10）f_留 ”（10）f_读 12 0 桂林电子科技大学编译原理课程设计说明书 第8页
说明：
1、字符转换表：字母，下划线（_）化为一类，为识别标识符用。0单独处理是用于识别单个0和以0开头的错误整数；这里的运算符是指可以和“=”连在一起作为一个词元的，如>=,<=,+=,-+,*=,/=；界符是指一个字符做为一个词元的，如｛ ｝（ ） ； ，等。
2、函数说明：
f_留，表示将当前字符存到缓冲数组里面；
f_读， 提取词元，从缓冲数组里面读出当前词元，并将缓冲数组清空； f_回，转到中转0状态之前，将当前字符回退到输入流中。
f_留2：为后面添加，单个字符组成的词元，不用存到缓冲数组里面，直接提取成一个词元，存到词元结构体数组里面。
3、字符转换表如下：（状态转换表、动作转换表略） 白’ / * \\r 字母、_ 数字 0 运算符 界符 = “ 0
1 2 3 4 5 6 7 8 9 10 2.2 .语法分析
2.2.1 递归下降手工编码
这个模块是给定状态转换表，action表，之后对输入的表达式进行词法分析，判断表达式正误。
其中文法如下：
E:=TE’
E’:=+TE’|@ T:=FT’
T’:=*FT’|@ F:=id|di|(E)
所定义的函数为：
void f_exp(); void f_term(); void f_factor();
void f_term_remains(); void f_exp_remains();
2.2.2 first集合的计算
这个模块进行的是first集合的计算。定义的文法存储数据结构为： struct define { char left;
桂林电子科技大学编译原理课程设计说明书 第9页
string right; };
设计思路：整体上采用不动点算法
依次扫描每条文法右部，若遇到终止符，则将该终止符加入文法左部非终止符的first集中。如果遇到非终止符，则先判断该终止符的first集合中是否包含@（“@”代表“可空”），如果不包含@，则将该非终止符的first集加到文法左部的非终止符的first集中；如果包含@，并且该非终止符不是最后一个非终止符，则将该非终止符的first集合去掉@后，加到文法左部的first集合中；否则直接将此非终止符的first集合加到文法左部的first集合中。
具体描述如下：
对于任意给定的LL(1) 文法G,为了构造它的预测分析表M,我们就必须构造与文法G有关的集合First和fellow.首先我们对每一个X∈VT U Vn ,构造
FIRST(X),办法是,连续使用下面的规则,直至每个集合FIRST不再增大为止. (1)若X∈VT,,则FIRST(X)={X}.
(2)若X∈Vn ,且有产生式X->a??,则把a加入到FIRST(X)中,若X->ε,也是一条产
生式,则把ε也加到FIRST(X)中.
(3)若X->Y??是一个产生式且Y∈Vn,则把FIRST(Y)中所有非ε-元素都加到
FIRST(X)中,若X->Y1Y2??YK ,是一个连续的产生式, Y1Y2??Yi-1 都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj) 都含有ε(即Y1Y2??Yi-1=>ε),则把FIRST(Yi) 中的所有非ε-元素都加到FIRST(X)中,特别是,若所有的FIRST(Yj)均含有ε,j=1,2,??,k,则把ε加到FIRST(X)中.
辅助函数：
/*统计文法条数，非终止符个数，终止符个数，并把非终止符，终止符弄成一个字符串，用于查找下标*/
void get_gene() //获得产生式，并统计
int get_index(char b); //得到终止符或非终止符的统一下标 void add(string &tLeft , string s);将s添加到tLeft中，即将右边的字符串添加到左边的字符串中，去掉重复，如果右边存在新的字符，要将flag置为 1 ，用于不动点算法。
2.2.3 左递归消除
设计思路：
将间接左递归变成左递归，然后消除直接左递归。 （1） 把文法的所有非终止符按某一顺序排序，如： A1，A2，…….An；
（2） 从A1开始消除都为A1的产生式的直接左递归，然后把左部为A1的所有规则的右部逐个替换为A2开始的产生式中的A1，并消除左部位A2的产
桂林电子科技大学编译原理课程设计说明书 第10页
生式中的直接左递归，继而以同样的方式吧A2的右部代入左部为A3右部以A1或A2开始的产生式中，消除左部为A3的产生式之直接左递归，直到把左部为A1，A2，…….An-1的右部代入左部为An的产生式中，从An中消除直接左递归。
把上述算法归结为：
如非终止符的排序为：A1，A2，…….An FOR i:=1 TO N DO BEGIN FOR j:=1 TO i-1 DO BEGIN 如Aj的所有产生式为： Aj->a1|a2|….|ak 替换形成Ai->Ajr的产生式变为： Ai->a1r|a2r|….|akr END
消除Ai中的一切直接左递归. END.
（3） 去掉无用产生式。 2.2.4
selection表自动生成
设计思路：
扫描文法，计算文法右部的first集合（“@”不计算在内），直接将文法去右部填入文法右部计算得到的相应first集合和文法左部对应的selection表项中。此代码比较简单，附如下：
void count_selection(define *p,string *first,string *follow,string **selection,int count,int count_T) { for(int i = 0;i