编译原理LL(1)语法分析实验报告要点

编译原理程序设计实验报告——表达式语法分析器的设计实现班级：计算机1306班姓名：王利达学号：20133959 实验目标：使用LL(1)分析法构造表达式语法分析器程序，判别算术表达式，给出判别结果。

实验内容：一、概要设计1.算术表达式文法：E→ T | Eω0TT→ F | Tω1FF→ 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 + - * / ( ) #E MT,p MT,pM MT,n MT,n ε,p ε,pT NF,p NF,pN NF,n NF,n ε,p ε,pF ε,n )E,n) ε,n# OK二、数据结构1.输入表达式定义char型数组expstr为存放输入表达式的数组，char expstr[100];2.分析栈定义一个栈来进行LL(1)分析。

栈中有bottom、top、stacksize 等元素，用于程序调用栈和对栈操作。

typedef struct //定义语法的栈{SElemType *bottom;//底SElemType *top;//顶int stacksize;}SqStack;（包括：概要设计、数据结构、流程图、关键函数等有选择填写）源程序代码：（加入注释）#include<iostream>#include<stdio.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 expstr[100];typedef struct //定义语法的栈{SElemType *bottom;//底SElemType *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=(SElemType*)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 wrong()//调用此函数，表示出错{cout<<"Wrong!"<<endl;getchar();exit(0);}bool ch_judge(char s[],int n) //字符是否合法{if((s[n]=='(')||(s[n]==')')||(s[n]>='0'&&s[n]<='9')||(s[n]>='a'&&s[n]<='z')||(s[n]=='+')||(s[n]=='-')||(s[ n]=='*')||(s[n]=='/')||(s[n]=='#'))return 1;elsereturn 0;}bool ter_judge(char c) //终结符集合与非终结符集合{if((c=='(')||(c==')')||(c>='0'&&c<='9')||(c>='a'&&c<='z')||(c=='+')||(c=='-')||(c=='*')||(c=='/')) return 1; //终结符返回1else //if(c=='E'||c=='E1'||c=='T'||c=='T1'||c=='F')return 0; //非终结符或#，返回0}bool num_letter(char s[],int i) //判断当前字符是数字还是字母{if((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')){i++;while((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')){i++;count1++;}while(count1!=0){i--;count1--;}i--;return 1; //是字母或数字返回1}elsereturn 0; //不是字母或数字返回0}void LL1(SqStack &S,char s[],int i)//LL1文法分析函数{SElemType e;PUSH(S,'#');PUSH(S,'E');while(s[i]!='#'){if(ch_judge(s,i)){POP(S,e);if(!(ter_judge(e))) //是非终结符{if(e=='#'&&s[i]=='#')break; //表达式正确else if(e=='#'&&s[i]!='#')wrong();else if(e!='#') //分析表匹配{switch(e){case 'E':if(num_letter(s,i)||s[i]=='('){e='M'; // E' MPUSH(S,e);e='T';PUSH(S,e);break;}elsewrong();case 'M':if(s[i]=='+'||s[i]=='-'){e='M';PUSH(S,e);e='T';PUSH(S,e);e=s[i];PUSH(S,e);break;}else if(s[i]==')'||s[i]=='#'){break;}elsewrong();case 'T':if(num_letter(s,i)||s[i]=='('){e='N'; //T' NPUSH(S,e);e='F';PUSH(S,e);break;}elsewrong();case 'N':if(s[i]=='+'||s[i]=='-'||s[i]==')'||s[i]=='#'){break;}else if(s[i]=='*'||s[i]=='/'){e='N';PUSH(S,e);e='F';PUSH(S,e);e=s[i];PUSH(S,e);break;}elsewrong();case 'F':if(num_letter(s,i)){while((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')) //将连续的终结符压栈{e=s[i];PUSH(S,e);i++;count2++; //给连续终结符计数}i--; //使s[i]为连续终结符即一个整数的最后一字break;}else if(s[i]=='('){e=')';PUSH(S,e);e='E';PUSH(S,e);e='(';PUSH(S,e);break;}elsewrong();default:wrong();}}}else{if((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z'))//如果是数字或字母则依次计数{while(ter_judge(e)){if(e==s[i]){i--;POP(S,e);}elsewrong();}while(count2!=0){i++;count2--;}PUSH(S,e);i++;}else //如果是+-*/则直接比较{if(e==s[i])i++;elsewrong();}}}elsewrong();}}int main(){SqStack S;InitStack(S);cout<<"LL(1)\nPlease enter the expression and end with the \"#\":"<<endl;cin>>expstr;LL1(S,expstr,i);cout<<"Right! "<<endl;getchar();return 0;}程序运行结果：（截屏）图1.正确的算术表达式(((a+b)*(c/B)))的判断图2.错误的算术表达式a/b++的判断思考问题回答：（如果有）LL(1)分析法和递归下降子程序法在语法分析中同属于自顶向下分析法，LL(1)分析法相对于递归下降子程序法的优势是：LL(1)分析法消除了文法的左递归性，而且克服了回溯，使程序运行的效率大大提升。

