下载文档原格式
实验二语法分析（自上而下分析）一、实习目的熟悉并设计一个表达式的语法分析器二、实验内容1.设计表达式的语法分析器算法2.编写代码并上机调试运行通过要求：输入表达式输出——表达式语法是否正确三、实验要求运用算术表达式的LL（1）分析算法来设计的表达式的语法分析器。
LL（1）文法是一个自上而下的语法分析方法，它是从文法的识别符号出发，生成句子的最左推导，从左到右扫描源程序，每次向前查看一个字符，便能确定当前应该选择的产生式。
LL（1）分析需要用一个分析表和一个符号栈。
分析表是一个矩阵，它的元素可以存放一个非终结符的产生式，表明当符号栈的栈顶元素非终结符遇到当前输入字符时，所应选择的产生式；分析表的元素还可以是存放一个出错标志，说明符号栈S 的栈顶元素非终结符不应该遇到当前输入符（终结符）。
重复调用LL（1）分析方法对每一个输入字符进行分析，直到输入栈为空为止。
四、运行结果注：此程序只能对由‘i’,’+’,’*’,’<’,’>’构成的以‘#’结速的字符串进行分析。
五、源程序（此程序只能在VC++中运行）#include<stdio.h>#include<stdlib.h>#include<string.h>#include<dos.h>char A[20];/*分析栈*/char B[20];/*剩余串*/char v1[20]={'i','+','*','(',')','#'};/*终结符*/ char v2[20]={'E','G','T','S','F'};/*非终结符*/int j=0,b=0,top=0,l;/*L为输入串长度*/typedef struct type/*产生式类型定义*/ {char origin;/*大写字符*/char array[5];/*产生式右边字符*/int length;/*字符个数*/}type;type e,t,g,g1,s,s1,f,f1;/*结构体变量*/type C[10][10];/*预测分析表*/void print()/*输出分析栈*/{int a;/*指针*/for(a=0;a<=top+1;a++)printf("%c",A[a]);printf("\t\t");}/*print*/void print1()/*输出剩余串*/{int j;for(j=0;j<b;j++)/*输出对齐符*/ printf(" ");for(j=b;j<=l;j++)printf("%c",B[j]);printf("\t\t\t");}/*print1*/void main(){int m,n,k=0,flag=0,finish=0;char ch,x;type cha;/*用来接受C[m][n]*//*把文法产生式赋值结构体*/ e.origin='E';strcpy(e.array,"TG");e.length=2;t.origin='T';strcpy(t.array,"FS");t.length=2;g.origin='G';strcpy(g.array,"+TG");g.length=3;g1.origin='G';g1.array[0]='^';g1.length=1;s.origin='S';strcpy(s.array,"*FS");s.length=3;s1.origin='S';s1.array[0]='^';s1.length=1;f.origin='F';strcpy(f.array,"(E)");f.length=3;f1.origin='F';f1.array[0]='i';f1.length=1;for(m=0;m<=4;m++)/*初始化分析表*/for(n=0;n<=5;n++)C[m][n].origin='N';/*全部赋为空*//*填充分析表*/C[0][0]=e;C[0][3]=e;C[1][1]=g;C[1][4]=g1;C[1][5]=g1;C[2][0]=t;C[2][3]=t;C[3][1]=s1;C[3][2]=s;C[3][4]=C[3][5]=s1;C[4][0]=f1;C[4][3]=f;printf("提示:本程序只能对由'i','+','*','(',')'构成的以'#'结束的字符串进行分析,\n");printf("请输入要分析的字符串:");do/*读入分析串*/{scanf("%c",&ch);if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')){printf("输入串中有非法字符\n");exit(1);}B[j]=ch;j++;}while(ch!='#');l=j;/*分析串长度*/ch=B[0];/*当前分析字符*/A[top]='#'; A[++top]='E';/*'#','E'进栈*/printf("步骤\t\t分析栈\t\t剩余字符\t\t所用产生式\n"); do{x=A[top--];/*x为当前栈顶字符*/printf("%d",k++);printf("\t\t");for(j=0;j<=5;j++)/*判断是否为终结符*/if(x==v1[j]){flag=1;break;}if(flag==1)/*如果是终结符*/{if(x=='#'){finish=1;/*结束标记*/printf("acc!\n");/*接受*/getchar();getchar();exit(1);}/*if*/if(x==ch){print();print1();printf("%c匹配\n",ch);ch=B[++b];/*下一个输入字符*/flag=0;/*恢复标记*/}/*if*/else/*出错处理*/{print();print1();printf("%c出错\n",ch);/*输出出错终结符*/exit(1);}/*else*/}/*if*/else/*非终结符处理*/{for(j=0;j<=4;j++)if(x==v2[j]){m=j;/*行号*/break;}for(j=0;j<=5;j++)if(ch==v1[j]){n=j;/*列号*/break;}cha=C[m][n];if(cha.origin!='N')/*判断是否为空*/ {print();print1();printf("%c->",cha.origin);/*输出产生式*/for(j=0;j<cha.length;j++)printf("%c",cha.array[j]);printf("\n");for(j=(cha.length-1);j>=0;j--)/*产生式逆序入栈*/A[++top]=cha.array[j];if(A[top]=='^')/*为空则不进栈*/top--;}/*if*/else/*出错处理*/{print();print1();printf("%c出错\n",x);/*输出出错非终结符*/exit(1);}/*else*/}/*else*/}while(finish==0);}/*main*/。
第五章⾃上⽽下语法分析第五章⾃上⽽下语法分析1、教学⽬的及要求：本章介绍编译程序的第⼆个阶段语法分析的设计⽅法和实现原理，包括⾃上⽽下分析的⽆回朔的递归下降分析、 LL(1)分析法。
要求理解递归下降分析、LL(1)⽂法的基本概念；掌握⽆回朔的递归下降分析的设计和实现、LL(1)分析表的构造与分析⽅法。
◇能够对⼀个给定的⽂法判断是否是LL(1)⽂法；◇能构造预测分析表；◇能⽤预测分析⽅法判断给定的输⼊符号串是否是该⽂法的句⼦；◇能对某些⾮LL(1)⽂法做等价变换：①消除左递归②提取左公共因⼦可能会变成LL(1)⽂法。
这样可扩⼤⾃顶向下分析⽅法的应⽤。
2、教学内容：语法分析器的功能，⾃上⽽下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序。
3、教学重点：递归下降⼦程序，预测分析表构造，LL(1)⽂法。
4、教学难点：对⼀个⽂法如何判断是否是LL(1)⽂法，由于在判断 LL(1)⽂法时⽤到⽂法符号串的开始符号集合（FIRST集）和⾮终结符后跟符号集合（FOLLOW集）的计算，⽽⼀般学⽣往往因概念不清或不够细⼼对这两个集合的计算常常出错，导致判断和分析结果的错误。
5、课前思考为了了解⾃顶向下（⾃上⽽下）分析的⼀般过程和问题，请学⽣⾸先回顾本章之前介绍的有关基本概念：◇句⼦、句型和语⾔的定义是什么？◇什么叫最左推导？◇什么叫最右推导和规范推导？◇什么叫确定的⾃顶向下语法分析？◇⾃顶向下语法分析是从⽂法的开始符号出发，反复使⽤各种产⽣式，寻找与输⼊符号匹配的推导。
◇确定的⾃顶向下语法分析中⽤的是哪种推导？◇在确定的⾃顶向下语法分析过程中，当以同⼀个⾮终结符为左部的产⽣式有多个不同右部时，如何选择⽤哪个产⽣式的右部替换当前的⾮终结符？◇确定的⾃顶向下语法分析对⽂法有何限制？6、章节内容第⼀节概述第⼆节 LL(1)分析⽅法第三节递归下降分析法5.1 概述LL分析法确定的⾃上⽽下分析⾃上⽽下分析递归下降分析法语法分析不确定的⾃上⽽下分析——即带回溯的分析⽅法算符优先分析⾃下⽽上分析LR分析⼀、带回溯的⾃顶向下分析⽅法是⾃顶向下分析的⼀般⽅法，即对任⼀输⼊符号串，试图⽤⼀切可能的办法，从树根结点（识别符号）出发，根据⽂法⾃上⽽下地为输⼊串建⽴⼀棵语法树，或者说，从识别符号开始，根据⽂法为输⼊串建⽴⼀个推导序列，这种分析过程本质上是⼀种试探过程，是反复使⽤不同规则谋求匹配输⼊串的过程。
