编译原理课件

编译基础---形式语言第一节字母表、串、语言1字母表：有穷非空字符集语言允许使用的字符集—可识别符号例：Σ={a-z,A-Z,0-9,+,_,*,/,’/(,),=….2字符串：字母表中符号组成的任何有穷序列—单词例：scanf,int,3.1415,x1,100,a…3字符串运算：A、B为字符串集合

x，y为字符串连接：

xy称为x和y的连接例：intxx=100积：A•B={xy/x∈A,而y∈B}∈

闭包：A*=A0∪

A1∪

A2∪….

An

其中：A0={ε}，

Ai=Ai-1•A

A+=A*-{ε}A+中的每一个元素即为一个语句例：x=3.14159*r*r形式语言是一个字母表上按某种规则构成的所有串的集合。在语言中这些串称为句子。对于一个句子，存在两个过程：读---识别过程----编译的过程写---推导过程----书写源程序第二节文法的引例

句子：Iamateach.<句子><主语><谓语><代词>I<系词><表语>am<冠词><名词>ateacher<句子>→<主语><谓语><主语>→<代词><谓语>→<系词><表语><系词>→am<表语>→<冠词><名词><冠词>→a<名词>→teacher<代词>→i第三节文法的形式定义一、几个概念1、非终结符—语法变量2、终结符—单词3、产生式—规则二、文法的定义文法是一个四元组，表示为：

G=（VN，VT，P，S）其中：VN---非终结符集合

VT---终结符集合

P---产生式集合

S---开始符号P：α→β

α∈V+

，β∈V*

V=VN∪VT例：描述系表结构的文法，其形式描述为G=（VN，VT，P，S）VN={<主语><谓语><宾语><动词><代词><名词><冠词><句子>}VT={I，am,a,teacher}S=<句子><句子>→<主语><谓语><主语>→<代词><谓语>→<系词><表语><系词>→am<表语>→<冠词><名词><冠词>→a<名词>→teacher}P={<代词>→i再给出一个描述算术表达式的文法例子p={E→E+T|T

T→T*F|F

F→(E)|a

}文法G（E）：G=（VN，VT，P，S）VN={E，T，F}VT={+，*，（，），a}S=E*句型：S=>α,α

∈V*α为句型例：<主语><谓语>Iam<冠词><名词>*句子：S=>w,w

∈VT*w为句子例：Iamateacher*语言：L={w/ww

∈VT*,且S=>w例：{Iamateacher}推导的定义若存在vw0w1...wn=w(n>0)

则记为v=>+w，v推导出w，或w归约到v若有v=>+w，或v=w，则记为v=>*w例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a句子：用符号a，+，*，(和)构成的算术表达式EE+TTFaT*FFaaEE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式α→β，都有

α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外2型文法：对任一产生式A→β，都有A∈VN

，

β∈(VN∪VT)*3型文法：任一产生式A→β的形式都为A→aB或

A→a，其中A∈VN

，B∈VN

，a∈VT文法分类：文法的类型自然语言属于上下文有关文法例：1型（上下文有关）文法文法G[S]：

S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD文法的类型是语法分析的基础例：2型（上下文无关）文法

文法G[S]：

S→AB A→BS|0 B→SA|13型文法G[S]：

S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

是词法分析的基础文法的类型四种文法之间的逐级“包含”关系0型文法1型文法2型文法3型文法文法和语言0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）根据形式语言理论,文法和识别系统间有这样的关系

0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的

1型文法（上下文有关文法）：产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。

2型文法（上下文无关文法CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。

3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合第四节正规文法与有穷自动机一、正规文法1.正规文法能产生语言L(G)2.写出产生语言L(G)的正规文法第四节正规文法与有穷自动机1、正规文法产生的语言的推导例：文法G=（VN，VT，P，S）其中：VN={A，B，C}VT={a,b,c}S=AP:A→aBA→aAB→bBB→bCC→cCC→cL(G)={ambncp/m,n,p≥1}A=>aA=>aaA=>…..=>aa…aB=>aa…abB=>aa…abb…bC=>aa…abb…bcC=>aa…abb…bccC=>aa…abb…bcc…c最小句子：abcP:A→aBA→aAB→bBB→bCC→cCC→c例1：写出产生语言L(G)={ambcn/m,n≥0}的正规文法解：文法G=（VN，VT，P，S）其中：VN={A，C}VT={a,b}S=AP:最小语言：bA→aAA→bA→bCC→cCC→c2.写出产生语言L(G)的正规文法例2：C语言标识符的文法描述L（G）={w/w为字母或‘-’打头的字母数字串}解：P:I→aBI→-BB→aBB→dBB→aB→dI→aIBTTa-a,d

其它2.写出产生语言L(G)的正规文法二、有穷自动机正规文法产生的正规语言用有穷自动机来识别根据文法---写程序----编译时用有穷自动机识别二、有穷自动机1、特点：接收离散输入，状态有穷，只需考虑当前输入和当前内部状态2、原理：有穷自动机控制器读头自左向右逐个扫描并读入输入符号，并且根据控制器的当前状态和当前输入符号控制转入下一个状态３、模型Main(){intI,j,k;有穷控制器４、表示—状态图IBTTa-a,d

其它例：C语言的标识符５、形式定义确定的有穷自动机是一个五元组

M=（Q，∑，δ

，q0，Z）其中：Q是一有穷状态集∑是有穷输入字母表δ是Qx∑→Q的映射函数其含义：δ（q1,a)=q2q0∈

Q,唯一的初态Z是Ｑ的子集，是终态集∈

∈

例：奇偶测试器q00q11q101自动机：Ｍ＝（Q，∑，δ

，q0，Z）

Q＝｛q0,q1}

∑={0,1}q0=q0Z={q1}映射函数：δ（q０,０)=q０δ（q０,１)=q１δ（q1,０)=q１δ（q1,１)=q０例：０００１１０００１q00q11q101三、正规表达式与有穷自动机关系：等价、交换文法G=（VN，VT，P，S）和自动机M=（Q，∑，δ

