编译原理第04章 词法分析

编译原理

词法分析软件学院网络工程教研室万仲保TEL：704682113907097766E-mail:zbwan@第四章词法分析4.1词法分析程序的设计4.2单词的描述工具4.3有穷自动机4.4正规式和有穷自动机的等价性4.5正规文法和有穷自动机间的转换词法分析程序执行词法分析的程序称为词法分析程序或扫描程序。词法分析程序的主要功能：读入的源程序；输出单词符号。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析程序和语法分析程序的关系词法分析程序的输出词法分析工作分离的意义词法分析程序和语法分析程序的关系词法分析程序的输出单词符号是一个程序设计语言的基本语法符号。单词符号的分类单词符号的一般输出表达方式单词符号的分类1、基本字（关键字）：如PASCAL语言中的begin,end,if,while,var等；2、标识符：用来表示各种名字，如常量名、变量名和过程名等；3、常数（量）：各种类型的常数，如25，3.1415，TRUE和"ABC"等；4、运算符：如+-*/<<=等；5、界符：如逗号，分号，括号等。词法分析程序所输出的单词符号常常采用以下二元式表示：(单词种别，单词自身的值)。单词的种别是语法分析需要的信息，单词自身的值则是编译其它阶段需要的信息。单词符号的一般输出表达方式词法分析工作分离的意义使整个编译程序的结构更简洁、清晰和条理化。词法分析比语法分析简单的多，但是由于源程序结构上的一些细节，常使得识别单词的工作甚为曲折和费时。例如，空白和注释的处理；再比如对于FORTRAN那种受书写格式限制的语言，需在识别单词时进行特殊处理等等。如果统统合在语法分析时一并考虑，显然会使得分析程序的结构复杂得多。

编译程序的效率会改进。大部分编译时间是花费在扫描字符以把单词符号分离出来。把词法分析独立出来，采用专门的读字符和分离单词的技术可大大加快编译速度。另外，由于单词的结构可用有效的方法和工具进行描述和识别，进而可建立词法分析程序的自动构造工具。

增强编译程序的可移植性。在同一个语言的不同实现中，或多或少地会涉及到与设备有关的特征，比如采用ASCII还是EBCDIC字符编码。另外语言的字符集的特殊性的处理，一些专用符号，如PASCAL中的"↑"的表示等等，都可置于词法分析程序中解决而不影响编译程序其它成分的设计。单词的描述工具程序设计语言中的单词是基本语法符号。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，可以建立词法分析技术，进而可以建立词法分析程序的自动构造方法。正规文法正规式正规文法和正规式的转换正规文法（正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a是终结符。正规文法所描述的是VT*上的正规集。多数程序设计语言的单词语法都可用正规文法来描述。正规式正规式也称正则表达式，是表示正规集的数学工具。正规式和它所表示的正规集的递归定义：设字母表为Σ，辅助字母表Σ’={Φ，ε，|，·，*，(，)}。1、ε和Φ都是Σ上的正规式，它们所表示的正规集分别为{ε}和{}；2、任何a∈Σ，a是Σ上的一个正规式，它所表示的正规集为{a}；3、假定e1和e2都是Σ上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1|e2,e1·e2,e1*也都是正规式,它们所表示的正规集分别为L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))*。4、仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式，仅由这些正规式所表示的字集才是Σ上的正规集。示例4.2示例4.3正规式的运算律令={a，b}，上的正规式和相应的正规集的例子有：正规式 正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意个a的串}(ab) {,a,b,aa,ab……所有由a和b组成的串}(ab)(aabb)(ab) {上所有含有两个相继的a或两个相继的b组成的串}例4.2例4.3令Σ={d，·，ε，+，-},则Σ上的正规式d*(·dd*|ε)(ε(+|-ε|)dd*|ε)表示的是无符号数。其中d为0~9中的数字。正规式的运算律设r,s,t为正规式，正规式服从的代数规律有：1、rs=sr “或”满足交换律2、r(st)=(rs)t“或”的可结合律3、(rs)t=r(st) “连接”的可结合律4、r(st)=rsrt 分配律(st)r=srtr 5、r=r,r=r 是“连接”的恒等元素正规文法和正规式的转换正规式转换为正规文法的规则正规文法转换为正规式的规则正规式转换为正规文法的规则将上的一个正轨式转换为文法G=(VN，VT，P，S)，令VT=

确定文法的产生式和的VN规则为：选择识别符号S的生成产生式Sr；若x,y都是正规式，对形如Axy的产生式，可重写为AxBBy（BVN）

