编译原理实验LL1分析法

1、编译原理程序设计实验报告表达式语法分析器的设计实现班级：计算机1306班姓名：王利达学号：20133959实验目标：使用LL(1)分析法构造表达式语法分析器程序，判别算术表达式，给出判别结果。实验内容：一、概要设计1.算术表达式文法：E T | E0TT F | T1FF i | ( E )其中0：+ -1：* /i：数字或常数文法变换：E T MM 0 T M |T F | NN 1 F N |F i | ( E )其中0：+ -1：* /i：数字或常数2.LL(1)分析表表1.LL(1)分析表i+-*/()#EMT,pMT,pMMT,nMT,n,p,pTNF,pNF,pNNF,nNF,n,

2、p,pF,n)E,n),n#OK二、数据结构1.输入表达式定义char型数组expstr为存放输入表达式的数组，char expstr100;2.分析栈定义一个栈来进行LL(1)分析。栈中有bottom、top、stacksize等元素，用于程序调用栈和对栈操作。typedef struct /定义语法的栈 SElemType *bottom;/底 SElemType *top;/顶 int stacksize;SqStack; （包括：概要设计、数据结构、流程图、关键函数等有选择填写）源程序代码：（加入注释）#include<iostream>#include<stdio.

3、h>#include<cstdlib>using namespace std;#define STACKSIZE 30 /栈大小#define STACKINCREMENT 10 /栈增量#define OK 1#define Error 0#define OVERFLOW -1typedef char SElemType;typedef int Status;int i=0;int count1=0;int count2=0; /计数终结符的个数char expstr100;typedef struct /定义语法的栈 SElemType *bottom;/底 SElemT

4、ype *top;/顶 int stacksize;SqStack;Status InitStack(SqStack &S) /初始化栈 S.bottom=(SElemType*)malloc(STACKSIZE*sizeof(SElemType); if(!S.bottom) exit(OVERFLOW); S.top=S.bottom; S.stacksize=STACKSIZE; return OK;Status PUSH(SqStack &S,SElemType e) if(S.top-S.bottom>=S.stacksize) S.bottom=(SElemT

5、ype*)realloc(S.bottom,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.bottom) exit(OVERFLOW); S.top=S.bottom+S.stacksize; S.stacksize+=STACKINCREMENT; *(S.top)=e; (S.top)+; return OK;Status POP(SqStack &S,SElemType &e) if(S.top=S.bottom) return Error; S.top-; e=*(S.top); return OK;void

6、 wrong()/调用此函数，表示出错 cout<<"Wrong!"<<endl; getchar(); exit(0);bool ch_judge(char s,int n) /字符是否合法 if(sn='(')|(sn=')')|(sn>='0'&&sn<='9')|(sn>='a'&&sn<='z')|(sn='+')|(sn='-')|(sn='*

7、9;)|(sn='/')|(sn='#') return 1; else return 0;bool ter_judge(char c) /终结符集合与非终结符集合 if(c='(')|(c=')')|(c>='0'&&c<='9')|(c>='a'&&c<='z')|(c='+')|(c='-')|(c='*')|(c='/') return 1;

8、 /终结符 返回1 else /if(c='E'|c='E1'|c='T'|c='T1'|c='F') return 0; /非终结符或#，返回0bool num_letter(char s,int i) /判断当前字符是数字还是字母 if(si>='0'&&si<='9')|(si>='a'&&si<='z') i+; while(si>='0'&&si&l

9、t;='9')|(si>='a'&&si<='z') i+; count1+; while(count1!=0) i-; count1-; i-; return 1; /是字母或数字返回1 else return 0; /不是字母或数字返回0void LL1(SqStack &S,char s,int i)/LL1文法分析函数 SElemType e; PUSH(S,'#'); PUSH(S,'E'); while(si!='#') if(ch_judge(s,i

10、) POP(S,e); if(!(ter_judge(e) /是非终结符 if(e='#'&&si='#') break; /表达式正确 else if(e='#'&&si!='#') wrong(); else if(e!='#') /分析表匹配 switch(e) case 'E': if(num_letter(s,i)|si='(') e='M' / E' M PUSH(S,e); e='T' PUSH(S

11、,e); break; else wrong(); case 'M': if(si='+'|si='-') e='M' PUSH(S,e); e='T' PUSH(S,e); e=si; PUSH(S,e); break; else if(si=')'|si='#') break; else wrong(); case 'T': if(num_letter(s,i)|si='(') e='N' /T' N PUSH(S,e);

12、e='F' PUSH(S,e); break; else wrong(); case 'N': if(si='+'|si='-'|si=')'|si='#') break; else if(si='*'|si='/') e='N' PUSH(S,e); e='F' PUSH(S,e); e=si; PUSH(S,e); break; else wrong(); case 'F': if(num_letter(s,i) w

13、hile(si>='0'&&si<='9')|(si>='a'&&si<='z') /将连续的终结符压栈 e=si; PUSH(S,e); i+; count2+; /给连续终结符计数 i-; /使si为连续终结符即一个整数的最后一字 break; else if(si='(') e=')' PUSH(S,e); e='E' PUSH(S,e); e='(' PUSH(S,e); break; else wron

14、g(); default: wrong(); else if(si>='0'&&si<='9')|(si>='a'&&si<='z')/如果是数字或字母则依次计数 while(ter_judge(e) if(e=si) i-; POP(S,e); else wrong(); while(count2!=0) i+; count2-; PUSH(S,e); i+; else /如果是+-*/则直接比较 if(e=si) i+; else wrong(); else wrong(); int main() SqStack S; InitStack(S); cout<<"LL(1)nPlease enter the expression and end with the "#":"<<endl; cin>>expstr; LL1(S,expstr,i);