，q0，Z）可转换为：Ｑ＝VN∪｛Ｔ｝Ｔ为终态

q0＝Ｓ

∑＝VT

Ｚ＝｛Ｔ｝｛Ｔ，S｝若Ｓ→ε映射函数：１、Ｐ：Ａ１→aＡ2,

则δ（Ａ１,a)=A22、Ｐ：Ａ１→a,

则δ（Ａ１,a)=T3、δ（Ｔ,a)=φ

空动作例：已知正规文法Ｇ＝（｛A,B,C},｛a,b,c},P,S}其中：P:A→aAA→aBB→bBB→bCC→cCC→c试写出与其等价的ＦＡ解：Ｍ＝({A,B,C},{a,b,c},δ,S,{T})ABCTaabbcc映射函数：δ（A,a)=A

δ（A,a)=Bδ（B,b)=B

δ（B,b)=Cδ（C,c)=C

δ（C,c)=T练习：Ｌ＝｛w/w是０和１的个数都为偶数的０、１串｝试写出能识别该语言的自动机和描述该语言的文法第五节上下文无关文法－－语法基础一、上下文无关文法文法G=（VN，VT，P，S）

Ｐ：A→

α

α∈（

VN∪VT)＊例：Ｌ＝｛anbn/n≥1}P:S→

aSbS→

ab

二、自嵌套性如果上下文无关文法Ｇ中存在一个终结符，且Ａ＝>α１Ａα２(α１,α２不空），称该上下文无关文法具有可嵌套性例：Ｌ＝｛wcwr/w∈（a

|b)＊,wr是w的反置}P:S→

aSaS→

bSb

，S→

c句子abbacabba三、下推自动机１、模型输入带有穷控制器下推栈２、操作３、接收

b.空动作

δ（q,ε,Z)={(q1,α)}A、读入输入符号，替换栈顶，改变状态，读头右移

δ（q,a,Z)={(q1,α)}空栈：输入串空，栈内也空终态：规定终态，导致进入终态的串被认为接收。此时，栈内可能不为空４、定义ＰＤＡ是一个七元组，

M=（Q,∑,Г,δ,q0,Ｚ0,Ｆ）∑是有穷输入字母表；其中：Q是一有穷状态集Г是下推字母表δ是Qx(∑∪{ε})xГ

→QxГ*的映射函数,其含义：δ(q1,a,Z)=(q2,α)q0∈