对已转换的文法中的形如Axy的产生式，可重写为：AxBAyBxBBy（BVN）对形如Axy的产生式，可重写为：AxAy

不断应用上述规则做变换，直到每个产生式最多含一个终结符为止。示例：例4.4例4.4将R=a(ad)转换成相应的正规文法。解：令S为文法的开始符号，首先形成Sa(ad)，然后形成SaA和A(ad)，再重写第二条产生式形成SaAA(ad)BAB(ad)BB进而变换为SaAAaBAdBABaBBdBB正规文法转换为正规式的规则规则文法产生式正规式1AxBByr=xy2AxA|yr=xy3AxAyr=xy示例：例4.5例4.5G[s]:SaA

AaA AdA

Sa

Aa

AdS=aAa

A=(aAdA)(ad)

=(ad)(ad)将A右端代入S的正规式得：

S=a(ad)(ad)a利用正规式的运算律，可得：

S=a((ad)(ad))

=a(ad)

R=a(ad)4.3有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。有穷自动机分类:确定的有穷自动机（DFA）不确定的有穷自动机（NFA）NFADFA的转换DFA的化简确定的有穷自动机(DeterministicFiniteAutomata)定义示例：例4.6DFA的表示方式：状态转换图状态矩阵相关的定义符号串在自动机上接受符号串在自动机上运行正规式与DFA之间的关系DFA定义一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中：1、K是一个有穷集，它的每个元素称为一个状态；2、Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；3、f是转换函数，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4、S∈K是唯一的一个初态；5、ZK是一个终态集，终态也称可接受状态或结束状态。DFA例：例4.6DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=V f（V,b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q状态转换图一个DFA可以表示成一个状态图(或称状态转换图)。假定DFAM含有m个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出，整个图含有唯一一个初态结点和若干个终态结点，初态结点冠以双箭头“=>”或标以“-”，终态结点用双圈表示或标以“+”，若f(ki,a)=kj，则从状态结点ki到状态结点kj画标记为a的弧。示例DFA的状态图表示f（S，a）=U f（V，a）=Uf（S，b）=V f（V,b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bb状态矩阵一个DFA还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的新状态，即k行a列为f(k,a)的值。用双箭头"=>"标明初态；否则第一行即是初态，相应终态行在表的右端标以1，非终态标以0。示例DFA的矩阵表示f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q字符状态0100符号串在自动机上被接受对于∑*中的任何字符串t，若存在一条从初态结到某一终态结的道路，且这条路上所有弧的的标记符连接成的字符串等于t，则称t可为DFAM所接受，若M的初态结同时又是终态结，则空字可为M所接受（识别）。若t∑*，f(S，t)=P，其中S为DFA

M的开始状态，PZ，Z为终态集。则称t为DFAM所接受（识别）。一个输入符号串t，（我们将它表示成t1tx的形式，其中t1∈∑，tx∈∑*）在DFAM上运行的定义为：f（Q，t1tx）=f（f（Q，t1），tx）

其中Q∈K扩充转换函数f，是K×Σ*→K上的映射，且：

f（Q，）=Q符号串在自动机上运行正规式与DFA之间的关系∑上一个符号串集V∑*是正规的，当且仅当存在一个∑上的确定有穷自动机M，使得V=L(M)。示例：证明t=baab被例4.6的DFA所接受.证明：

f（S，baab）

=f（f（S，b），aab）

=f（V，aab）

=f（f（V，a），ab）

=f（U，ab）

=f（f（U，a），b）

=f（Q，b）

=QQ属于终态。得证。bSUVQaaaba，bb不确定的有穷自动机NFA定义不确定的有穷自动机NFAN=(K，∑，f，S，Z)，其中：

K是一个有穷集，它的每个元素称为一个状态；Σ是一个有穷字母表，它的每个元素称为一个输入符号；f为从K×∑*到K的子集的映射；SK是初始状态集；ZK为终止状态集。示例：例4.7字符串在NFA上的识别NFA和DFA的等价性例4.7一个NFAM=（{0，1，2，3，4}，{a，b}，f，{0}，{2，4}），其中

f（0，a）={0，3}f（0，b）={0，1}f（1，b）={2}f（2，a）={2}f（2，b）={2}f（3，a）={4}f（4，a）={4}f（4，b）={4}状态转换图如右图所示。b0314aaba，b2a，b

