logo资料库

编译原理LR(1)自动构造，自动分析输入语句.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.17M 资料格式：doc 举报 版权申诉
第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
资料共22页，剩余部分请下载后查看
    合肥工业大学 计算机与信息学院 实验报告 课 程：编译原理程序设计 专业班级：计算机科学与技术 学 姓 号：20082548 名：张 龙 -- 1 --
    合肥工业大学课程设计任务书 设 计 题 目 LR(1)分析表自动构造程序的实现 成绩 主 要 内 容 指 导 教 师 意 见 设计内容及要求：对任意给定的文法 G 构造 LR(1)项目集规范族 （要求实现 CLOSURE(I)、GO(I,X)、FIRST；然后实现 LR(1)分析表构造 算法。构造并输出其 LR(1)分析表。 附加：由 LR(1)分析表对输入语句测试. 该生能按时完成课程设计任务书所规定的程序设计，综合运用 。 程 序 设 计 方 。程 所 学 知 识 独 立 分 析 和 解 决 问 题 的 能 力 案 序运行结果 。程序验收时回答问题 。 。论文论述 ，文理 ，格式 签名： -- 2 --
    目 录 引言.............................................................4 第一章 概述................................................... 4 1.1 设计内容.................................................. 1.2 设计要求.................................................. 4 5 第二章 设计的基本原理......................................... 5 2.1 CLOSURE(I)的构造......................................... 6 2.2 GO(I,X)的构造............................................ 6 2.3 FIRST 集合的构造.......................................... 6 2.4 LR（1）分析表的构造........................ ............. 6 第三章 程序设计.............................................. 6 3.1 总体方案设计............................................. 7 3.2 各模块设计............................................... 8 3.2.1 读入模块：Read_G().................................. 8 3.2.2 计算 FIRST 模块：get_first() ．．．．．．．．．．．．．．．．．．．．．．． 8 3.2.3 判断项目数否在项目集里：is_in(proj temp,int T)．．．．. 8 3.2.4 获得计算 closure(I)时需要的 First(βa)： gete_expc(proj temp)．．．．．．．．．．．．．．．．．．．．．．......... 8 3.2.5 项目集的 CLOSURE 计算：e_closure(int T) ．．．．．．．．．．．．． 8 3.2.6 检查项目集是否已经在项目集族里：is_contained()．．．．．． 9 3.2.7 GO()函数的实现：go(). ............................... 9 3.2.8 LR(1)分析表的构造：get_action()..................... 9 3.2.9 对输入串的语法分析：在 main()中实现 ................ 9 -- 3 --
    程序测试................................................ 9 第四章 表达式文法的 LR(1)分析器的构造和语法分析............... 9 第五章 结论.................................................... 12 参考文献.......................................................... 12 附录 程序清单................................................ 13 《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。通过课程 设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握 引言 -- 4 --
    所学知识，对提高自己的软件设计水平具有十分重要的意义。 我选择的是老师给的第 31 题，并予以扩充。即对任意给定的文法 G 构造 LR(1)项目集规范 族，其中要实现 CLOSURE(I)、GO(I,X)、FIRST 集合等。在此基础上， 构造了 LR（1）分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程序采用 文件输入输出方式。其中包括两个输入文件：文法 grammar.txt，以及输入串 input.txt；两个 输出文件：项目集 items.txt 和文法的 LR(1)分析表 action_table.txt。由于语法分析的结果只 给出接受或错误报告，比较简单。所以直接在屏幕上输出，也便于用户查看。 在具体编写程序过程中，对文法操作的各个功能模块独立成为一个子程序，而对具体输 入串的分析则放在 main()函数中进行。各个变量及函数的意义和用法我将在叙述程序设计的 总体方案中详细给出。 程序的总体算法思想来自《编译原理》课程。具体实现由我独立完成。程序用 C/C++语言编 写。在 Microsoft Visual C++ 2005 环境下调试通过。 第一章 概述 1.1 设计内容 对任意给定的上下文无关文法 G，构造其 LR（1）项目集族，并且在此基础上进一步构造其 LR（1）分析表。然后分析输入的“句子”。 1.2 设计要求 对输入的文法 G（要求是上下文无关文法）,在程序中实现 CLOSURE(I)、GO(I,X)、FIRST 等的构造，并利用这些功能函数构造出 LR(1)项目集族。并且输出结果。在此基础上构造出 G 的 LR(1)分析表（这个表也输出给用户），并对输入的“句子”进行语法分析，给出分析 结果。 第二章 设计的基本原理 2.1 CLOSURE(I)的构造 CLOSURE(I)表示和 I 中项目可以识别同样活前缀的所有项目的集合。它可以由以下方 法得到： ⑴ I 中的所有项目都属于 CLOSURE(I)； -- 5 --
    ⑵ 若项目[A→α·Bβ,a]属于 CLOSURE(I)，B→ξ是一个产生式，那么，对于 FIRST （βa）中的每一个终结符 b，如果[B→·ξ，b]原来不在 CLOSURE(I)中，则把它加进去； ⑶ 重复执行步骤⑵，直到 CLOSURE(I)不再增大为止。 2.2 GO(I,X)的构造 GO(I,X) = CLOSURE(J) 其中 J={任何形如[A→αX·β,a]的项目|[A→α·Xβ,a]属于 I} 2.3 FIRST 集合的构造 在这个程序中使用的是 FIRST（βa），这基于每一个非终结符的 FIRST 集合（终结符 的 FIRST 就是它本身）。所以需要对每一个非终结符构造其 FIRST 集合。方法如下： 连续使用下面的规则，直到每个集合 FIRST 不再增大为止。 ⑴ 若 X 属于 VT，则 FIRST（X）= {X}。 ⑵ 若 X 属于 VN，且有产生式 X→a…，则把 a 加入到 FIRST（X）中；若 X→ε也是 一条产生式，则把ε也加入到 FIRST（X）中。 ⑶ 若 X→Y…是一个产生式且 Y 属于 VN，则把 FIRST（Y）中的所有非ε元素都加 入到 FIRST（X）中；若 X→Y1Y2…Yk 是一个产生式，Y1，…,Yｉ－１都是非终结符，而 且，对于任何 j,１<= j <= i-1，FIRST(YJ)都含有ε（即 Y1…Yｉ－１=­­­>ε）,则把 FIRST(Yi) 中的所有非ε元素都加入到 FIRST(X)中；特别的，若所有的 FIRST(YJ)都含有ε,j=1,2,3...k, 则把ε加入到 FIRST(X)中。 2.4 LR（1）分析表的构造 在实现 GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后，再扫描所有 的项目集，找到其中包含归约项目的那些项目集，根据其中的项目，得到分析表中那些归约 的部分。 第三章 程序设计 3.1 总体方案设计 在 main()函数中读入文法。并对文法进行扩展，同时记录下文法的所有终结符和非 终结符。对每一个非终结符计算它的 FIRST 集合。以备在计算 CLOSURE(I)时使用。然后， 调用 GO（）函数。完成 LR（1）项目集族的计算。计算的结果记录到 items.txt 中。并且记 -- 6 --
    产生式的条数 每条产生式的长度 length[20]; number = 0; 存放输入的文法；为简单起见，设文法的产生式条数不 多于 录下状态之间的转换关系。接下来，调用 get_action()根据上面的项目集族和记录的状态转 换数组获得 LR（1）分析表。然后就可以对输入的句子进行语法检查。程序中主要变量以及 函数的说明如下： ·char G[20][20]; 20 条，每个产生式不多与 20 个字符，用@表示ε，且产生式输入的时候要以$结束 ·int ·int ·bool tempofinput[150]; 记录哪些 ASCII 字符在文法中，以求得所有的 VN 和 VT ·char str_vn[20]; ·int size_vn = 0; ·char str_vt[150]; ·int size_vt = 0; ·bool first_vn[30][150]; 记录每个非终结符的 first 集合 ·char buffer[50]; 输入串 ·int ·struct thri{ int beg; int nex; char ch; 用来存放 CLOSURE(I)时需要的 first_set 也用来读入用户的 记录所有的非终结符 记录非终结符的个数 buffer 的有效长度 记录所有的终结符 记录终结符的个数 bsize = 0; }; ·thri trans[200]; ·int ·struct proj{ size_trans = 0; int formula_numb; int part; char expc; }; 定义状态转换数组中的元素格式 用来在 GO（）函数中记录状态间的转换 trans 数组的大小 定义项目集的格式 items[100][100]; 项目集数组，假设项目集的个数不超过 100 个，且每个项目集中的 Ccount = 0; size_item[100]; 每个项目集中项目的个数 项目集的个数 ·proj 项目个数不超过 100 个 ·int ·int ·struct action{ ch; nxt_sta; char int }; 定义状态转换表的格式 状态转换表的大小 状态转换表 输入文法的文件指针 action_table[100][100]; size_act_table[100]; ·action ·int ·ifstream G_ifile; ·ifstream input_ifile; 输入句子的文件指针 ·ofstream items_ofile; ·ofstream act_ofile; ·void Read_G() ·void get_first() 输出转换表的文件指针 输出项目集族的文件指针 读入文法的子程序模块 计算每一个非终结符的 first 集合 -- 7 --
    计算 items[T]的 closure 闭包 ·bool is_in(proj temp,int T) 判断项目 temp 是否已经在项目集族 items[T]中 ·void gete_expc(proj temp) 计算在生成 CLOSURE(I)时用到的 FIRST（βa） ·void e_closure(int T) ·int is_contained() ·void go() ·void get_action() ·int main() 3.2 各模块设计 判断新生成的项目集是否已经在项目集族中 实现 GO（I，X）的功能 生成 LR(1)表 调用各个字模块，并在其中对输入串进行语法分析 3.2.1 读入模块：Read_G() 文法要为上下文无关文法。输入文件的格式为：首先输入产生式的条数；每条产生 式的第一个字符为非终结符。以$结尾。输入的同时用 tempofinput[temp] = true 来记录字符 temp。为统计有哪些非终结符和终结符作准备。这些都通过 ASCLL 码对应位是否为 true 来 判断。 3.2.2 计算 FIRST 模块：get_first() 先设置 flag1 表示本轮扫描 first_vn 中有没有新增加的内容。要是有，还要进行下一 次扫描。每一轮扫描所有的产生式，在扫描每一个产生式的时候，设置一个下标指针 t 用来 保证不会扫过本产生式，还设置 flag2 表示 t 的位置是否是一个可以推导出ε的非终结符。 是的话，还要进行下一个 t 位置的检查。如果 t 走到产生式的最后位置的下一个位置，则表 明ε属于此产生式左边非终结符的 FIRST 集合； 3.2.3 判断项目数否在项目集里：is_in(proj temp,int T) Scan 项目集原有的每一个项目，和新生成的项目作比较。若有相同的就返回 true,否则 返回 false 3.2.4 获得计算 closure(I)时需要的 First(βa)：gete_expc(proj temp) 设置 flag 表示是否还要进行下一轮计算（即此次处理的为非终结符且它的 FIRST 中有 ε），若处理的位置已经超过了产生式的长度，则直接把项目中的那个搜索字符添加进去。 这个模块的返回结果放在 buffer 数组中。 3.2.5 项目集的 CLOSURE 计算：e_closure(int T) 在 Go()函数中会生成 items[T]的一些基本项目。对 items[T]中已经有的每一个项目检 查在”·”之后的是否为非终结符；若是，则计算 FIRST（βa），把每一个 buffer 中的元素和 相应的产生式构成一个项目，加入到项目集中。（注意，此时的项目集的大小是随着项目的 不断加入而变大的，所以可以用 for 循环保证项目集中不会有遗漏。） 3.2.6 检查项目集是否已经在项目集族里：is_contained() -- 8 --
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料