Q,唯一的初态;F是Ｑ的子集，是终态集Ｚ0∈Г是栈底符号例：Ｌ＝｛wcwr/w∈（a

|b)＊,wr是w的反置},写出识别该语言的ＰＤＦ解：M=（Q,∑,Г,δ,q0,Ｚ0,Ｆ）Q＝｛q0，q１，q２｝∑＝｛a,b}；Г={Z0，Ａ，Ｂ｝q0＝q0Ｚ0=Ｚ0映射函数：δ(q0,a,Z0)=(q1,AZ0),δ(q0,b,Z0)=(q1,BZ0)δ(q1,a,A)=(q1,AA),δ(q1,a,B)=(q1,AB)δ(q1,b,A)=(q1,BA),δ(q1,b,B)=(q1,BB)δ(q1,c,A)=(q2,A),δ(q1,c,B)=(q2,B)δ(q2,a,A)=(q2,ε),δ(q2,b,B)=(q2,ε)δ(q2,ε,Z0)=(q0,ε),δ(q0,c,Z0)=(q0,ε)句型、推导E

E+TT+T

T+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*aG[E]：E→E+T|T

T→T*F|F

F→(E)|aE

E+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*a对于句子a+a*a有不同的推导规范推导规范句型最左（最右）推导：在推导的任何一步α

β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型语法树设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个内结点都有一个标记，此标记是VN的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈VN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一个产生式语法树---句型推导的直观表示给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)语法树的结果：

从左到右读出叶子的标记所构成的符号串称为句子构造语法树EE+TG[E]：E→E+T|T

T→T*F|F

F→(E)|aT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TTFEE+TTEE+T构造语法树EE+TG[E]：E→E+T|T

T→T*F|F

F→(E)|aT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TTFaT*FFaaa+a*aE

E+TT+T

T+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*aE

E+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*aEE+TTFaT*FFaa语法树看不出推导顺序上下文无关文法的语法树的用处用于描述上下文无关文法句型推导的直观方法

例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

a句型aabbaa的语法树（推导树）叶子结点：树中没有子孙的结点。

从左到右读出推导树的叶子标记连接成的文法符号串，为G[S]的句型。也把该推导树称为该句型的语法树。

但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?

一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程.例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的两个不同的最左推导：

推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i二义文法

若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件二义文法改造为无二义文法G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)规定优先顺序和结合律

如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。句型的分析算法分类分析算法可分为：自上而下分析法：

从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法：

从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种语法树的构造过程。自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树自上而下的语法分析例：文法G：S→cAd

A→ab

A→a识别输入串w=cabd是否为该文法的句子 S S S

c A d

c A d

a

b推导过程：S

cAd

cAd

cabd自下而上的语法分析例：文法G：S→cAd

A→ab

A→a识别输入串w=cabd是否该文法的句子 S

A

A

cabd

ca

bd

ca

b

d

规约过程构造的推导：

cAd

cabdS

cAd词法分析对于词法分析器的要求词法分析器的设计正规表达式与有穷自动机词法分析器的自动产生-LEX词法分析词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(LexicalAnalyzer)又称扫描器(Scanner)：执行词法分析的程序3.1 对于词法分析器的要求一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字：如begin，repeat，

标识符——表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，