a，b若t∈∑*，f(S，t)=P，其中S为N的开始状态，P∈Z，Z为终态集。则称t为NFAN所接受（识别）。对于Σ*中的任何一个串t，若存在一条从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串(不理采那些标记为ε的弧)等于t，则称t可为NFAM所识别(读出或接受)。若M的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结的ε道路，那么空字可为M所接受。字符串在NFA上的识别NFA和DFA的等价性对于每一个NFAM，存在一个DFAM´，使得L（M）=L（M´）。对于任何两个有穷自动机M和M´，如果L（M）=L（M´），则称M和M´是等价的。NFADFA的转换——NFA的确定化NFA确定化定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的自动机L(M)=L(M')。状态集合I的运算定义NFA确定化状态集合I的运算定义状态集合I的-闭包，表示为-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条弧而能到达的状态的集合。状态集合I的任何状态S都属于-closure(I)。状态集合I的a弧转换，表示为move(I,a)定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。示例转换的计算：对于自动机M=(K,∑,f,K0,Kt)，设I={s1,s2,,sj}，a是∑中的一个元素，则move(I,a)=f(s1,a)∪f(s2,a)∪

∪f(sj,a)

状态集合I的运算示例

-closure(0)={0,1,2,4,7}即{0,1,2,4,7}中的任一状态都是从状态0经任意条弧可到达的状态，令A={0,1,2,4,7},则move(A,a)={3,8}，因为在状态0,1,2,4,7中，只有状态2和7有a弧射出，分别到达状态3和8。-closure(3,8)={1,2,3,4,6,7,8}b124ab10a

0356789b返回例4.8a返回例4.8bNFA确定化NFA确定为DFA的构造方法构造NFA的状态K的子集的算法示例：示例一：对NFAN构造其子集——例4.8a示例二：对NFAN确定化——例4.8bNFA确定为DFA的构造方法假设NFAN=(K,,f,K0,Kt)按如下办法构造一个DFAM=(S,,d,S0,St)，使得L(M)=L(N)：1.M的状态集S由K的一些子集组成。用[S1S2...

Sj]表示S的元素，其中S1,S2,,...

Sj是K的状态。并且约定，状态S1,S2,,...

Sj是按某种规则排列的，即对于子集{S1,S2}={S2,S1,}来说，S的状态就是[S1S2]；2.M和N的输入字母表是相同的，即是；3.转换函数是这样定义的：

D([S1,S2,...

,

Sj],a)=[R1,

R2,...

,

Rt]

其中

-closure(move([S1,S2,...

,

Sj],a))=[R1,

R2,...

,

Rt]4.S0=-closure(K0)为M的开始状态；5.St={[Si,Sk,...,Se]，其中[Si,Sk,...,Se]S且{Si

,Sk,,...

Se}∩Kt}构造NFAN的状态K的子集的算法假定所构造的子集族为C,即C=(T1,T2,,...

Ti),其中T1,T2,,...

Ti为状态K的子集。1.开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。2.while（C中存在尚未被标记的子集T）do{标记T；for每个输入字母ado{U:=-closure(move(T,a))；ifU不在C中then

将U作为未标记的子集加在C中}}例4.8aNFAN的状态转换图构造子集的步骤：首先计算ε-closure(0)，令T0=ε-closure(0)={0,1,2,4,7}，T0未被标记，它现在是子集族C的唯一成员。标记T0；令T1=ε-closure(move(T0,a))={1,2,3,4,6,7,8}，将T1加入C中，T1未被标记。

令T2=ε-closure(move(T0,b))={1,2,4,5,6,7}，将T2加入C中，它未被标记。标记T1；计算ε-closure(move(T1,a))，结果为{1,2,3,4,6,7,8}，即T1，T1已在C中。

计算ε-closure(move(T1,b))，结果为{1,2,4,5,6,7,9}，令其为T3，T3加至C中，它未被标记。标记T2，计算ε-closure(move(T2,a))，结果为{1,2,3,4,6,7,8}，即T1，T1已在C中。

计算ε-closure(move(T2,b))，结果为{1,2,4,5,6,7}，即T2，T2已在C中。标记T3，计算ε-closure(move(T3,a))，结果为{1,2,3,4,6,7,8}，即T1。

计算ε-closure(move(T3,b))，结果为{1,2,4,5,6,7,10}，令其为T4，加入C中，T4未被标记。标记T4，计算ε-closure(move(T4,a))，结果为{1,2,3,4,6,7,8}，即T1

计算ε-closure(move(T4,b))结果为{1,2,4,5,6,7}，即T2。至此，算法终止共构造了五个子集：T0={0,1,2,4,7}T1={1,2,3,4,6,7,8}T2={1,2,4,5,6,7}T3={1,2,4,5,6,7,9}T4={1,2,4,5,6,7,10}例4.8bNFAN的状态转换图确定化：构造子集、确定构造的DFAM；作出状态转换图。确定构造的DFAMNFAN构造的DFAM为

S={[T0]，[T1]，[T2]，[T3]，[T4]}Σ={a,b}D([T0]，a)=[T1]D([T2]，a)=[T1]D([T0]，b)=[T2]D([T2]，b)=[T2]D([T1]，a)=[T1]D([T3]，a)=[T1]D([T1]，b)=[T3]D([T3]，b)=[T4]D([T4],a)=[T1]D([T4]，b)=[T2]S0=[T0]St=[T4]不妨将[T0]，[T1]，[T2]，[T3]，[T4]重新命名，以利于书写，或用A，B，C，D，E或用0，1，2，3，4分别表示。作出状态转换图DFA的最小化（化简）最小状态DFA没有多余状态(死状态)：指这样的状态，从该自动机的开始状态出发，任何输入串也不能到达的那个状态。没有两个状态是互相等价（不可区别）。多余状态消除示例状态可区别的示例两个状态s和t等价：满足一致性条件——状态s和t必须同时为可接受状态或不可接受状态。蔓延性条件——对于所有输入符号，状态s和状态t必须转换到等价的状态里。如果有穷自动机的状态s和t不等价，则称这两个状态是可区别的。DFA的最小化方法——分割法DFA最小化实例消除多余状态示例s1s5

s2s7

s2s5

s5s7

s5s6

s3s1

s8s0

s0s1

s3s6010

1

1

0

0

0

1

1

0s0

s1

s2

s3

s4

s5

s6

s7

s8s1s5

s2s7

s2s5

s5s7

s5s6

s3s1

s8s0

s0s1

s3s6010

1

1

0

0

0

1

1

0s0

s1

s2

s3

s4

s5

s6

s7

s8s1s5

s2s7

s2s5

s5s7

s3s1

s0s1010

1

1

0

0

1s0

s1

s2

s3

s5

s7(a)(b)(c)从状态矩阵（a）可知，状态s4、s6、s8不可以从s0出发，经过任何输入串到达的状态，因此，可以将其状态连同射出的弧一并消除。其中（b）为过程，（c）为消除后的状态矩阵。状态可区别的示例如下图所示。状态0和4是可区别的。因为状态4是可接受态(终态)，而0是不可接受态。状态2和3是可区别的，因为读入b后分别到达2和4，而2和4不是等价的。b02134abaaaabbbDFA的最小化方法DFA的最小化

对于一个DFAM=（K,∑,f,k0,kt)，存在一个最小状态DFAM’=（K’,∑,f’,k0’,kt’)，使L(M’)=L(M)。算法的核心是把M的状态集K分成不相交的子集。结论：接受L的最小状态有穷自动机不计同构是唯一的。分割法算法分割法算法1．首先，将M的状态集K按终态与非终态划分为两个子集Z及K-Z，以构成初始分别，记为π＝(z，K-z)。2．设当前的分划π中已含有m个子集，即π＝{I1,I2,…,Im}，其中，属于不同子集的状态是可区分的，而属于同一子集中的诸状态则是待区分的。即需对每一子集Ii={Si1,Si2,…,Sim}中各状态Sir(SirK,1≤r≤n)进行考察，看是否还能对它们再进行区分。例如，Sip和Siq是Ii中的两个状态，若有某个a∑，使f(Sip,a)＝Sju及f(Siq，a)＝Skv，而状态Sju及Skv分别属于π中两个不同的子集Ij和Ik，故Sju和Skv为某一w所区分，从而Sju和Skv必为w所区分，故应将子集Ii进一步划分，使Sip和Siq分别属于Ii的不同的子集。也就是说，对于每一子集Ii及每一a∑，需考察；Iia＝f(Ii，a)＝Uf(Sir，a)。若Iia中的状态分别落于π中的p个不同的子集，则将Ii分为p个更小的状态子集Ii(1),Ii(2),…,Ii(p)，使得对于每一个Ii(j)，f(Ii(j)，a)中的全部状态都落于π的同一子集之中。注意，若对某状态Sir，f

