编译原理chapter3

1、第三章第三章 词法分析词法分析 Lexical analysis 张志远张志远 2008-9-4 Outlines n词法分析器的功能和输出形式词法分析器的功能和输出形式 n正规表达式与有限自动机正规表达式与有限自动机 n词法分析器的设计：状态转换图的实现词法分析器的设计：状态转换图的实现 nlex的一般描述与实现的一般描述与实现 词法分析器：词法分析器：scanner 正规式：正规式：regular expression 有限自动机：有限自动机：finite automata 词法分析的任务词法分析的任务 词法分析的任务是：从左至右逐个字符地对源词法分析的任务是：从左至右逐个字符地对源 程序

2、进行扫描，产生一个个单词符号，把作为程序进行扫描，产生一个个单词符号，把作为 字符串的源程序改造成为单词符号串的中间程字符串的源程序改造成为单词符号串的中间程 序。序。 去掉注释去掉注释: : /*this is a comment*/ 编译预处理编译预处理: : #include #define pi 3.1415926 The role of the lexical analyzer Fig. 3.1 Interaction of lexical analyzer with parser 3.1 对词法分析器的要求对词法分析器的要求 3.1.1 词法分析器功能和输出形式词法分析器功能和输出

3、形式 n 词法分析器功能：输入源程序，输出单词符号。词法分析器功能：输入源程序，输出单词符号。 n 程序语言的单词符号一般分为五种程序语言的单词符号一般分为五种 关键字关键字:keywords 标识符标识符:identifiers 常数常数:constants 运算符运算符:operators 界符界符:delimiter 需要考虑哪些问题？需要考虑哪些问题？ n 字符串的问题字符串的问题 字符串中有引号怎么办？双引号，单引号？字符串中有引号怎么办？双引号，单引号？ C，VB，Pascal SQL Server，Oracle 换行符号呢？换行符号呢？ 允许空字符串吗？允许空字符串吗？ n 整数

4、的问题整数的问题 是否允许是否允许0开头的整数？开头的整数？ n 小数的问题小数的问题 0.1，10.01可以吗？可以吗？ .1，或者，或者10.呢？呢？ 需要考虑哪些问题？需要考虑哪些问题？ n 历史上词法定义中的一些问题历史上词法定义中的一些问题 忽略空格带来的困难忽略空格带来的困难(FORTRAN) DO 8 I 3. 75 DO8I 3. 75 DO 8 I 3, 75 关键字不保留关键字不保留(PL/I) IF THEN THEN THEN=ELSE；ELSE 关键字太多了关键字太多了(COBOL) zero, zeros, zeroes 单词符号的表示单词符号的表示 词法分析器输出

5、的单词符号常常表示为二元式：词法分析器输出的单词符号常常表示为二元式： ( (单词种别，单词符号的属性值单词种别，单词符号的属性值) ) 单词种别：单词种别： 关键字采用一字一种的分法处理较为方便关键字采用一字一种的分法处理较为方便; ; 标识符按一种处理；标识符按一种处理； 常数按类型分种；常数按类型分种； 运算符可采用一符一种的分法，但也可以把具有一定共运算符可采用一符一种的分法，但也可以把具有一定共 性的运算符视为一种性的运算符视为一种; ; 界符一般采用一符一种的分法界符一般采用一符一种的分法; ; 单词符号的属性单词符号的属性 n 如果一个种别只含有一个单词符号，那么对于这个单词符如

6、果一个种别只含有一个单词符号，那么对于这个单词符 号，种别编码就完全代表它自身了。号，种别编码就完全代表它自身了。 n 若一个种别含有多个单词符号，那么，对于它的每个单词若一个种别含有多个单词符号，那么，对于它的每个单词 符号，除了给出种别编码之外，还应给出有关单词符号的符号，除了给出种别编码之外，还应给出有关单词符号的 属性信息。属性信息。 n 单词符号的属性是指单词符号的特征或特性。属性值则是单词符号的属性是指单词符号的特征或特性。属性值则是 反映特性或特征的值。反映特性或特征的值。 n 例如，对于某个标识符，常将存放它有关信息的符号表项例如，对于某个标识符，常将存放它有关信息的符号表项

7、的指针作为其属性值；对于某个常数，则将存放它的常数的指针作为其属性值；对于某个常数，则将存放它的常数 表项的指针作为其属性值。表项的指针作为其属性值。 举例举例 作为例子考虑下述作为例子考虑下述C+代码段：代码段： while (i=j) i- -; 经词法分析器处理后，它将转换为如下的单词符号序列：经词法分析器处理后，它将转换为如下的单词符号序列： = , - 扫描器作为独立的子程序扫描器作为独立的子程序 词法 分析器 语法分析器 符号表 源程序 记号 取下一个 记号 作为独立的遍：简单，但需增加额外的开销作为独立的遍：简单，但需增加额外的开销 作为独立的子程序：节省内存作为独立的子程序：节