界符：逗号、分号、括号和空白输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。例FORTRAN程序IF(5.EQ.M)GOTO100输出单词符号：逻辑IF (34，-)左括号 (2，-)整常数 (20，‘5’的二进制)等号 (6，-)标识符 (26，‘M’)右括号 (16，-)GOTO (30，-)标号 (19，‘100’的二进制)助忆符：直接用编码表示不便于记忆，因此用助忆符来表示编码。例：IF (34，-)(IF，-)左括号 (2，-)((，-)等号 (6，-)(=，-)例C程序while(i>=j)i--;输出单词符号：<while,-><(,-><id,指向i的符号表项的指针><>=,-><id,指向j的符号表项的指针><),-><id,指向i的符号表项的指针><--,-><;,->二、词法分析器作为一个独立子程序词法分析是作为一个独立的阶段，是否应当将其处理为一遍呢？作为独立阶段的优点：结构简洁、清晰和条理化，有利于集中考虑词法分析一些枝节问题。不作为一遍：将其处理为一个子程序。词法分析器词法分析器语法分析器符号表源程序单词符号取下一单词...词法分析器的结构预处理子程序扫描器输入缓冲区扫描缓冲区单词符号输入3.2词法分析器的设计删除无用的空白、跳格、回车和换行等编辑性字符区分标号区、捻接续行和给出句末符等WhatALong…Word

WhatALong…Word…WhatALong…Word…WhatALong…Wo扫描缓冲区↑↑

起点搜索指示器指示器一、扫描缓冲区

二、单词符号的识别:超前搜索以基本字的识别为例：例如:DO99K=1，10

DO99K=1，10IF(5.EQ.M)GOTO55IF(5.EQ.M)GOTO55DO99K=1.10IF(5)=55需要超前搜索才能确定哪些是基本字几点限制——不必使用超前搜索所有基本字都是保留字；用户不能用它们作自己的标识符；基本字作为特殊的标识符来处理;不用特殊的状态图来识别，只要查保留字表。如果基本字、标识符和常数（或标号）之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔三、状态转换图1概念状态转换图是一张有限方向图。213a数字结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧上的标记(字符)代表射出结状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态。识别标识符的状态转换图123字母其他字母或数字*识别整常数的状态转换图123数字其他数字*一个状态转换图可用于识别(或接受)一定的字符串。词法分析器设计流程某程序设计语言的单词符号串集分析词法规则画出识别单词的状态图根据状态图写词法分析器程序123456789101112130空白字母字母或数字非字母与数字数字非数字数字=+*非*,()其它****3状态转换图的实现思想：每个状态结对应一小段程序。做法:1)对不含回路的分叉结，可用一个CASE语句或一组IF-THEN-ELSE语句实现GetChar();if(IsLetter()){…状态j的对应程序段…;}elseif(IsDigit()){…状态k的对应程序段…;}elseif(ch=‘/’){…状态l的对应程序段…;}else{…错误处理…;}ijkl字母数字/3状态转换图的实现2)对含回路的状态结，可对应一段由WHILE语句构成的程序.i字母或数字其它jGetChar();while(IsLetter()orIsDigit()) GetChar();…状态j的对应程序段…3状态转换图的实现3)终态结表示识别出某种单词符号，因此，对应语句为

RETURN(C，VAL)

其中，C为单词种别，VAL为单词自身值.全局变量与过程1)ch

字符变量、存放最新读入的源程序字符2)strToken

字符数组，存放构成单词符号的字符串3)GetChar

子程序过程，把下一个字符读入到ch

中4)GetBC

子程序过程，跳过空白符，直至ch

中读入一非空白符5)Concat

子程序，把ch中的字符连接到strToken

6)IsLetter和

IsDisgital

布尔函数，判断ch中字符是否为字母和数字7)

Reserve

整型函数，对于strToken

中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送08)Retract

子程序，把搜索指针回调一个字符位置9)InsertId整型函数，将strToken中的标识符插入符号表，返回符号表指针10)InsertConst整型函数过程，将strToken中的常数插入常数表，返回常数表指针。intcode,value;strToken:=“”; /*置strToken为空串*/GetChar();GetBC();if(IsLetter())begin while(IsLetter()orIsDigit()) begin Concat();GetChar(); end

Retract();//搜索指针回调 code:=Reserve();//判断是否为保留字 if(code=0)//标识符 begin value:=InsertId(strToken); return($ID,value); end else return(code,-); //保留字end012字母其他字母或数字*空白elseif(IsDigit())beginwhile(IsDigit())beginConcat();GetChar();end Retract(); value:=InsertConst(strToken); return($INT,value);endelseif(ch=‘=’)return($ASSIGN,-);elseif(ch=‘+’)return($PLUS,-);5=*034数字非数字数字*空白6*+elseif(ch=‘*’)begin GetChar(); if(ch=‘*’)return($POWER,-); Retract();return($STAR,-);endelseif(ch=‘;’)return($SEMICOLON,-);elseif(ch=‘(’)return($LPAR,-);elseif(ch=‘)’)return($RPAR,-);elseProcError(); /*错误处理*/将状态图的代码一般化变量curState用于保存现有的状态用二维数组表示状态图：stateTrans[state][char]012字母其他字母或数字*空白curState=初态GetChar();While(stateTrans[curState][ch]有定义){//存在后继状态，读入，拼接Contact();//转入下一状态，读入下一字符curState=stateTrans[curState][ch]；IfcurState是终态then返回strToken中的单词GetChar();｝此处给出的只是一个框架，还有很多细节需要考虑FA正规集正规式DFANFA正规文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.63.3正规表达式与有限自动机易于程序实现易于人工设计程序的单词集合词法规则词法规则3.3正规表达式与有限自动机几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε例如:设∑={a，b}，则∑*={ε,a,b,aa,ab,ba,bb,aaa,...}∑*的子集U和V的连接（积）定义为UV＝{

