第二章 形式语言及自动机理论

1、主要内容：主要内容：l文法及文法二义性文法及文法二义性l文法等价变换文法等价变换lDFADFA与与NFANFA等价性等价性lDFADFA化简化简l正则表达式正则表达式l字母表字母表l符号串符号串l符号串的连接符号串的连接l符号串的方幂符号串的方幂l前缀和后缀前缀和后缀l子字符串子字符串l符号串集合符号串集合l符号串集合的乘积符号串集合的乘积l符号串集合的方幂符号串集合的方幂l符号串集合的正闭包符号串集合的正闭包l符号串集合的星闭包符号串集合的星闭包l语言语言 给定字母表给定字母表，则，则 上任一字符串集合就上任一字符串集合就是是上的一个语言上的一个语言基本概念基本概念l文法能清晰地描述程序设计

2、语言的语法构成文法能清晰地描述程序设计语言的语法构成 易于理解。易于理解。l文法能自动地构造有效的语法分析器，检文法能自动地构造有效的语法分析器，检 查源程序是否符合语言规定的语法形式。查源程序是否符合语言规定的语法形式。l文法定义可以了解程序设计语言的结构，有文法定义可以了解程序设计语言的结构，有 利于将源程序转化为目标代码，以及检查出利于将源程序转化为目标代码，以及检查出 语法错误。语法错误。l基于文法实现的语言易于扩展基于文法实现的语言易于扩展l文法文法G G定义为四元组定义为四元组(V(VT T,V,VN N,S,P),S,P)V VT T是有限的终极符集合是有限的终极符集合 V VN

3、 N是有限的非终极符集合是有限的非终极符集合S S是开始符，是开始符，S S V VN NP P是产生式的集合，且具有下面的形式：是产生式的集合，且具有下面的形式： ，其中，其中 ，( (V VT T V VN N ) )* *lO O型文法型文法: : 也称为短语文法，其产生式具有形也称为短语文法，其产生式具有形式式: : ，其中，其中 , ,(V(VT T V VN N) )* *，并且，并且 至少至少含一个非终极符含一个非终极符 。l1 1型文法型文法: : 也称为上下文有关文法。它是也称为上下文有关文法。它是0 0型文型文法的特例，要求法的特例，要求| | | | | | | (S|

4、(S 例外，但例外，但S S不得出现于产生式右部不得出现于产生式右部) )。l2 2型文法型文法: : 也称为上下文无关文法。它是也称为上下文无关文法。它是1 1型文型文法的特例，即要求产生式左部是一个非终极符法的特例，即要求产生式左部是一个非终极符: : AA 。l3 3型文法型文法: : 也称为正则文法。它是也称为正则文法。它是2 2型文法的特型文法的特例，即产生式的右部至多有两个符号，而且具例，即产生式的右部至多有两个符号，而且具有下面形式之一有下面形式之一: A a : A a ，A a BA a B其中其中A,BA,B V VN N ，a a V VT T 。 l定义为四元组定义为四

5、元组(V(VT T,V,VN N,S,P),S,P)V VT T是有限的终极符集合是有限的终极符集合 V VN N是有限的非终极符集合是有限的非终极符集合S S是开始符，是开始符，S S V VN NP P是产生式的集合，且具有下面的形式：是产生式的集合，且具有下面的形式： A AX X1 1X X2 2XXn n 其中其中A A V VN N，X Xi i (V (VT T V VN N) ) ，右部可空。，右部可空。l推导推导：如果：如果A A是一个产生式，则有是一个产生式，则有 A A , ,其中其中表示一步推导表示一步推导( (用用A A ) )。这时称这时称是由是由 A A 直接推导

6、的。直接推导的。 的含义是，的含义是，使用一条规则，代替使用一条规则，代替左边的某个符号，产左边的某个符号，产生生右端的符号串右端的符号串l + + : : 表示表示 通过一步或多步可推导出通过一步或多步可推导出 l * * : : 表示表示 通过通过0 0步或多步可推导出步或多步可推导出 l句型：句型： 如果有如果有S S* * ，则称符号串，则称符号串 为为CFGCFG的的 句型句型 。我们用。我们用SF(G)SF(G)表示文法表示文法G G的所有句的所有句型的集合型的集合 l句子：句子： 如果如果 只包含终极符，则称只包含终极符，则称 为为CFGCFG的句的句子，其中子，其中S S是文法

