编译原理chapter3

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

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

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

4、的问题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 如果一个种别只含有一个单词符号，那么对于这个单词符如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自身了。号，种别编码就完全代表它自身了。n 若

6、一个种别含有多个单词符号，那么，对于它的每个单词若一个种别含有多个单词符号，那么，对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的符号，除了给出种别编码之外，还应给出有关单词符号的属性信息。属性信息。n 单词符号的属性是指单词符号的特征或特性。属性值则是单词符号的属性是指单词符号的特征或特性。属性值则是反映特性或特征的值。反映特性或特征的值。n 例如，对于某个标识符，常将存放它有关信息的符号表项例如，对于某个标识符，常将存放它有关信息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属性值。表项的指针

7、作为其属性值。举例举例作为例子考虑下述作为例子考虑下述C+代码段：代码段： while (i=j) i- -; 经词法分析器处理后，它将转换为如下的单词符号序列：经词法分析器处理后，它将转换为如下的单词符号序列： = , - 扫描器作为独立的子程序扫描器作为独立的子程序词法分析器语法分析器符号表源程序记号取下一个记号作为独立的遍：简单，但需增加额外的开销作为独立的遍：简单，但需增加额外的开销作为独立的子程序：节省内存作为独立的子程序：节省内存(PL/0)相关问题相关问题n 符号表的查填兼顾问题符号表的查填兼顾问题兼顾：兼顾：token自身值作为符号表的入口自身值作为符号表的入口Token串长度

8、统一，可放宽对标识符的限制，但要增加串长度统一，可放宽对标识符的限制，但要增加额外负担额外负担不兼顾：不兼顾： token自身值就是标识符、常数本身的符号串自身值就是标识符、常数本身的符号串速度快，但要限制标识符的长度速度快，但要限制标识符的长度n 发现词法错误发现词法错误行、列计数行、列计数发现并定位词法错误发现并定位词法错误一种符号表的数据结构一种符号表的数据结构数组symtablelexptr 记号divdivmodmodidididid属性01234d i v EOS m o d EOS c o u n t EOS i EOS数组lexemes3.2 正规式与有限自动机正规式与有限自动

9、机本节掌握内容：本节掌握内容：n正规式的定义正规式的定义n根据条件写正规式根据条件写正规式nDFA和和NFA的定义的定义n正规式到正规式到NFA以及以及NFA到到DFA的转换的转换3.3.1 正规式与正规集正规式与正规集定义：定义：n 和和 都是都是 上的正规式，表示的正规集分别为上的正规式，表示的正规集分别为 和和 ；n a , 则则a是是上的一个正规式，表示的正规集为上的一个正规式，表示的正规集为a;n e1和和e2都是都是上的正规式，则上的正规式，则(e1|e2), e1e2和和(e1)*也也都是正规式，表示的正规集分别为都是正规式，表示的正规集分别为L(e1) L(e2), L(e1)

