编译原理之LL(1)文法的判断，递归下降分析程序

1. 文法 G（S）:

（1）S -> AB

（2）A ->Da|ε

（3）B -> cC

（4）C -> aADC |ε

（5）D -> b|ε

验证文法 G（S）是不是 LL（1）文法？

解：因为

First(Da)={b, a}

First(ε)={ε}

First(aADC)={a}

First(b)={b}

Follow(A)={c.b.a, #}

　　FIRST(B)

　　FIRST(D), FIRST(C), FOLLOW(C)

Follow(C)={#}

Follow(D)={a,#}

所以

SELECT(A->Da)={b. a}

SELECT(A->ε)={c. b, a, #}

SELECT(C->aADC)={a}

SELECT(C->ε)={#}

SELECT(D->b)={b}

SELECT(D->ε)={a, #}

其中因为SELECT(A->Da)与SELECT(A->ε)有交集所以该G（S）不是LL（1）文法。

2.判断下列文法是否是LL(1)文法？

E -> TE'

E' -> +TE' | ε

T -> FT'

T' -> *FT' | ε

F -> (E) | i

解：由题可得

SELECT(E'->+TE')=FIRST(+TE')={+}

SELECT(E'->ε)=follow(E')=follow(E)={#, )}

SELECT(T'->*FT')=FRIST(*FT')={*}

SELECT(T'->ε)=follow(T')=follow(T)={#, ), +}

SELECT(F->(E))=FRIST((E)) ={(}

SELECT(F->i)=FRIST(i) ={i}

其中SELECT(E'->+TE')与SELECT(E'->ε)互不相交，SELECT(T'->*FT')与SELECT(T'->ε)互不相交，SELECT(F->(E))与SELECT(F->i)互不相交，故原文法为LL（1）文法。

3.接2，如果是LL(1)文法，写出它的递归下降语法分析程序代码。

E()

｛T();

E'();

}

E'()

T()

T'()

F()

解：

SELECT(E->TE) =FIRST(TE')=FIRSI(T)-FIRST(F)U{*}={(, i, *}

SELECT(E'->+TE')=FIRST(+TE')={+}

SELECT(E'->ε)=follow(E')=follow(E)={#, )}

SELECT(T -> FT')=FRIST(FT')=FIRST(F)={(, i}

SELECT(T'->*FT')=FRIST(*FT')={*}

SELECT(T'->ε)=follow(T')=follow(T)={#, ), +}

SELECT(F->(E))=FRIST((E)) ={(}

SELECT(F->i)=FRIST(i) ={i}

伪代码：

void ParseE(){

　　switch(lookahead){

　　　　case '(','i', '*':

　　　　　　ParseT();

　　　　　　ParseEP();

　　　　　　break;

　　　　default:

　　　　　　print("语法错误 \n");

　　　　　　exit(0);

　　}

}

void ParseEP(){

　　switch(lookahead){

　　　　case '+':

　　　　　　MatchToken('+');

　　　　　　ParseT();

　　　　　　ParseEP();

　　　　　　break;

　　　　case '#', ')':

　　　　   　break;

　　　　default:

　　　　　　print("语法错误 \n");

　　　　　　exit(0);

　　}

}

void ParseT(){　

　　switch(lookahead){

　　　　case '(','i':

　　　　　　ParseF();

　　　　　　ParseTP();

　　　　　　break;

　　　　default:

　　　　　　print("语法错误 \n");

　　　　　　exit(0);

　　}

}

void ParseTP(){

　　switch(lookahead){

　　　　case '*':

　　　　　　MatchToken('*');

　　　　　　ParseF();

　　　　　　ParseTP();

　　　　　　break;

　　　　case '#', ')', '+':

　　　　　　break;

　　　　default:

　　　　　　print("语法错误 \n");

　　　　　　exit(0);

　　　　}

　　}

void ParseF(){

　　switch(lookahead){

　　　　case '(':

　　　　　　MatchToken('(');

　　　　　　ParseE();

　　　　　　MatchToken(')');

　　　　　　break;

　　　　case 'i':

　　　　　　MatchToken('i');

　　　　　　break;

　　　　default:

　　　　　　print("语法错误 \n");

　　　　　　exit(0);

　　　　}

　　}

4.加上词法分析程序，形成可运行的语法分析程序，分析任意输入的符号串是不是合法的表达式。

巴特西

编译原理之LL(1)文法的判断，递归下降分析程序

最新文章

热门文章