8、省内存(PL/0) 相关问题相关问题 n 符号表的查填兼顾问题符号表的查填兼顾问题 兼顾：兼顾：token自身值作为符号表的入口自身值作为符号表的入口 Token串长度统一，可放宽对标识符的限制，但要增加串长度统一，可放宽对标识符的限制，但要增加 额外负担额外负担 不兼顾：不兼顾： token自身值就是标识符、常数本身的符号串自身值就是标识符、常数本身的符号串 速度快，但要限制标识符的长度速度快，但要限制标识符的长度 n 发现词法错误发现词法错误 行、列计数行、列计数 发现并定位词法错误发现并定位词法错误 一种符号表的数据结构一种符号表的数据结构 数组symtable lexptr 记号 di

9、vdiv modmod idid idid 属性 0 1 2 3 4 d i v EOS m o d EOS c o u n t EOS i EOS 数组lexemes 3.2 正规式与有限自动机正规式与有限自动机 本节掌握内容：本节掌握内容： n正规式的定义正规式的定义 n根据条件写正规式根据条件写正规式 nDFA和和NFA的定义的定义 n正规式到正规式到NFA以及以及NFA到到DFA的转换的转换 3.3.1 正规式与正规集正规式与正规集 定义：定义： n 和和 都是都是 上的正规式，表示的正规集分别为上的正规式，表示的正规集分别为 和和 ； n a , 则则a是是上的一个正规式，表示的正规

10、集为上的一个正规式，表示的正规集为 a; n e1和和e2都是都是上的正规式，则上的正规式，则(e1|e2), e1e2和和(e1)*也也 都是正规式，表示的正规集分别为都是正规式，表示的正规集分别为L(e1) L(e2), L(e1)L(e2)(连接积）和（连接积）和（L(e1)*（闭包）（闭包）; n 正规式所表示的字集叫做正规式所表示的字集叫做上的正规集上的正规集 举例：举例： =a, b 正规式正规式正规集正规集 ba*上所有以上所有以b为首后跟着任意多个为首后跟着任意多个a的字的字 a(a|b)*上所有以上所有以a为首的字；为首的字； (a|b)*(aa|bb)(a|b)* 上所有两

11、个相继的上所有两个相继的a或相继的或相继的b的字的字 =A,B,0,1 (A|B)(A|B|0|1)*上的上的“标识符标识符”的全体的全体 (0|1)(0|1)* 上上“数数”的全体的全体 正规式等价：表示的正规集相同正规式等价：表示的正规集相同 复杂的例子复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000010000010111001 正规式的性质：正规式的性质： 交换律交换律r | s = s | r 但是但是rs sr 结合律结合律r | (s | t) = (r | s) | t r(st) =

12、 (rs)t 分配律分配律r(s | t) = rs | rt (s | t)r = sr | tr 幺元幺元r = r= r 举例：举例： C语言中的标识符语言中的标识符 letter_ A | B | | Z | a | b | | z | _ digit 0 | 1 | | 9 id letter_(letter_ |digit)* 无符号数集合，例无符号数集合，例1946,11.28,63E8,1.99E 6 digit 0 | 1 | | 9 digits digit digit* optional_fraction .digits| optional_exponent ( E (

13、+ | | ) digits ) | numberdigits optional_fraction optional_exponent 简化表示简化表示 number digit+ (.digit+)? (E(+| )? digit+)? n 正规式的缩写正规式的缩写 r+ = r r* 表示表示1个或者多个实例个或者多个实例 r? = r | 表示表示0个或者个或者1个实例个实例 abc = a | b | c a z = a | b | c | z 正规式和正规文法的等价性正规式和正规文法的等价性 n正规式转换成正规文法正规式转换成正规文法 规则规则正规式正规式正规文法正规文法 规则规则1

14、 A-xyA-xB B-y 规则规则2A-x*yA-xB A-y B-xB B-y 规则规则3A-x|yA-x A-y 正规式转换成正规文法正规式转换成正规文法 r = a(a|d)* S-aA A-(a|d)* A-(a|d)B A- B-(a|d)B B- A-aB A-dB B-aB B-dB S-aA A-aB A-dB A- B-aB B-dB B- 正规式和正规文法的等价性正规式和正规文法的等价性 n正规文法转换成正规式正规文法转换成正规式 规则规则正规文法正规文法正规式正规式 规则规则1 A-xB B-yA=xy 规则规则2 A-xA A-yA=x*y 规则规则3 A-x A-y

15、A=x|y 正规文法转换成正规式正规文法转换成正规式 S-aA|a A-aA|dA|a|d S=aA|a A=(a|d)A|(a|d) A=(a|d)*(a|d) 代入代入S得：得： S=a(a|d)*(a|d)|a 分配率：分配率： S=a(a|d)*(a|d)| ) S=a(a|d)* 3.3.2 确定有限自动机确定有限自动机 (Deterministic Finite Automata, DFA) 确定有限自动机确定有限自动机(DFA)是一个五元式是一个五元式 M= (S, ,s0, F) 其中其中: 涵义：涵义： nS：有限状态集：有限状态集 n ：有穷字母表：有穷字母表 n：从从S

