编译原理_语法分析_实验报告

《语法分析》

学生姓名艾力娜·托里干

依勒斯江·木尔扎合买提

克勒曼·沙布勒别克

学号 5011110132

5011110131

5011110136

所属学院信息工程学院

专业计算机科学与技术

班级民本15-1班

信息工程学院

一．LL(1)预测语法分析器

[实现目标]

简单的算术表达式的LL(1)语法分析器

实现工具

Microsoft Visual C++ 6.0,使用C/C++语言实现代码编程。

需求分析与概要设计：

编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。

语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。

详细的算法描述：

（1）自顶向下带递归语法分析（这个方法用的是老师给的文法）

1、首先对所以的生成式消除左递归、提取公共左因子

2、在源程序里建立一个字符串数组，将所有的生成式都存在这个数组中。

3、给每个非终结符写一个带递归的匹配函数，其中起始符的函数写在main函数里。这些函数对生成式右边从左向右扫描，若是终结符直接进行匹配，匹配失败，则调用出错函数。如果是非终结符则调用相应的非终结符函数。

4、对输入的符号串进行扫描，从起始符的生成式开始。如果匹配成功某个非终结符生成式右边的首个终结符，则将这个生成式输出。匹配过程中，应该出现的非终结符没有出现，则出错处理。

[文法]

l 产生式 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 */

l 开始符号S: E

l 终结符集Vt: { E, e, T, t, F }

l 非终结符集Vn: { +, -, *, /, (, ), i }

[构造预测分析表]

l FIRST集:

first(E)= first(T)= first(F)={ ﹝, i }

first(e)={+, -, ε}

first(t)={*, /, ε}

l 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<stdio.h>

#include<iostream.h>

#include<string.h>

#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<Vnn;i++)

for(int j=0;j<Vtn;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 < MaxStLength;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<len;i++)

analyseStack[topAnalyse-i]=Pint[r][i]; //逆序入栈

}

void ShowStack()

{

int i;

for(i =0;i<=topAnalyse;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<Vtn)&&(c!= Vt[i]))

i++;

if((i<Vtn)&&(c==Vt[i])) return 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]<100)

{

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<MaxStLength)

{

if(c=='$')

{

st[i]='$';

break;

}

else if(c!=' '&&c!='\n')

st[i++]=c;

c=getchar();

if(c=='\n')

{

printf("请以$结束：");

c=getchar();

}

if(i<MaxStLength)

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)文法是不含二义性的,也不含左递归的.故在构造分析器前要对所给的文法提取左因子,消除左递归.

相关推荐