编译原理_语法分析_实验报告
《编译原理及实践》结课大作业
《语法分析》
学生姓名 艾力娜·托里干
学 号
所属学院 信息工程学院
专 业 计算机科学与技术
班 级
信息工程学院
一．LL(1)预测语法分析器
[实现目标]
简单的算术表达式的LL(1)语法分析器
实现工具
Microsoft Visual C++ 6.0,使用C/C++语言实现代码编程。
需求分析与概要设计：
编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。
语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。
详细的算法描述：
（1） 自顶向下带递归语法分析 （这个方法用的是老师给的文法）
1、首先对所以的生成式消除左递归、提取公共左因子
2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。
3、给每个非终结符写一个带递归的匹配函数，其中起始符的函数写在main函数里。这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函数。如果是非终结符则调用相应的非终结符函数。
4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出现，则出错处理。
[文法]
产生式 P :
E -> E+T T -> T/F
E -> E-T T -> F
E -> T F -> (E)
T -> T*F F -> i
提取左因子并消除左递归得
产生式 P :
(0) E→Te
(1) e→+Te
(2) e→-Te
(3) e→ε
(4) T→Ft
(5) t→*Ft
(6) t→/Ft
(7) t→ε
(8)F→(E)
(9) F→i /*表示id */
开始符号S: E
终结符集Vt: { E, e, T, t, F }
非终结符集Vn: { +, -, *, /, (, ), i }
[构造预测分析表]
FIRST集:
first(E)= first(T)= first(F)={ ﹝, i }
first(e)={+, -, ε}
first(t)={*, /, ε}
FOLLOW集:
follow(E)={$, ﹞}
follow(e)=follow(E)={$, }}
follow(T)={fitsr(e)- ε}+follow(e)={+, _ , ﹞, $}
follow(t)=follow(T)+follow(t)={+, _ , ﹞, $}
follow(F)={follow(t)- ε}+follow(T)+follow(t)={*, /, +, _ ,﹞, $}
[预测分析器模型]
图1-1非递归的预测语法分析器模型
[源代码]
#include
#include
#include
#define Vtn 8
#define Vnn 5
#define Pn 10
#define Pmaxlen 20
#define MaxStLength 50
#define MaxStackDepth 50
char Vn[Vnn]={'E','e','T','t','F'};
char Vt[Vtn]={'i','+','-','*','/','(',')','$'};
char Pstr[Pn][Pmaxlen]={
"E->Te",
"e->+Te",
"e->-Te",
"e->ε",
"T->Ft",
"t->*Ft",
"t->/Ft",
"t->ε",
"F->(E)",
"F->i"
};
int Prlen[Pn]={2,3,3,1,2,3,3,1,3,1};
int Pint[Pn][3]={
{102,101},
{1,102,101},
{2,102,101},
{-1},
{104,103},
{3,104,103},
{4,104,103},
{-1},
{5,100,6},
{0}
};
int analyseTable[Vnn][Vtn+1];
int analyseStack[MaxStackDepth+1];
int topAnalyse;
char st[MaxStLength]; //要分析的符号串
/* ----------------------初始化----------------------------*/
void InitanalyseTable()
{
/*---预测分析表存放各个产生式的编号，-1表示找不到相匹配的产生式---*/ for(int i=0;i
for(int j=0;j
analyseTable[i][j]=-1;
analyseTable[0][0]=0;
analyseTable[0][5]=0;
analyseTable[1][1]=1;
analyseTable[1][2]=2;
analyseTable[1][6]=3;
analyseTable[1][7]=3;
analyseTable[2][0]=4;
analyseTable[2][5]=4;
analyseTable[3][1]=7;
analyseTable[3][2]=7;
analyseTable[3][3]=5;
analyseTable[3][4]=6;
analyseTable[3][6]=7;
analyseTable[3][7]=7;
analyseTable[4][0]=9;
analyseTable[4][5]=8;
}
void Init()
{
//分析栈的初始化
analyseStack[0]=7; //入栈
analyseStack[1]=100; //初始符入栈
topAnalyse=1;
//初始符号串
int i;
for(i = 0; i
st[i] = '\0';
}
void Pop()
{
topAnalyse--;
}
/*--------------------产生式入栈操作----------------------*/
void Push(int r)
{
int i,len;
Pop();
len=Prlen[r];
//为空时
if((len==1)&&(Pint[r][0]==-1))
return;
//不为空时
topAnalyse+=len;
for(i=0;i
analyseStack[topAnalyse-i]=Pint[r][i]; //逆序入栈
}
void ShowStack()
{
int i;
for(i =0;i
{
if(analyseStack[i]>=100)
printf("%c",Vn[analyseStack[i]-100]);
else
printf("%c", Vt[analyseStack[i]]);
}
}
/*----------------------返回表中的位置，-1表示未找到----------*/
int Index(char c)
{
int i=0;
while((i
i++;
if((i
else return -1;
}
void Identify()
{
int current,step,r;
printf("\n%s：\n\n", st);
step = 0;
current = 0;
printf("%d\t",step);
ShowStack();
printf("\t\t%s\t\t- -\n", st+current);
while(1)
{
if(analyseStack[topAnalyse]
{
if(Vt[analyseStack[topAnalyse]]==st[current])
{
Pop();
current++;
step++;
printf("%d\t",step);
ShowStack();
printf("\t\t%s\t\t出栈、后移\n", st+current);
}
else
{
printf("字符 %c 与字符 %c 不匹配！", Vt[analyseStack[topAnalyse]], st[current]);
printf("此串不是此文法的句子\n");
return;
}
}
else
{
int n,m;
n=analyseStack[topAnalyse] - 100;
m=Index(st[current]);
if(m==-1)
{
printf(" %c 字符不符合输入，输入出错！" ,st[current]); printf("此串不是此文法的句子\n");
return;
}
r = analyseTable[n][m];
if( r!=-1)
{
Push(r);
step++;
printf("%d\t", step);
ShowStack();
printf("\t\t%s\t\t%s\n", st+current,Pstr[r]);
}
else
{
printf("无可用产生式，此串不是此文法的句子！\n"); return;
}
}
if(topAnalyse==0&&st[current]=='$') break;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////
void main()
{
InitanalyseTable();
while(1)
{
Init();
printf("请输入符号串(以$结束) : ");
int i=0;
char c;
c=getchar();
while(i
{
if(c=='$')
{
st[i]='$';
break;
}
else if(c!=' '&&c!='\n')
st[i++]=c;
c=getchar();
if(c=='\n')
{
printf("请以$结束：");
c=getchar();
}
}
if(i
Identify();
else printf("输入的符号串超过额定长度");
}
}
[测试]
请输入符号串(以$结束) : i+i*i$
i+i*i$：
0 $E i+i*i$ - -
1 $eT i+i*i$ E->Te
2 $etF i+i*i$ T->Ft
3 $eti i+i*i$ F->i
4 $et +i*i$ 出栈、后移
5 $e +i*i$ t->ε
6 $eT+ +i*i$ e->+Te
7 $eT i*i$ 出栈、后移
8 $etF i*i$ T->Ft
9 $eti i*i$ F->i
10 $et *i$ 出栈、后移
11 $etF* *i$ t->*Ft
12 $etF i$ 出栈、后移
13 $eti i$ F->i
14 $et $ 出栈、后移
15 $e $ t->ε
16 $ $ e->ε
请输入符号串(以$结束) : i-(i+i/i)$
i-(i+i/i)$：
0 $E i-(i+i/i)$ - -
1 $eT i-(i+i/i)$ E->Te
2 $etF i-(i+i/i)$ T->Ft
3 $eti i-(i+i/i)$ F->i
4 $et -(i+i/i)$ 出栈、
5 $e -(i+i/i)$ t->ε
6 $eT- -(i+i/i)$ e->-Te
7 $eT (i+i/i)$ 出栈、
8 $etF (i+i/i)$ T->Ft
9 $et)E( (i+i/i)$ F->(E)
10 $et)E i+i/i)$ 出栈、后移
11 $et)eT i+i/i)$ E->Te
12 $et)etF i+i/i)$ T->Ft
13 $et)eti i+i/i)$ F->i
14 $et)et +i/i)$ 出栈、后移
15 $et)e +i/i)$ t->ε
16 $et)eT+ +i/i)$ e->+Te
17 $et)eT i/i)$ 出栈、后移
18 $et)etF i/i)$ T->Ft
19 $et)eti i/i)$ F->i
20 $et)et /i)$ 出栈、后移
21 $et)etF/ /i)$ t->/Ft
22 $et)etF i)$ 出栈、后移
23 $et)eti i)$ F->i
24 $et)et )$ 出栈、后移
25 $et)e )$ t->ε
26 $et) )$ e->ε
27 $et $ 出栈、后移
28 $e $ t->ε
29 $ $ e->ε
请输入符号串(以$结束) :
[总结体会]
1.通过本实验,我们不仅对语法分析有了进一步的了解,而且对相关知识点有了更深刻的了解.
2.LL(1)文法是不含二义性的,也不含左递归的.故在构造分析器前要对所给的文法提取左因子,消除左递归.