16、至至S的的单值部分映射单值部分映射。(s,a）=s。意味着：。意味着： 当现行状态为当现行状态为s、输入字符为、输入字符为a时，将转换到下一个状时，将转换到下一个状 态态s。我们称。我们称s为为s的后继状态的后继状态 nS0 S：唯一的初态：唯一的初态 nF S：终态集（可空）：终态集（可空） 状态转换矩阵状态转换矩阵 DFA可以用一个矩阵表示，该矩阵的行表示状态，可以用一个矩阵表示，该矩阵的行表示状态， 列表示输入字符，矩阵元表示列表示输入字符，矩阵元表示(s,a）的值，该矩）的值，该矩 阵称为状态转换矩阵。阵称为状态转换矩阵。 例如：例如： M=0,1,2,3,a,b, ,0,3 其中其中

17、 为：为： （0，a）=1; （0，b）=2; （1，a）=3; （1，b）=2; （2，a）=1; （2，b）=3; （3，a）=3; （3，b）=3; 状态转换矩阵：状态转换矩阵： 状态状态 a b 0 1 2 1 3 2 2 1 3 3 3 3 状态转换图：状态转换图： DFA的图形表示的图形表示 n 假定假定DFA M 含有含有m个状态个状态n个输入字符，那末，这张图含个输入字符，那末，这张图含 有有m个状态结点，每个结点顶多有个状态结点，每个结点顶多有n条箭弧射出和别的结条箭弧射出和别的结 点相连接，每条箭弧用点相连接，每条箭弧用 上的一个不同字符作标记，整张上的一个不同字符作标记，

18、整张 图含有唯一的初态和若干个（可以是图含有唯一的初态和若干个（可以是0个）终态结点。个）终态结点。 n 对于对于 *中的任何一个字符中的任何一个字符 ，若存在一条从初态结点到某，若存在一条从初态结点到某 一终态结点的通路，且这条通路上所有箭弧的标记符连接一终态结点的通路，且这条通路上所有箭弧的标记符连接 成的字等于成的字等于 ，则称，则称 为为DFA M所识别（读出或接受）。所识别（读出或接受）。 n 若若M的初态结点同时又是终态结点，则为空字的初态结点同时又是终态结点，则为空字 可以为可以为M所所 识别。识别。DFA M所能识别的字的全体记为所能识别的字的全体记为L(M). 正规式：正规式

19、： (a | b)* (aa | bb) (a | b)* 正规集：正规集： a, b上两个连续的上两个连续的a或者或者b组成的字组成的字 定理：定理： *上的正规集上的正规集V都有一个确定的都有一个确定的DFA与之对应，与之对应， 反之也成立。反之也成立。 ：S - S的单值映射决定了的单值映射决定了DFA和和NFA的区别的区别 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1010111000 1010 111000 10101 11000 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始

20、4 0 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 n例：识别例

21、：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 1 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 1 0 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数 0123 开始开始 4 1 0 0 1 0 1 0 1 0 1 n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数

22、0123 开始开始 4 1 0 0 1 0 1 0 1 0 1 10102 = 1010 1112 = 710 例：例：DFA, ,接受接受 0和和1的个数都是偶数的字符串的个数都是偶数的字符串 3 1 2 0 1 1 1 1 0000 开始开始 偶偶0偶偶1 奇奇0奇奇1奇奇0偶偶1 偶偶0奇奇1 3.3.3 非确定有限自动机非确定有限自动机 (Nondeterministic Finite Automata, NFA) 一个非确定有限自动机（一个非确定有限自动机（NFA)是一个五元式是一个五元式 M= (S, ,S0, F) n S：有限状态集：有限状态集 n ：有穷字母表：有穷字母表 n

23、 是一个从是一个从S x *到到S的子集的映照，即的子集的映照，即 ：S x *2s n S0 S,是一个非空的初态集；是一个非空的初态集； n F S，是一个终态集（可空），是一个终态集（可空） 说明：说明： n NFA也可以表示成一张状态转换图。也可以表示成一张状态转换图。 n 假定假定NFA 含有含有m个状态个状态n个输入字符，那末，这个输入字符，那末，这 张图含有张图含有m个状态结点，每个结点可以射出若干个状态结点，每个结点可以射出若干 条箭弧和别的结点相连接，每条箭弧用条箭弧和别的结点相连接，每条箭弧用 *上的一上的一 个字（不一定要不同的字而且可以是空字个字（不一定要不同的字而且可

24、以是空字 ）作标）作标 记（称为输入字），整张图至少含有一个的初态记（称为输入字），整张图至少含有一个的初态 和若干个（可以是和若干个（可以是0个）终态结点。个）终态结点。 n 某结点既可以是初态也可以是终态结点。某结点既可以是初态也可以是终态结点。 n 对于对于 *中的任何一个字符中的任何一个字符 ，若存在一条从初态，若存在一条从初态 结点到某一终态结点的通路，且这条通路上所有结点到某一终态结点的通路，且这条通路上所有 箭弧的标记符连接成的字（忽略那些标记为箭弧的标记符连接成的字（忽略那些标记为 的弧）的弧） 等于等于 ，则称，则称 为为NFA M所识别（读出或接受）。所识别（读出或接受）。

25、 n 若若M的初态结点同时又是终态结点，或者存在一的初态结点同时又是终态结点，或者存在一 条某处态结点到某各终态结点的条某处态结点到某各终态结点的 通路，则为空字通路，则为空字 可以为可以为M所识别。所识别。 n 这里应注意这里应注意DFA与与NFA的异同点。的异同点。 NFA的例子的例子 识别语言识别语言 (a|b)*ab 的的NFA 12 开始开始a 0 a b b 识别语言识别语言 aa*|bb* 的的NFA 12 开始开始 a 0 a b b 3 4 DFA例子例子 12 开始开始a 0 a b b a b 识别语言识别语言 (a|b)*ab 的的DFA 例：下图所示的例：下图所示的N

26、FA能识别的字是含有连续的能识别的字是含有连续的 两个两个a或者连续的两个或者连续的两个b的由的由a和和b组成的字。你组成的字。你 看出来了吗？看出来了吗？ 由正规式到由正规式到NFA的替换规则的替换规则 A B 例例1：正规式：正规式：R=(a*b)*ba(a|b)* 其中（其中（a*b)* 和和(a|b)*分别可以看成一个闭包。形分别可以看成一个闭包。形 成成A和和G结点。可以画为：结点。可以画为： 例例2：画出（：画出（a|b)*(aa|bb)(a|b)*对应的对应的NFA NFA到到DFA的转换子集法的转换子集法 1、 _closure( I ) 若若q I，则，则q _closure