7、的开始符是文法的开始符 l语言：语言： L(G)= u| S L(G)= u| S + + u ,u u ,u V VT T* * 。 文法文法G G所定义的语言是其开始符所能推导所定义的语言是其开始符所能推导的所有终极符号串的所有终极符号串( (句子句子) )的集合。的集合。 l最左（右）推导：最左（右）推导： 如果进行推导时选择的是句型中的最左如果进行推导时选择的是句型中的最左( (右）右）非终极符，则称这种推导为最左非终极符，则称这种推导为最左( (右右) )推导，推导，并用符号并用符号lmlm（rmrm）表示最左（右）推导。）表示最左（右）推导。 l左（右）句型：左（右）句型： 用最左

8、推导方式导出的句型，称为左句型，用最左推导方式导出的句型，称为左句型，而用最右推导方式导出的句型，称为右句型而用最右推导方式导出的句型，称为右句型( (规范句型规范句型) )。l结论：结论： 每个句子都有相应的最右和最左推导（但对每个句子都有相应的最右和最左推导（但对句型此结论不成立）句型此结论不成立） l短语：短语：设设S S是文法的开始符，是文法的开始符，是句型是句型( (即即有有S S * *），如果满足条件：），如果满足条件：S S * * A A A A + + 则称则称 是句型是句型的一个短语。的一个短语。 l直接短语（简单短语）：直接短语（简单短语）：如果满足条件：如果满足条件：

9、S S * * A A A A 则称则称 是句型是句型的一个简单短语。的一个简单短语。 l句柄：句柄：一个句型可能有多个简单短语，其中一个句型可能有多个简单短语，其中最左的简单短语称之为句柄。最左的简单短语称之为句柄。 q语法分析树语法分析树( (简称分析树简称分析树) )用来描述句型的结构，是句用来描述句型的结构，是句型推导的一种树型表示。文法型推导的一种树型表示。文法 G=(VG=(VN N,V,VT T,S,P),S,P)，则称，则称满足下面条件的树为满足下面条件的树为G G的一棵分析树：的一棵分析树：1. 1. 每个节点都有每个节点都有G G的一个文法符号，并且根节点标的一个文法符号，

10、并且根节点标 有初始符有初始符S S，非叶节点标有非终极符，叶节点标有，非叶节点标有非终极符，叶节点标有 终极符或非终极符或终极符或非终极符或 。 2.2.如果一个非叶节点如果一个非叶节点A A有有n n个儿子结点个儿子结点( (从左到右）为从左到右）为 X1,X2,.,XnX1,X2,.,Xn，则，则G G一定有产生式一定有产生式 AX1X2 .Xn AX1X2 .Xn 。q线性推导：线性推导：我们称用我们称用符号进行的推导为线性推导符号进行的推导为线性推导 。q树型推导与线性推导的不同：树型推导与线性推导的不同：线性推导指明了推导的线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。

11、因此，句顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵分析树型一般只有一棵分析树( (如果无二义性如果无二义性) )，而线性推导，而线性推导则可很多。则可很多。v二义性文法：如果一个句型有两棵不同二义性文法：如果一个句型有两棵不同的语法分析树，则称其文法具有二义性的语法分析树，则称其文法具有二义性v文法文法G=( +,*,I,(,), E, E, P),其中其中P为：为：l E il E E + El E E * El E ( E )句型句型i*i+i:推导推导1: E E + E E * E + E i * E + E i * i + E i * i + i推导推导1: E E

12、 * E i * E i * E + E i * i + E i * i + i推导推导1的语法树的语法树E+EEE*EiiiEE*EE+Eii推导推导2的语法树的语法树il增加拓广产生式增加拓广产生式定理：对任一文法定理：对任一文法G1都可以构造文法都可以构造文法G2，使得使得L(G1)=L(G2)，且，且G2的开始符唯一且不的开始符唯一且不出现于任何产生式的右部。出现于任何产生式的右部。l消除空产生式消除空产生式定理：对任一文法定理：对任一文法G1，可构造文法，可构造文法G2，使，使得得L(G1)=L(G2)，且，且G2中无空产生式。中无空产生式。例：例： AaBcD Bb | DBB |

13、 dl消除不可达产生式消除不可达产生式定理：对任一文法定理：对任一文法G1都可以构造文法都可以构造文法G2，使，使得得L(G1)=L(G2)，且，且G2中的每个非终极符必中的每个非终极符必出现在它的某个句型中。出现在它的某个句型中。l消除特型产生式消除特型产生式定理：对任一文法定理：对任一文法G1，可以构造文法，可以构造文法G2，使，使得得L(G1)=L(G2)，且在，且在G2中没有特型产生式。中没有特型产生式。例：例：AB | D | aBBC | bCcDB | dl消除公共前缀消除公共前缀某个非终极符某个非终极符A A有如下的两个产生式：有如下的两个产生式： A A ，A A ( (即有

14、左公共前缀即有左公共前缀) )消除方法：消除方法：1. 产生式形如：产生式形如：A1|2|n| 表示不以表示不以 开头的字符串。开头的字符串。2.引进非终极符引进非终极符A，使产生式替换为：，使产生式替换为： A A | A 1| 2 | nl消除左递归消除左递归一个文法含有下列形式的产生式时一个文法含有下列形式的产生式时（1 1）A AA A A A V VN N, , V V* *（2 2）A AB B B BA A A,B A,B V VN N, , , , V V* *其中（其中（1 1）为）为直接左递归直接左递归，（，（2 2）为）为间接左递间接左递归归，因此文法中只要有，因此文法中

15、只要有A A+ +AA，则称文法为，则称文法为左递归的。左递归的。（1 1）对直接左递归形如：）对直接左递归形如： A A A A | | 消除左递归为：消除左递归为： A A A A A A A A | | （2 2）间接左递归形如：）间接左递归形如： A A B B | | B B A A | b | b 消除左递归：消除左递归： 转为直接左递归形式：转为直接左递归形式： A A A A | b | b | | 或者或者 B B B B | | | b | b 按照直接左递归方式消除。去掉多余的按照直接左递归方式消除。去掉多余的 产生式产生式描述程序设计语言中的单词的识别过程。描述程序设计

16、语言中的单词的识别过程。主要内容：主要内容：l确定有限自动机确定有限自动机DFA(Deterninistic FA)DFA(Deterninistic FA)l非确定有限自动机非确定有限自动机NFA(Nondeterninistic FA)NFA(Nondeterninistic FA)lNFANFA到到DFADFA的转换的转换lDFADFA的化简的化简l确定有限自动机确定有限自动机DFADFA为一个五元组为一个五元组 ( ( ,SS,S,SS,S0 0, ,f f,TS),TS)，其中：，其中：l 是一个有穷字母表，它的每个元素称为一个是一个有穷字母表，它的每个元素称为一个输入字符；输入字符

17、；lSSSS是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称为一个状态；lS S0 0 SSSS是唯一的一个初始状态；是唯一的一个初始状态；lf f是在是在 SS SS SS SS上的转换函数（单值）上的转换函数（单值）lTSTS SSSS，是一个终止状态集，又称为接受状态，是一个终止状态集，又称为接受状态集集l 状态转换图：状态转换图： 结点表示状态，转换边表示转换函数，边结点表示状态，转换边表示转换函数，边 的箭头方向指向转换函数中定义的转换方的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。向。标识出初始状态和终止状态。l 状态转换表：状态转换表：

18、可用二维数组描述。标识出初始状态和终可用二维数组描述。标识出初始状态和终 止状态。止状态。 Trans（ S SI I ，a） S SJ JlDFA M=( a,b, S,U,V,Q, S, f, Q ),l其中其中 f 定义为：定义为： f ( S, a )=U f ( V, a )=U f ( S, b )=V f ( V, b )=Q f ( U, a )=Q f ( Q, a )=Q f ( U, b )=V f ( Q, b )=Ql对于对于 * *中的任何字符串中的任何字符串t,t,若存在一条从初始若存在一条从初始结点到某一终止结点的路径，且这条路上所结点到某一终止结点的路径，且这

19、条路上所有弧的标记符连接成的字符串等于有弧的标记符连接成的字符串等于t,t,则称则称t t可为可为DFA MDFA M所所接受（识别）接受（识别）。lDFA M DFA M 所能接受的字符串的全体记为所能接受的字符串的全体记为L(M).L(M).l初始状态唯一。初始状态唯一。l转换函数转换函数f:SSf:SSSSSS是一个单值函数，也就是一个单值函数，也就是说，对任何状态是说，对任何状态S S SS,SS,和输入符号和输入符号a a , , f(S,a)f(S,a)唯一地确定了下一个状态。即转换函唯一地确定了下一个状态。即转换函数至多确定一个状态。数至多确定一个状态。l没有空边。即没有输入为没

20、有空边。即没有输入为 （ ）l定义定义1 1：一个非确定有限自动机一个非确定有限自动机(NFA)A(NFA)A是是一个五元组一个五元组A=(A=( ,SS,S,SS,S0 0,f,TS).,f,TS).其中其中l 是字母表是字母表l SSSS是状态集是状态集l S S0 0是初始状态集是初始状态集l f f是转换函数，但不要求是单值的是转换函数，但不要求是单值的l f: SS f: SS ( ( ) 2 2SSSSl TS TS是终止状态集是终止状态集l定义定义2 2：设设A A是一个是一个NFANFA，A= (A= ( ,SS,S,SS,S0 0,f,TS),f,TS)则定义则定义L(A)L

21、(A)为从任意初始状态到任意终止状为从任意初始状态到任意终止状态所接受的字符串。态所接受的字符串。 L(A)=L(A)= | |s s0 0 s, ss, s0 0 S S0 0 ss TS l定义定义3 3：设设A A1 1和和A A2 2是同一个字母表上的自动机，是同一个字母表上的自动机，如果有如果有L(AL(A1 1)=L(A)=L(A2 2),),则称则称A A1 1和和A A2 2等价。等价。l定理定理 对于每一个非确定自动机对于每一个非确定自动机A,A,存在一个存在一个确定自动机确定自动机A,A,使得使得L(A)=L(A).L(A)=L(A).l转换转换： 符号合并符号合并 同一状

22、态的不同输出边标有相同的字符。同一状态的不同输出边标有相同的字符。 合并合并 含有含有 边边 l 合并合并 1.1.寻找寻找 边边f(A,f(A, )=B)=B，且，且B B不输出不输出 边。边。 2.2.设设B B的输出边分别为：的输出边分别为：f(B,a1)=B1,f(B,a2)=B2,f(B,an)=Bnf(B,a1)=B1,f(B,a2)=B2,f(B,an)=Bn，则，则1)1)去掉去掉A A、B B间的间的 边。边。2)2)增加边增加边f(A,ai)=Bif(A,ai)=Bi，(i=1,2,n)(i=1,2,n)3)3)若若B B为终止状态，则令为终止状态，则令A A为终止状态。为

23、终止状态。4)4)若从开始状态到若从开始状态到A A有有 路，则令路，则令B B为开始状态。为开始状态。 3.3.重复重复1 1和和2 2，直到无，直到无 边。边。 4.4.如有如有 环路，可把这些状态合并成一个状态，边作环路，可把这些状态合并成一个状态，边作相应处理。相应处理。 l符号合并符号合并：A A：NFA, A:DFANFA, A:DFA 1. 1.令令AA的初始状态为的初始状态为S S0 0=S=S1 1,S,S2 2,S,Sk k, 其中其中S S1 1SSk k是是A A的全部初始状态。的全部初始状态。 2.2.若若S=SS=S1 1,S,Sm m 是是AA的一个状态，的一个状

