编译原理实验报告：自下而上语法分析
1. 实验题目：自下而上语法分析
实验目的
- 给出PL/0文法规范，要求编写PL/0语言的语法分析程序。
- 通过设计、编制、调试一个典型的自下而上语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。
- 选择最有代表性的语法分析方法，如算符优先分析法、LR分析法；或者调研语法分析器的自动生成工具YACC的功能与工作原理，使用YACC生成一个自底向上的语法分析器。
实验内容
已给 PL/0 语言文法，构造表达式部分的语法分析器。
分析对象〈算术表达式〉的 BNF 定义如下：
<表达式> ::= [+|-]<项>{<加法运算符> <项>}
<项> ::= <因子>{<乘法运算符> <因子>}
<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<关系运算符> ::= =|#|<|<=|>|>=
实验要求
- 将实验一“词法分析”的输出结果，作为表达式语法分析器的输入，进行语法解析，对于语法正确的表达式，报告“语法正确法错误的表达式，报告“语法错误”， 指出错误原因。
- 把语法分析器设计成一个独立一遍的过程。
- 采用算符优先分析法或者LR分析法实现语法分析；或者调研语法分析器的自动生成工具YACC的功能与工作原理，使用YACC生成一个自底向上的语法分析器。
输入输出
输入：
PL/0 表达式，用实验一的输出形式作为输入。例如：对于 PL/0 表达式，（a+15）*b 用下列形式作为输入：
(lparen,( )
(ident, a)
(plus, + )
(number, 15)
(rparen,) )
(times, * )
(ident, b )
输出：
对于语法正确的表达式，报告“语法正确”；
对于语法错误的表达式，报告“语法错误”， 指出错误原因
2. 设计思想
对于文法G：
<表达式> ::= [+|-]<项>{<加法运算符> <项>}
<项> ::= <因子>{<乘法运算符> <因子>}
<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<关系运算符> ::= =|#|<|<=|>|>=
可以改成如下：
S’-><表达式>
<表达式>-><项>
<表达式>-><表达式>+<项>
<表达式>-><表达式>-<项>
<项>-><因子>
<项>-><项>*<因子>
<项>-><项>/<因子>
<因子>->(<表达式>)
<因子>-><标识符>
<因子>-><无符号整数>
算符优先分析是定义在算符之间的某种优先关系，借助于这种优先关系寻找可规约串和进行规约。
算符文法的定义：
所有产生式的右部都不是两个相继并列的非终结符设有一个文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法。
算符优先文法的特点：
一旦我们构造了算符优先语法分析器，就可以忽略原来的文法，栈中的非终结符仅仅作为与这些非终结符相关的属性的占位符，难以处理像减号这样有不同优先级的符号，由于分析的语言的文法和算符优先语法分析器本身的关系不是很紧密，所以不能肯定语法分析器接受的就是所期望的语言。
对于优先关系进行如下定义：
a的优先级小于b
(1) a<b： 当且仅当文法G中有形如A→…aR…的产生式而R⇒+b…或R⇒+Qb…
a的优先级等于b
(2) a=b：当且仅当文法G中有形如A→…ab…或者A→…aQb…的产生式
a的优先级高于b
(3) a>b：当且仅当文法G中有形如A→…Rb…的产生式,而R⇒+…a或R⇒+…aR
如果一个算符文法G中的任何终结符对（a，b）至多满足下述三关系之一：
a<b,a=b,a>b
则称G是一个算符优先文法。
定义并构造FIRSTVT和LASTVT两个集合
FIRSTVT§={a|P⇒+a⋯或P⇒+Qa⋯}
LASTVT§={a|P⇒+⋯a或P⇒+⋯aQ}
在此构造文法的FIRSTVT集和LASTVT集
文法如下
<表达式> ::= [+|-]<项>{<加法运算符> <项>}
<项> ::= <因子>{<乘法运算符> <因子>}
<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’
<加法运算符> ::= +|-
<乘法运算符> ::= *|/
<关系运算符> ::= =|#|<|<=|>|>=
FIRSTVT(表达式)={+，-，(，， /，标识符，无符号整数 }
FIRSTVT(项)={，/，（，标识符，无符号整数}
FIRSTVT(因子)={（，标识符，无符号整数}
FRTSTVT(加法运算符)={+，-}
FRTSTVT(乘法运算符)={，/}
LASTVT(表达式)={+，-，），， /，标识符，无符号整数 }
LASTVT(项)={*，/，），标识符，无符号整数}
LASTVT(因子)={），标识符，无符号整数}
构造优先表
实验流程
- 根据文法求FIRSTVT集和LASTVT集
- 构造算符优先分析表
- 构造总控程序
算法描述如下：
stack S;
k = 1; //符号栈S的使用深度
S[k] = ‘#’
REPEAT
把下一个输入符号读进a中；
If S[k] VT then j = k else j = k-1;
While S[j] > a do
Begin
Repeat
Q = S[j];
if S[j-1] VT then j = j-1 else j = j-2
until S[j] < Q;
把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号；
K = j+1;
S[k] = N;
end of while
if S[j] < a or S[j] = a then
begin k = k+1; S[k] = a end
else error //调用出错诊察程序
until a = ‘#’
- 对给定的表达式，给出准确与否的分析过程
- 给出表达式的计算结果。
3. 算法流程
4. 源程序
#include<fstream>
#include<cstring>
#include<string>
#include<fstream>
#include<sstream>
#include<iostream>
#include<map>
#include<bits/stdc++.h>
#define MAXN 9
using namespace std;
ifstream infile("C:\\Users\\46799\\Desktop\\编译原理\\第三次实验\\result.txt");
map<string,int> order;//定义终结符在优先表中的序号
stack<string> s,save;//s为符号栈，save为临时存储符号的容器
vector<string> Terminal;//用来存放终结符，以此来进行对照，检查是不是终结符
vector<string>::iterator result;//一个迭代器来判断是不是终结符
string reduction[100];//定义本次需要进行规约的符号串
string str;//读入的字符串
string sym;//用来指示读入的符号
int flag=0;
int prioritytable[MAXN][MAXN]={{0,0,1,1,1,1,1,2,2},//算符优先分析的优先表，0代表=，1代表<,2代表>,3代表空
{0,0,1,1,1,1,1,2,2},
{2,2,0,0,1,1,1,2,2},
{2,2,0,0,1,1,1,2,2},
{2,2,2,2,0,3,3,2,2},
{2,2,2,2,3,0,3,2,2},
{1,1,1,1,1,1,1,0,2},
{2,2,2,2,3,3,0,2,2},
{1,1,1,1,1,1,1,1,0}};
void init(){//进行初始化，定义终结符的序号，以及简化终结符的查找通过vector的find函数
order["plus"]=0;
order["minus"]=1;
order["times"]=2;
order["slash"]=3;
order["ident"]=4;
order["number"]=5;
order["lparen"]=6;
order["rparen"]=7;
order["#"]=8;
for(int i=0;i<9;i++){
Terminal.push_back("plus");
Terminal.push_back("minus");
Terminal.push_back("times");
Terminal.push_back("slash");
Terminal.push_back("ident");
Terminal.push_back("number");
Terminal.push_back("lparen");
Terminal.push_back("rparen");
Terminal.push_back("#");
}
}
int judgePrior(string a,string b){//从优先关系表中判断两个符号的优先关系
int row_prior,column_prior;//行列优先关系定位指针
row_prior=order[a];
column_prior=order[b];
if(prioritytable[row_prior][column_prior]==0){//=
return 0;
}else if(prioritytable[row_prior][column_prior]==1){//<
return 1;
}else if(prioritytable[row_prior][column_prior]==2){//>
return 2;
}else return 3;//空
}
int advance(){//用来读入下一个符号
int found;
if(!getline(infile,str)){
flag++;
if(flag==1){
sym="#";
return 1;
}
else if(flag>1){
return 0;
}
}
found=str.find(',',0);
sym=str.substr(1,found-1);
return 1;
}
int SearchSyn(string c){//根据相应字符返回其对应序号
return order[c];
}
int SearchTerminal(string c){//判断是不是终结符
result=find(Terminal.begin(),Terminal.end(),c);
if(result == Terminal.end()){
return 0;
}else{
return 1;
}
}
int Proc_Analysis(){//主控程序
int k=1,j=0;
string a,b,q;
s.push("#");//符号栈S将#推入
while(advance()){//把下一个输入符号读进a中；
if(SearchTerminal(s.top())){
j=k;
q=s.top();
}else{
j=k-1;
b=s.top();
s.pop();
save.push(b);
q=s.top();
}
while(judgePrior(q,sym)==2){//判断优先关系While S[j] > a do
if(!SearchTerminal(s.top())){
b=s.top();
s.pop();
save.push(b);
}
do{ //If S[k] VT then j = k else j = k-1;如果不为终结符则将要跳到下一个字符
b=s.top();
s.pop();
save.push(b);
j--;
if(SearchTerminal(s.top())){
q=s.top();
}else{
save.push(s.top());
s.pop();
q=s.top();
j--;
}
}while(judgePrior(q,b)!=1);
for(int i=0;i<k-j;i++){//这里我对需要规约的串进行存储，以方便规约
b=save.top();
save.pop();
reduction[i]=b;
}
for(int i=0;i<k-j;i++){
cout<<reduction[i]<<" ";
}
cout<<endl;
//如下为进行规约
if(reduction[0]=="term"){//<表达式> ::= <项>{<加法运算符> <项>}
if(!((k-j)%2)){
printf("语法错误，表达式归约错误");
return 0;
}
for(int i=0;i<k-j;i++){
if(!(i%2)){
if(reduction[i]!="term"){
printf("语法错误，表达式归约错误");
return 0;
}
}else{
if(reduction[i]!="plus"||reduction[i]!="minus"){
printf("语法错误，表达式归约错误");
return 0;
}
}
k=j+1;
s.push("expression");
}
}else if(reduction[0]=="factor"){//<项> ::= <因子>{<乘法运算符> <因子>}
if(!((k-j)%2)){
printf("语法错误，项归约错误");
return 0;
}
for(int i=0;i<k-j;i++){
if(i%2){
if(reduction[i]!="factor"){
printf("语法错误，项归约错误");
return 0;
}
}else{
if(reduction[i]!="times"||reduction[i]!="slash"){
printf("语法错误，项归约错误");
return 0;
}
}
}
k=j+1;
s.push("term");
}else if(reduction[0]=="lparen"){//<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’
if(reduction[0]=="lparen"){
if((k-j)!=3){
printf("语法错误，因子归约错误");
return 0;
}
if(reduction[1]!="expression"||reduction[2]!="rparen"){
printf("语法错误，因子归约错误");
return 0;
}
}
k=j+1;
if(s.top()!="times"||s.top()!="slash"||sym!="times"||sym!="slash"){
s.push("term");
}
else s.push("factor");//这里我直接将因子直接化成项，但正确性还有待考虑
}else if(reduction[0]=="number"||reduction[0]=="ident"){//<因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’
k=j+1;
if(s.top()!="times"||s.top()!="slash"||sym!="times"||sym!="slash"){
s.push("term");
}
else s.push("factor");
}else{
printf("语法错误，字符错误");
return 0;
}
}
if(judgePrior(q,sym)==1||judgePrior(q,sym)==0){
k++;
s.push(sym);
}
}
if(k==3){//如果最后为#表达式#则正确
for(int i=0;i<3;i++){
b=s.top();
s.pop();
if(i==0&&b!="#"){
printf("语法错误，表达式错误");
return 0;
}else if(i==1&&b!="expression"){
printf("语法错误，表达式错误");
return 0;
}else if(i==2&&b!="#"){
printf("语法错误，表达式错误");
return 0;
}
}
return 1;
}
else{
printf("语法错误，表达式错误");
return 0;
}
}
int main(){
init();
int right=Proc_Analysis();
if(right){
cout<<"语法正确"<<endl;
}
return 0;
}
5. 调试数据
待输入的文件流：
输出数据：