编译原理程序设计实验报告
——表达式语法分析器的设计实现
班级：计算机1306班 姓名：王利达
学号：20133959
实验目标：使用LL(1)分析法构造表达式语法分析器程序，判别算术表达式，给出判别结果。
实验内容： 一、概要设计
1.算术表达式文法：
E→ T | Eω0T T→ F | Tω1F F→ i | ( E ) 其中ω0：+ - ω1：* / i：数字或常数 文法变换： E → T M M → ω0 T M |ε T → F | N N → ω1 F N |ε
F → i | ( E ) 其中ω0：+ - ω1：* / i：数字或常数 2.LL(1)分析表
表1.LL(1)分析表 E M T N F ) # i MT,p NF,p ε,n + MT,n - MT,n * NF,n / NF,n ( MT,p NF,p )E,n ) ε,p ε,p ε,n # ε,p ε,p OK
二、数据结构
1.输入表达式
定义char型数组expstr为存放输入表达式的数组，
char expstr[100];
2.分析栈
定义一个栈来进行LL(1)分析。栈中有bottom、top、stacksize等元素，用于程序调用栈和对栈操作。
typedef struct //定义语法的栈 {
SElemType *bottom;//底 SElemType *top;//顶 int stacksize; }SqStack;
（包括：概要设计、数据结构、流程图、关键函数等 有选择填写）
源程序代码：（加入注释）
#include #include #includeusing namespace std;
#define STACKSIZE 30 //栈大小 #define STACKINCREMENT 10 //栈增量 #define OK 1 #define Error 0
#define OVERFLOW -1
typedef 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!\"<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; 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; //终结符 返回1
else //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 } else
return 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' M PUSH(S,e); e='T';
PUSH(S,e); break; } else
wrong(); 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; } else
wrong(); case 'T':
if(num_letter(s,i)||s[i]=='(') {
e='N'; //T' N PUSH(S,e); e='F';
PUSH(S,e); break; }
else
wrong(); 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; } else
wrong(); 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; } else
wrong(); 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); } else
wrong(); }
while(count2!=0) {
i++; count2--; }
PUSH(S,e); i++; }
else //如果是+-*/则直接比较 {
if(e==s[i]) i++; else
wrong(); } } } else
wrong(); } }
int main()
{
SqStack S; InitStack(S);
cout<<\"LL(1)\\nPlease enter the expression and end with the \\\"#\\\":\"<>expstr; LL1(S,expstr,i);cout<<\"Right! \"<程序运行结果：（截屏）图1.正确的算术表达式(((a+b)*(c/B)))的判断
图2.错误的算术表达式a/b++的判断
思考问题回答：（如果有）
LL(1)分析法和递归下降子程序法在语法分析中同属于自顶向下分析法，LL(1)分析法相对于递归下降子程序法的优势是：LL(1)分析法消除了文法的左递归性，而且克服了回溯，使程序运行的效率大大提升。