24、态， a a则定义则定义 f(S,a)=f(Sf(S,a)=f(S1 1,a),a) f(Sf(S2 2,a),a) f(Sf(Sm m,a),a) 3. 3.若若S=SS=S1 1,S,Sn n 是是AA的一个状态的一个状态, ,且存且存 在一个在一个S Si i是是A A的终止状态，则令的终止状态，则令SS为为AA 的终止状态。的终止状态。定义：定义：设I是NFA的状态集的子集，则I的闭包为： _CLOSURE(I)=Iq|f(p, )=q,p_CLOSURE(I)定义：定义：设I是NFA状态集的子集，则Ia=_CLOSURE(J)，J=q|f(p,a)=q,pIlA A：NFA, A:D

25、FANFA, A:DFA 1. 1.令令AA的初始状态为的初始状态为I I0 0= = _CLOSURE(S S1 1,S,S2 2,S,Sk k), , 其中其中S S1 1SSk k是是A A的全部初始状态。的全部初始状态。 2.2.若若I I=S=S1 1,S,Sm m 是是AA的一个状态，的一个状态， a a则定义则定义 f(S,a)=f(S,a)=I Ia a 3. 3.若若I I=S=S1 1,S,Sn n 是是AA的一个状态的一个状态, ,且存且存 在一个在一个S Si i是是A A的终止状态，则令的终止状态，则令I I为为AA 的终止状态。的终止状态。l 状态等价状态等价 对对

