♻️ 资源大小507KB➡️资源下载https://download.csdn.net/download/s1t16/87430287词法分析器语法分析器《编译原理》是计算机专业的一门重要的专业课程其中包含大量软件设计细想。通过课程设计实现一些重要的算法或设计一个完整的编译程序模型能够进一步加深理解和掌握所学知识对提高自己的软件设计水平具有十分重要的意义。整个设计过程持续两个周的时间包括前期的搜集资料整理思路到前面一个周的编写程序调试代码优化代码。这样的设计过程很是锻炼我们的编程能力和对词法分析、语法分析的理解。概述编写目的巩固编译原理课程中学到的知识学习程序设计语言编译程序的一般原理、基本设计方法、主要实现技术加深对词法分析、语法分析的理解和认识通过编程给出具体的实现进而掌握词法分析和语法分析的基本思想。实现要求词法分析创建一个词法分析程序它支持对正规文法的分析。必须使用 DFA确定性有限自动机或 NFA非确定性有限自动机来实现这一项目。该程序的输入是一个文本文件包括一组由该正规文法产生的产生式以及待识别源代码字符串。该程序的输出是一个符号表二元式它由 5 种类型符号关键词识别符常量界符和操作符。语法分析创建一个语法分析程序它采用 LL1方法或 LR1方法。该程序的输入是一个文本文档包括一组 2 型文法上下文无关文法的产生式和任务 1 程序输出的符号表。任务 2 的输出是一个 YES 或 NO即源代码字符串是否符合本 2 型文法。开发环境操作系统windows 7编程语言C基本原理分析过程词法分析器分析过程从词法分析_文法.txt 中读入预先写好的文法并将其转换为 NFA存储 NFA 的数据结构为二维结构体结构体定义如下struct NFA_set { char set[100]; int len0; };用子集法将 NFA 转化为 DFA。转化过程与课本中子集法的转化过程是一致的。程序中int Is_in(NFA_set temp)函数用于判断新产生的一个子集是否是已经存在的防止重复。不重复则返回-1重复则返回重复的编号。void get_closure(NFA_set temp)函数用于计算 ε-closure。bool Is_contained_Y(NFA_set temp)函数用于判断该状态是否是终态。转化过程是具体实现是做一个 NFA_set 类型的栈新状态不停的进栈每次从堆栈中弹出一个计算其转换的结果是新状态就进栈重复则丢弃只记录好 dfa 的转换直到栈空。最后成功构造出 DFA。对输入源程序的扫描过程很简单一次读入一个字符成串的送入匹配和 DFA 判断其合法性。给出输出结果。最终的词法分析结果要送入语法分析因此我将标识符统一映射为 2常量映射为 3关键字用一个字符表示输入到文本文件中去方便语法分析。语法分析器分析过程从预先写好的文本文件中读入 2 型文法保存在一个 char 类型的二维数组中每个文法的长度由 length 数组记录。计算 first 集。具体实现过程为不停的扫描每个文法其首个字符是终结符则加入到对应的非终结符的 first 集中如果首个字符是非终结符则扫描该非终结符的 first 集把他们全部加入到当前非终结符的 first 集中为空则扫描下一个字符。直到某一次没有发生任何改动说明 first 集计算完成。求 LR(1)项目集族。该计算过程和书上的求法一致从 S‘-S 开始构造第一个项目集通过求闭包构造转换函数期间注意项目集内部元素的重复和项目集之间的重复保证不重复可以求出所有的项目集。构造 LR(1)分析表。有了前面项目集族的构造分析表很容易就能构建出来。这里我用一个二维结构体表示转换表。struct action { char ch; int next_state; };ACTION 和 GOTO 表是合在一起的ch 是转换的元素包括终结符和非终结符转换到的状态用 int 类型表示移近项目和 GOTO 表用正数表示为了避免歧义规约项目我用负数表示这样既可以节省空间又方便查询。分析过程。分析过程与书上类似用一个状态栈一个符号栈但是在分析的过程中遇到 GOTO 语句时要再次扫描 ACTION 表查询转换到的状态。在这里我将分析结果一步步详细地输出到了文本文件中栈的输出有点麻烦我用另一个同类型的栈和符号栈或状态栈做一个对换在对换的过程中实现输出这里我感觉有点麻烦如果抛去输出过程程序还是很快捷的。主要函数词法分析void createNFA()从文本文件中创建文法带程序中。void showNFA()显示 NFAint Is_in(NFA_set temp)和已有的 newset 有没有重复的有就返回重复的编号void get_closure(NFA_set temp)得到一个完整的子集bool Is_contained_Y(NFA_set temp)判断是否是终态void NFA_to_DFA() NFA 转换为 DFA 的关键函数bool DFA(char str[])返回 str 串是否可以由 DFA 表示出来void scan()扫描源程序给出词法分析的结果。语法分析void get_grammar() 读文法void get_first() 计算 first 集void write_first_set() 把 first 集写进文本文件中void gete_search(project temp) 得到向前搜索符bool is_in(project temp,int T) 当前项目集元素是否重复void e_closure(int T) 求项目集族int is_contained() 当前项目集和以前比较不相同返回-1相同则返回相同的编号void make_set() 构建项目集void get_action() 构建分析表void judge() 判断句子是不是该文法的语言程序设计示例定义词法分析的正规文法可以由 NFA 转化成 DFA该文法定义了由 123abc 组成的标识符以及 123 组成的常量还有复数的表示形式和科学技术法的表示形式还可以科学计数法和复数结合使用。要分析的源程序如图。识别程序的一部分输出结果。对应的用于语法分析的输入。语法分析对应的文法包含了头文件、while 语句、定义函数语句赋值语句定义变量语句等可以嵌套配合使用。求得的 first 集如图“”不算项目集较多只列几个作为演示。分析表如图。包含 ACTION 表和 GOTO 表合在一起。分析过程如图因为分析的串很长因此一页也没有放下但是可以看出规约过程是非常正确的最后匹配成功得到结果。程序输出 YES 表示分析成功。报错功能如图所示去掉一个右括号并保存运行程序在查找分析表的时候可以发现找不到匹配的右括号这时便可以很简单的实现程序报错功能。如图报错提示缺少右括号。感悟心得持续两个周的编译原理课程设计让我学到了很多东西。首先是加深了对编译原理课程的理解对词法分析、语法分析了有了更进一步的掌握其次是编程能力的提高这样的代码量一年也只有几次能够遇到。有了前面课程设计的经验这一次的编译原理课程设计我更注重数据结构数据结构的好坏直接决定了代码的复杂度代码的量有一些可以用链表做的东西我尽量避免用链表换用一个数组和一个表示长度的整型变量的数据结构来表示因为链表虽然方便灵活但是其很难调试遇到错误常常会使程序直接崩溃。虽然没有做语义分析但是通过这一段时间写词法分析器和语法分析器我对一个编译器的组成有了更深层次的认识。通过本次的课程设计我对自动机有了更深入的了解也希望这些理论会再我们日后的学习中发挥更大的作用。参考资料《编译原理》 吕映芝 张素琴 蒋维杜 编著 清华大学出版社