27、( I ) ； 若若q I,那么从那么从q出发经任意条出发经任意条弧而能达到的任弧而能达到的任 何状态何状态q都属于都属于_closure( I ) ； 2、Ia=_closure( J )，其中，其中J是那些可从是那些可从I中的某一中的某一 状态出发经过一条状态出发经过一条a弧而到达的状态结点的全体。弧而到达的状态结点的全体。 3、假定、假定 =a1,a2,a3.ak,我们构造一张表，此我们构造一张表，此 表的每一行含有表的每一行含有K+1列。首行首列为列。首行首列为_closure( x )， 其中其中x为为NFA的初始状态结点的闭包。一般而言，的初始状态结点的闭包。一般而言， 如果某一行

28、的第一列的状态子集已经确定，例如记如果某一行的第一列的状态子集已经确定，例如记 为为I，那么置该行的，那么置该行的i1列为列为Iai。然后，检查该行上。然后，检查该行上 的所有状态子集，看他们是否已在表的第一列中出的所有状态子集，看他们是否已在表的第一列中出 现，把未出现的填入到后面空行的第一列。重复上现，把未出现的填入到后面空行的第一列。重复上 述过程，直到出现在第述过程，直到出现在第i1列上的所有状态子集均列上的所有状态子集均 已在第一列上出现。已在第一列上出现。 例例：用状态子集法构造图：用状态子集法构造图3.6的状态转换矩阵：的状态转换矩阵： I Ia Ib X,5,1 5,3,1 5

29、,4,1 5,3,1 5,3,1,2,6,Y 5,4,1 5,4,1 5,3,1 5,4,1,2,6,Y 5,3,1,2,6,Y 5,3,1,2,6,Y 5,4,1,6,Y 5,4,1,6,Y 5,3,1,6,Y 5,4,1,2,6,Y 5,4,1,2,6,Y 5,3,1,6,Y 5,4,1,2,6,Y 5,3,1,6,Y 5,3,1,2,6,Y 5,4,1,6,Y 对上表中状态子集重新命名后状态转换矩阵对上表中状态子集重新命名后状态转换矩阵 S a b 0 1 2 1 3 2 2 1 5 3 3 4 4 6 5 5 6 5 6 34 对应的未化简对应的未化简DFA 例2 确定有限自动机的化简

