编译原理：基于预测方法的语法分析程序的设计
程序员文章站
2022-07-13 17:37:00
...
实验二 基于预测方法的语法分析程序的设计（必修）
一、实验目的
了解预测分析器的基本构成及用自顶向下的预测法对表达式进行语法分析的方法，掌握预测语法分析程序的手工构造方法。
二、实验内容
1、了解编译程序的基于预测方法的语法分析过程。
2、根据预测分析原理设计一个基于预测方法的语法分析程序。
三、实验要求
对给定文法G[S]：
S->AT A->BU T->+AT|$ U->*BU|$ B->(S)|m
其中，$表示空串。
1、判断上述文法G[S]是否LL(1)文法，若不是，将其转变为LL(1)文法；
2、对转变后的LL(1)文法建立预测分析表；
3、根据清华大学出版编译原理教材教材第五章P94的图5.11手工构造预测分析程序；
4、用预测分析程序对任意给定的键盘输入串m+m*m#进行语法分析，并根据栈的变化状态输出给定串的具体分析过程。
四、运行结果
从任意给定的键盘输入串：
m+m*m#；
输出：
用预测分析法分析符号串m+m*m#的过程
Step |
Stack |
String |
Rule |
Step |
Stack |
String |
Rule |
1 |
#S |
m+m*m# |
S->AT |
10 |
#TUm |
m*m# |
M匹配 |
2 |
#TA |
m+m*m# |
A->BU |
11 |
#TU |
*m# |
U->*BU |
3 |
#TUB |
m+m*m# |
B->m |
12 |
#TUB* |
*m# |
*匹配 |
4 |
#TUm |
m+m*m# |
M匹配 |
13 |
#TUB |
m# |
B->m |
5 |
#TU |
+m*m# |
U->$ |
14 |
#TUm |
m# |
M匹配 |
6 |
#T |
+m*m# |
T->+AT |
15 |
#TU |
# |
U->$ |
7 |
#TA+ |
+m*m# |
+匹配 |
16 |
#T |
# |
T->$ |
8 |
#TA |
m*m# |
A->BU |
17 |
# |
# |
接受 |
9 |
#TUB |
m*m# |
B->m |
|
|
|
|
五、提示
本实验重点有两个：一是如何用适当的数据结构实现预测分析表存储和使用；二是如何实现各规则右部串的逆序入栈处理。
建议：使用结构体数组。
主函数：main.cpp
#include <iostream>
#include <string.h>
#include <iomanip>
#include "Stack.h"
using namespace std;
#define ROW_SIZE 10
#define COLUMN_SIZE 10
#define RULE_SIZE 10
char row[ROW_SIZE];
char column[COLUMN_SIZE];
char Rule[RULE_SIZE];
///定义一个结构体，存储规则右部的值
typedef struct
{
char rules[COLUMN_SIZE][RULE_SIZE];
}analyse;
///函数声明部分
int element_Search(char a[],char e,int length);
int rule_Search(analyse anal[],char e,char element,int m,int n);
int analyse_Process(Stack s,char str[],analyse anal[],int m,int n);
/**
样例：
5 6
m ( ) + * #
S ->AT ->AT 0 0 0 0
A ->BU ->BU 0 0 0 0
T 0 0 ->$ ->+AT 0 ->$
U 0 0 0 ->$ ->*BU ->$
B ->m ->(S) 0 0 0 0
m+m*m#
2 3
p q #
S ->pR ->qq 0
R ->p ->q 0
pqqppq#
2 3
a b #
S ->aM ->bb 0
M ->a ->b 0
abb#
**/
int main()
{
///将预测分析表输入进行存储
analyse anal[ROW_SIZE];
int m,n;
int i,j;
cout<<"请将预测分析表按下列要求进行输入"<<endl;
cout<<"请输入两个整数"<<endl;
cout<<"终结符个数：";
cin>>m;
cout<<"非终结符个数（包括‘#’)：";
cin>>n;
cout<<"请输入终结符列："<<endl;
for(i=0;i<n;i++)
cin>>column[i];
cout<<"请按非终结符行输入预测分析表中的内容（对于没有内容的单元用0表示）："<<endl;
for(i=0;i<m;i++)
{
cin>>row[i];
for(j=0;j<n;j++)
{
cin>>anal[i].rules[j];
}
}
while(1)
{
///输入待分析符号串
cout<<endl;
char str[30];
cout<<"请输入待分析符号串(以#结尾)：";
cin>>str;
cout<<endl;
Stack s;
InitStack(s);
int result=analyse_Process(s,str,anal,m,n);
if(result==0)
{
cout<<"输入的串不是该文法的句子"<<endl;
cout<<endl;
}
else
{
cout<<"输入的分析串是该文法的句子"<<endl;
cout<<endl;
}
int cmd=0;
while(1){
cout<<"是否结束分析（Y/N）：";
char want;
cin>>want;
if(want=='Y' ||want=='y')
{
cmd=1;
break;
}
else if (want=='n' || want=='N')
{
break;
}
else
{
cout<<"输入指令有误，请重新输入"<<endl;
}
}
if(cmd==1)
{
break;
}
}
return 0;
}
///分析过程的输出
int analyse_Process(Stack s,char str[],analyse anal[],int m,int n)
{
Push(s,'#');///对栈进行初始化，将‘#’号和开始符入栈
Push(s,row[0]);
int i=0,j,step=1,k;
char e=row[0],a[30];
cout<<"用预测分析法分析符号串"<<str<<"的过程"<<endl;
cout<<"step Stack String Rule"<<endl;
while(e!='#')
{
///输出步骤数以及栈中的内容
cout<<std::left<<setw(8)<<step;
reverseTraverse(s);
///输出剩余匹配串
k=0;
for(j=i;str[j]!='\0';j++)
{
a[k]=str[j];
k++;
}
a[k]='\0';
printf("%-10s",a);
Pop(s,e);
if(e==str[i])
{
i++;
}
else
{
int result=rule_Search(anal,e,str[i],m,n);
if(result==-1 || result==0)
{
cout<<"报错"<<endl;
return 0;
}
else
{
int e2;
for(j=strlen(Rule)-1;j>1;j--)
{
e2=Rule[j];
if(e2!='$')
Push(s,e2);
}
}
}
///输出Rule
if(e=='#' && str[i-1]=='#')
cout<<std::left<<setw(10)<<"接受"<<endl;
else if (e==str[i-1])
cout<<e<<std::left<<setw(10)<<"匹配"<<endl;
else
cout<<e<<std::left<<setw(10)<<Rule<<endl;
step++;
}
return 1;
}
///从预测分析表中查找栈顶元素行，剩余串列查找规则
///如果没有该行或者该列，返回值为-1，如果该行没有规则（即为“0”时），返回值为0
///如果有规则，则将规则右部存储在Rule数组内，返回值1；
int rule_Search(analyse anal[],char e,char element,int m,int n)
{
int row_index=element_Search(row,e,m);
int col_index=element_Search(column,element,n);
if(row_index==-1 || col_index==-1)
{
return -1;
}
else
{
if(strcmp(anal[row_index].rules[col_index],"0")==0)
{
return 0;
}
else
{
strcpy(Rule,anal[row_index].rules[col_index]);
return 1;
}
}
}
///查找元素，返回其对应的下标，如果不存在返回-1；
int element_Search(char a[],char e,int length)
{
int i,result=-1;
for(i=0;i<length;i++)
{
if(a[i]==e)
{
result=i;
break;
}
}
return result;
}头文件： Stack.h
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define STACK_INT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct
{
char *base;
char *top;
int stacksize;
}Stack;
///创造一个空栈
int InitStack(Stack &S)
{
S.base=(char *)malloc(STACK_INT_SIZE*sizeof(char));
if(!S.base)
exit(-2);
S.top=S.base;
S.stacksize=STACK_INT_SIZE;
return 1;
};
///销毁栈S，栈S不再存在
int DestroyStack(Stack &S)
{
while(S.top!=S.base)
{
free(--S.top);
S.top--;
}
free(S.base);
return 1;
}
///把S置为空栈
int ClearStack(Stack &S)
{
while(S.top!=S.base)
{
free(--S.top);
S.top--;
}
return 1;
}
///返回S的元素个数，即栈的长度
int StackLength(Stack S)
{
return S.top-S.base;
}
///返回S的元素个数，即栈的长度
int StackEmpty(Stack S)
{
if(S.top==S.base)
return 1;
else
return 0;
}
///若栈不为空，则用e返回栈顶元素，并返回OK，否则返回ERROR
int GetTop(Stack S,char &e)
{
if(S.base==S.top)
return 0;
e=*(S.top-1);
return 1;
}
///插入元素e为新的栈顶元素
int Push(Stack &S,char e)
{
if(S.top-S.base>=S.stacksize)///栈满追加存储空间
{
S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if(!S.base)///存储分配失败
exit(-2);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top=e;
S.top++;
return 1;
}
///若栈不为空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR；
int Pop(Stack &S,char &e)
{
if(S.top==S.base)
return 0;
e=*--S.top;
return 1;
}
///遍历栈中的元素
int StackTraverse(Stack S)
{
if(S.base==NULL)
return -1;
if(S.base==S.top)
printf("栈中没有元素\n");
char *p;
p=S.top;
while(p-S.base>0)
{
p--;
printf("%c ",*p);
}
printf("\n");
return 1;
}
int reverseTraverse(Stack S)
{
if(S.base==NULL)
return -1;
if(S.base==S.top)
printf("栈中没有元素\n");
char *p,a[30];
int i=0;
p=S.base;
while(p<S.top)
{
a[i]=*p;
i++;
p++;
}
a[i]='\0';
printf("%-9s",a);
return 1;
}
#endif // STACK_H_INCLUDED运行结果如下：