(Sir，a)无意义，则Sir与任何Sir(f(Sir，a)有定义)都是可区分的。这样，每细分一次，就得一个新的分划πnew，且分划中的子集数也由原来的m个变为m+p-1个。分割法算法(2)3．若πnew≠π，则将πnew作为π再重复第二步中的过程，如此等等，直到最后得到一个分划π，使πnew=π，即π中的各个子集不能再划分为止。4．对于所得的最后分划π，从它的每一子集Ij={Sj1,Sj2,…,Sjm}中任选一个状态，比方说Sj1，作为Ij中所含各状态的代表，这些所选出的状态便组成了M’的状态集K’。而且，若Ij中含有M的初态，则Sj1为M‘的初态；若Ij中合有M的终态，则Sj1为M’的一个终态。此外，为构成DFAM’，还应将各子集中落选的状态从原DFAM中则去，并将原来进入这些状态的所有矢线都改为进入它们的代表状态。例4.9将右上图所示的DFAM最小化。解：首先将M的状态分成两个子集：一个由终态(可接受态)组成，一个由非终态组成，这个初始划分P0为：P0=({1，2，3，4}，{5，6，7})，显然第一个子集中的任何状态都与第二个子集中的任何状态不等价。

现在观察第一个子集{1，2，3，4}，在读入输入符号a后，状态3和4分别转换为第一个子集中所含的状态1和4，而1和2分别转换为第二个子集中所含的状态6和7，这就意味着{1，2}中的状态和{3，4}中的任何状态在读入a后到达了不等价的状态，因此{1，2}中的任何状态与{3，4}中的任何状态都是可区别的，因此得到了新的划分P1如下：