26、DFADFA中的两个状态中的两个状态S S1 1和和S S2 2， 如果将它们看作是初始状态，所接受如果将它们看作是初始状态，所接受 的符号串相同，则定义的符号串相同，则定义S S1 1和和S S2 2是等价的。是等价的。l 方法方法 状态合并法状态合并法 状态分离法状态分离法 l 状态合并法（状态吸收方法）状态合并法（状态吸收方法） 寻找等价状态寻找等价状态S S1 1和和S S2 2 如果如果S S2 2为初始状态，则为初始状态，则S S1 1和和S S2 2对调对调 S S2 2的出现修改为的出现修改为S S1 1 删除状态删除状态S S2 2。 l 状态分离法状态分离法 初始化为两个不

27、等价状态集组：非终止状态初始化为两个不等价状态集组：非终止状态 组和终止状态组。组和终止状态组。 对每组中的某个状态分离出与之不等价的状对每组中的某个状态分离出与之不等价的状 态组，直至所有状态组内部状态都等价为止态组，直至所有状态组内部状态都等价为止l描述程序设计语言中单词的一种简单而描述程序设计语言中单词的一种简单而且数学化的工具。且数学化的工具。l表示符号串的构成模式表示符号串的构成模式l正则表达式正则表达式r r定义了一个符号串集合定义了一个符号串集合rs, rs, rsrs内的每个符号串都与内的每个符号串都与r r所定义的模式所定义的模式相匹配，相匹配，rsrs称为由称为由r r生成

