没有合适的资源？快使用搜索试试~ 我知道了~

文库首页行业互联网实验三 LR(K)语法分析实验指导书.doc

实验三 LR(K)语法分析实验指导书.doc

LR(K)语法分析

编译原理

数据结构

项目集规范族

分析表/栈

5星 · 超过95%的资源需积分: 12 3 下载量 73 浏览量 2021-06-06 16:08:56 上传评论 1 收藏 197KB DOC 举报

温馨提示

试读

19页

实验配套指导书，便于更直观的去理解、学习编译原理的核心思想。

资源详情

资源评论

资源推荐

实验三 LR（K）语法分析

一、实验目的

1、掌握 SLR(1)分析法进行语法分析的原理

2、掌握语法分析器的设计与调试

二、实验原理与要求

1、原理：

LR 分析法是一种自底向上的语法分析。SLR(1)分析表内包含几种操作：①移进；②归

约；③接受。通过构造项目集规范族的状态转换表（即 LR 分析表）实现不同状态的跳转

或归约，最后归约为文法的开始符号，从而接受。

2、要求：

（1）定义语言子集的文法

（2）构造识别文法活前缀的项目集规范族

（3）构造 SLR(1)分析表

（4）根据 SLR(1)分析表对输入串进行 LR 分析

（5）测试要满足对文法的每个候选项的覆盖。

三、实验设备

配置有 VC 开发环境的计算机设备。

四、实验内容

采用 SLR(1)分析法对表达式文法进行语法分析。表达式文法如下所示：

G[E]：E→E+T | T T→(E) | i

五、实验步骤

说明：本实验共 4 学时，下面第 1—4 步为 2 学时，构造出文法的项目集规范族和 SLR(1)分

析表，第 5-6 步为 2 学时，在实验一词法分析基础上完成对输入串的 SLR(1)分析过程。

1、将文法 G[E]拓广为 G’[E’]

E’ →E

E →E+T

E →T

T →(E)

T →i

文法 G’可存放在一个文件 G1.txt 中

2、构造文法 G’的 LR(0)项目集规范族

【数据结构设计】

如何存储表示项目、项目集、项目集规范族？

typedef struct //表示一个项目

{ char str[81];

int R; //项目对应的产生式的编号

}Aitem;

typedef struct //表示项目集

{ Aitem item[100]; // item[ ]存放一个项目集中若干个项目

: E’→ ． E

E→ ． E+T

E→ ． T

T→ ． (E)

T→ ． i

: E’→E ．

E→E ． +T

: E→T ．

T→( ． E)

E→ ． E+T

E→ ． T

T→ ． (E)

T→ ． i

: T→i ．

: E→E+ ．

T→ ． (E)

T→ ． i

: T→

(E ． )

E→E ． +T

T→(E) ．

E→E+T ．

(

)

int number; //该项目集中项目的个数

}Item;

typedef struct //表示项目集规范族

{ Item I[100]; //I[0],I[1],I[2]…表示各个项目集 I0,I1,I2,…

int number; //项目集的个数

}C;

C c; //项目集规范族

Item wenfa; //文法，将文法 G’存放到一个项目集中

wenfa.item[0].str

G->．E#

wenfa.item[1].str

E->．E+T

wenfa.item[2].str

E->．T

wenfa.item[3].str

T->．(E)

wenfa.item[4].str

T->．i

int Save[100][100]; //LR 分析表

char ch[100]; //存放 ACTION 子表第 1 行中的终结符和‘#’以及 GOTO 子表第 1 行中的非终结

符。且 ch[j]中下标 j 与 Save[i][j]中的列下标 j 对应，也就是说，若 ch[j]存放的是'a'，则

Save[i][j]的第 j 列为'a'列；且 Save[i][j]中的行下标 i 对应分析表第 1 列中的状态。

【算法设计】

void Load_Wenfa()//从文件 G1.txt 中获得表达式文法，存入全局变量 wenfa 中

{ FILE *fp;int i,j;

char temp[81];

if((fp=fopen("G1.txt","r"))==NULL)

{ printf("cannot open G1.txt\n"); getchar( ); exit(0);

}

fgets(ch,81,fp);//从文件中获得 ACTION 子表第 1 行中的终结符和'#'以及 GOTO 子表第 1

行中的非终结符存入 ch 中，串尾的'\n'也存入了 ch 中。

for(i=0;(ch[i])!='\n';i++); ch[i]='\0'; //删除串尾的'\n'

i=0;

while((fgets(temp,81,fp))!=NULL)

{

strcpy(wenfa.item[i].str,temp);

for(j=0;(wenfa.item[i].str[j])!='\n';j++); wenfa.item[i].str[j]='\0'; //删除串尾的'\n'

wenfa.item[i].R=100+i; //存放产生式的编号，编号统一加 100，如第 1 个产生式的

编号为 101

i++;

}

wenfa.number=i;

fclose(fp);

}

