首页 > 其他 > 详细

LL(1)文法的判断,递归下降分析程序

时间:2019-11-22 01:22:58      阅读:119      评论:0      收藏:0      [点我收藏+]

1. 文法 G(S):

(1)S -> AB

(2)A ->Da|ε

(3)B -> cC

(4)C -> aADC |ε

(5)D -> b|ε

验证文法 G(S)是不是 LL(1)文法?

FIRST集:

First(Da)={b,a}

First(aADC)={a}

First(b)={b}

First(ε)={ε}

 

FOLLOW集:

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

Follow(C)={#}

Follow(D)={a,#}

 

SELLECT集:

Sellect(A->Da)={b,a}

Sellect(A->ε)=Follow(A)={c,b,a,#}

Sellect(C -> aADC)={a}

Sellect(C -> ε)=Follow(C)={#}

Sellect(D -> b)={b}

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

 

Sellect(A->Da) ∩ Sellect(A->ε) ≠ ∅

Sellect(C->aADC) ∩ Sellect(C->ε) ≠ ∅

Sellect(D->b) ∩ Sellect(D->ε) ≠ ∅

所以:文法 G(S)不是 LL(1)文法。

 

2.(上次作业)消除左递归之后的表达式文法是否是LL(1)文法?

E-> TE‘

E‘-> +TE‘ | ε 

T-> FT‘

T‘-> *FT‘ | ε

F-> (E) | i

 

FIRST集:

First(TE‘)=First(T)=Fisrt(F)={ ( , i }

First(+TE‘)={+}

First(ε)={ε}

First(FT‘)=First(F)={ ( , i }

First(*FT‘)={*}

First((E))={ ( }

First(i)={i}

 

FOLLOW集:

Follow(E)={ ),# }

Follow(E‘)={ ),# }

Follow(T)=First(E‘)-{ε} U Follow(E‘)={+,),#}

Follow(T‘)=Follow(T)={+,),#}

Follow(F)=First(T‘)-{ε} U Follow(T‘)={*,+,),#} 

 

SELLECT集:

Sellect(E->TE‘)=First(TE‘)={ ( , i }

Sellect(E‘-> +TE‘)=First(+TE‘)={+}

Sellect(E‘-> ε )=First( ε )-{ ε } U Follow(E‘)=Follow(E‘)={),#}

Sellect(T-> FT‘)=First{FT‘}={ ( , i }

Sellect(T‘-> *FT‘)=First(*FT‘)={*}

Sellect(T‘->ε)=First(ε)-{ε} U Follow(T‘)=Follow(T‘)={+,),#}

Sellect{F-> (E)}=First((E))={ ( }

Sellect(F-> i)=First(i)={i}

 

Sellect(E‘->+TE‘) ∩ Sellect(E->ε) = ∅

Sellect(T‘->*FT‘) ∩ Sellect(T‘->ε) = ∅

Sellect(F->(E)) ∩ Sellect(F->i) = ∅

所以:文法 G(S)是 LL(1)文法。

 

 

 

E-> TE‘

E‘-> +TE‘ | ε 

T-> FT‘

T‘-> *FT‘ | ε

F-> (E) | i

Sellect(E->TE‘)=First(TE‘)={ ( , i }

Sellect(E‘-> +TE‘)=First(+TE‘)={+}

Sellect(E‘-> ε )=First( ε )-{ ε } U Follow(E‘)=Follow(E‘)={),#}

Sellect(T-> FT‘)=First{FT‘}={ ( , i }

Sellect(T‘-> *FT‘)=First(*FT‘)={*}

Sellect(T‘->ε)=First(ε)-{ε} U Follow(T‘)=Follow(T‘)={+,),#}

Sellect{F-> (E)}=First((E))={ ( }

Sellect(F-> i)=First(i)={i}

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

E()

    {T();

       E‘();

     }

E‘()

T()

T‘()

F()

 

void ParseE(){
switch(lookhead){
case ‘(‘,‘i‘:
Parsee();
MatchToken(‘(‘);
ParseE();
break;

default:
printf("syntax error\n");
exit(0);
}
}

void Parese(){
if(lookhead==‘(‘){
MatchToken(‘(‘)
}
else if(lookhead==‘i‘){
}
else{
printf("syntax error\n");
exit(0);
}
}

void ParseE1(){
switch(lookhead){
case ‘+‘:
Parse_e1();
MatchToken(+)
ParseE1();
break;

case ‘)‘,‘#‘:
Parse_e2();
MatchToken(‘)‘)
ParseE1();
break;

default:
printf("syntax error\n");
exit(0);
}
}

void Parese_e1(){
if(lookhead==‘+‘){
MatchToken(‘+‘)
}
else{
printf("syntax error\n");
exit(0);
}
}
void Parese_e2(){
if(lookhead==‘)‘){
MatchToken(‘)‘)
}
else if(lookhead==‘#‘){
}
else{
printf("syntax error\n");
exit(0);
}
}

void ParseT(){
switch(lookhead){
case ‘(‘,‘i‘:
Parset();
MatchToken(‘(‘);
ParseT();
break;

default:
printf("syntax error\n");
exit(0);
}
}

void Parest(){
if(lookhead==‘(‘){
MatchToken(‘(‘)
}
else if(lookhead==‘i‘){
}
else{
printf("syntax error\n");
exit(0);
}
}

void ParseT1(){
switch(lookhead){
case ‘*‘:
Parse_t1();
MatchToken(+)
ParseT1();
break;

case ‘+‘,‘)‘,‘#‘:
Parse_t2();
MatchToken(‘)‘)
ParseT1();
break;

default:
printf("syntax error\n");
exit(0);
}
}

void Parese_t1(){
if(lookhead==‘*‘){
MatchToken(‘*‘)
}
else{
printf("syntax error\n");
exit(0);
}
}
void Parese_t2(){
if(lookhead==‘+‘){
MatchToken(‘+‘)
}
else if(lookhead==‘#‘){
}
else if(lookhead==‘)‘){
}
else{
printf("syntax error\n");
exit(0);
}
}

void ParseF(){
switch(lookhead){
case ‘(‘:
Parse_f1();
MatchToken(‘(‘)
ParseF();
break;

case ‘i‘:
Parse_f2();
MatchToken(‘i‘)
ParseF();
break;

default:
printf("syntax error\n");
exit(0);
}
}

void Parese_f1(){
if(lookhead==‘(‘){
MatchToken(‘(‘)
}
else{
printf("syntax error\n");
exit(0);
}
}

void Parese_f2(){
if(lookhead==‘i‘){
MatchToken(‘i‘)
}
else{
printf("syntax error\n");
exit(0);
}
}

 

 

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

LL(1)文法的判断,递归下降分析程序

原文:https://www.cnblogs.com/q1uj1e/p/11896708.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!