编译原理程序设计实验报告——表达式语法分析器的设计班级：计算机1306班姓名：张涛学号：20133967实验目标：用LL（1）分析法设计实现表达式语法分析器实验内容：⑴概要设计：通过对实验一的此法分析器的程序稍加改造，使其能够输出正确的表达式的token序列。

然后利用LL（1）分析法实现语法分析。

⑵数据结构：int op=0; //当前判断进度char ch; //当前字符char nowword[10]=""; //当前单词char operate[4]={'+','-','*','/'}; //运算符char bound[2]={'(',')'}; //界符struct Token{int code;char ch[10];}; //Token定义struct Token tokenlist[50]; //Token数组struct Token tokentemp; //临时Token变量struct Stack //分析栈定义{char *base;char *top;int stacksize;};⑶分析表及流程图逆序压栈int IsLetter(char ch) //判断ch是否为字母int IsDigit(char ch) //判断ch是否为数字int Iskey(char *string) //判断是否为关键字int Isbound(char ch) //判断是否为界符int Isboundnum(char ch) //给出界符所在token值int init(STack *s) //栈初始化int pop(STack *s,char *ch) //弹栈操作int push(STack *s,char ch) //压栈操作void LL1(); //分析函数源程序代码：（加入注释）#include<stdio.h>#include<string.h>#include<ctype.h>#include<windows.h>#include <stdlib.h>int op=0; //当前判断进度char ch; //当前字符char nowword[10]=""; //当前单词char operate[4]={'+','-','*','/'}; //运算符char bound[2]={'(',')'}; //界符struct Token{int code;char ch[10];}; //Token定义struct Token tokenlist[50]; //Token数组struct Token tokentemp; //临时Token变量struct Stack //分析栈定义{char *base;char *top;int stacksize;};typedef struct Stack STack;int init(STack *s) //栈初始化{(*s).base=(char*)malloc(100*sizeof(char));if(!(*s).base)exit(0);(*s).top=(*s).base;(*s).stacksize=100;printf("初始化栈\n");return 0;}int pop(STack *s,char *ch) //弹栈操作{if((*s).top==(*s).base){printf("弹栈失败\n");return 0;(*s).top--;*ch=*((*s).top);printf("%c",*ch);return 1;}int push(STack *s,char ch) //压栈操作{if((*s).top-(*s).base>=(*s).stacksize){(*s).base=(char*)realloc((*s).base,((*s).stacksize+10)*sizeof(char));if(!(*s).base)exit(0);(*s).top=(*s).base+(*s).stacksize;(*s).stacksize+=10;}*(*s).top=ch;*(*s).top++;return 1;}void LL1();int IsLetter(char ch) //判断ch是否为字母{int i;for(i=0;i<=45;i++)if ((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))return 1;return 0;}int IsDigit(char ch) //判断ch是否为数字{int i;for(i=0;i<=10;i++)if (ch>='0'&&ch<='9')return 1;return 0;}int Isbound(char ch) //判断是否为界符{int i;for(i=0;i<2;i++)if(ch==bound[i]){return i+1;}}return 0;}int Isoperate(char ch) //判断是否为运算符{int i;for(i=0;i<4;i++){if(ch==operate[i]){return i+3;}}return 0;}int main(){FILE *fp;int q=0,m=0;char sour[200]=" ";printf("请将源文件置于以下位置并按以下方式命名：F:\\2.txt\n");if((fp=fopen("F:\\2.txt","r"))==NULL) {printf("文件未找到！\n");}else{while(!feof(fp)){if(isspace(ch=fgetc(fp)));else{sour[q]=ch;q++;}}}int p=0;printf("输入句子为：\n");for(p;p<=q;p++)printf("%c",sour[p]);}printf("\n");int state=0,nowlen=0;BOOLEAN OK=TRUE,ERR=FALSE;int i,flagpoint=0;for(i=0;i<q;i++){if(sour[i]=='#')tokenlist[m].code=='#';switch(state){case 0:ch=sour[i];if(Isbound(ch)){if(ERR){printf("无法识别\n");ERR=FALSE;OK=TRUE;}else if(!OK){printf("<10,%s>标识符\n",nowword);tokentemp.code=10;tokentemp.ch[10]=nowword[10];tokenlist[m]=tokentemp;m++;OK=TRUE;}state=4;}else if(IsDigit(ch)){if(OK){memset(nowword,0,strlen(nowword));nowlen=0;nowword[nowlen]=ch;nowlen++;state=3;OK=FALSE;break;}else{nowword[nowlen]=ch;nowlen++;}}else if(IsLetter(ch)){if(OK){memset(nowword,0,strlen(nowword));nowlen=0;nowword[nowlen]=ch;nowlen++;OK=FALSE;}else{nowword[nowlen]=ch;nowlen++;}}else if(Isoperate(ch)){if(!OK){printf("<10,%s>标识符\n",nowword);tokentemp.code=10;tokentemp.ch[10]=nowword[10];tokenlist[m]=tokentemp;m++;OK=TRUE;}printf("<%d,%c>运算符\n",Isoperate(ch),ch);tokentemp.code=Isoperate(ch);tokentemp.ch[10]=ch;tokenlist[m]=tokentemp;m++;}break;case 3:if(IsLetter(ch)){printf("错误\n");nowword[nowlen]=ch;nowlen++;ERR=FALSE;state=0;break;}if(IsDigit(ch=sour[i])){nowword[nowlen]=ch;nowlen++;}else if(sour[i]=='.'&&flagpoint==0){flagpoint=1;nowword[nowlen]=ch;nowlen++;}else{printf("<20,%s>数字\n",nowword);i--;state=0;OK=TRUE;tokentemp.code=20;tokentemp.ch[10]=nowword[10];tokenlist[m]=tokentemp;m++;}break;case 4:i--;printf("<%d,%c>界符\n",Isbound(ch),ch);tokentemp.code=Isbound(ch);tokentemp.ch[10]=ch;tokenlist[m]=tokentemp;m++;state=0;OK=TRUE;break;}}printf("tokenlist值为%d\n",m);int t=0;tokenlist[m+1].code='r';m++;for(t;t<m;t++){printf("tokenlist%d值为%d\n",t,tokenlist[t].code);}LL1();printf("tokenlist值为%d\n",m);if(op+1==m)printf("OK!!!");elseprintf("WRONG!!!");return 0;}void LL1(){STack s;init(&s);push(&s,'#');push(&s,'E');char ch;int flag=1;do{pop(&s,&ch);printf("输出栈顶为%c\n",ch);printf("输出栈顶为%d\n",ch);printf("当前p值为%d\n",op);if((ch=='(')||(ch==')')||(ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')||(ch==10)||(ch==20)){if(tokenlist[op].code==1||tokenlist[op].code==20||tokenlist[op].code==10||tokenlist[op].code==2||tokenlist[op] .code==3||tokenlist[op].code==4||tokenlist[op].code==5||tokenlist[op].code==6)op++;else{printf("WRONG!!!");exit(0);}}else if(ch=='#'){if(tokenlist[op].code==0)flag=0;else{printf("WRONG!!!@@@@@@@@@");exit(0);}}else if(ch=='E'){printf("进入E\n");if(tokenlist[op].code==10||tokenlist[op].code==20||tokenlist[op].code==1) {push(&s,'R');printf("将R压入栈\n");push(&s,'T');}}else if(ch=='R'){printf("进入R\n");if(tokenlist[op].code==3||tokenlist[op].code==4){push(&s,'R');push(&s,'T');printf("将T压入栈\n");push(&s,'+');}if(tokenlist[op].code==2||tokenlist[op].code==0){}}else if(ch=='T'){printf("进入T\n");if(tokenlist[op].code==10||tokenlist[op].code==20||tokenlist[op].code==1) {push(&s,'Y');push(&s,'F');}}else if(ch=='Y'){printf("进入Y\n");if(tokenlist[op].code==5||tokenlist[op].code==6){push(&s,'Y');push(&s,'F');push(&s,'*');}elseif(tokenlist[op].code==3||tokenlist[op].code==2||tokenlist[op].code==0||tokenlist[op].code==4) {}}else if(ch=='F'){printf("进入F\n");if(tokenlist[op].code==10||tokenlist[op].code==20){push(&s,10);}if(tokenlist[op].code==1){push(&s,')');push(&s,'E');push(&s,'(');}}else{printf("WRONG!!!!");exit(0);}}while(flag);}程序运行结果：（截屏）输入：((Aa+Bb)*(88.2/3))#注：如需运行请将文件放置F盘，并命名为：2.txt输出：思考问题回答：LL（1）分析法的主要问题就是要正确的将文法化为LL （1）文法。

