LR分析过程模拟 编译原理课程设计

《编译原理》实验

《编译原理》是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的

一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组

成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂

涉及到大量的软件设计算法，因此，一直是一门比较难学的课程。为了使学生更好地理解

和掌握编译技术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过上机进

行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析

问题、解决问题的能力，并对提高学生软件设计水平大有益处。

对 C 语言的一个子集设计并实现一个简单的词法分析器，掌握利用状态转换图设计词

法分析器的基本方法。

2．实验要求

利用该词法分析器完成对源程序字符串的词法分析。输出形式是源程序的单词符号二

元式的代码，并保存到文件中。

3．实验内容

(1) 假设该语言中的单词符号及种别编码如下表所示。

单词符号及种别编码

单词符号 种别编码 单词符号 种别编码

main 1 [ 28

；

标识符 ID

10

＞

35

整型常数 NUM

20

＜

36

= 21

＞＝

37

+ 22

＜＝

38

- 23

39

(2) 关键字 main int char if else for while 都是小写并都是保留字。

算符和界符 = + － * / & ＜ ＜＝ ＞ ＞＝ ＝＝　!＝ && || , : ; { } [ ] ( )

作间隔。空格由空白、制表符和换行符组成。

(3) 设计词法分析器的步骤：

(4) 测试该设计词法分析器，可对下面的源程序进行词法分析：输出如下二元式代码序列：

main()

{

}

(1,main) (26,() (27,)) (30,{) (2,int) (10,i) (21,=) (20,10) (34,;)

(7,while) (26,() (10,i) (27,)) (10,i) (21, =) (10,i) (23,-) (20,1) (34,;)

设计并实现计算状态集合 I 的 ε 闭包的算法 ε_Closure(I)和转换函数 Move(I,a)，并

在此基础上实现子集构造算法 Subset_Construction。利用该从 NFA 到 DFA 的转换程序

Subset_Construction，任意输入一个 NFA N=（S,Σ,δ,s0,F），输出一个接收同一语言

的 DFA M=（S’,Σ,δ’,s0’,F’）。

3．实验内容

(a) 若 s∈I，则 s∈ε_Closure(I)；

(b) 若 s∈ε_Closure(I)且 δ(s, ε)=s’而 s’ ∉ε_Closure(I) ，则 s’∈ε_Closure(I)

根据上面的规则，下面给出了一个计算 I 的 ε 闭包的算法 ε_Closure(I)。

SET S;

Nfa_state i;

pop(); /* 把栈顶元素弹出并送入 i */

if(存在 δ(i, ε)=j)

if(j 不在 S 中) {

把 i 加到 S 中;

把 j 压入栈中;

}

}

return S; /* 返回 ε_Closure(input)集合 */

}

态转换表 Trans，表中的每个状态是 NFA N 状态的集合，DFA M 将“并行”地模拟

NFA N 面 对 输 入 符 号 串 所 有 可 能 的 移 动 。 下 面 给 出 了 子 集 构 造 算 法

Subset_Construction 的框架，请完成其设计过程。

有关数据结构：

States[] 是一个 M 的数组，每个状态有两个域，set 域存放 N 的状态集合，

Vg 域为一标识。

Trans[] 是 M 的转移矩阵（输入字母表 Σ 元素个数×最大状态数），Trans[i]

[a]=下一状态。

初始化：

States[0].set=ε_Closure({N 的初态})

States[0].Vg=FALSE

Nstates=1

i=0

Trans 初始化为无状态’-’

while(States[i]的 Vg 为 FALSE){

}

Trans[i][a]= States 中一个 set 域为 S 的下标;

此算法的输出 M 主要由 Trans 矩阵描述，其中省略了每个状态是否为终态的描述，

对下图所示的 NFA N 用子集构造算法 Subset_Construction 确定化。

NFA N 的初态为 12，DFA M 的初态为 ε_Closure({12})。

整个转换过程可用下表来概括。

{12}

{1,5

}

{8}

{0,1,3,4,5,7,13,14,1

8,19}

{8,9}

{1,5

}

{1,5

}

{15}

-

3

-

-

建立文法及其 LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程