30、确定有限自动机的化简 n等价等价 n一致性条件：同为终态或非终态一致性条件：同为终态或非终态 n蔓延性条件：对所有输入均到达等价状态蔓延性条件：对所有输入均到达等价状态 n 首先把首先把M的状态分为两组：终态组的状态分为两组：终态组3，4，5，6，和非终，和非终 态组态组0，1，2 n 其次考察终态组，由于其次考察终态组，由于 n 3，4，5，6a 3,4,5,6和和 n 3，4，5，6b 3,4,5,6所以不能再划分所以不能再划分 再考察再考察0，1，2 n 由于由于0，1，2a1，3，它既不属于，它既不属于0，1，2也不属于也不属于 3，4，5，6，因此应将其一分为二，由于，因此应将其一分

31、为二，由于1态经态经a弧到达弧到达 3态，而且状态态，而且状态0，2经经a弧到达弧到达1态故应把态故应把1态分出形成态分出形成1， 0，2。 n 现在划分已经有现在划分已经有3个组：个组：3，4，5，6，1，0，2。 n 由于由于0，2b=2,5未包括在上述分组中，故未包括在上述分组中，故0，2应一分应一分 为二为二0，2。 n 到此四个分组到此四个分组3，4，5，6，0，1，2。每个组都不。每个组都不 可再分。可再分。 n 最后，令状态最后，令状态3代表代表3，4，5，6。把原来到达。把原来到达4，5，6的的 弧都导入弧都导入3，并删除，并删除4，5，6状态。得到化简的状态。得到化简的DFA

32、. 算法实现：从算法实现：从NFA构造构造DFA n 输入：一个输入：一个NFA N n 输出：一个接受同样语言的输出：一个接受同样语言的DFA D n 方法：为方法：为D构造转换表构造转换表Dtran，DFA的每个状态是的每个状态是NFA的的 状态集，状态集，D将将“并行并行”的模拟的模拟N对输入串的所有可能的移动。对输入串的所有可能的移动。 n 我们用以下操作来记录我们用以下操作来记录NFA的状态集的轨迹（的状态集的轨迹（s代表代表NFA 的状态，的状态，T代表代表NFA的状态集合）的状态集合） 操作操作描述描述 _closure(s) 从从NFA状态状态s只经过只经过转换可以到达的状态集