|

U&

V}

V自身的n次积记为

Vn=VV…V规定V0={

}，令

V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;记V＋＝VV*

，称V+是V的正规闭包。3.3.1正规式和正规集正规集可以用正规表达式（简称正规式）表示。正规表达式是表示正规集一种方法。一个字集合是正规集当且仅当它能用正规式表示。正规式和正规集的递归定义：对给定的字母表

1)

和

都是

上的正规式，它们所表示的正规集为{

}和

;2)任何a

，a是

上的正规式，它所表示的正规集为{a};3)假定e1和e2都是

上的正规式，它们所表示的正规集为L(e1)和L(e2)，则i)(e1|e2)为正规式，它所表示的正规集为L(e1)

L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为L(e1)L(e2)(连接积)，iii)(e1)*为正规式，它所表示的正规集为(L(e1))*（闭包，即任意有限次的自重复连接），仅由有限次使用上述三步骤而定义的表达式才是

上的正规式，仅由这些正规式表示的字集才是

上的正规集。所有词法结构一般都可以用正规式描述。若两个正规式所表示的正规集相同，则称这两个正规式等价。如b(ab)*=(ba)*b (a*b*)*=(a|b)*

L((ba)*b)=L((ba)*)L(b)=(L(ba))*L(b)=(L(b)L(a))*L(b)={ba}*{b}={

,ba,baba,bababa,…}{b}={b,bab,babab,bababab,…}L(b(ab)*)=L(b)L((ab)*)=L(b)(L(ab))*=L(b)(L(a)L(b))*={b}{ab}*={b}{

,ab,abab,ababab,…}={b,bab,babab,bababab,…}∵L(b(ab)*)=L((ba)*b)∴b(ab)*=(ba)*b对正规式，下列等价成立：e1|e2=e2|e1

交换律e1|(e2|e3)=(e1|e2)|e3 结合律e1(e2e3)=(e1e2)e3 结合律e1(e2|e3)=e1e2|e1e3 分配律(e2|e3)e1=e2e1|e3e1 分配律e=e=e

e1e2<>e2e1

L(e1|e2)=L(e1)

L(e2)=L(e2)

L(e1)=L(e2|e1)FA正规集正规式DFANFA3.3.13.3.23.3.3程序的单词集合词法规则3.3.2确定有限自动机(DFA)对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S,

,f,S0,F),其中：1.S:有穷状态集，2.

：输入字母表(有穷)，3.f:状态转换函数，为SS的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状态。4.S0S是唯一的一个初态；5F

S：终态集(可空)。例如：DFAM=({0，1，2，3}，{a，b}，f，0，{3})，其中：f定义如下：f(0，a)=1 f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1 f(2，b)=3f(3，a)=3 f(3，b)=3状态转换矩阵0312aaaa状态转换图bbbb对于

*中的任何字符串

，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字符串等于

，则称

为DFAM所识别(接收)。DFAM所识别的字符串的全体记为L(M)。142300011011练习下图DFA识别的L(M)是什么？A.L(M)=｛以aa或bb开头的字符串｝B.L(M)=｛含aa或bb的字符串｝C.L(M)=｛以aa或bb结尾的字符串｝答案：B0312aaaaDFAbbbb3.3.3非确定有限自动机(NFA)1976年图灵奖

Fortheirjointpaper“Finiteautomata

and

theirdecisionproblems”whichintroducedtheideaofnondeterministicmachines，whichhasprovedtobeanenormouslyvaluableconcept.Theirclassicpaperhasbeenacontinuoussourceofinspirationforsubsequentworkinthisfield.3.3.3非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,

