编译原理课程设计--利用词法自动生成实现词法扫描器.docVIP

目录 0 引言 2 1 设计原则 2 2 需求分析 2 2.1 词法扫描器的功能 2 2.2 符号表 3 2.3 需求描述 3 3 总体设计 3 3.1 正规式 4 3.2由正规式构造NFA 4 3.3将NFA转化为DFA 5 3.4 DFA的最小化 6 3.5 LEX编译系统 7 3.6 LEX源程序 7 4 数据结构 8 4.1 定义正则表达式 8 4.2 构造DFA图 9 4.3 符号表 9 5 详细设计 10 5.1 设计中包含的文件 10 5.2 scaner.l源程序 10 5.3 操作步骤 16 6 软件测试与结果 16 6.1 程序调试 16 6.2 软件测试 16 6.2.1 软件环境 17 6.2.2 功能测试 17 6.3实验结果 17 7 心得体会 20 8 结束语 20 9 参考文献 21 利用词法自动生成实现词法扫描器 0 引言 计算机系统与人信息交换界面多数是应用高级语言来实现。一个高级语言程序的实现,必须依赖于相应的编译系统。所谓编译程序就是指能够把某一种语言程序转换成另一种与之等价的语言程序。它通常包括五个阶段:词法分析,语法分析,语义分析与中间代码的生成，代码优化,目标代码生成。词法分析是完成计算机翻译过程的关键阶段,是整个编译系统的基础。词法扫描器是从基于正规式的描述来构造词法分析器,并且广泛用于描述各种语言的词法分析器。可以用词法扫描器来依次源程序中字符串形式的各个字符，逐个识别出单词，并二元。LEX的工作原理是将源程序中的正规式转换成相应的，而相应的动作则插入到中适当的地方，控制流由该的解释器掌握，不同的源程序，这个解释器是相同的。:运算速度快、准确性高等，从而极大地提高词法分析器的效率。 1设计原则 在编译程序工作的五个阶段中,每个阶段都必须遵从功能等价的原则。词法规则与语法分析阶段依据的语法规则一同构成了一个语言的语法,而语法则是从形的角度衡量一个程序是否合法。所以在词法分析阶段,词法规则成为重要的研究对象。词法分析器所处理的对象即词法分析程序的输入数据,实际上是源程序经过编译预处理,去掉多余的符号后而形成的代码,这样给词法分析带来方便。词法分析的过程是线性的，从头至尾扫描一遍,复杂度较低,易实现。 2需求分析 2.1词法扫描器的功能 词法分析器的输入是源程序,可以看作是特定语言所允许的基本字符流。这些符号在多数高级程序语言中分成了五种单词记号:关键字,标识符,运算符,常量,分界符。词法分析器的基本功能是,按照语言的定义规则,逐个的读入源程序的符号,识别出对语言有意义的符号串,即单词符号，以便编译的后续阶段使用。词法分析程输出结果是组成语言的基本元素即单词,在实际处理的时候,输出并非单词,而是每个单词对应的二元式,形为(单词种别,单自身值)的二元组。单词的种别是语法分析需要的信息,而单词自身值则是编译的语义分析和代码生成等阶段需要的信息。 2.2符号表 符号表记录了程序中所有的单词符号的信息,包括单词符号和种别编码。每当词法分析器识别了一个单词的时候,第一项工作就是查询符号表。对于不同的单词种别,查询的方式和随后的处理完全不同。例如,对于关键字,分界符和运算符等,只需在各自的符号表中查询,获得并记录其属性值,生成相应的单词二元组。而处理常量,特别是处理标识符要复杂得多,仅仅在词法分析阶段是无法获得一个标识符的所有信息的。 2.3 需求描述 设计实现词法扫描器需要完成的任务是： （1）新建文本文档，输入源程序并保存； （2）定义目标语言的可用符号表和构词规则，编写代码，编译源程序，无错误后运行使其对源程序进行词法扫描； （3）删除无用的空白字符，回车字符以及其他非实质性字符。（）依次源程序中字符串形式的各个字符，逐个识别出单词，并二元进行词法检查，Σ上的正则表达式； 输出：能够接受L（r）的NFA N； 方法：首先将构成r的各个元素分解，对于每一个元素，按下述规则1和规则2生成NFA。 注意：如果r中记号a出现了多次，那么对于a的每次出现都需要生成一个单独的NFA。之后依照正规表达式r的文法规则，将生成的NFA按照下述规则3组合在一起。 规则1 对于空记号ε，生成下面的NFA。 规则2 对于Σ的字母表中的元素a，生成下面的NFA。 规则3 令正规表达式s和t的NFA分别为N(s)和N(t)。 a) 对于s|t，按照以下的方式生成NFA N(s|t)。 b) 对于st，按照以下的方式生成NFA N(st)。 c) 对于s*，按照以下的方式生成NFA N(s*)。 d) 对于(s)，使用s本身的NFA N(s)。输入 NFA N 输出 能够接受与N相同语言的DFA D 方法D构造对应的状态迁移表Dtran。DFA的各个状态为NFA的状态集合，对于每一个输入符号，D模拟N中