33、转换可以到达的状态集 _closure(T) 从从T中的状态只经过中的状态只经过转换可以到达的状态集转换可以到达的状态集 move(T,a)从从T中的状态经过输入符号中的状态经过输入符号a上的转换可以到达的上的转换可以到达的 状态集状态集 算法实现：从算法实现：从NFA构造构造DFA n 子集构造算法子集构造算法 初始时，初始时，_closure(s0)是是Dstates中唯一的状态且未被标记；中唯一的状态且未被标记； While Dstates中存在一个未标记的状态中存在一个未标记的状态T 标记标记T； for 每个输入符号每个输入符号a U= _closure(move(T,a); if

34、U没在没在Dstates中中 将将U作为一个未标记的状态添加到作为一个未标记的状态添加到Dstates中；中； DtranT, a = U 算法实现：从算法实现：从NFA构造构造DFA n _closure的的计算计算 将所有的状态压入栈将所有的状态压入栈stack中；中； 将将_closure(T)初始化为初始化为T； While 栈栈stack不空不空 将栈顶元素将栈顶元素 t 弹出栈；弹出栈； for 每个这样的状态每个这样的状态u：从：从 t 到到 u 有一条标记为有一条标记为的边的边 if u不在不在_closure(T)中中 将将u添加到添加到_closure(T)中；中； 将将u

35、压入栈压入栈stack中；中； 3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性 正规文法：正规文法： 左线性文法：左线性文法： U a或或U Va; 右线性文法：右线性文法： U a或或U aV； 其中，其中，U，V VN，a VT 结论：结论： （1）对每一个右线性或者左线性正规文法）对每一个右线性或者左线性正规文法G，都存在一个，都存在一个 有限自动机有限自动机(FA)M，使得，使得L(M) = L(G)。 （2）对每一个）对每一个FA M，都存在一个右线性正规文法，都存在一个右线性正规文法GR和左和左 线性正规文法线性正规文法GL，使得，使得L(M) = L(GR)

36、 = L(GL) A、右线性文法转换成自动机、右线性文法转换成自动机 （1）增加结点）增加结点Z为终止状态（为终止状态（G的的中没有中没有Z） （2）以每一个非终结符号作为状态的结点；）以每一个非终结符号作为状态的结点； （3）对于）对于U-a的每个规则，引一条从的每个规则，引一条从U到到Z的的 弧，其标记为弧，其标记为a； （4）对于）对于U-aV的每个规则，引一条从的每个规则，引一条从U到到V的的 弧，其标记为弧，其标记为a； 假设右线性文法为，求与其对应的自动机假设右线性文法为，求与其对应的自动机 A - 0 | 0B | 1D B - 0D | 1C C - 0 | 0B | 1D D

37、 - 0D | 1D B、左线性文法转换成自动机、左线性文法转换成自动机 （1）增加结点）增加结点S为开始状态（为开始状态（S 不属于不属于VN）；）； （2）以每一个非终结符号作为状态的结点；）以每一个非终结符号作为状态的结点； （3）对于）对于U-a的每个规则，引一条从的每个规则，引一条从S到到U的弧，的弧， 其标记为其标记为a； （4）对于）对于U - Va的每个规则，引一条从的每个规则，引一条从V到到U的的 弧，其标记为弧，其标记为a； 例：画出下面正规文法对应的例：画出下面正规文法对应的NFA Z - A0 A - A0 | Z1 | 0 解：增加一个解：增加一个S作为开始状态作为开

38、始状态 A -0，所以引一条从，所以引一条从S到到A的弧，标记为的弧，标记为0； Z - A0，所以引一条从，所以引一条从A到到Z的弧，标记为的弧，标记为0； A - A0，所以引一条从，所以引一条从A到到A的弧，标记为的弧，标记为0； A - Z1，所以引一条从，所以引一条从Z到到A的弧，标记为的弧，标记为1； 00 0 1 ASZ C、自动机转换成右线性文法、自动机转换成右线性文法 开始结点作为开始符号；开始结点作为开始符号； 若有若有(A, a) = B，即有从一条从，即有从一条从A到到B的弧，且其的弧，且其 标记为标记为a，则：，则： （1）当）当B不是终态符号时，令不是终态符号时，令

39、A - aB； （2）当）当B是终态符号时，令是终态符号时，令A - a | aB； 若开始符号若开始符号S0也是终态符号，则还需要增加一个也是终态符号，则还需要增加一个 新的非终结符号新的非终结符号S0作为新的开始符号，并增加一个作为新的开始符号，并增加一个 产生式产生式S0 - S0 | 例子：例子： 写成右线性文法为：写成右线性文法为： A - 0 | 0B | 1D B - 0D | 1C C - 0 | 0B | 1D D - 0D | 1D D、自动机转换成左线性文法、自动机转换成左线性文法 终态结点作为开始符号，若有多个终态符号终态结点作为开始符号，若有多个终态符号Y1Y2.Yn

40、，则，则 增加一个状态增加一个状态Y作为新的终态符号，从原来的终态符号各引作为新的终态符号，从原来的终态符号各引 一条空弧到一条空弧到Y，且有，且有Y - Y1 | Y2. Yn； 若有若有(A, a) = B，即有从一条从，即有从一条从A到到B的弧，且其标记为的弧，且其标记为a， 则：则： （1）当）当A不是开始符号，令不是开始符号，令B - Aa； （2）当）当A是开始符号时，令是开始符号时，令B - a； 若开始符号若开始符号S0也是终态符号，则需要增加一个产生式也是终态符号，则需要增加一个产生式Y - 例子：例子： 将自动机转换成左将自动机转换成左 线性文法线性文法 左线性文法为：左线

41、性文法为： F - 0 | C0 C - B1 B - 0 | C0 D - 1 | C1 | D0 | D1 | B0 例子例子:设文法设文法G S 0A A 0A | 1S | 0 S Z A 0 0 1 0 NFA: 识别识别:(01 | 0)*0 对吗？对吗？ 下面将如下面将如 何转换为何转换为 DFA 3.2 词法分析器的设计词法分析器的设计 输入和预处理输入和预处理 n 词法分析器工作的第一步是输入源程序文本。输入串一般词法分析器工作的第一步是输入源程序文本。输入串一般 放在一个缓冲区中，这个缓冲区称输入缓冲区。放在一个缓冲区中，这个缓冲区称输入缓冲区。 n 预处理工作包括对空白符

42、、跳格符、回车符和换行符等编预处理工作包括对空白符、跳格符、回车符和换行符等编 辑性字符的处理，及删除注解等。辑性字符的处理，及删除注解等。 n 扫描缓冲区扫描缓冲区 两个指示器，一个指向当前正在识别单词的开始位置（指两个指示器，一个指向当前正在识别单词的开始位置（指 向新单词的首字符），另一个用于向前搜索以寻找单词的向新单词的首字符），另一个用于向前搜索以寻找单词的 终点。终点。 互补的两个缓冲区互补的两个缓冲区 我们认定在另半区一定可以达到单词的终点。这意味着得我们认定在另半区一定可以达到单词的终点。这意味着得 标识别符和常数的长度实际上必须加以限制，否则即使缓标识别符和常数的长度实际上必

43、须加以限制，否则即使缓 冲区再大也无济于事。冲区再大也无济于事。 PL/I语言中的特殊情况语言中的特殊情况:declare(arg1,arg2,.,argn) 在扫描到右括号之前，无法确认在扫描到右括号之前，无法确认declare究竟是关键字还究竟是关键字还 是数组名称。是数组名称。 Eof(end of file:词法分析器的终止词法分析器的终止) n双缓冲区问题双缓冲区问题_超前扫描导致的超前扫描导致的效率问题效率问题 单词开始 向前 : : : E : : = : : M : *C : * : * : 2 : eof : : : : if forward在缓冲区第一部分末尾在缓冲区第一部

44、分末尾 then begin 重装缓冲区第二部分重装缓冲区第二部分; forward := forward +1 end else if forward在缓冲区第二部分末尾在缓冲区第二部分末尾 then begin 重装缓冲区第一部分重装缓冲区第一部分; 将将forward移到缓冲区第一部分开始移到缓冲区第一部分开始 end else forward:= forward +1; 每 次 移 动每 次 移 动 forward指指 针都需要进针都需要进 行两遍测试行两遍测试 单词开始 向前 : : : E : : = : : M : * : eof C : * : * : 2 : eof : :

45、: : : eof forward := forward + 1; if forward= eof then begin if forward在第一部分末尾在第一部分末尾 then begin 重装第二部分重装第二部分; forward := forward +1 end else if forward在第二部分末尾在第二部分末尾 then begin 重装第一部分重装第一部分; 将将forward 移到第一部分开始移到第一部分开始 end else /* eof 在表示输入结束在表示输入结束 */ 终止词法分析终止词法分析 end 在每半个缓在每半个缓 冲区的末尾冲区的末尾 增 加 一 个增

46、 加 一 个 eof标记后，标记后， 平均只需要平均只需要 大 概大 概 1 次 测次 测 试。试。 超前搜索超前搜索 貌似匹配，其实远未结束貌似匹配，其实远未结束 关键字的识别关键字的识别 DO99K=1,10/循环语句循环语句 DO99K=1.10/赋值语句赋值语句 IF(5.EQ.M)I=10/逻辑逻辑IF IF(5)=55/自定义标识符自定义标识符 标识符的识别标识符的识别 常数的识别常数的识别 3HABC/文字常数，等同于文字常数，等同于“ABC” 5.EQ.M和和5.E08 算符和界符的识别算符和界符的识别 +, -, *=, , 补充知识：算术补充知识：算术IF语句语句 IF(s

47、calar-numeric- expression)label，label， label 首先计算数值表达式，如果为首先计算数值表达式，如果为 负值，则分支到第一个标签；负值，则分支到第一个标签； 如果得到如果得到0，则分支到第二个，则分支到第二个 标签；如果得到正值，则分支标签；如果得到正值，则分支 到第三个标签。到第三个标签。 3.2.3 状态转换图状态转换图(Transition diagram) n 状态用圆圈表示，状态之间用箭状态用圆圈表示，状态之间用箭 弧连结弧连结 n 结束状态用双圈表示结束状态用双圈表示 n 箭弧上的标记（字符）代表在射箭弧上的标记（字符）代表在射 出结点（即箭

48、弧始结点）状态下出结点（即箭弧始结点）状态下 可能出现的输入字符或字符类。可能出现的输入字符或字符类。 说明：说明： n 此图用于识别一般情况下的标识符此图用于识别一般情况下的标识符 n 终态上打个终态上打个* *号表示多读进了一个不属于标识符部分的字号表示多读进了一个不属于标识符部分的字 符，应把它退还给输入串符，应把它退还给输入串 n 如果在状态如果在状态0 0时输入字符不为时输入字符不为“字母字母”，则意味着这个转，则意味着这个转 换图不工作换图不工作 关系算符的转换图关系算符的转换图 0 5 1 6 2 4 8 3 7 return(relop, LE) return(relop, N

49、E) return(relop, LT) return(relop, GE) return(relop, GT) return(relop, EQ) 开始开始 = = * * other other 标识符和保留字的转换图标识符和保留字的转换图 91011 开始开始 letterother * letter或或digit return(installId( ) 无符号数的转换图无符号数的转换图 开始开始 19 12 131415161718 digit digit digit digit digit digit other .E+/ E digit other other return( in

50、stallNum( ) ) * number digit+ (. .digit+)? (E (+ | )? digit+)? 空白空白的转换图的转换图 ws delim+ delim blank | tab | newline 21 22 开始开始delimother * delim 20 n 符号符号 +、- n 整数整数 10进制：进制：11 8进制：进制：011 16进制：进制：0 x11 long形：形：123l、123L n 实数实数 10进制形式：进制形式： 0.123、.123、123.0、123.、0.0 指数形式：（指数形式：（e或或E前面必须有数字，且后面指数必须是前面必须

51、有数字，且后面指数必须是 整数整数 123E3、123e3 思考：识别思考：识别C语言语言 中数字的状态转中数字的状态转 换图？换图？ 几点限制：几点限制： n 关键字都是保留字关键字都是保留字 n 关键字不设置专门的转换图，而是用一张保留字表来管理关键字不设置专门的转换图，而是用一张保留字表来管理 n 关键字、标识符和常数之间没有确定的运算符或界符做间关键字、标识符和常数之间没有确定的运算符或界符做间 隔，则必须至少用一个空白符做间隔隔，则必须至少用一个空白符做间隔 加了这几点限制后，单词符号的识别就可以不用超前搜索加了这几点限制后，单词符号的识别就可以不用超前搜索 一个简单的状态转换图一个

52、简单的状态转换图 3.2.4状态转换图的实现状态转换图的实现 Ch strToken GetChar GetBC Concat IsLetter, IsDigit Reserve Retract InsertId InsertConst PL/0的的 词法分词法分 析程序析程序 3.4 词法分析器的自动生成词法分析器的自动生成 nLex程序包括三个部分程序包括三个部分 声明声明 翻译规则翻译规则 辅助过程辅助过程 nLex程序的翻译规则程序的翻译规则 p1动作动作1 p2动作动作2 pn动作动作n 3.4 词法分析器的自动生成词法分析器的自动生成 n 用用Lex建立词法分析器的步骤建立词法分析

53、器的步骤 Lex 编译器编译器 Lex源程序源程序lex.l lex.yy.c C 编译器编译器 lex.yy.cLex.yy.exe Lex.yy.exe 输入流输入流 记号序列记号序列 3.4 词法分析器的自动生成词法分析器的自动生成 n例例-声明部分声明部分 /* %和和%是声明规则中的特殊的括号，括号中的内是声明规则中的特殊的括号，括号中的内 容直接复制到容直接复制到lex.yy.c中，不做任何处理。中，不做任何处理。 */ % /* need this for the call to atof() below */ #include % DIGIT 0-9 ID a-za-z0-9*

54、 3.4 词法分析器的自动生成词法分析器的自动生成 n 例例-翻译规则部分翻译规则部分 % DIGIT+ printf( An integer: %s (%d)n, yytext, atoi( yytext ) ); DIGIT+.DIGIT* printf( A float: %s (%g)n, yytext, atof( yytext ) ); if|then|begin|end|procedure|function printf( A keyword: %sn, yytext ); 3.4 词法分析器的自动生成词法分析器的自动生成 n 例例-翻译规则部分翻译规则部分(contd) ID

55、printf( An identifier: %sn, yytext ); +|-|*|/ printf( An operator: %sn, yytext ); n* /* eat up one-line comments */ tn+ /* eat up whitespace */ . printf( Unrecognized character: %sn, yytext ); 3.4 词法分析器的自动生成词法分析器的自动生成 n例例-辅助过程部分辅助过程部分 % main( argc, argv ) int argc; char *argv; +argv, -argc; /* skip

56、over program name */ if ( argc 0 ) yyin = fopen( argv0, r ); else yyin = stdin; yylex(); 3.4 Flex的的执行过程执行过程 1、安装、安装flex 2、编写、编写lex源文件，例如源文件，例如mylex.l 3、在、在dos命令中敲入命令中敲入flex mylex.l，系统自动生成，系统自动生成mylex.yy程程 序，请注意序，请注意环境变量中添加了环境变量中添加了flex的执行文件路径，例如：的执行文件路径，例如： C:Program FilesGnuWin32bin 4、用、用vc6.0打开打开m

57、ylex.yy.c程序，编译并运行该程序程序，编译并运行该程序 5、如果报错，请检查以下配置：、如果报错，请检查以下配置： toolsoptionsdirectories，添加，添加include，library和和execute files项目项目 projectsettingslink找到找到object/library项目，输入项目，输入libfl.a 6、如果需要对文件进行扫描，可以采用命令行的方式，或、如果需要对文件进行扫描，可以采用命令行的方式，或 者在者在projectsettingsdebug找到找到program arguments项，项， 填入文件的名称，例如填入文件的名称，例如inputfile.txt 例例3.1 写一个文法，使其语言是奇数集，且每个奇数不以写一个文法，使其语言是奇数集，且每个奇数不以0开头。开