编译原理数学表达式的语法分析

1、编译原理数学表达式1、算术表达式的语法表示E->E+T|E-T|TT->T*F|T/F|FF->num|(E)文法 1.1算术 4 则运算的表达式有左递归，首先要消除左递归进行语法 变换，变换成如下形式：E->TE'E'->(+T-T)E'T->FT'T'->(*F|/F)T 'F->num|(E)文法 1.22、确定文法的 firSt 集合2.1、FirSt集合的定义 ?FirSt(A) = a | A? a ,A VN a ?其中VN是非终结符，？?是终结符 A=X, X VN?A=X1X2Xn

2、, Xi Vn ?2.2、构造FirSt集合的算法对于每个 X VN ?, 连续使用下面的规则，直至每个 FirSt 集合不再增大位置： 如果 X ?则 FirSt(X)=X。 如果 X VN, 且有产生式 X->a., 则把 a 加入到 First(X) 中，其中a ?;如果X-> 也是一条产生式，则把也加入到 FirSt(X) 中。 如果X->Y是一个产生式，并且 Y VN则把First(Y的所有 非元素都加入到FirSt(X)中; 如果 X-> Y1Y2.Y i-1 Yi. Yk 是一个产生式， Y1Y2.Y i-1 都 是非终结符，对于任何j，1 j i-1，F

3、irSt(Y j)都含有 (即?Y1Y2.Y i-1 ? ),则把FirSt(Y i)中的所有非元素都加入到 FirSt(X)中；如果所有的FirSt(Y j)均含有, j=1,2，,k, 则把加到FirSt(X)中。2.3、确定算术表达式的FirSt集合根据 2.2 中所描述的算法，来确定文法 1.2 的各个非终结符的FirSt集合FirSt(E) = FirSt(T) 根据规则 3FirSt(E'-), =+ , 根据规则 2FirSt(T) = FirSt(F) 根据规则 3FirSt(T')=*,/, 根据规则 2FirSt(F)=num, ( 根据规则 2将后来确定的

4、FirSt集合带入到不确定的FirSt集合就能得到风格 非终结符的FirSt集合：First(E) = num, ( First(E ' -),=+, First(T)=num, ( First(T ' )=*,/, First(F)= num, ( 3、 确定文法的 Follow 集合3.1、Follow 集合的定义?FolloW(A) = aS?Aa； a ?,其中？是终结符。3.2、构造Follow集合的算法对与文法G的每个非终结符A构造Follow(A)的办法是连续使用下 面的规则，直至每个Follow不再增大为止： 、对于文法的开始符号5,置#于Follow(S);

5、、如果A-> Be是一个产生式，则把First( )的非空项，加 入到 Follow(B); 、如果A-> B是一个产生式，或者A-> Be是一个产生式而?且 e ? (即 First( e ),则 把 Follow(A)加 入 到Follow(B) 。3.3、确定算术表达式的Follow集合根据 3.2 中描述的 Follow 集合的构造算法，为文法 1.2 构造Follow 集合：Follow(E)=#,) 根据规则 1 和 2FolloW(E ' ) = Follow(E根据规则 3FolloW(T) = First(E-, Fo)ow(E) 根据规则 2,3F

6、ollow(T ' )=Follow(T根据规则 3Follow(F) = First(T- , Fo'llo)w(T) 根据规则 2， 3最终Follow(E)=#， ) Follow(E ' )=#,) Follow(T)=+,-,#,)Follow(T ' )-=,#+,),Follow(F)=*,/,+,-, #,)4、 递归下降分析算法实现 针对最终的经过变换的 1.2 文法编写递归下降分析程序，为便 于理解每条文法规则下面直接给出C程序实现。E->TE'其对应的C语言实现void parse_E()parse_T();parse_EDo

7、t();return;E'(+T-T)E ' 其实现：void parse_EDot()char c = stri;if (c = '+' | c = '-')i +;parse_T(); parse_EDot();return ;T->FT'其实现：void parse_T()parse_F(); parse_TDot(); return;T'->(*F|/F)T'其实现：void parse_TDot()char c = stri;if (c = '*' | c = '/')

8、i +;parse_F(); parse_TDot();return ;F->num|(E)其实现void parse_F()char c = stri;if (isdigit(c)i+;return;if (c='(')i+;parse_E();c = stri;if (c=')')i+;return;error ("')'", c);return;error ("'0 -9' or '('", c);return;上面的分析程序没有考虑 Follow 集合的处理，这

9、是因为 Follow 集 合即便不处理，也能在后续的分析处理中，发现错误。 最后给出错误处理程序和主程序， 主程序中有几个算术表达式的例子， 可以将代码整合起来，直接编译执行。void parse (char *e)str = e;i = 0;parse_E();if (stri='0')return;error ("'+' or '0'", stri); return;int main (char argc, char *argv)char *e;e = "(2)"parse(e);e = "(

10、3+4*5)"parse(e);e = "(8-2)*3"parse(e);e = "(8-2)/3"parse(e);printf("complier stop!n");return 0;int i;char *str = 0;void error (char *want, char got)fprintf (stderr, "Compling this expression:n%sn", str); int j = i;while (j-)fprintf (stderr, " ");fprintf (stderr, &qu