语法分析LR分析器.doc

第4次上机—语法分析2

目的：熟练掌握自下而上的语法分析方法，并能用程序实现。
要求：
1. 使用如下文法：
E ® E+T | T
T ® T*F | F
F ® (E) | id
2. 对于任意给定的输入串（词法记号流）进行语法分析，要求采用LR分析器来完成。手工构造LR分析表，利用移进-归约分析算法（P69 图3.12）输出（P70 表3.8）对应的动作部分。如：
输入：id*+id/(id+id)#
输出：移进
按 F->id归约
移进
error
……
3. 要有一定的错误处理功能。即对错误能提示，并且能在一定程度上忽略尽量少的记号来进行接下来的分析。
例如：
从状态0开始的记号流为：bm
将b移进之后，栈里的情况应该为： 0 b 2
此时查表发现 action[2,m]=error
输出打印：error
把A和状态1相继压入栈，用户指针后移到FOLLOW(A)对应的元素继续分析。
0
.
.
.
.
.
.
栈
.. . . . a . .
A
发现错误
I0 :
C®a ·Ac
A®· bn
. . .
I 1
C®a A ·c
. . .
A
I 2
A®b · n
. . .
b

扩展：
1.利用P92页的表3.13的方式将错误进行分类提示，即给出具体的出错信息。
2. 在已有文法的基础上再加上减法“-”和除法“/”对应的产生式构成最终的文法。从而使得记号流可以处理带括号的加、减、乘、除四则运算。

代码实现：
#include<iostream>
#include<stack>
using namespace std;
stack<char> symbol;
stack<int> state;
char sen[50];
char sym[12][6]={//符号表
{'s','e','e','s','e','e'},
{'e','s','e','e','e','a'},
{'r','r','s','r','r','r'},
{'r','r','r','r','r','r'},
{'s','e','e','s','e','e'},
{'r','r','r','r','r','r'},
{'s','e','e','s','e','e'},
{'s','e','e','s','e','e'},
{'e','s','e','e','s','e'},
{'r','r','s','r','r','r'},
{'r','r','r','r','r','r'},
{'r','r','r','r','r','r'}
};
char snum[12][6]={//数字表
{5,1,1,4,2,1},
{3,6,5,3,2,0},
{2,2,7,2,2,2},
{4,4,4,4,4,4},
{5,1,1,4,2,1},
{6,6,6,6,6,6},
{5,1,1,4,2,1},
{5,1,1,4,2,1},
{3,6,5,3,11,4},
{1,1,7,1,1,1},
{3,3,3,3,3,3},
{5,5,5,5,5,5}
};
int go2[12][3]={//goto表
{1,2,3},
{0,0,0},
{0,0,0},
{0,0,0},
{8,2,3},
{0,0,0},
{0,9,3},
{0,0,10},
{0,0,0},
{0,0,0},
{0,0,0},
{0,0,0}
};
void action(int i,char *&a,char &how,int &num,char &A,int &b)//action函数[i,a]
{
int j;
switch(*a)
{
case 'i':
j=0;break;
case '+':
j=1;break;
case '*':
j=2;break;
case '(':
j=3;break;
case ')':
j=4;break;
case '#':
j=5;break;
default:
j=-1;break;
}
if(j!=-1)
{
how=sym[i][j];
num=snum[i][j];
if(how=='r')
{
switch(num)
{
case 1:
A='E',b=3;
cout<<"按E->E+T规约"<<endl;
break;
case 2:
A='E',b=1;
cout<<"按E->T规约"<<endl;
break;
case 3:
A='T',b=3;
cout<<"按T->T*F规约"<<endl;
break;
case 4:
A='T',b=1;
cout<<"按T->F规约"<<endl;
break;
case 5:
A='F',b=3;
cout<<"按F->(E)规约"<<endl;
break;
case 6:
A='F',b=1;
cout<<"按F->id规约"<<endl;
break;
default:
break;
}
}
}
}

int go(int t,char A)//goto[t,A]
{
switch(A)
{
case 'E':
return go2[t][0];break;
case 'T':
return go2[t][1];break;
case 'F':
return go2[t][2];break;
}
}
void error(int i,int j,char *&a)//error处理函数
{
cout<<"error"<<endl;
switch(j)
{
case 1://期望输入id或左括号,但是碰到+,*,或$,就假设已经输入id了,转到状态5
state.push(5);
symbol.push('i');//必须有这个,如果假设输入id的话,符号栈里必须有....
cout<<"缺少运算对象id"<<endl;
break;
case 2://从输入中删除右括号
a++;
cout<<"不配对的右括号"<<endl;
break;
case 3://期望碰到+,但是输入id或左括号,假设已经输入算符+,转到状态6
state.push(6);
symbol.push('+');
cout<<"缺少运算符"<<endl;
break;
case 4://缺少右括号,假设已经输入右括号,转到状态11
state.push(11);
symbol.push(')');
cout<<"缺少右括号"<<endl;
break;
case 5:
a++;
cout<<"*号无效,应该输入+号!"<<endl;
case 6:
a++;
}
}

int main()
{
int s;
char *a;
char how;
int num;
int b;
char A;
while(1)
{
cin>>sen;
a=sen;
state.push(0);//先输入0状态
while(*a!='\0')
{
b=0;num=0;how='\0';A='\0';
s=state.top();
action(s,a,how,num,A,b);
if(how=='s')//移进
{
cout<<"移进"<<endl;
symbol.push(*a);
state.push(num);
// if(*a=='i')
// a++;//在这里忽略i后面的d
a++;
}
else if(how=='r')//规约
{
for(int i=0;i<b;i++)
{
if(!state.empty())
state.pop();
if(!symbol.empty())
symbol.pop();
}
int t=state.top();
symbol.push(A);
state.push(go(t,A));
}
else if(how=='a')//接受
break;
else
{
error(s,num,a);//错误处理
}
}
cout<<"成功接受"<<endl;
}
return 0;
}