首页 > 代码库 > 递归下降分析
递归下降分析
对于给定的文法G[E] :
E→E+T|E-T|T
T→T*F| T/F|F
F→(E)|i
消除左递归后的文法是:
E→TE‘
E‘→+TE‘|-TE‘|∑
T→FT‘
T‘→*FT‘|/FT‘|∑
F→(E)|i
是否是LL(1)文法?
select(E→TE‘)=first(TE‘)={(,i}
select(E‘→+TE‘)=first(+TE‘)={+}
select(E‘→-TE‘)=first(-TE‘)={-}
select(E‘→∑)=follow(E‘)={),#}
select(T→FT‘)=first(FT‘)={(,i}
select(T‘→*FT‘)=first(*FT‘)={*}
select(T‘→/FT‘)=first(/FT‘)={/}
select(T‘→∑)=follow(T‘)={+,-,),#)
select(F→(E))=first((E))={(}
select(F→i)=first(i)={i}
由上分析,得知此文法满足LL(1)文法.
C语言代码如下:
#include<stdio.h> #include <string.h> void scaner(); void E(); void E1(); void T(); void T1(); void F(); void error(); char proce[100],ch,token[20]; int syn,i,j,m,sum=0; char *keyword[6]= {"begin","if","then","while","do","end"}; main() { i=0;//记录输入多少个字符 printf("\n 请输入词法分析程序:"); do{ ch=getchar(); proce[i]=ch; i++; }while (ch!=‘#‘); i=0; do{ scaner(); switch(syn) { case 11: printf("\n(%d,%d)",syn,sum); break; case -1: printf("\n(%s,#)",token); break; default: printf("\n(%d,%s)",syn, token); } }while (syn!=0); printf("\n"); i=0; scaner(); E(); if (syn==0) printf("\n 语法正确. \n"); else printf("\n 语法失败. \n"); } void scaner() { for (j=0;j<20;j++) token[j]=NULL;//将token赋值为空 m=0; sum=0; ch=proce[i]; i++; while (ch==‘ ‘) { ch=proce[i++]; } if (ch>=‘a‘&& ch<=‘z‘) {while (ch>=‘a‘&& ch<=‘z‘||ch>=‘0‘ && ch<=‘9‘) { token[m++]=ch; ch=proce[i++];//继续看后面的 } syn=10;i--;//判断为变量 for (j=0;j<6;j++) if(strcmp(token,keyword[j])==0) { syn=j+1; break; }//如果有可以匹配的就为关键字 } else if(ch>=‘0‘ && ch<=‘9‘) {while (ch>=‘0‘ && ch<=‘9‘) { sum=sum*10+(ch-‘0‘); ch=proce[i]; i++; } syn=11; i--; } else switch(ch) { case ‘<‘: token[m]=ch; m++; ch=proce[i]; i++; if (ch==‘>‘) { syn=21; token[m]=ch; m++; } else if (ch==‘=‘) { syn=22; token[m]=ch; m++; } else { syn=20; i--; } break; case ‘>‘: m=0; token[m]=ch; m++; ch=proce[i]; i++; if (ch==‘=‘) { syn=24; token[m]=ch; m++; } else { syn=23; i--; } break; case ‘:‘: m=0; token[m++]=ch; ch=proce[i++]; if (ch==‘=‘) { syn=18; token[m++]=ch; } else { syn=17; i--; } break; case ‘+‘: syn=13; token[0]=ch; break; case ‘-‘: syn=14; token[0]=ch; break; case ‘*‘: syn=15; token[0]=ch; break; case ‘/‘: syn=16; token[0]=ch; break; case ‘=‘: syn=25; token[0]=ch; break; case ‘;‘: syn=26; token[0]=ch; break; case ‘(‘: syn=27; token[0]=ch; break; case ‘)‘: syn=28; token[0]=ch; break; case ‘#‘: syn=0; token[0]=ch; break; default: syn=-1; token[0]=ch; } }
void E() { printf("E "); T(); E1(); } void E1() { printf("E1 "); if (syn==13) { scaner(); T(); E1(); } else { if (syn!=28 && syn!=0) error(); } } void T() { printf("T "); F(); T1(); } void T1() { printf("T1 "); if (syn==15) { scaner(); F(); T1(); } else { if (syn!=28 && syn!=0 && syn!=13) error(); } } void F() { printf("F "); if (syn==27) { scaner(); E(); if(syn==28) scaner(); else error(); } else if (syn==11 || syn==10) scaner(); } void error() { printf("\n (%d,%s)语法错误! \n",syn, token); }
递归下降分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。