,f,S0,F)，其中：

1S:有穷状态集；

2

：输入字母表(有穷)；

3f:状态转换函数，为S

*2S的部分映射(非单值)；

4S0S是非空的初态集；

5FS

：终态集(可空)。从状态图可看出NFA和DFA的区别：

1

可有多个初态

2

弧上的标记可以是

*中的一个字（甚至可以是一个正规式），而不一定是单个字符；

3同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。021aaa|bb*cab142000110131NFADFA对于

*中的任何字

，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于（忽略那些标记为

的弧），则称

为NFAM所识别(接收)NFAM所识别的字符串的全体记为L(M)。021a|baaa|bbba|b012abab识别所有含相继两个a或相继两个b的字{ambn|m，n1}NFA示例定义：对于任何两个有限自动机M和M’，如果L(M)=L(M’)，则称M与M’等价。自动机理论中一个重要的结论：判定两个自动机等价性的算法是存在的。对于每个NFAM存在一个DFAM’，使得L(M)=L(M’)。亦即DFA与NFA描述能力相同。NFA与DFA1.

假定NFAM=<S,

,

,S0,F>，我们对NFAM的状态转换图进行以下改造：

1)引进新的初态结点X和终态结点Y，X,Y

S，从X到S0中任意状态结点连一条

箭弧，从F中任意状态结点连一条

箭弧到Y。

2)按以下3条规则对NFAM的状态转换图进一步施行替换，直到把这个图转变为每条弧只标记为

上的一个字符或

；其中k是新引入的状态。NFA转换为等价的DFA代之为ikABjijAB代之为ijA|BijBA代之为ijA*ik

jA按下面的3条规则对箭弧进行分裂:例：识别所有含相继两个a或相继两个b的字XY

514236ab

ababab5126ab

abaabb2.把上述NFA确定化——采用子集法.设I是NFA的状态集的一个子集，定义I的

-闭包

-closure(I)为:i)若sI，则s-closure(I)；

ii)若sI，则从s出发经过任意条

弧而能到达的任何状态s’都属于

-closure(I)

即

-closure(I)=I{s’|从某个sI出发经过任意条

弧能到达s’}设a是

中的一个字符，定义Ia=-closure(J)

其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。IIaaIJaK

-closure({1})={1，2}=IJ={5，4，3}Ia=-closure(J)=-closure({5，4，3})={5，4，3，6，2，7，8}61a

234578aa

设a是

中的一个字符，定义Ia=-closure(J)

其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。Ia=？确定化的过程:

不失一般性，设字母表只包含两个a和b，我们构造一张表:｛…｝｛…｝｛…｝｛…｝｛…｝｛…｝｛…｝｛…｝首先，置第1行第1列为

-closure({X})求出这一列的Ia，Ib；然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合...重复上述过程，知道所有第2，3列子集全部出现在第一列为止。IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}XY

514236ab

ababab现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。这张表唯一刻划了一个确定的有限自动机M，它的初态是

-closure({X})

，它的终态是含有原终态Y的子集。不难看出，这个DFAM与M’等价。IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}Iab012132214334465565634Iab0121322143344655656340123546aabbbabaabababFA正规集正规式DFANFA3.3.13.3.23.3.3程序的单词集合词法规则3.3.53.3.5正规式与有限自动机的等价性定理：

1.对任何FAM，都存在一个正规式r，使得L(r)=L(M)。

2.对任何正规式r，都存在一个FAM，使得L(M)=L(r)。对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)证明：

1对

上任一NFAM，构造一个

上的正规式r，使得L(r)=L(M)。首先，在M的转换图上加进两个状态X和Y，从X用

弧连接到M的所有初态结点，从M的所有终态结点用

弧连接到Y，从而形成一个新的NFA，记为M’，它只有一个初态X和一个终态Y，显然L(M)=L(M’)。然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；代之为ijr1r2kikr1r2代之为ijr1|r2ijr2r1代之为ikr1r2*r3ijr1r3kr212354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1最后，X到Y的弧上标记的正规式即为所构造的正规式r显然L(r)=L(M)=L(M’)XYr定理：

1.对任何FAM，都存在一个正规式r，使得L(r)=L(M)。

2.对任何正规式r，都存在一个FAM，使得L(M)=L(r)。证明2:对于

