【实验目的】
练习构造语法分析程序的方法,熟悉上下文无关文法的使用,加深对课堂教学的理解;提高词法分析方法的实践能力
【实验要求】
利用某一高级程序设计语言构造语法分析程序
【具体要求】对于给定的文法G[E]
E->TE’
E’->+TE’ | ε
T->FT’
T’->*F T’| ε
F->(E) | i
采用递归下降分析法编写语法分析程序及LL(1)语法分析法编写语法分析程序,该语法分析程序判断输入的字符串是否符合上述文法,并能够输出相应的结果(是语法成分或不是语法成分)。
- /*
- 实验名称:实验2 语法分析器实验
- 学号:
- 姓名:niu91(859222829)
- 班级:
- */
- #include<stdio.h>
- #include<string.h>
- #include<malloc.h>
- #define N 100
- int seekProd(int stackTop,int inputstrTop);
- //char inputstr[10]="i*i+i#";
- char inputstr[20];
- char stack[10]="";
- typedef struct production{
- char leftChar;
- char rightChars[4];
- char allChars[8];
- }Prod;
- Prod productions[8];
- void init();
- int stackPush(int *top, Prod prod);
- int matching(int *top, char *inputstr);
- int main()
- {
- int len;//输入串的长度
- int stackTop=1;
- int inputstrTop=0;
- int i;
- char *z="#";
- int index=0;
- init();//产生式初始化
- stack[0]='#';
- stack[stackTop]='E';
- printf("请输入字符串:");
- gets(inputstr);
- len=strlen(inputstr);
- inputstr[len]='#';
- while( stackTop>=0 )
- {
- // printf("%d,%d\n",stackTop,inputstrTop);
- printf("第%2d步:",++index);
- printf("当前栈:%-8s",stack);
- printf("输入字符串:%8s",inputstr);
- //根据栈定元素和字符串首字母
- if(matching(&stackTop,inputstr)){
- printf("\n");
- }else{
- i=seekProd(stackTop,inputstrTop);
- stackPush(&stackTop,productions[i]);//压栈
- printf("进行下一步所用的产生式:%s\n",productions[i].allChars);
- }
- }
- if(stackTop+1==0)
- {
- printf("分析成功!\n");
- }
- return 0;
- }
- //搜索分析表
- int seekProd(int stackTop,int inputstrTop)
- {
- // printf("stack[stackTop]=%c\n",stack[stackTop]);
- if(stack[stackTop]=='E'){
- if(inputstr[inputstrTop]=='i')
- {
- return 0;
- }else if(inputstr[inputstrTop]=='('){
- return 0;
- }else{
- return -1;
- }
- }else if(stack[stackTop]=='X'){
- if(inputstr[inputstrTop]=='+')
- {
- return 1;
- }else if(inputstr[inputstrTop]==')'){
- return 2;
- }else if(inputstr[inputstrTop]=='#'){
- return 2;
- }else{
- return -1;
- }
- }else if(stack[stackTop]=='T'){
- if(inputstr[inputstrTop]=='i')
- {
- return 3;
- }else if(inputstr[inputstrTop]=='('){
- return 3;
- }else{
- return -1;
- }
- }else if(stack[stackTop]=='Y'){
- if(inputstr[inputstrTop]=='+')
- {
- return 5;
- }else if(inputstr[inputstrTop]=='*'){
- return 4;
- }else if(inputstr[inputstrTop]==')'){
- return 5;
- }else if(inputstr[inputstrTop]=='#'){
- return 5;
- }else{
- return -1;
- }
- }else if(stack[stackTop]=='F'){
- if(inputstr[inputstrTop]=='i'){
- return 7;
- }else if(inputstr[inputstrTop]=='('){
- return 6;
- }else{
- return -1;
- }
- }else{
- printf("错误!");
- }
- return -1;
- }
- void init()
- {
- productions[0].leftChar='E';strcpy(productions[0].rightChars,"TX"); strcpy(productions[0].allChars,"E->TX");
- productions[1].leftChar='X';strcpy(productions[1].rightChars,"+TX");strcpy(productions[1].allChars,"E->+TX");
- productions[2].leftChar='X';strcpy(productions[2].rightChars,"ε"); strcpy(productions[2].allChars,"X->ε");
- productions[3].leftChar='T';strcpy(productions[3].rightChars,"FY"); strcpy(productions[3].allChars,"T->FY");
- productions[4].leftChar='Y';strcpy(productions[4].rightChars,"*FY");strcpy(productions[4].allChars,"Y->*FY");
- productions[5].leftChar='Y';strcpy(productions[5].rightChars,"ε"); strcpy(productions[5].allChars,"Y->ε");
- productions[6].leftChar='F';strcpy(productions[6].rightChars,"(E)");strcpy(productions[6].allChars,"F->(E)");
- productions[7].leftChar='F';strcpy(productions[7].rightChars,"i"); strcpy(productions[7].allChars,"F->i");
- }
- int stackPush(int *top, Prod prod)
- {
- int len;
- int i;
- char *c="ε";
- len=strlen(prod.rightChars);
- if(!strcmp(prod.rightChars,c))
- {
- stack[(*top)]='\0';
- }else{
- for(i=len-1;i>=0;i--)
- {
- stack[(*top)++] = prod.rightChars[i];
- }
- }
- --(*top);
- return 0;
- }
- int matching(int *top, char *inputstr)
- {
- int len;
- int i;
- if(stack[(*top)]==inputstr[0])
- {
- stack[(*top)--]='\0';
- len=strlen(inputstr);
- for(i=0;i<len-1;i++)
- {
- inputstr[i]=inputstr[i+1];
- }
- inputstr[i]='\0';
- return 1;
- }else
- {
- return 0;
- }
- }