logo资料库

LR(1)文法分析及其预测分析表的构造.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：1.63M 资料格式：doc 举报 版权申诉
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
资料共19页，剩余部分请下载后查看
    目 录
    前 言
    用C语言编写源程序建立LR(1)分析器
    一，设计目的，要求，算法与设计思想
    1.设计内容
    2.设计要求
    3.设计的基本原理
    1.CLOSURE(I)的构造
    2.GO(I,X)的构造
    3.FIRST集合的构造
    4.LR(1)分析表的构造
    二，LR（1）分析器
    1.LR(1)分析器的实现图：
    2.LR分析器与逻辑结构及工作过程
    三，总体方案设计
    1.各模块设计
    四，程序测试
    1.教科书的第142页文法的LR1分析器的构造和语法分析
    2.表达式文法的LR1分析器的构造和语法分析器
    五，源程序
    六，总结
    七，参考文献
    目 录 前 言 .................................................................................................................................................. 2 用 C 语言编写源程序建立 LR(1)分析器.........................................................................................3 一，设计目的，要求，算法与设计思想........................................................................................3 1.设计内容 ................................................................................................................................ 3 2.设计要求 ................................................................................................................................ 3 3.设计的基本原理 .................................................................................................................... 3 1.CLOSURE(I)的构造........................................................................................................3 2.GO(I,X)的构造.............................................................................................................. 3 3.FIRST 集合的构造......................................................................................................... 4 4.LR(1)分析表的构造 ......................................................................................................4 二，LR（1）分析器 .......................................................................................................................... 4 1.LR(1)分析器的实现图： ......................................................................................................4 2.LR 分析器与逻辑结构及工作过程.......................................................................................5 三，总体方案设计 ............................................................................................................................ 5 1. 各模块设计........................................................................................................................... 6 四，程序测试 .................................................................................................................................... 8 1.教科书的第 142 页文法的 LR1 分析器的构造和语法分析............................................... 8 2.表达式文法的 LR1 分析器的构造和语法分析器 ................................................................9 五，源程序...................................................................................................................................... 10 六，总结 .......................................................................................................................................... 19 七，参考文献 .................................................................................................................................. 19
    编译原理学年论文 前 言 《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计 细想。通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型， 能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要 的意义。 我选的是老师给的题，并予以扩充。即对任意给定的问法 G 构造 LR(1)项目 集规范族，其中要实现 CLOSURE(1)，GO(I,X)，FIRST 集合符。在此基础上，构 造了 LR(1)分析表。然后对输入的句子进行语法分析，给出接受或出错报告。程 序采用文件输入输出方式。其中包括两个输入文件：文法 grammar.txt，以及输 入 串 input.txt ； 两 个 输 出 文 件 : 项 目 集 items.txt 和 文 法 的 LR(1) 分 析 表 action_table.txt。由于语法分析的结果只给出接受或错误报告，比较简单。所 以直接在屏幕上输出，也便于用户查看。 在具体编写程序中，对文法操作的各个功能模块独立成为一个子程序，而对 具体输入穿得分析则放在 main()函数中进行。各个变量奇函数的意义和用法我 将在论述程序设计的通体方案中向西给出。 程序的通体算法细想来自《编译原理》课程。具体实现有我独立完成。程序 用 C/C++语言编写。在 Microsoft Visual C++2005 环境下调使通过。 2
    编译原理学年论文 用 C 语言编写源程序建立 LR(1)分析器 一，设计目的，要求，算法与设计思想 1.设计内容 对任意给定的上下文无关文法 G，构造其 LR(1)项目集族，并且在此基础上 进一步构造其 LR(1)分析表。然后分析输入的句子。 2.设计要求 对 输 入 的 文 法 G （ 要 求 是 上 下 文 无 关 文 法 ）， 在 程 序 终 实 现 CLOSURE(1),GO(I,X)，FRIST 等的构造，并利用这些功能函数构造出 LR(1)项目 集族。并且输出结果。在此基础上构造 G 的 LR(1)分析表（这个表也输出给用户）， 并对输入的句子进行语法分析表，给出分析结果。 3.设计的基本原理 1.CLOSURE(I)的构造 CLOSURE(I)表示和 I 中项目可以识别同样活前缀的所有项目的集合。它可以 有以下方法得到： (1)I 中的所有项目都属于 CLOSURE(I)； (2)若项目[A→a.Bβ,a]属于 CLOSURE(I)，B→ξ是一个产生式，那么，对于 FIRST<βa>中的每一个中介符 b,如果[β→.ξ,b]原来不在 CLOSURE(I)中，则把它 加进去； (3)重复执行步骤（2），直到 CLOSURE(I)不再增大为止。 2.GO(I,X)的构造 GO(I,X)=CLOSURE(J) 其中 J={任何形如[A→aX.Β,a]的项目[A→a.X.Β,a]属于 I} 3
    编译原理学年论文 3.FIRST 集合的构造 在这个程序中使用的是 FIRST(βa)，这基于每一个非终结符的 FRIST 集合（终 结符的 FIRST 就是它本身）。所以需要对每一个非终结符构造其 FIRST 集合。 方法如下： 连续使用下面的规则，直到每个集合 FIRST 不再增大为止。 （1）若 X 属于 VT，则 FIRST(X)={X}。 （2）若 X 属于 VN，且有产生式 X→a…，则把 A 加入到 FIRST(X)中；若 X→ξ也是一条产生式，则把ξ也加入到 FIRST 中。 4.LR(1)分析表的构造 在实现 GO(I,X)时，记录下状态的转化。得到分析表中的移进部分。然后再 扫描所有的项目集，找到其中包含归约项目的哪些项目集，根据其中项目，得到 分析表中那些鬼月的部分。 二，LR（1）分析器 1.LR(1)分析器的实现图： 图1 LR（1）分析器的实现 4
    编译原理学年论文 2.LR 分析器与逻辑结构及工作过程 图2 LR分析器的逻辑结构 三，总体方案设计 在 main()函数中读入文件，并堆文法进行扩展，同时记录下文法的所有终 结符和非终结符，对每个非终结符计算它的 FIRST 集合。以备在计算 CLOSURE(1) 时使用。然后调用 GO()函数。完成 LR(1)项目集组的计算。计算的结果记录到 ITEMS.TXT 中。并且记录下状态之间转换关系。接下来，调用 GET_ACTION()根据 上面的项目集族和记录的状态转换数组获得 LR(1)分析表。然后就可以对输入的 句子进行语法检查。程序中主要变量以及函数的说明如下： // 存放输入的文法：为简单起见，设问发的产生式条 数不多于 20 条，每个产生式不多与 20 个字符，用@ 表示，且产生式输入的时候要以 S 结束。 // 每条产生式的长度 // 产生式的条数 //记录哪些 ASCII 字符在文法中，以求得所有的 VT 和 VN //记录所有的非终结符 //记录非终结符的个数 //记录所有的终结符 //记录终结符的个数 //记录每个非终结符的 FIRST 集 char str_vn[20][20]; int length [20]; int number=0; bool tempofinput char str_vn[20]; int size_vn=0; char str_vt[150]; int size_vt=0; bool first_vn[30][150]; char buffer[50]; //用来存放 CLOSURE(I)时需要的 FIRST_SET 也用来读入用户的输入电 // buffer 的有效长度 int bsize=0 struct thri{ int beg; 5
    编译原理学年论文 int nex; char ch; }; thri trans[200]; int size-trans=0; struct proj{ int part; char expc; }; proj irems[100][100]; CCOUNT=0; size_item[100]; int int struct action{ char ch; int nxt_sta; }; action //定义状态转换组中的元素格式 //用来在 go()函数中记录状态间的转换 trans 数组 的大小 //定义项目集的格式 //项目集数组，假设项目集的个数不超过 100 个， 且每个项目集中的项目个数不超过 100 个 //项目集的个数 //每个项目集中的项目个数 //定义状态转换表的格式 action_table[100][100]; int size_act_table[100]; ifstream G_ifile; ofstream input_ifile; ofstream items_ofile; void read_G() void get_first() //定义状态转换表的格式 //状态转换表 // 输入文法的文件指针 // 输入句子的文件指针 // 输出项目集族的文件指针 // 输出转换表的文件指针 // 计算每个非终结符的 FIRST 集合 // 判断项目 temp 是否已经在项目集族 bool is_in(proj temp,int,T) void e_closure(intT) int is_containd() void go() void get_action() int main() items[T]中 // 计算 item[T]closure(1)时用到的 frst(βa) // 计算 items[T]的 closure 闭包 //判断新生成的项目集是否已经 de 在项目集 族中 //实现 go(1)的功能 //生成 LR(1)表 // 调用个个子模块，并在其中堆输入串进行语法分析 1.各模块设计 1.读入模块：Read_G() 文法要为上下无关文法。输入文件的格式为：首先输入产生式的条数：每条 产 生 式 的 第 一 个 字 符 为 非 终 结 符 。 以 S 结 尾 。 输 入 的 同 时 用 tempofinput[temp]=true 来记录符 temp。为统计有哪些非终结符和终结符作准 备。这些都通过 ASCLL 码对应位是否为 true 来判断。 6
    编译原理学年论文 2.计算 FIRST 模块：get_first() 现设计 FLAG1 表示本轮扫描 first_vn 中有没有新增加的内容。要是有，还 有进行下一次扫描。每一轮扫描所有的产生式，在扫描每一个产生式的时候，设 置一个下标指针 t 用来保证不会扫过本产生式，还设置 flag 表示 t 的位置是否 式一个可以推导出ξ的非终结符。是的话，还有进行下一个 t 位置的检查。如果 t 走到产生式的最后位置的下一个位置，则表明ξ属于此产生式左边非终结符的 first 集合。 3.判断项目数是否在项目集里：is_in(proj temp,int T) Scan 项目集原有的每一个项目，和新生成的项目作比较。若有相同的就返回 true，否则返回 false。 4.获得计算 closure(I)时需要的 First(βa):gete_expc(proj temp) 设计 Flag 表示是否还要进行下一轮计算，若处理的位置已经查过了产生式 的长度，则直接把项目中的那个搜索字符添加进去。这个模块的返回结果放在 BUFFER 数据中。 5.项目集的 CCLUSER 计算：e_closure(int T) 在 GO()函数中会产生 items[T]的一些基本项目。对 items[T]中已经有的每 一个项目检查在“。”之后的是否为非终结符；若是，则计算 FIRST(a)，把每一 个 BUFFER 中的元素和相应的产生式构成一个项目，加入到项目集中。（注意，此 时的项目记得大小时随着项目的不断加入而变大的，所以可以用 FOR 循环保证项 目集中不会有错误。 6.检查项目集是否已经在项目族里：is_contation() 把已经有的项目集和新生成的项目集进行比较，要是有相等的话则表示已经 存在相同的项目集合，此时返回相同的那个项目集的编号，否则，返回 0.四， 程序测试。 7.GO()函数地实现： 第一步制作一个初始项目（即扩展文法的第一条产生式），然后用 e_closure 构造项目集 0.在程序中 Ccount 制作项目集的计数从 0 开始到（包括 n)，所以在 for 循环中是。即扫描每一个项目集，对每一个项目在“.”之后的终结符，向 后移动一位“.”的位置生成新的项目，暂存在 buf 数组中。然后预生成项目集， 并且求其 closure，再判断新的项目集是否已经存在，若存在了，就删除这个项 目集，并设置相应的 trans。否则就生成的项目集，也设置相应的 trans。在以 上过程中，每次确定生成一个项目集的时候都把它输出到 items.txt 中。 8.LR(1)分析表的构造 get_action() Scan 每一个项目集，若其中有规约项目，则转换表增加一个归约（用负值 表示）。然后，根据 trans 数组中的元素，构造转换表的移进项（用正值表示）。 接受项目也是一个归约项，用 0 表示。生成的转换表输出到 action_table.txt 中。 7
    编译原理学年论文 9.堆输入串的语法分析：在 main()中实现 用 stack 模拟语法分析的过程，先在 stack 中放入（0，#），然后，用当前 栈项状态和当前输入字符查找 action_table。根据 action_table 中的值的情况 做相应处理（即执行移进和归约动作）。若遇到接受项目则给出接受提示，程序 结束。若遇到出错的情况给出出错提示，页结束程序。 四，程序测试 本程序在 Dev_C++和 Microsoft Visual C++2005 中调试通过。下面给出两个 调试实例： 1.教科书的第 142 页文法的 LR1 分析器的构造和语法分析 输入文法： 3 EBBS BaBS BbS  生成的项目集族：  生成的转换表：  输入句子测试： 图 3 输入句子运行结果 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料