⾃下⽽上语法分析⼀实验题⽬⾃下⽽上语法分析⼆实验⽬的1.给出PL/0⽂法规范，要求编写PL/0语⾔的语法分析程序。
2．通过设计、编制、调试⼀个典型的⾃下⽽上语法分析程序，实现对词法分析程序所提供的单词序列进⾏语法检查和结构分析，进⼀步掌握常⽤的语法分析⽅法。
3．选择最有代表性的语法分析⽅法，如算符优先分析法、LR分析法；或者调研语法分析器的⾃动⽣成⼯具YACC的功能与⼯作原理，使⽤YACC⽣成⼀个⾃底向上的语法分析器。
三实验环境Ubuntu16.04、C++语⾔、gcc⼯具链四实验内容已给PL/0语⾔⽂法，构造表达式部分的语法分析器。
分析对象（算术表达式）的BNF定义如下：<表达式>::=[-|+]<项>{<加法运算符><项>}<项>::=<因⼦>{<乘法运算符><因⼦>}<因⼦>::=<标识符>|<⽆符号整数>|‘(’<表达式>‘)’<加法运算符>::=+|-<乘法运算符>::=*|/<关系运算符>::==|#|<|<=|>|>=五实验要求1. 将实验⼀的“词法分析”的输出结果，作为表达式语法分析器的输⼊，进⾏语法解析，对于语法正确的表达式，报告“语法正确”；对于语法错误的表达式，报告“语法错误”，指出错误原因。
2. 把语法分析器设计成⼀个独⽴的⼀遍的过程。
3. 采⽤算符优先分析法或者LR分析法实现语法分析；或者调研语法分析器的⾃动⽣成⼯具YACC的功能与⼯作原理，使⽤YACC⽣成⼀个⾃底向上的语法分析器。
六设计思想我采⽤LR(0)分析法，⾸先写出表达式的⽂法，再写出⽂法的项⽬，画出识别前缀的DFA，构造LR(0)分析表，根据分析表写出程序。
四实验步骤1写出表达式的⽂法：2⽂法的项⽬:3画出识别前缀的DFA：4构造LR(0)分析表：五算法流程六源程序#include<stdio.h>#include<string.h>#include<stdlib.h>char sym[20][8]={//符号表 {'s','s','e','s','s','s','e','e'},//1 {'e','e','e','e','e','e','a','e'},//2 {'e','e','e','s','s','s','e','e'},//3 {'r','r','r','r','r','r','r','r'},//4{'r','r','r','r','r','r','r','r'},//5{'s','e','e','e','e','e','e','e'},//6 {'s','e','s','e','e','e','e','s'},//7{'r','r','r','r','r','r','r','r'},//8{'r','r','r','r','r','r','r','r'},//9{'s','s','e','s','s','s','e','e'},//10{'r','r','r','r','r','r','r','r'},//11{'e','e','e','s','s','s','e','e'},//12{'r','r','r','r','r','r','r','r'},//13{'e','e','e','s','s','s','e','e'},//14{'e','e','e','e','e','e','e','s'},//15{'s','e','e','e','e','e','e','e'},//16{'e','e','s','e','e','e','a','e'},//17{'r','r','r','r','r','r','r','r'},//18{'r','r','r','r','r','r','r','r'},//19{'r','r','r','r','r','r','r','r'}};//20char snum[20][8]={//数字表{3,4,0,7,8,9,0,0},//1{0,0,0,0,0,0,0,0},//2{0,0,0,7,8,9,0,0},//3{8,8,8,8,8,8,8,8},//4{11,11,11,11,11,11,11,11},//5{11,0,0,0,0,0,0,0},//6{11,0,13,0,0,0,0,17},//7{26,26,26,26,26,26,26,26},//8{28,28,28,28,28,28,28,28},//9{3,4,0,7,8,9,0,0},//10{6,6,6,6,6,6,6,6},//11{0,0,0,7,8,9,0,0},//12{19,19,19,19,19,19,19,19},//13{0,0,0,7,8,9,0,0},//14{0,0,0,0,0,0,0,17},//15{11,0,0,0,0,0,0,0},//16{0,0,13,0,0,0,0,0},//17{32,32,32,32,32,32,32,32},//18{15,15,15,15,15,15,15,15},//19{23,23,23,23,23,23,23,23}};//20int go[20][6]={//goto表{2,1,0,0,0,6},//1{0,0,0,0,0,0},//2{0,0,5,0,0,6},//3{0,0,0,0,0,0},//4{0,0,0,0,0,0},//5{0,0,0,10,0,0},//6{0,0,0,0,12,0},//7{0,0,0,0,0,0},//8{0,0,0,0,0,0},//9{2,14,0,0,0,6},//10{0,0,0,0,0,0},//11{0,0,15,0,0,6},//12{0,0,0,0,0,0},//13{0,0,0,0,0,16},//14{0,0,0,0,0,0},//15{0,0,0,18,0,0},//16{0,0,0,0,19,0},//17{0,0,0,0,0,0},//18{0,0,0,0,0,0},//19{0,0,0,0,0,0}};//20void main(){int step=1;/*number of analysis step*/int length=0;/*length of string*/int i,j,m,n;int l=0;/*length of state & ch*/int k=0;int num,x=1;int state[20]={0};/*initial state stack*/char ch[20]={'#'};/*initial character stack*/char str[20];/*define array of string*/char cha;char how;/*how include's','r','a'and null*/char A;//clrscr();printf("please input a string:");do{scanf("%c",&cha);str[length]=cha;length++;}while(cha!='#');/*input a string calculate it's length*/printf("\n--------------------------------------------------------------------------\n"); printf("step\tstate\t\tcharacter\tstring\t\taction\n");printf("--------------------------------------------------------------------------\n"); do{//if(step==10) {printf("\nhhh:%c %c\n",ch[1],ch[2]);}switch(str[k])/*judge str[k]*/{case '+':j=0;break;case '-':j=1;break;case '*':j=2;break;case 'i':j=3;break;case 'n':j=4;break;case '(':j=5;break;case '#':j=6;break;case ')':j=7;break;default:j=-1;break;}if(j!=-1){how=sym[state[l]][j];/*judge how*/num=snum[state[l]][j];/*state's number*/if(how=='s'){printf("%d\t",step);/*output step*/for(i=0;i<=l;i++){printf("%d ",state[i]);/*ouput state stack*/}if(l>=3) printf("\t");else printf("\t\t");for(i=0;i<=l;i++){if(ch[i]==' ' && x==1){ch[i]='*';x++;}printf("%c",ch[i]);/*ouput character stack*/}printf("\t\t");for(i=0;i<k;i++){str[i]=' ';printf("%c",str[i]);}for(i=k;i<length;i++){printf("%c",str[i]);/*output string stack*/}printf("\t");printf("push state %d!\n",num);/*output action*/ l=l+1;state[l]=num;ch[l]=str[l-1];//printf("ch:%c\n",ch[l]);step=step+1;k=k+1;/*next rotate value*/}else if(how=='r'){printf("%d\t",step);/*output step*/for(i=0;i<=l;i++){printf("%d ",state[i]);/*ouput state stack*/}if(l>=3) printf("\t");else printf("\t\t");for(i=0;i<=l;i++){if(ch[i]==' ' && x==2){ch[i]='i';x++;}printf("%c",ch[i]);/*ouput character stack*/}printf("\t\t");for(i=0;i<k;i++){str[i]=' ';printf("%c",str[i]);}for(i=k;i<length;i++){printf("%c",str[i]);/*output string stack*/ }printf("\t");switch(num)/*judge num*/{case 8:A='S',m=1;l=l-m;printf("s->+");break;case 11:A='S',m=1;l=l-m;printf("S->-");break;case 26:A='F',m=1;l=l-m;printf("F->i");break;case 28:A='F',m=1;l=l-m;printf("F->n");break;case 6:A='E',m=3;l=l-m;printf("E->STA");break;case 19:A='T',m=2;l=l-m;printf("T->FB");break;case 32:A='F',m=5;//printf("l=%d",l);//3l=l-m;printf("F->(E)");//F->(F+F)break;case 15:A='A',m=3;l=l-m;printf("A->+TA");break;case 23:A='B',m=3;l=l-m;printf("B->*FB");break;}switch(A)/*judge A*/{case 'S':n=0;break;case 'E':n=1;break;case 'T':n=2;break;case 'A':n=3;break;case 'B':n=4;break;case 'F':n=5;break;}num=go[state[l]][n];printf(",push%d!\n",num);l=l+1;state[l]=num;ch[l]=A;//if(l==1) l++;step=step+1;k=k;}else if(how=='a'){printf("%d\t",step);/*output step*/for(i=0;i<=l;i++){printf("%d ",state[i]);/*ouput state stack*/}if(l>=3) printf("\t");else printf("\t\t");for(i=0;i<=l;i++){printf("%c",ch[i]);/*ouput character stack*/}printf("\t\t");for(i=0;i<k;i++){str[i]=' ';printf("%c",str[i]);}for(i=k;i<length;i++){printf("%c",str[i]);/*output string stack*/}printf("\t");//\tprintf("acc!\n");printf("语法正确！\n");exit(1);}else{printf("ERROR!\n");exit(1);}}else{printf("wrong character!\n");exit(1);}}while(str[k]!='\0');printf("--------------------------------------------------------------------------\n");return ;}七调试数据及结果调试数据：(i+n)*i最终结果：⼋实验体会这次实验为了更⽅便观察⾃下⽽上的分析过程，我将标识符的符号简写为i，将数字的符号简写为n，将加号简写为+，将减号简写为-，将括号简写为(),其实可以从词法分析输出的⽂件中使⽤ident、plus等符号来进⾏分析，但上述符号的表⽰⽅法更符合书中的分析过程，并且更易观察程序分析的对错。
