03第3章 词法分析2.ppt

* 限定：在Ri中只能出现字母表Σ中的字符，以及前面已 定义的正规表达式名字，我们用这种辅助定义式 (相当于规则)来定义程序语言的单词符号。 * “(”和“)”打上引号是为了和正规表达式中的元符号相区别 3.6.6 根据DFA构造词法分析程序 构造词法分析器的一般步骤： 用正则表达式对程序设计语言的词法规则进行描述 为每一个正则表达式构造一个NFA，用来识别正则表达式描述的语言。 将构造的NFA转换成等价的DFA。 简化DFA，使其状态数最少。 根据化简后DFA构造词法分析程序。 * * 根据DFA构造词法分析程序有两种方法。 1.直接编程法 将DFA识别过程转化为程序，即用程序来模拟DFA的行为。首先将DFA用状态图表示，然后按下列步骤根据状态图画出词法分析程序流程图： 1)初始状态对用程序的开始； 2)终止状态对应程序的结束 3)状态转移对应条件语句或多分支选择语句； 4)状态图的环对应程序中循环语句； 5)终态返回时，应满足最长匹配原则。 其中最长匹配原则指识别出的单词有混淆时，按长度最长的来确定。例如符号串“=”认为是一个单词，而不是””和“=”。 * * 例：画出图示DFA的流程图 * * 0 1 2 a a b b 3 a a b b 状态1 状态3 状态2 状态0 该设计方法适合手工实现，编写出的词法分析程序比较精简，分析速度快。 该方法设计的词法分析程序与要识别的语言单词密切有关，通过程序的控制流转移来完成对输入字符的识别，程序中的每一条语句都与要识别的单词符号有关，一旦语言的单词符号集即词法规则发生变化，则要重新编写程序。 一般来讲，这种方法适合编写词法比较简单的词法分析程序。 * * 2.表驱动法 表驱动的词法分析程序的模型如图所示。由输入字符序列、分析表和控制程序组成。 分析表就是DFA的状态转换矩阵如表所示。 输入字符序列 分析表 控制程序 表驱动的词法分析程序的模型 Σ 状态 0 1 S* B A A C S B S C C A B 分析表 * * 控制程序有两个参数，一个参数接受扫描的字符a，另一个参数为DFA的状态i。其控制程序的算法： ?1) 在输入字符序列后面加一个结束符‘#’，将扫描指针设在输入序列的最左端，状态参数i设为开始状态。 2) 扫描下一字符a，如果是结束符‘#’，则停止；否则，根据状态参数i和输入字符a查分析表，将状态参数i设为查分析表(i,a）后得到的状态。 3)? 如果i是终态，则表示识别出一个单词转到4；否则，如果i为空，出错；不为空转到2。 4) 处理识别出的单词，输出单词符号。状态参数i设为开始状态，转到2。 问题：该算法能否实现最长匹配？若不能，应怎样修改？ * * 表驱动的词法分析程序根据分析表内容进行操作，与要识别的单词符号无关,具体识别什么单词符号，由分析表的内容决定，是一种典型的数据与操作分离的工作模式。 构造不同的词法分析程序实质上是构造不同的分析表，而控制程序是不变的，为词法分析程序的自动生成提供了极大的方便。 表驱动的词法分析程序相对直接编程的词法分析器来说，程序比较复杂，由于在工作中需要查表确定分析动作，因此，分析速度也慢一些。 * * * * 构造词法分析器的每一步都可借助成熟算法实现，将这些算法组合起来形成词法分析程序生成器。 生成器输入是描述程序设计语言单词符号的正则表达式 生成器输出是能够识别单词符号的词法分析程序。 3.7 词法分析程序的自动生成器LEX LEX（lexical Ananlyzer Generator）是一个词法分析程序的自动生成器，1972年贝尔实验室首先在UNIX上实现。 FLEX（Fast lexical Ananlyzer Generator）是对LEX的扩充，可在MS-DOS下运行。 LEX能根据给定的正则表达式自动生成相应的词法分析程序。 LEX的输入是用LEX语言写的源程序，生成一个用C语言描述的词法分析器。 LEX生成的目标程序包含一个状态转换矩阵和一个控制执行程序 * * 3.7 词法分析程序的自动生成器LEX 使用LEX的流程如图所示。 * * LEX源程序 LEX 编译器 C程序 C程序 C 编译器 词法分析程序 输入流 词法分 析程序 单词序列 * LEX的源程序 一个LEX源程序主要由三个部分组成，每部分间用%% 隔开 说明部分 －－可选 %% －－必须有 识别规则 －－必须有（LEX的核心） %%