实验一词法分析程序开发.doc

实验一词法分析程序开发
【实验目的】
•  深入理解有限自动机及其应用
•掌握根据语言的词法规则构造识别其单词的有限自动机的方法
•  深入理解词法分析程序自动生成原理
•  掌握词法分析程序的开发。
【实验学时】
4学时
【实验要求】
•掌握词法分析程序自动生成工具LEX的使用。
•掌握各类单词的形式描述
•学会用数据中心法实现有限自动机
•学会用直接转向法实现有限自动机
•独立完成SNL语言的词法分析器
【实验原理】
词法分析是编译过程的第一阶段。它的任务就是对输入的字符串形式的源程序按顺序进行扫描,根据源程序的词法规则识别具有独立意义的单词(符号),并输出与其等价的Token序列。
有限自动机是描述程序设计语言单词构成的工具,而状态转换图是有限自动机的比较直观的描述方法。我们使用确定的有限状态自动机,简记为DFA。
下面给出能够识别SNL中各类单词的DFA:
根据语言的词法规则构造出识别其单词的确定有限自动机DFA, 仅仅是词法分析程序的一个形式模型,距离词法分析程序的真正实现还有一定的距离。状态转换图的实现通常有两种方法,一种是用状态转换表T;另一种是直接转向法。
状态转换表法又称数据中心法,是把状态转换图看作一种数据结构(状态转换表),由控制程序控制字符在其上运行,从而完成词法分析。用转换表的优点是程序短,但占存储空间多,直接转向法的优缺点正好与此相反。
直接转向法又称程序中心法,是把状态转换图看成一个流程图,从状态转换图的初态开始,对它的每一个状态结点都编一段相应的程序。
【实验步骤】
构造识别单词的自动机
。
2. 对各类单词的状态转换图合并,构成一个能识别语言所有单词的状态转换图。合并步骤为:
(1) 将各类单词的状态转换图的初始状态合并为一个唯一的初态;
(2) 化简调整状态冲突和对冲突状态重新编号;
(3) 如有必要,增加出错状态。
用数据中心法实现有限自动机,生成词法分析程序。
用直接转向法实现有限自动机,生成词法分析程序
用自动生成工具LEX生成词法分析程序。
对比上述各种方法生成的程序,总结其优缺点。