P1=({1，2}{3，4}{5，6，7})

下面试图在P1中寻找一个子集和一个输入符号使得这个子集中的状态可区别，P1中的子集{3，4}对应输入符号a将再分割，而得到划分P2=({1，2}，{3}，{4}，{5，6，7})。

P2中的{5，6，7}可由输入符号a或b而分割，得到划分P3=({1，2}，{3}，{4}，{5}，{6，7})。

经过考察，P3不能再划分了。令1代表{1，2}消去2，令6代表{6，7}，消去7，便得到了右下图所示的DFAM′，它是所求最小化的DFAM。正规式和有穷自动机的等价性正规式和有穷自动机的等价性说明：1.

对于∑上的NFAM，可以构造一个∑上的正规式R，使得

L(R)=L(M)。2.对于∑上的一个正规式R，可以构造一个∑上的NFAM，使得L(M)=L(R)。由NFAM求解正规式的方法由正规式构造NFAM的方法构造NFA的形式描述由NFAM求解正规式的方法1、在M的状态转换图上加进二个结点，记为x、y。其中x结点用弧与M的所有初态结点连接，将M的所有终态结点用弧与y结点连接，组成一个等价M，且M’只有x为初态，y为终态。2、运用消结规则逐步消去M’中除x、y之外的所有结点，最后得到的x、y两个结点间弧上的标记即为NFA相应的正规式。消除拓广状态转换图结点的规则示例：例4.10消除拓广状态转换图结点的规则例4.10b0314aaba，b2a，b

a，b由正规式构造NFAM的方法单一的正规式，相应的NFA构造规则：对于正规式，所构造的NFA为；对于正规式ε，所构造的NFA为；对于正规式a，a∈Σ，所构造的NFA为。组合的正规式，若s，t为Σ上的正规式，相应的NFA构造规则：对正规式R=s|t，所构造的NFA(R)为；对正规式R=st，所构造的NFA(R)为；对于正规式R=s*，所构造的NFA(R)为；正规式(s)的NFA同s的NFA一样。示例：例4.11

例4.11a正规式所构造的NFA正规式ε所构造的NFA正规式a(a∈Σ)所构造的NFA正规式R=s|t所构造的NFA(R)其中x是NFA(R)的初态，y是NFA(R)的终态，x到N(s)和N(t)的初态各有一ε弧，从N(s)和N(t)的终态各有一ε弧到y，现在N(s)和N(t)的初态或终态已不作为N(R)的初态和终态了。正规式R=st所构造的NFA(R)其中N(s)的初态成了N(R)的初态，N(t)的终态成了N(R)的终态。N(s)的终态与N(t)的初态合并为N(R)的一个既不是初态也不是终态的状态。正规式R=s*所构造的NFA(R)这里x和y分别是NFA(R)的初态和终态，从x引ε弧到N(s)的初态，从N(s)的终态引ε弧到y，从x到y引ε弧，同样N(s)的终态可沿ε弧的边直接回到N(s)的初态。N(s)的初态或终态不再是N(s)的初态和终态。例4.11为R=(a|b)*abb构造NFAN，使得L(N)=L(R)。解：从左到右分解R，令r1=a，第一个a，则其NFA的状态转换图如下：令r2=b，则其NFA的状态转换图如下：例4.11令r3=r1|r21，则其NFA的状态转换图如下：令r4=r3'，则其NFA的状态转换图如下：例