编译原理语法分析器实验报告班级：学号：姓名：实验名称语法分析器一、实验目的1、根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。

2、本次实验的目的主要是加深对自上而下分析法的理解。

二、实验内容[问题描述]递归下降分析法：0.定义部分：定义常量、变量、数据结构。

1.初始化：从文件将输入符号串输入到字符缓冲区中。

2.利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。

LL（1）分析法：模块结构：1、定义部分：定义常量、变量、数据结构。

2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）；3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则；4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。

[基本要求]1. 对数据输入读取2. 格式化输出分析结果2．简单的程序实现词法分析public static void main(String args[]) {LL l = new LL();l.setP();String input = "";boolean flag = true;while (flag) {try {InputStreamReader isr = newInputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);System.out.println();System.out.print("请输入字符串(输入exit退出)：");input = br.readLine();} catch (Exception e) {e.printStackTrace();}if(input.equals("exit")){flag = false;}else{l.setInputString(input);l.setCount(1, 1, 0, 0);l.setFenxi();System.out.println();System.out.println("分析过程");System.out.println("----------------------------------------------------------------------");System.out.println(" 步骤| 分析栈| 剩余输入串| 所用产生式");System.out.println("----------------------------------------------------------------------");boolean b = l.judge();System.out.println("----------------------------------------------------------------------");if(b){System.out.println("您输入的字符串"+input+"是该文法的一个句子");}else{System.out.println("您输入的字符串"+input+"有词法错误！");}}}}//实现各函数并且加注释三、编程并上机调试运行运行结果如下图：四、实验小结通过这次实验，我对语法分析有了更深刻的了解，对它的形成有了更清楚得认识。

编译原理实验ll1分析基本的功能下面主要采用了ll1分析方法来进行语法分析先通过判断该文法是不是ll1文法如果不是先将其改写成ll1文法再将ll1文法改造成等价形式ll1分析表通过分析表来进行语法分析本程序的主要功能是对一个文法句子的生成过程进行分析
实验三语法分析---LL（1）分析器
一
（
1.用程序的方法实现语法分析的LL（1）方法。
}
void put_setence()
{
char ch;
int i=0;
while((ch=cin.get()) != '#') {
analyz_sentence[i] = ch;
i++;
}
analyz_sentence[i] = '#';
}
void init_stack()
{
stack[0] = '#';
return i;
}
return -1;
}
void reve()
{
strcpy(s, tp);
int i,j;
char t;
i=0;
while (s[i] != '\0')
++i;
--i;
if (s[i] == '\n')
--i;
j=0;
while (j<i)
{
t = s[j];
s[j] = s[i];
cout << "=>";
if (top == 'u')
pop();
}
void pop()
{