28、的语言生成的语言L(r)L(r)l正则表达式中出现的所有符号构成的集正则表达式中出现的所有符号构成的集合为该正则表达式的字母表，用合为该正则表达式的字母表，用S S表示表示 主要内容：主要内容：l基本概念基本概念l正则表达式定义及一些性质正则表达式定义及一些性质l扩充的正则表达式及程序设计语言中扩充的正则表达式及程序设计语言中单词的定义单词的定义l正则表达式的局限性。正则表达式的局限性。l正则表达式与有限自动机等价正则表达式与有限自动机等价l 为给定的字母表，则每个为给定的字母表，则每个S S上的正则表达上的正则表达式将定义式将定义S S上的一个字符串集。上的一个字符串集。 用用R RS S表

29、示表示 上的正则表达式上的正则表达式，用用L(RL(RS S) )表示表示R RS S所表示的字所表示的字符串集合符串集合 。即：函数。即：函数L L表示正则表达式表示正则表达式字字符串集的映射。符串集的映射。l则则R RS S 的定义及其含义如下：的定义及其含义如下： 是是 正则表达式，即正则表达式，即R RS S 。其中。其中L(L()= )= 。 是正则表达式，即是正则表达式，即R RS S 。其中。其中L(L( )= )= 。 c cSS是正则表达式，即是正则表达式，即c c R RS S。其中。其中L(c)=cL(c)=c。 A A和和B B是正则表达式，即是正则表达式，即A A R

30、 RS S，B B R RS S ，则有，则有 ( A )( A ) R RS S，L( (A) )L( (A) )= L(A)= L(A)A | BA | B R RS S，L( A | B )L( A | B )= L(A)= L(A) L(B)L(B)A BA B R RS S，L( A B )L( A B )= L(A)L(B)= L(A)L(B)A A* * R RS S，L( AL( A* *) )= L(A)= L(A)* * l = a,b .= a,b . 正则表达式正则表达式e eabab* *2. a(a|b)2. a(a|b)* * L(e)L(e) 上所有以上所有以a

31、 a为首后跟任意多为首后跟任意多个（包括个（包括0 0个）个）b b的字符串集的字符串集1.1. 上所有以上所有以a a为首的字符串集为首的字符串集q A | B = B | A A | B = B | A | | 的可交换性的可交换性q A | (B | C) =(A | B ) CA | (B | C) =(A | B ) C | | 的可结合性的可结合性q A (B C) =(A B )CA (B C) =(A B )C 连接的可结合性连接的可结合性q A (B | C) =A B | A C A (B | C) =A B | A C 连接的可分配性连接的可分配性q (A | B ) C =A C | B C (A | B ) C =A C | B C 连接的可分配性连接的可分配性q A A* * * =A =A* * 幂的等价性幂的等价性q A A=A=AA=A 是连接的恒等元素是连接的恒等元素 l 一次或多次重复一次或多次重复: A: A+ +l 任何符号任何符号:“”:“”在字母表中任何符号在字母表中任何符号.|.|.l 符号范围符号范围: 0-9 a-z A-Z: 0-9 a-z A-Zl 不在给定范围内的符号不在给定范围内的符号: (a|b|c): (a|b|c)或或 aal 可选可选: : （|-|-）? ?l保留字保