编译原理chapter3 (新2016).pptVIP

Chapter3 词法分析;3.1 词法分析器的设计;词法分析的主要工作: 从源程序的第一个字符开始，从左到右扫描源程序， 一次读一个字符，根据词法规则将有关字符组合成单词， 并识别各类单词，当确定单词类别后，将单词输出。;词法分析与语法分析的接口方式：;源程序的输入：;(3)超前有哪些信誉好的足球投注网站：词法分析程序在组合单词的时候，为了进一步判明情况和确定下一步要做什么以及为了处理上的方便等，常采取向前假读字符的办法(超前有哪些信誉好的足球投注网站)，即最近向前读取字符和判别字符是什么，不马上处理，当情况判明后，再回来处理已读过的字符。;（4）输入缓冲区的处理：无论缓冲区设定为多大， 都不能保证单词不会被它的边界打断。;单词的输出：;例如：程序段 if (i==5) x=y；在经过词法分析器扫 描后，输出的单词可表示如下： ;词法分析的分离：;3.2 正则文法与状态转换图 ; 一个状态转换图可用于接受（或识别）一定的 符号串。在状态转换图中从初始状态到某一终止状 态的序列为路径。对于某一符号串β，在状态转换图 中，若存在一条路径产生β，则称状态转换图接受（ 或识别）该符号串β，否则符号串β不能被接受。 能被状态转换图TG接受的符号串的集合记为L(TG)， 称为状态转换图所能识别的语言。;由状态转换图可见，字母表Σ={a,b}上的符号串：;二、正则文法的状态转换图表示 ;例： 给出与正则文法G[S]等价的状态转换图。 G[A0]： A0→0A0 | 1A0 | 1A1 A1→1A2 A2→ε ;练习： 给出与正则文法G[S]等价的状态转换图。 G[S]： S→aA | bB | ε A→aB | bA B→aS | bA | ε ;对于左线性文法G[Z]，状态转换图的表示方法如下： ;例如： 给出与正则文法G[Z]等价的状态转换图。 G[Z]： Z→U0 | V1 U→Z1 | 1 V→Z0 | 0 ;补充作业： 试构造一右线性文法，使得它与如下文法等价。 S →AB A →UT U →a | aU T →b | bT B →c | cB 并根据所得的右线性文法构造出相应的状态转换图。;3.3 正规表达式与有限自动机;采用正规式有以下几个原因： ;正规式和正规集的定义 ; 正规式也称正则表达式，是用于描述单词的另外一个 工具，也是表示正规集的工具。下面我们给出正规式和它 所表示的正规集的递归定义：;(1)ε和ф是Σ上的正规式，它们所表示的正规集分别为{ε}和ф;;例：正规式(a)| ((b) * (c))可以表示成 a|b*c，它所表 示的正规集为：; 如果两个正规式r和s表示同样的正规集，我们称 两个正规式r和s等价，写作r=s。;1．r | s = s | r “ | ”运算满足交换律 ;采用正规式有以下几个原因： ; 正则文法可以用状态转换图非形式的进行表示， 这就表明正则文法所对应的语言(正则语言)可以用状 态转换图来接受(识别)。我们将看到，有限自动机正 是对状态转换图进一步形式化的结果，它对于扫描器 的构造，特别是扫描器自动生成将带来很大的方便。;确定的有限自动机（DFA） M=(S，Σ，f，S0，F);例：为下图所示的状态图构造确定的有限自动机。 ; 一个DFA还可以用一个矩阵(状态矩阵）表示： 矩阵的行表示状态，列表示输入字符，矩阵元素表示 相应状态行和输入字符列下的新状态。; 对于Σ*中的任何字符串α，若DFA M中存在一条从 初态结点到某一终态结点的路，且这条路上所有弧的标 记连接成的字符串等于α，则称α可以被DFA M所接受 (识别)。; 为了加深对上述定义的理解，我们给出扩充的转 换函数的定义： ; DFA的确定性表现在转换函数f: S×Σ→S是一个单值函数，也就是说对任何状态k∈S,和输入符号a∈Σ，f(k,a)唯一地确定了下一个状态。 从状态转换图来看，若字母表含有n个输入字符，那么任何一个状态结点最多有n条弧射出，而且每条弧以一个不同的输入字符进行标记。;例：  ;非