语法分析器实验报告

词法分析器实验报告

实验名称：语法分析器

实验内容：利用LL（1）或LR（1）分析语句语法，判断其是否符合可识别语法。学会根据状态变化、first、follow或归约转移思想构造状态分析表，利用堆栈对当前内容进行有效判断

实验设计：

1. 实现功能

可对一段包含加减乘除括号的赋值语句进行语法分析，其必须以$为终结符，语句间以；隔离，判断其是否符合语法规则，依次输出判断过程中所用到的产生式，并输出最终结论，若有错误可以报错并提示错误所在行数及原因

2. 实验步骤

3． 算法与数据结构

a) LLtable:left记录产生式左端字符；right记录产生式右端字符；ln记录产生式右端字符长度

Status：记录token分析情况

Token：category，类型；value，具体内容

b) 根据LL（1）算法，手工构造分析表，并将内容用数组存储，便于查找

c) 先将当前语句的各token按序存储，当前处理语句最后一个token以#标记，作为输入流与产生式比较，堆栈中初始放入#，x，a为处理输入流中当前读头内容

ü 若top=a=‘#‘表示识别成功，退出分析程序

ü 若top=a！=‘#‘表示匹配，弹出栈顶符号，读头前进一个

ü 若top为i或n，但top！=a，出错，输出当前语句所在行，出错具体字符

ü 若top不为i或n，查预测分析表，若其中存放关于top产生式，则弹出top，将产生式右部自右向左压入栈内，输出该产生式，若其中没有产生式，出错，输出当前语句所在行，出错具体字符

d) 以；作为语句终结，每次遇到分号则处理之前语句并清空后预备下语句处理，当遇到$表示该段程序结束，停止继续处理

4． 分析表构造过程

a) x->i=e

e->e+t|e-t|t

t->t*f|t/f|f

f->(e)|i|n

note: i表示变量，n表示数字,!表示空串

b) 提取左公因子

x->i=e

e->ea|t

a->+t|-t

t->tb|f

b->*f|/f

f->(e)|i|n

c) 消除左递归

x->i=e

e->tc

c->ac|!

a->+t|-t

t->fd

d->bd|!

b->*e|/f

f->(e)|i|n

d) FIRST & FOLLOW

e) 分析表

5． 类

class parser

{

public:

LLtable table[100][100]; //LL(1)表

void scanner(); //扫描输入流中内容并分析

parser(istream& in); //初始化，得到输入文件地址

int getLine() const; //得到当前行数

private:

int match(); //分析语法

stack proStack; //分析堆栈

void constructTable(); //建立LL（1）表

int getRow(char ch); //取字符所在表中行

int getCol(char ch); //取字符所在表中列

istream* pstream; //输入流

void insertToken(token& t); //插入当前token

status getToken(token& t); //找到token

int getChar(); //得到当前字符

int peekChar(); //下一个字符

void putBackChar(char ch); //将字符放回

void skipChar(); //跳过当前字符

void initialization(); //初始化堆栈等

int line; //当前行数

token tokens[1000]; //字符表

int counter; //记录当前字符表使用范围

}

6． 主要代码

void parser::constructTable() //建立LL（1）表

