(重庆理工大学计算机学院)编译原理课程设计报告.doc

编译原理课程设计报告 实验名称 编译原理课程设计 班 级 学 号 姓 名 指导教师 实验成绩 2013 年06月 实验目的 通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。 通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR(0)分析表的步骤，对文法的要求，能够从文法G出发生成LR(0)分析表，并对给定的符号串进行分析。 实验内容 正规式——NFA——DFA——MFA 1.正规式转化为不确定的有穷自动机 （1）目的与要求 通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompson算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。 （2）问题描述 任意给定一个正规式r（包括连接、或、闭包运算），根据Thompson算法设计一个程序，生成与该正规式等价的NFA N。 （3）算法描述 对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 步骤1：首先构造基本符号的有穷自动机。 步骤2：其次构造连接、或和闭包运算的有穷自动机。 （4）基本要求 算法实现的基本要求是： (1) 输入一个正规式r； (2) 输出与正规式r等价的NFA。 （5）测试数据 输入正规式：(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N （6）输出结果 2.不确定的有穷自动机的确定化 （1）目的与要求 通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。 （2）问题描述 任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。 （3）算法描述 用子集法将NFA转换成接受同样语言的DFA。 步骤一：对状态图进行改造 (1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变 步骤2：对NFA 进行确定化，构造状态转换表。 (1) 子集构造法： 初始时，ε_closure(s0)是Dstates中唯一的状态且未被标记； while Dstates中存在一个未标记的状态T do begin 标记T； for 每个输入符号a do begin U:= ε_closure(move(T,a)); ifU没在Dstates中then 将U作为一个未标记的状态添加到Dstates中； end; end; (2) ε_closure的计算，计算ε_closure(T)的简单算法是用栈来保存其弧还没有完成ε转换检查的状态。 将T中所有的状态压入栈stack中： 将ε_closure(T)初始化为T； while栈stack不空 do begin 将栈顶元素t弹出栈； for每个这样的状态u：从t到u有一条标记为ε的边do if u不在ε_closure(T)中do begin 将u添加到ε_closure(T); 将u压入栈stack中; end; end; （4）基本要求 算法实现的基本要求是： (1) 输入一个NFA N； (2) 输出与之等价的DFA。 （5）测试数据 给定不确定的有穷自动机： 得到与之等价的确定的有穷自动机： （6）输出效果 输出状态转换表表示的确定的有穷自动机如下： 3.确定的有穷自动机的化简 （1）目的与要求 通过设计、编写和调试将确定的有穷自动机的状态数变为最少的程序，使学生掌握化简有穷自动机的过程中的相关概念和方法。DFA的表现形式可以是表格或图形。 （2）问题描述 每一个正规集都可以由一个状态数最少的DFA所识别，这个DFA是唯一的（因状态名不同的同构情况除外）。任意给定一个确定的有穷自动机，根据算法设计一个程序，将该DFA化简为与之等价的最简DFA。 （3）算法描述 1．构造具有两个组的状态集合的初始划分Π：接受状态组F，非接受状态组S-F。 2．对Π采用下面所述的过程来构造新的划分Πnew。 for Π中每个组G do begin 当且仅当对任意输入符号a，状态s和t读入a后转换到Π的同一组中； /*最坏情况下，一个状态就可能成为一个组*/ 用所