上的正规式r，构造一个NFAM，使L(M)=L(r)，并且M只有一个终态，而且没有从该终态出发的箭弧。下面使用关于r中运算符数目的归纳法证明上述结论。(1)若r具有零个运算符，则r=

或r=

或r=a，其中a

。此时下图所示的三个有限自动机显然符合上述要求。q0q0qfaq0qf(2)假设结论对于少于k(k

1)个运算符的正规式成立。当r中含有k个运算符时，r有三种情形：情形1：r=r1|r2，r1,r2中运算符个数少于k。从而，由归纳假设，对ri存在Mi=<Si,

i,

i,qi,{fi}>，使得L(Mi)=L(ri)，并且Mi没有从终态出发的箭弧（i=1,2）。不妨设S1∩S2=

，在S1∪S2中加入两个新状态q0，f0。

令M=<S1∪S2∪{q0,f0},

1∪

2,

,q0,{f0}>，其中

定义如下：(a)

(q0,

)={q1,q2}(b)

(q,a)=

1(q,a),当q

S1-{f1},a

1∪{

}(c)

(q,a)=

2(q,a),当q

S2-{f2},a

2∪{

}(d)

(f1,

)=

(f2,

)={f0}。

M的状态转换如右图所示。

L(M)=L(M1)∪L(M2)=L(r1)∪L(r2)=L(r)

q0f0M1q1f1M2q2f2

情形2：r=r1r2,设Mi同情形1(i=1,2)。令M=<S1∪S2,

1∪

2,

,q1,{f2}>，其中

定义如下：(a)

(q,a)=

1(q,a),当q

S1-{f1},a

1∪{

}(b)

(q,a)=

2(q,a),当q

S2,a

2∪{

}(c)

(f1,

)={q2}M的状态转换如右图所示。

L(M)=L(M1)L(M2)=L(r1)L(r2)=L(r)。

M1q1f1M2q2f2情形3：r=r1*。设M1同情形1。令M=<S1∪{q0,f0},

1,

,q0,{f0}>，其中q0,f0

S1，

定义如下：(a)

(q0,

)=

(f1,

)={q1,f0}(b)

(q,a)=

1(q,a),当q

S1-{f1},a

1∪{

}。M的状态转换如右图所示。L(M)=L(M1)*=L(r1)*=L(r)至此，结论2获证。

M1q1f1q0f0

1)构造

上的NFAM’使得L(V)=L(M’)首先，把V表示成XYV上述证明过程实质上是一个将正规表达式转换为有限自动机的算法。代之为ijV1V2kikV1V2代之为ijV1|V2ijV2V1代之为ikV1*ij

kV1然后，按下面的三条规则对V进行分裂逐步把这个图转变为每条弧只标记为

上的一个字符或

，最后得到一个NFAM’，显然L(M’)=L(V)(a|b)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY

514236ab

abababIIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}XY

514236ab

abababIab0121322143344655656340123546aabbbabaabababFA正规集正规式DFANFA3.3.13.3.23.3.33.3.5程序的单词集合词法规则易于程序实现易于人工设计DFA3.3.63.3.6确定有限自动机的化简对DFAM的化简:寻找一个状态数比M少的DFAM’，使得L(M)=L(M’)假设s和t为M的两个状态，称s和t等价:如果从状态s出发能读出某个字

而停止于终态，那么同样，从t出发也能读出

而停止于终态；反之亦然。两个状态不等价，则称它们是可区别的。对一个DFAM最少化的基本思想:

把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。具体做法:对M的状态集进行划分首先，把S划分为终态和非终态两个子集，形成基本划分

。假定到某个时候，

已含m个子集，记为

={I(1)，I(2)，

，I(m)}，检查

中的每个子集看是否能进一步划分:对某个I(i)，令I(i)={s1,s2,

,sk}，若存在一个输入字符a使得Ia(i)

不会包含在现行

的某个子集I(j)中（即，Ia(i)中的元素分布在现行划分的多个子集中），则至少应把I(i)分为两个部分。例如，假定状态s1和s2经a弧分别到达t1和t2，而t1和t2属于现行

中的两个不同子集，说明有一个字

，t1读出

后到达终态，而t2读出

后不能到达终态，或者反之，那么对于字a