{

for (int i=0;i<8;i++)

{

for (int j=0;j<9;j++)

{

table[i][j].left=' ';

for (int k=0;k<3;k++)

table[i][j].right[k]=' ';

}

}

table[0][6].left='x';

table[0][6].ln=3;

table[0][6].right[0]='i';

table[0][6].right[1]='=';

table[0][6].right[2]='e';

table[1][4].left='e';

table[1][4].ln=2;

table[1][4].right[0]='t';

table[1][4].right[1]='c';

table[1][6].left='e';

table[1][6].ln=2;

table[1][6].right[0]='t';

table[1][6].right[1]='c';

table[1][7].left='e';

table[1][7].ln=2;

table[1][7].right[0]='t';

table[1][7].right[1]='c';

table[2][0].left='c';

table[2][0].ln=2;

table[2][0].right[0]='a';

table[2][0].right[1]='c';

table[2][1].left='c';

table[2][1].ln=2;

table[2][1].right[0]='a';

table[2][1].right[1]='c';

table[2][5].left='c';

table[2][5].ln=0;

table[2][5].right[0]='!';

table[2][8].left='c';

table[2][8].ln=0;

table[2][8].right[0]='!';

table[3][0].left='a';

table[3][0].ln=2;

table[3][0].right[0]='+';

table[3][0].right[1]='t';

table[3][1].left='a';

table[3][1].ln=2;

table[3][1].right[0]='-';

table[3][1].right[1]='t';

table[4][4].left='t';

table[4][4].ln=2;

table[4][4].right[0]='f';

table[4][4].right[1]='d';

table[4][6].left='t';

table[4][6].ln=2;

table[4][6].right[0]='f';

table[4][6].right[1]='d';

table[4][7].left='t';

table[4][7].ln=2;

table[4][7].right[0]='f';

table[4][7].right[1]='d';

table[5][0].left='d';

table[5][0].ln=0;

table[5][0].right[0]='!';

table[5][1].left='d';

table[5][1].ln=0;

table[5][1].right[0]='!';

table[5][2].left='d';

table[5][2].ln=2;

table[5][2].right[0]='b';

table[5][2].right[1]='d';

table[5][3].left='d';

table[5][3].ln=2;

table[5][3].right[0]='b';

table[5][3].right[1]='d';

table[5][5].left='d';

table[5][5].ln=0;

table[5][5].right[0]='!';

table[5][8].left='d';

table[5][8].ln=0;

table[5][8].right[0]='!';

table[6][2].left='b';

table[6][2].ln=2;

table[6][2].right[0]='*';

table[6][2].right[1]='f';

table[6][3].left='b';

table[6][3].ln=2;

table[6][3].right[0]='/';

table[6][3].right[1]='f';

table[7][4].left='f';

table[7][4].ln=3;

table[7][4].right[0]='(';

table[7][4].right[1]='e';

table[7][4].right[2]=')';

table[7][6].left='f';

table[7][6].ln=1;

table[7][6].right[0]='i';

table[7][7].left='f';

table[7][7].ln=1;

table[7][7].right[0]='n';

}

int parser::match() //分析语法

{

ofstream ofs("out.txt",ios::app);

char a;

int i=0;

for (int p=0;p

{

cout<

ofs<

}

cout<

ofs<

while(1)

{

if(tokens[i].category=='n' || tokens[i].category=='i')

a=tokens[i].category;

else

a=(tokens[i].value)[0];

if(a==proStack.top())

{

if(a=='#')

{

cout<<"This is valid!"<

ofs<<"This is valid!"<

return 0;

}

else

{

proStack.pop();

i++;

}

}

else

{

if(proStack.top() =='n'|| proStack.top() =='i')

{

if(a!='#')

{

cout<<"ERROR(LINE "<

ofs<<"ERROR(LINE "<

}

else

{

cout<<"ERROR(LINE "<

ofs<<"ERROR(LINE "<

}

cout<<"This is invalid!"<

ofs<<"This is invalid!"<

return 0;

}

else

{

if((table[getRow(proStack.top())][getCol(a)]).left!=' ')

{

char pst=proStack.top();

int n=table[getRow(pst)][getCol(a)].ln;

int k=0;

ofs<"<

proStack.pop();

while (n>0)

{

//cout<

proStack.push(table[getRow(pst)][getCol(a)].right[n-1]);

n--;

}

}

else

{

if(a!='#')

{

cout<<"ERROR(LINE "<

ofs<<"ERROR(LINE "<

}

else

{

cout<<"ERROR(LINE "<

ofs<<"ERROR(LINE "<

}

cout<<"This is invalid!"<

ofs<<"This is invalid!"<

return 0;

}

}

}

}

}

实验结果：

l 输入（in.txt）

l 输出1

l 输出2（out.txt）

实验总结：

原本以为处理四则运算赋值将会很困难，但在使用LL（1）后发现，思路还是挺清晰简单的，但在实验过程中，由于LL（1）不能出现左递归和左公因子，不得不将其消除，原本简单的产生式一下变多了，而在产生式理解上也没有原来直观，不过其状态复杂度没有LR高，故仍选择该方法。另外，在分别求first、follow时容易出错，在程序运行中没有得到期望结果时才发现，因此手工构造分析表较容易出错。最简单的四则运算赋值也牵涉到如此多的细节、转换，相信更为复杂的语句判断、循环等更不简单，如今计算机各种处理都远比四则运算赋值复杂得多，牵涉到诸多关系，而机器则能根据规则无差错完成，这也是人类依靠机器的重要原因，机器只是根据产生式一步步判断得出结论。而关于树形输出，在操作过程中发现较为困难，没有成功实现。