編譯原理數(shù)學(xué)表達式的語法分析

1、編譯原理數(shù)學(xué)表達式1、算術(shù)表達式的語法表示E->E+T|E-T|TT->T*F|T/F|FF->num|(E)文法 1.1算術(shù) 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是非終結(jié)符，？?是終結(jié)符 A=X, X VN?A=X1X2Xn

2、, Xi Vn ?2.2、構(gòu)造FirSt集合的算法對于每個 X VN ?, 連續(xù)使用下面的規(guī)則，直至每個 FirSt 集合不再增大位置： 如果 X ?則 FirSt(X)=X。 如果 X VN, 且有產(chǎn)生式 X->a., 則把 a 加入到 First(X) 中，其中a ?;如果X-> 也是一條產(chǎn)生式，則把也加入到 FirSt(X) 中。 如果X->Y是一個產(chǎn)生式，并且 Y VN則把First(Y的所有 非元素都加入到FirSt(X)中; 如果 X-> Y1Y2.Y i-1 Yi. Yk 是一個產(chǎn)生式， Y1Y2.Y i-1 都 是非終結(jié)符，對于任何j，1 j i-1，F(xiàn)

3、irSt(Y j)都含有 (即?Y1Y2.Y i-1 ? ),則把FirSt(Y i)中的所有非元素都加入到 FirSt(X)中；如果所有的FirSt(Y j)均含有, j=1,2，,k, 則把加到FirSt(X)中。2.3、確定算術(shù)表達式的FirSt集合根據(jù) 2.2 中所描述的算法，來確定文法 1.2 的各個非終結(jié)符的FirSt集合FirSt(E) = FirSt(T) 根據(jù)規(guī)則 3FirSt(E'-), =+ , 根據(jù)規(guī)則 2FirSt(T) = FirSt(F) 根據(jù)規(guī)則 3FirSt(T')=*,/, 根據(jù)規(guī)則 2FirSt(F)=num, ( 根據(jù)規(guī)則 2將后來確定的

4、FirSt集合帶入到不確定的FirSt集合就能得到風(fēng)格 非終結(jié)符的FirSt集合：First(E) = num, ( First(E ' -),=+, First(T)=num, ( First(T ' )=*,/, First(F)= num, ( 3、 確定文法的 Follow 集合3.1、Follow 集合的定義?FolloW(A) = aS?Aa； a ?,其中？是終結(jié)符。3.2、構(gòu)造Follow集合的算法對與文法G的每個非終結(jié)符A構(gòu)造Follow(A)的辦法是連續(xù)使用下 面的規(guī)則，直至每個Follow不再增大為止： 、對于文法的開始符號5,置#于Follow(S);

5、、如果A-> Be是一個產(chǎn)生式，則把First( )的非空項，加 入到 Follow(B); 、如果A-> B是一個產(chǎn)生式，或者A-> Be是一個產(chǎn)生式而?且 e ? (即 First( e ),則 把 Follow(A)加 入 到Follow(B) 。3.3、確定算術(shù)表達式的Follow集合根據(jù) 3.2 中描述的 Follow 集合的構(gòu)造算法，為文法 1.2 構(gòu)造Follow 集合：Follow(E)=#,) 根據(jù)規(guī)則 1 和 2FolloW(E ' ) = Follow(E根據(jù)規(guī)則 3FolloW(T) = First(E-, Fo)ow(E) 根據(jù)規(guī)則 2,3F

6、ollow(T ' )=Follow(T根據(jù)規(guī)則 3Follow(F) = First(T- , Fo'llo)w(T) 根據(jù)規(guī)則 2， 3最終Follow(E)=#， ) Follow(E ' )=#,) Follow(T)=+,-,#,)Follow(T ' )-=,#+,),Follow(F)=*,/,+,-, #,)4、 遞歸下降分析算法實現(xiàn) 針對最終的經(jīng)過變換的 1.2 文法編寫遞歸下降分析程序，為便 于理解每條文法規(guī)則下面直接給出C程序?qū)崿F(xiàn)。E->TE'其對應(yīng)的C語言實現(xiàn)void parse_E()parse_T();parse_EDo

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

8、i +;parse_F(); parse_TDot();return ;F->num|(E)其實現(xiàn)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 集 合即便不處理，也能在后續(xù)的分析處理中，發(fā)現(xiàn)錯誤。 最后給出錯誤處理程序和主程序， 主程序中有幾個算術(shù)表達式的例子， 可以將代碼整合起來，直接編譯執(zhí)行。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