LR(0)项目集规范族的构造算法

定义三个函数：

CLOSURE(I)：项目集 I 的闭包函数

GO(I, X)：状态转换函数

ItemSets(G’)：计算文法 G’的 LR(0)项目集规范族

Item CLOSURE(Item i)//项目集 i 的闭包函数

{ Item J=i; Aitem K; int j,m,k,t,flag;

for(j=0;j<J.number;j++)

{

for(m=0;(J.item[j].str[m])!=‘\0’;m++)//找待约项目

if(J.item[j].str[m]=='.')

break;

m++;

if(J.item[j].str[m]>='A'&&J.item[j].str[m]<='Z')//存在待约项目

for(k=0;k<wenfa.number;k++)//将待约项目中圆点后面的非终结符与文法表 wenfa 中存放的

产生式左部进行比较，以便将该非终结符的初始项目加入项目集 i 中。

{

if(J.item[j].str[m]==wenfa.item[k].str[0])

{

K=wenfa.item[k];//在文法表中找到该非终结符对应的初始项目，赋给 K

//接下来判断项目集 i 中是否已存在这个初始项目 K，若已存在，无需加入；若不

存在，则加入。

…………

}

return J;

}

Item Go(Item K,char x)//状态转换函数，即：由项目集 K 和面临的符号 x 产生下一个项目

集 J。

{ Item J; J.number=0; //J 存放产生的新项目集

char t; int j,m;

for(j=0;j<K.number;j++)//在项目集 K 中找形如 A→α.xβ 的项目，将这些项目（圆点从 x

的左边移到右边）加入 J 中

{ for(m=0;(K.item[j].str[m])!='\0';m++)

if(K.item[j].str[m]=='.')break;

m++;

if(K.item[j].str[m]==x)

{ //接下来将这个项目 K.item[j]加入 J 中，且圆点从 x 的左边移到右边。

…………

}

return CLOSURE(J);

}

void items()//构造项目集规范族和 SLR(1)分析表

{ Item T,S;char CH[100];int flag,i,j,k,t,l,d;

T.item[0]=wenfa.item[0];//将文法中 E'对应的初始项目 E'→.E 加入项目集 T 中

剩余18页未读，继续阅读

郑华滨

2023-06-20

本指导书采用问题解答的方式，让阅读者更好地理解和掌握知识。

内容反馈

RichardLau_Cx

粉丝: 63
资源: 8

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

实验三 LR(K)语法分析实验指导书.doc

评论10

最新资源

实验三 LR(K)语法分析 实验指导书.doc

评论10

编译技术实验3--LR语法分析

lR语法分析器设计.pdf

LR 语法分析及中间代码生成.exe

北京邮电大学编译原理实验LR1语法分析器.zip

语法分析器实验指导书

编译原理实验LR语法分析

编译原理实验LR语法分析器

北邮编译原理实验LR语法分析 实验报告.pdf

MiniPascal的LR语法分析程序设计文档.doc

实验五 LR分析器设计

编译原理实验报告LR(1)分析法.doc

编译原理课程设计报告\LR1语法分析器自动识别.rar

编译原理-LR0语法分析-java

java编写的LR语法分析器（编译原理实验）

编译原理实验指导书-语法分析1

编译原理实验 语法分析LL(1)、SLR(1)、LR(1)、词法分析、语法制导翻译

[编译原理实验]LR0语法分析C语言版.zip

LR1语法分析生成器

LR0语法分析器.zip

用c++实现LR语法分析器

LR(0)语法分析的设计与实现.doc

编译原理实验之词法分析器、LL(1)语法分析器、LR(1)语法分析器.zip

编译原理实验（c++实现LR(1)语法分析器）

实验二 递归下降语法分析 实验指导书.doc

实验四 LR（0）分析方法的设计与实现.doc

编译原理实验5语法分析（二）.doc

LR实现语法分析

最新资源

实验三 LR(K)语法分析实验指导书.doc

北邮编译原理实验LR语法分析实验报告.pdf

编译原理实验语法分析LL(1)、SLR(1)、LR(1)、词法分析、语法制导翻译

实验二递归下降语法分析实验指导书.doc