10、L(e2)(连接积）和（连接积）和（L(e1)*（闭包）（闭包）;n 正规式所表示的字集叫做正规式所表示的字集叫做上的正规集上的正规集举例：举例：=a, b正规式正规式正规集正规集ba*上所有以上所有以b为首后跟着任意多个为首后跟着任意多个a的字的字a(a|b)*上所有以上所有以a为首的字；为首的字；(a|b)*(aa|bb)(a|b)* 上所有两个相继的上所有两个相继的a或相继的或相继的b的字的字=A,B,0,1(A|B)(A|B|0|1)*上的上的“标识符标识符”的全体的全体(0|1)(0|1)* 上上“数数”的全体的全体正规式等价：表示的正规集相同正规式等价：表示的正规集相同复杂的例子复

11、杂的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：01001101000010000010111001正规式的性质：正规式的性质：交换律交换律r | s = s | r但是但是rs sr结合律结合律r | (s | t) = (r | s) | tr(st) = (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

12、id letter_(letter_ |digit)* 无符号数集合，例无符号数集合，例1946,11.28,63E8,1.99E 6 digit 0 | 1 | | 9digits digit digit*optional_fraction .digits| optional_exponent ( E ( + | | ) digits ) | numberdigits optional_fraction optional_exponent 简化表示简化表示number digit+ (.digit+)? (E(+| )? digit+)?n 正规式的缩写正规式的缩写r+ = r r* 表示表

13、示1个或者多个实例个或者多个实例r? = r | 表示表示0个或者个或者1个实例个实例abc = a | b | ca z = a | b | c | z正规式和正规文法的等价性正规式和正规文法的等价性n正规式转换成正规文法正规式转换成正规文法规则规则正规式正规式正规文法正规文法规则规则1 A-xyA-xB B-y规则规则2A-x*yA-xB A-yB-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-dBS-aAA-aBA-dB

14、A- B-aBB-dBB- 正规式和正规文法的等价性正规式和正规文法的等价性n正规文法转换成正规式正规文法转换成正规式规则规则正规文法正规文法正规式正规式规则规则1 A-xB B-yA=xy规则规则2 A-xA A-yA=x*y规则规则3 A-x A-yA=x|y正规文法转换成正规式正规文法转换成正规式S-aA|aA-aA|dA|a|dS=aA|aA=(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 Fini

15、te Automata, DFA) 确定有限自动机确定有限自动机(DFA)是一个五元式是一个五元式 M= (S, ,s0, F) 其中其中: 涵义：涵义：nS：有限状态集：有限状态集n ：有穷字母表：有穷字母表n：从从S 至至S的的单值部分映射单值部分映射。(s,a）=s。意味着：。意味着：当现行状态为当现行状态为s、输入字符为、输入字符为a时，将转换到下一个状时，将转换到下一个状态态s。我们称。我们称s为为s的后继状态的后继状态nS0 S：唯一的初态：唯一的初态nF S：终态集（可空）：终态集（可空）状态转换矩阵状态转换矩阵DFA可以用一个矩阵表示，该矩阵的行表示状态，可以用一个矩阵表示，该

16、矩阵的行表示状态，列表示输入字符，矩阵元表示列表示输入字符，矩阵元表示(s,a）的值，该矩）的值，该矩阵称为状态转换矩阵。阵称为状态转换矩阵。例如：例如：M=0,1,2,3,a,b, ,0,3其中其中 为：为： （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 b0 1 21 3 22 1 33 3 3状态转换图：状态转换图：DFA的图形表示的图形表示n 假定假定DFA M 含有含有m个状态个状态n个输入字符，那末，这张图含个输入字符，那末，这张图含有有m个状态

17、结点，每个结点顶多有个状态结点，每个结点顶多有n条箭弧射出和别的结条箭弧射出和别的结点相连接，每条箭弧用点相连接，每条箭弧用 上的一个不同字符作标记，整张上的一个不同字符作标记，整张图含有唯一的初态和若干个（可以是图含有唯一的初态和若干个（可以是0个）终态结点。个）终态结点。 n 对于对于 *中的任何一个字符中的任何一个字符 ，若存在一条从初态结点到某，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字等于成的字等于 ，则称，则称 为为DFA M所识别（读出或接受）。所识别（读出或接受）。n 若若M的初态结点同时又

18、是终态结点，则为空字的初态结点同时又是终态结点，则为空字 可以为可以为M所所识别。识别。DFA M所能识别的字的全体记为所能识别的字的全体记为L(M).正规式：正规式：(a | b)* (aa | bb) (a | b)*正规集：正规集：a, b上两个连续的上两个连续的a或者或者b组成的字组成的字定理：定理： *上的正规集上的正规集V都有一个确定的都有一个确定的DFA与之对应，与之对应，反之也成立。反之也成立。 ：S - S的单值映射决定了的单值映射决定了DFA和和NFA的区别的区别n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41010111000

19、1010 11100010101 11000n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始40n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始410n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始4100n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41001n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始410010n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的

20、二进制数0123开始开始4100101n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41001010n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始410010101n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始4100101010n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始41001010101n例：识别例：识别 =0,1上能被能上能被能5整除的二进制数整除的二进制数0123开始开始4100101010110102 =

21、 10101112 = 710例：例：DFA, ,接受接受 0和和1的个数都是偶数的字符串的个数都是偶数的字符串312011110000开始开始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇13.3.3 非确定有限自动机非确定有限自动机 (Nondeterministic Finite Automata, NFA)一个非确定有限自动机（一个非确定有限自动机（NFA)是一个五元式是一个五元式M= (S, ,S0, F) n S：有限状态集：有限状态集n ：有穷字母表：有穷字母表n 是一个从是一个从S x *到到S的子集的映照，即的子集的映照，即 ：S x *2sn S0 S,是一个非空的初态集；

22、是一个非空的初态集；n F S，是一个终态集（可空），是一个终态集（可空）说明：说明：n NFA也可以表示成一张状态转换图。也可以表示成一张状态转换图。n 假定假定NFA 含有含有m个状态个状态n个输入字符，那末，这个输入字符，那末，这张图含有张图含有m个状态结点，每个结点可以射出若干个状态结点，每个结点可以射出若干条箭弧和别的结点相连接，每条箭弧用条箭弧和别的结点相连接，每条箭弧用 *上的一上的一个字（不一定要不同的字而且可以是空字个字（不一定要不同的字而且可以是空字 ）作标）作标记（称为输入字），整张图至少含有一个的初态记（称为输入字），整张图至少含有一个的初态和若干个（可以是和若干个（可

23、以是0个）终态结点。个）终态结点。n 某结点既可以是初态也可以是终态结点。某结点既可以是初态也可以是终态结点。n 对于对于 *中的任何一个字符中的任何一个字符 ，若存在一条从初态，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有结点到某一终态结点的通路，且这条通路上所有箭弧的标记符连接成的字（忽略那些标记为箭弧的标记符连接成的字（忽略那些标记为 的弧）的弧）等于等于 ，则称，则称 为为NFA M所识别（读出或接受）。所识别（读出或接受）。n 若若M的初态结点同时又是终态结点，或者存在一的初态结点同时又是终态结点，或者存在一条某处态结点到某各终态结点的条某处态结点到某各终态结点的 通路

24、，则为空字通路，则为空字 可以为可以为M所识别。所识别。n 这里应注意这里应注意DFA与与NFA的异同点。的异同点。NFA的例子的例子识别语言识别语言(a|b)*ab 的的NFA12开始开始a0abb识别语言识别语言aa*|bb*的的NFA12开始开始a0abb34 DFA例子例子12开始开始a0abbab识别语言识别语言(a|b)*ab 的的DFA例：下图所示的例：下图所示的NFA能识别的字是含有连续的能识别的字是含有连续的两个两个a或者连续的两个或者连续的两个b的由的由a和和b组成的字。你组成的字。你看出来了吗？看出来了吗？由正规式到由正规式到NFA的替换规则的替换规则AB例例1：正规式：

25、正规式：R=(a*b)*ba(a|b)*其中（其中（a*b)* 和和(a|b)*分别可以看成一个闭包。形分别可以看成一个闭包。形成成A和和G结点。可以画为：结点。可以画为： 例例2：画出（：画出（a|b)*(aa|bb)(a|b)*对应的对应的NFANFA到到DFA的转换子集法的转换子集法1、 _closure( I )若若q I，则，则q _closure( I ) ；若若q I,那么从那么从q出发经任意条出发经任意条弧而能达到的任弧而能达到的任何状态何状态q都属于都属于_closure( I ) ；2、Ia=_closure( J )，其中，其中J是那些可从是那些可从I中的某一中的某一状态

26、出发经过一条状态出发经过一条a弧而到达的状态结点的全体。弧而到达的状态结点的全体。3、假定、假定 =a1,a2,a3.ak,我们构造一张表，此我们构造一张表，此表的每一行含有表的每一行含有K+1列。首行首列为列。首行首列为_closure( x )，其中其中x为为NFA的初始状态结点的闭包。一般而言，的初始状态结点的闭包。一般而言，如果某一行的第一列的状态子集已经确定，例如记如果某一行的第一列的状态子集已经确定，例如记为为I，那么置该行的，那么置该行的i1列为列为Iai。然后，检查该行上。然后，检查该行上的所有状态子集，看他们是否已在表的第一列中出的所有状态子集，看他们是否已在表的第一列中出现

27、，把未出现的填入到后面空行的第一列。重复上现，把未出现的填入到后面空行的第一列。重复上述过程，直到出现在第述过程，直到出现在第i1列上的所有状态子集均列上的所有状态子集均已在第一列上出现。已在第一列上出现。例例：用状态子集法构造图：用状态子集法构造图3.6的状态转换矩阵：的状态转换矩阵： I Ia Ib X,5,1 5,3,1 5,4,15,3,1 5,3,1,2,6,Y 5,4,15,4,1 5,3,1 5,4,1,2,6,Y5,3,1,2,6,Y 5,3,1,2,6,Y 5,4,1,6,Y5,4,1,6,Y 5,3,1,6,Y 5,4,1,2,6,Y5,4,1,2,6,Y 5,3,1,6,

28、Y 5,4,1,2,6,Y5,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确定有限自动机的化简确定有限自动机的化简n等价等价n一致性条件：同为终态或非终态一致性条件：同为终态或非终态n蔓延性条件：对所有输入均到达等价状态蔓延性条件：对所有输入均到达等价状态n 首先把首先把M的状态分为两组：终态组的状态分为两组：终态组3，4，5，6，和非终，和非终态组态组0，1，2n 其次考察终

29、态组，由于其次考察终态组，由于 n 3，4，5，6a 3,4,5,6和和n 3，4，5，6b 3,4,5,6所以不能再划分所以不能再划分再考察再考察0，1，2n 由于由于0，1，2a1，3，它既不属于，它既不属于0，1，2也不属于也不属于3，4，5，6，因此应将其一分为二，由于，因此应将其一分为二，由于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应一分应一分为二

30、为二0，2。n 到此四个分组到此四个分组3，4，5，6，0，1，2。每个组都不。每个组都不可再分。可再分。n 最后，令状态最后，令状态3代表代表3，4，5，6。把原来到达。把原来到达4，5，6的的弧都导入弧都导入3，并删除，并删除4，5，6状态。得到化简的状态。得到化简的DFA.算法实现：从算法实现：从NFA构造构造DFAn 输入：一个输入：一个NFA Nn 输出：一个接受同样语言的输出：一个接受同样语言的DFA Dn 方法：为方法：为D构造转换表构造转换表Dtran，DFA的每个状态是的每个状态是NFA的的状态集，状态集，D将将“并行并行”的模拟的模拟N对输入串的所有可能的移动。对输入串的所

31、有可能的移动。n 我们用以下操作来记录我们用以下操作来记录NFA的状态集的轨迹（的状态集的轨迹（s代表代表NFA的状态，的状态，T代表代表NFA的状态集合）的状态集合）操作操作描述描述_closure(s) 从从NFA状态状态s只经过只经过转换可以到达的状态集转换可以到达的状态集_closure(T) 从从T中的状态只经过中的状态只经过转换可以到达的状态集转换可以到达的状态集 move(T,a)从从T中的状态经过输入符号中的状态经过输入符号a上的转换可以到达的上的转换可以到达的状态集状态集算法实现：从算法实现：从NFA构造构造DFAn 子集构造算法子集构造算法初始时，初始时，_closure(

32、s0)是是Dstates中唯一的状态且未被标记；中唯一的状态且未被标记；While Dstates中存在一个未标记的状态中存在一个未标记的状态T 标记标记T；for 每个输入符号每个输入符号a U= _closure(move(T,a);if U没在没在Dstates中中将将U作为一个未标记的状态添加到作为一个未标记的状态添加到Dstates中；中；DtranT, a = U算法实现：从算法实现：从NFA构造构造DFAn _closure的的计算计算将所有的状态压入栈将所有的状态压入栈stack中；中；将将_closure(T)初始化为初始化为T；While 栈栈stack不空不空 将栈顶元素

33、将栈顶元素 t 弹出栈；弹出栈；for 每个这样的状态每个这样的状态u：从：从 t 到到 u 有一条标记为有一条标记为的边的边 if u不在不在_closure(T)中中 将将u添加到添加到_closure(T)中；中；将将u压入栈压入栈stack中；中；3.3.4 正规文法与有限自动机的等价性正规文法与有限自动机的等价性正规文法：正规文法：左线性文法：左线性文法： U a或或U Va;右线性文法：右线性文法： U a或或U aV；其中，其中，U，V VN，a VT结论：结论：（1）对每一个右线性或者左线性正规文法）对每一个右线性或者左线性正规文法G，都存在一个，都存在一个有限自动机有限自动机

34、(FA)M，使得，使得L(M) = L(G)。（2）对每一个）对每一个FA M，都存在一个右线性正规文法，都存在一个右线性正规文法GR和左和左线性正规文法线性正规文法GL，使得，使得L(M) = L(GR) = L(GL)A、右线性文法转换成自动机、右线性文法转换成自动机（1）增加结点）增加结点Z为终止状态（为终止状态（G的的中没有中没有Z）（2）以每一个非终结符号作为状态的结点；）以每一个非终结符号作为状态的结点；（3）对于）对于U-a的每个规则，引一条从的每个规则，引一条从U到到Z的的弧，其标记为弧，其标记为a；（4）对于）对于U-aV的每个规则，引一条从的每个规则，引一条从U到到V的的弧

35、，其标记为弧，其标记为a；假设右线性文法为，求与其对应的自动机假设右线性文法为，求与其对应的自动机A - 0 | 0B | 1DB - 0D | 1CC - 0 | 0B | 1DD - 0D | 1DB、左线性文法转换成自动机、左线性文法转换成自动机（1）增加结点）增加结点S为开始状态（为开始状态（S 不属于不属于VN）；）；（2）以每一个非终结符号作为状态的结点；）以每一个非终结符号作为状态的结点；（3）对于）对于U-a的每个规则，引一条从的每个规则，引一条从S到到U的弧，的弧，其标记为其标记为a；（4）对于）对于U - Va的每个规则，引一条从的每个规则，引一条从V到到U的的弧，其标记为

36、弧，其标记为a；例：画出下面正规文法对应的例：画出下面正规文法对应的NFAZ - A0A - A0 | Z1 | 0解：增加一个解：增加一个S作为开始状态作为开始状态A -0，所以引一条从，所以引一条从S到到A的弧，标记为的弧，标记为0；Z - A0，所以引一条从，所以引一条从A到到Z的弧，标记为的弧，标记为0；A - A0，所以引一条从，所以引一条从A到到A的弧，标记为的弧，标记为0；A - Z1，所以引一条从，所以引一条从Z到到A的弧，标记为的弧，标记为1；0001ASZC、自动机转换成右线性文法、自动机转换成右线性文法开始结点作为开始符号；开始结点作为开始符号；若有若有(A, a) =

37、B，即有从一条从，即有从一条从A到到B的弧，且其的弧，且其标记为标记为a，则：，则：（1）当）当B不是终态符号时，令不是终态符号时，令A - aB；（2）当）当B是终态符号时，令是终态符号时，令A - a | aB；若开始符号若开始符号S0也是终态符号，则还需要增加一个也是终态符号，则还需要增加一个新的非终结符号新的非终结符号S0作为新的开始符号，并增加一个作为新的开始符号，并增加一个产生式产生式S0 - S0 | 例子：例子：写成右线性文法为：写成右线性文法为：A - 0 | 0B | 1DB - 0D | 1CC - 0 | 0B | 1DD - 0D | 1DD、自动机转换成左线性文法、

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

39、产生式Y -例子：例子：将自动机转换成左将自动机转换成左线性文法线性文法左线性文法为：左线性文法为：F - 0 | C0C - B1B - 0 | C0D - 1 | C1 | D0 | D1 | B0例子例子:设文法设文法GS 0AA 0A | 1S | 0SZA0010NFA:识别识别:(01 | 0)*0对吗？对吗？下面将如下面将如何转换为何转换为DFA3.2 词法分析器的设计词法分析器的设计输入和预处理输入和预处理n 词法分析器工作的第一步是输入源程序文本。输入串一般词法分析器工作的第一步是输入源程序文本。输入串一般放在一个缓冲区中，这个缓冲区称输入缓冲区。放在一个缓冲区中，这个缓冲区

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

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

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

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

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

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

46、说明：说明：n 此图用于识别一般情况下的标识符此图用于识别一般情况下的标识符n 终态上打个终态上打个* *号表示多读进了一个不属于标识符部分的字号表示多读进了一个不属于标识符部分的字符，应把它退还给输入串符，应把它退还给输入串n 如果在状态如果在状态0 0时输入字符不为时输入字符不为“字母字母”，则意味着这个转，则意味着这个转换图不工作换图不工作关系算符的转换图关系算符的转换图 051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, E

47、Q)开始开始=*otherother标识符和保留字的转换图标识符和保留字的转换图91011开始开始letterother*letter或或digitreturn(installId( )无符号数的转换图无符号数的转换图开始开始1912131415161718digitdigitdigitdigitdigitdigitother.E+/ Edigitotherotherreturn( installNum( ) )*number digit+ (. .digit+)? (E (+ | )? digit+)? 空白空白的转换图的转换图ws delim+delim blank | tab | new

48、line 2122开始开始delimother*delim20n 符号符号+、-n 整数整数10进制：进制：118进制：进制：01116进制：进制：0 x11long形：形：123l、123Ln 实数实数10进制形式：进制形式：0.123、.123、123.0、123.、0.0指数形式：（指数形式：（e或或E前面必须有数字，且后面指数必须是前面必须有数字，且后面指数必须是整数整数123E3、123e3思考：识别思考：识别C语言语言中数字的状态转中数字的状态转换图？换图？几点限制：几点限制：n 关键字都是保留字关键字都是保留字n 关键字不设置专门的转换图，而是用一张保留字表来管理关键字不设置专门

49、的转换图，而是用一张保留字表来管理n 关键字、标识符和常数之间没有确定的运算符或界符做间关键字、标识符和常数之间没有确定的运算符或界符做间隔，则必须至少用一个空白符做间隔隔，则必须至少用一个空白符做间隔加了这几点限制后，单词符号的识别就可以不用超前搜索加了这几点限制后，单词符号的识别就可以不用超前搜索一个简单的状态转换图一个简单的状态转换图3.2.4状态转换图的实现状态转换图的实现ChstrTokenGetCharGetBCConcatIsLetter, IsDigitReserveRetractInsertIdInsertConstPL/0的的词法分词法分析程序析程序3.4 词法分析器的自动

50、生成词法分析器的自动生成nLex程序包括三个部分程序包括三个部分 声明声明 翻译规则翻译规则 辅助过程辅助过程nLex程序的翻译规则程序的翻译规则 p1动作动作1 p2动作动作2 pn动作动作n3.4 词法分析器的自动生成词法分析器的自动生成n 用用Lex建立词法分析器的步骤建立词法分析器的步骤Lex编译器编译器Lex源程序源程序lex.llex.yy.cC编译器编译器lex.yy.cLex.yy.exeLex.yy.exe输入流输入流记号序列记号序列3.4 词法分析器的自动生成词法分析器的自动生成n例例-声明部分声明部分/* %和和%是声明规则中的特殊的括号，括号中的内是声明规则中的特殊的括

51、号，括号中的内容直接复制到容直接复制到lex.yy.c中，不做任何处理。中，不做任何处理。 */%/* need this for the call to atof() below */#include % DIGIT 0-9ID a-za-z0-9*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|t

52、hen|begin|end|procedure|function printf( A keyword: %sn, yytext );3.4 词法分析器的自动生成词法分析器的自动生成n 例例-翻译规则部分翻译规则部分(contd)ID printf( An identifier: %sn, yytext );+|-|*|/ printf( An operator: %sn, yytext );n* /* eat up one-line comments */ tn+ /* eat up whitespace */. printf( Unrecognized character: %sn, yyt

53、ext );3.4 词法分析器的自动生成词法分析器的自动生成n例例-辅助过程部分辅助过程部分%main( argc, argv )int argc;char *argv;+argv, -argc; /* skip over program name */if ( argc 0 ) yyin = fopen( argv0, r );else yyin = stdin;yylex();3.4 Flex的的执行过程执行过程1、安装、安装flex2、编写、编写lex源文件，例如源文件，例如mylex.l3、在、在dos命令中敲入命令中敲入flex mylex.l，系统自动生成，系统自动生成mylex.

54、yy程程序，请注意序，请注意环境变量中添加了环境变量中添加了flex的执行文件路径，例如：的执行文件路径，例如：C:Program FilesGnuWin32bin 4、用、用vc6.0打开打开mylex.yy.c程序，编译并运行该程序程序，编译并运行该程序5、如果报错，请检查以下配置：、如果报错，请检查以下配置：toolsoptionsdirectories，添加，添加include，library和和execute files项目项目projectsettingslink找到找到object/library项目，输入项目，输入libfl.a6、如果需要对文件进行扫描，可以采用命令行的方式，或、如果需要对文件进行扫描，可以采用命令行的方式，或者在者在projectsettingsdebug找到找到program arguments项，项，填入文件的名称，例如填入文件的名称，例如inputfile.txt例例3.1写一个文法，使其语言是奇数集，且每个奇数不以写一个文法，使其语言是奇数集，且每个奇数不以0开头。开头。n 解：文法解：文法G(N)：