LR0分析器实验报告.doc

《编译原理》
课程设计性实验报告

课程题目： LR(0)分析法
姓 名： 钟继文
专业班级： 计算机科学与技术（1）班
指导老师： 孙长圣老师
学 号： 110920120019
报告日期： 2015年6月7日
编译原理语法分析实验报告

一、 实验内容
利用C语言编写一个程序，对字符串进行语法分析，了解掌握实验的原理及方法，要求该文法为LR（0）文法。

二、 实验目的
LR(K)分析方法是1965年Knuth提出的，括号中的K表示向右查看输入串符号的个数。对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、及时地指出出错位置。它的主要缺点是对于一个实用语言文法的分析器的构造工作量相当大，K愈大构造愈复杂，实现相当困难。
LR分析法是一种自底向上分析方法。它的分析过程是一种规范归约过程，规范归约是规范推导的逆过程。规范推导是最右推导，规范归约是其逆过程，则是最左归约。 LR分析法的可归约串是当前句型的句柄，即最左直接短语。
对于大多数用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、及时地指出出错位置。
本实验通过设计、调试一个简单的的LR分析器，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。

三、 实验功能
通过定义的文法G，G是一个LR（0）文法，输入源码，能够基本判别出该源码是否是正确的。如果是正确的则接收，反之，如果是错误的则显示错误。

四、 实验步骤
1． 类ALGOLF的文法
<program> -> <Block>
<program> -><Compound Statement>
<Block> -> <Block head> ; <Compound Tail>
<Block head> ->begin
<Block head> -><Block head>;d
<Compound Tail> ->s;end
<Compound Tail> ->s;<Compound Tail>
<Compound Statement> -> begin <Compound Tail>
用小写字母表示终结符，大写字母表示非终结符
b:begin d:d s:s e:end
P:<Program>
B:<Block>
S:<Compound Statement>
H:<Block head>
T:<Compound Tail>
则文法为:
1 P->B 5 H->H;d
2 P->S 6 T->se
3 B->H;T 7 T->s;T
4 H->bd 8 S->bT
2． 拓广后为G’，增加产生式 P’->p
1 P’->P
2 P->B
3 P->S
4 B->H;T
5 H->bd
6 H->H;d
7 T->se
8 T->s;T
9 S->bT

3.项目集规范族：
P’->·P P’->P·
P->·B P->B·
P->·S P->S·
B->·H;T B->H·;T B->H;·T B->H;T·
H->·bd H->b·d H->bd ·
H->·H;d H->H·;d H->H;·d H->H;d·
T->·se T->s·e T->se·
T->·s;T T->s·;T T->s;·T T->s;T·
S->·bT S->b·T S->bT ·
4.LR（0）的分析表
（s表示移进，r表示归约）
状态
ACTION
GOTO
b
d
s
e
;
#
P
B
S
H
T
0
S12

1
2
3
4

1

acc

2
r2
r2
r2
r2
r2
r2

3
r3
r3
r3
r3
r3
r3

4

S5

5

S7
S8

6
r4
r4
r4
r4
r4
r4

7
r6
r6
r6
r6
r6
r6

8

S9
S10

9
r7
r7
r7
r7
r7
r7

10

S8

11
11
r8
r8
r8
r8
r8
r8

12

S14
S8

13
13
r9
r9
r9
r9
r9
r9

14
r5
r5
r5
r5
r5
r5

6.部分代码
n 界面（为了便于客户体验）
int menu()
{
int n;
printf("=======================\n");
printf("-------欢迎使用--------\n");
printf("1.显示文法信息\n");
printf("2.符号串判定\n");
printf("3.退出\n");
printf("-----------------------\n");
printf("=======================\n");
printf("请选择你要执行的内容：\n");
scanf("%d",&n);
getchar();
return n;
}
在main程序中可以直接调用。
void main()
{
int t=1,n;
char ch;
while(t)
{
n=menu();

}

n 分析过程的实现
void ActionTable(int sta, char symb,int col)
{ //statu用于状态栈，sym用于符号栈
if(sta == 1 && col == 5) //sta[1] col[5]中存放ACC，即表
//示所输入的源码是该文法的语法。
{
printf("\t接收\n");
IsAccept = 1; //IsAccept为void函数，如果
//源码判断成功，则显示接收，
//将IsAccept赋值为1，方便退出。
return; //ActionTable是void类型的
}
if(act[sta].st[col] != 0) //存放移进操作
{
//如果进行源码判断时，要进行移进操作，则直接将进行相应的栈操作
printf("\t移进\n");
sta[++sta_Index] = act[sta].st[col];
symbol[++mark_Index] = symb;
exp_top ++;
}else if(act[sta].re[col] != 0) //存放归约操作
{
printf("\t归约\n");
Reduce(sta, symb, col); //Reduce为void函数，用来对进行归
//约的项进行相应操作，使用栈来进行
//处理。
}else
{
printf("\t错误\n");
getchar(); //从stdio流中读字符用
}
}

n 使用到的头文件
#include<stdio.h> //标准输入输出函数 scnaf,printf
#include<string.h> //关于字符数组的函数定义

n 实验结果(截图)

五、 实验总结
通过这次LR(0)分析器的实验，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握了LR语法分析的方法。对于LR（0）方法有了更深刻的了解，不蛋蛋只是纸上谈兵，实验的完成，也就是实践的过程。虽然在这个实践的过程中遇到了许多的困难，但是在老师和同学的帮助下，最终还是将实验初步完成。完成的LR（0）分析器只能对于一个特定的文法进行判断，完整的是要求能够对于任一一中LR（0）文法都能够进行判断，在这方面上还需要对程序有进一步的了解才能够最终实现，通过后续的努力，终能够将LR（0）分析器完整实现。