，s1读出a

后到达终态，而s2读出a

不能到达终态，或者反之，所以s1和s2不等价。s1t1as2t2a

j

i则将I(i)分成两半，使得一半含有s1

:I(i1)={s|sI(i)且s经a弧到达t,

且t与t1属于现行

中的同一子集}

另一半含有s2

:I(i2)=I(i)-I(i1)s1t1as2t2a

j

i一般地，对某个a和I(i)，若Ia(i)

落入现行

中N个不同子集，则应把I(i)划分成N个不相交的组，使得每个组J的Ja都落入的

同一子集。这样构成新的划分。重复上述过程，直到

所含子集数不再增长。对于上述最后划分

中的每个子集，我们选取每个子集I中的一个状态代表其他状态，则可得到化简后的DFAM’。若I含有原来的初态，则其代表为新的初态，若I含有原来的终态，则其代表为新的终态。0123546aabbbabaabababI(1)={0,1,2}I(2)={3,4,5,6}Ia(1)={1,3}

I(11)={0,2}I(12)={1}I(2)={3,4,5,6}I(11)={0,2}Ia(11)={1}Ib(11)={2,5}

I(111)={0}I(112)={2}I(12)={1}

I(2)={3,4,5,6}

Ia(2)={3,6}Ib(2)={4,5}0123546aabbbabaababab0123aabbbaabFA正规集正规式DFANFA3.3.13.3.23.3.33.3.5DFA3.3.6程序的单词集合词法规则易于程序实现易于人工设计148

一.原理单词的词法规则用正规式描述正规式

NFADFAminDFALEX编译器LEX源程序lex.1词法分析程序Lex.yy.c二.用LEX建立词法分析程序的过程3.4词法分析器的自动产生--LEX149

C编译器词法分析程序Lex.yy.c词法分析程序Lex.out或lex.exe

词法分析程序L单词符号输入串状态转换矩阵控制执行程序3.4词法分析器的自动产生--LEX3.4词法分析器的自动产生--LEXlex源程序

lex源程序由三部分组成声明%%识别规则(翻译规则）%%辅助过程

声明包括变量，符号常量和正规定义式。正规定义式是形式如下的一系列定义：d1

r1d2

r2…dn

rn其中，di

表示不同的名字，ri

是正规式识别规则（翻译规则）的形式为：

p1{动作1}p2{动作2}

…

…

pn{动作n}

每个pi是一个正规式，称为词形。

每个{动作i}是一小段C程序代码，它指出了，在识别出词形为pi的单词之后，词法分析器应采取的动作。辅助过程是动作所需要的，这些过程用C书写，可以分别编译。AUXILIARYDEFINITIONletterA|B|...|Zdigit0|1|...|9RECOGNITIONRULES1 DIM {RETURN(1,-)}2 IF {RETURN(2,-)}3 DO {RETURN(3,-)}4 STOP {RETURN(4,-)}5 END {RETURN(5,-)}6 letter(letter|digit)* {RETURN(6,TOKEN)}7 digit(digit)* {RETURN(7,DTB)}8 = {RETURN(8,-)}9 + {RETURN(9,-)}10 * {RETURN(10,-)}11 ** {RETURN(11,-)}12 , {RETURN(12,-)}13 ( {RETURN(13,-)}14 ) {RETURN(14,-)}正规式LEX的工作过程：首先，对每条识别规则Pi构造一个相应的非确定有限自动机Mi；然后，引进一个新初态X，通过

弧，将这些自动机连接成一个新的NFA；最后，把M确定化、最小化，生成该DFA的状态转换表和控制执行程序X

P2

M1MmM2P1Pm

FA正规集正规式DFANFA正规文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.6词法规则词法规则3.3.4正规文法与有穷自动机的等价性文法G=（VN，VT，P，S）和自动机M=（Q，∑，δ

，q0，Z）可转换为：Ｑ＝VN∪｛Ｔ｝Ｔ为终态

q0＝Ｓ

∑＝VT

Ｚ＝｛Ｔ｝｛Ｔ，S｝若Ｓ→ε映射函数：１、Ｐ：Ａ１→aＡ2,

则δ（Ａ１,a)=A22、Ｐ：Ａ１→a,

则δ（Ａ１,a)=