《第四章词法分析.ppt》由会员分享，可在线阅读，更多相关《第四章词法分析.ppt（78页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第四章第四章 词法分析词法分析(Lexical(Lexical Analysis)Analysis)主要内容：主要内容：单词的描述工具：正规文法和正规式单词的描述工具：正规文法和正规式单词识别系统单词识别系统：有穷自动机有穷自动机词法分析程序的设计词法分析程序的设计词法分析程序的自动构造原理词法分析程序的自动构造原理学习目标学习目标:v掌掌握握：词词法法分分析析程程序序的的构构造造，正正规规式式和和正正规规文文法法到到有有穷穷自自动动机机的的转转换换，N NFAFA到到DFADFA的的转转换换、DFADFA的化简的化简v理理解解：正正规规文文法法、正正规规式式、DFADFA的的概概念念、NF
2、ANFA的的概念概念v了解：词法分析程序的自动构造工具了解：词法分析程序的自动构造工具4.1 单词的描述工具单词的描述工具4.2 有穷自动机有穷自动机4.3 正规式和有穷自动机的等价性正规式和有穷自动机的等价性4.4 正则文法和有穷自动机间的转换正则文法和有穷自动机间的转换4.5 词法分析程序的设计词法分析程序的设计4.6 词法分析程序的自动构造工具词法分析程序的自动构造工具4.1 4.1 单词的描述工具单词的描述工具作用作用:描述单词的构成规则描述单词的构成规则,基于这类描基于这类描述工具建立词法分析技术述工具建立词法分析技术,进而实现词法进而实现词法分析程序的自动构造分析程序的自动构造.工
3、具有工具有:正规文法正规文法 正规式正规式(Regular Expression)(Regular Expression)4.2.1正规文法正规文法多数程序设计语言单词的语法都能用正多数程序设计语言单词的语法都能用正规文法规文法(3型文法型文法)描述描述正规文法回顾正规文法回顾文法的任一产生式文法的任一产生式的形式都为的形式都为AaBAaB或或AaAa，其中其中A A，BVBVN N ，a Va VT T。正规文法描述的是正规文法描述的是V VT T*上的上的正规集正规集例如例如:用用ll表示表示azaz中的任一英文字母，中的任一英文字母，d d表示表示0909中任一数中任一数字字描述描述标识
4、标识符的正符的正规规文法文法为为 llll lld dll d d 描述无符号整数的正描述无符号整数的正规规文法文法 d dd d 4.2.2正规式正规式(正则表达式正则表达式)RegularExpression对于字母表对于字母表，我们感兴趣的是它的一些，我们感兴趣的是它的一些特殊字集正规集。特殊字集正规集。正正规规式是式是描述正规集的方便工具描述正规集的方便工具正规式与正规集的递归定义正规式与正规集的递归定义1.和和都是都是上的正规式，它所表示的正规集分上的正规式，它所表示的正规集分别为别为和和；2.任任何何，是是上上的的正正规规式式，它它所所表表示示的的正规集为；正规集为；3.假假定定1
5、和和2都都是是上上的的正正规规式式，他他们们所所表表示示的的正正规规集集分分别别为为(1)和和(2)，那那么么，以以下也都是正规式和他们所表示的正规集；下也都是正规式和他们所表示的正规集；正规式正规式正规集正规集(1)(1)12(1)(2)1.2(1)(2)1(1)说明说明:算符的优先顺序算符的优先顺序:.和和都是左结合都是左结合4.仅仅由由有有限限次次使使用用上上述述三三步步定定义义的的表表达达式式才才是是上上的的正正规规式式，仅仅由由这这些些正正规规式式所所表表示示的的字字集才是集才是上的正规集。上的正规集。例子例子令令=a=a，bb，上的正规式和相应的正规集有上的正规式和相应的正规集有正
6、规式正规式正规集正规集a aaaa a b b a,ba,babab abab(a(a b)(ab)(a b)b)aa,ab,ba,bbaa,ab,ba,bb a a ,a,aaa,aa,任意任意个个a a串串(a a b)b),a,b,aa,aba,b,aa,ab 所有由所有由a a和和b b 组成的串组成的串 正规式的代数性质正规式的代数性质设设 r，s，t 是正规式，正规式服从的代数规律是：是正规式，正规式服从的代数规律是：1.rs=sr“或或”满足交换律满足交换律2.r(st)=(rs)t“或或”的结合律的结合律3.(rs)t=r(st)“连接连接”的结合律的结合律4.r(st)=rs
7、rt(rs)t=rtst分配分配律律5.r=r=r是是“连接连接”的恒等元素的恒等元素6.6.r r r=rr=r “或或”的抽取律的抽取律 r r=r r rrrr 程序中的单词都能用正程序中的单词都能用正规规式来定义式来定义 令令ll为为azaz的字母，的字母，d d为为0909的数字的数字e e1 1=ll(l l|d d)*e e1 1表示表示标识符标识符集合集合e e2 2=dd dd*e e2 2表示表示无符号整数无符号整数注：注：llll lld dll d d 正正规规式式比比正正规规文文法法更更容容易易让让人人理理解解单单词词是是按按怎怎样样的的规规律律构构成成的的，且且可可
8、以以从从某某个个正正规规式式自自动动地地构构造造识别程序。识别程序。4.2.3正规文法和正规式间的转换正规文法和正规式间的转换等价性：等价性：对任意一个正规文法，存在一个定义同对任意一个正规文法，存在一个定义同一语言的正规式一语言的正规式对任意一个正规式，存在一个定义同一对任意一个正规式，存在一个定义同一语言的正规文法语言的正规文法1.将将上的一个正规式上的一个正规式r r转换成文法转换成文法G=(VG=(VN N,V,VT T,S,P),S,P)V VT T=,=,首先形成产生式首先形成产生式Sr,SSr,S为为G G的开始符的开始符不断利用下面的规则做变换不断利用下面的规则做变换,直到每个
9、产生式最直到每个产生式最多含有一个终结符为止多含有一个终结符为止原原产生式产生式变换后产生式变换后产生式规则规则1 1AxyAxyAxBAxB ByBy规则规则2 2AxAx*y yAxAAxA AyAy规则规则3 3Ax|yAx|yAxAx AyAy其中其中B B为一新非终结符为一新非终结符例例:将将R=a(a|d)*转换成相应的正则文法转换成相应的正则文法令转换成文法令转换成文法G=(VN,VT,P,S)其中其中VT=a,d，文法开始符为文法开始符为S首先形成首先形成Sa(a|d)*,然后变换然后变换SaAA(a|d)*A(a|d)AAAaAAdA最终有产生式：最终有产生式：SaA，A，A
10、aA，AdA2.2.将正规文法转换成正规式将正规文法转换成正规式将每条产生式改写为正规式将每条产生式改写为正规式用代入法解正规式方程组用代入法解正规式方程组最最后后只只剩剩下下一一个个开开始始符符号号定定义义的的正正规规式式,其其中中不含非终结符不含非终结符正正规规文法到正文法到正规规式的转换规则式的转换规则:文法产生式文法产生式正正规规式式规则规则1 1 AxBAxB ByByA=A=xyxy规则规则2 2 AxA|yAxA|yA=xA=x*y y规则规则3 3 AxAx AyAyA=x|yA=x|y例：将文法例：将文法GS转换成正规式转换成正规式G：SaA|aAdA|d先由产生式得先由产生
11、式得:S=aA|aA=d*d将将A代入代入S中得中得:S=ad*d|a利用正利用正规规式变换得式变换得S=a(d*d|)=ad*说明说明:d*d|=(|d|dd|)d|=d|dd|=d*所求正规式为所求正规式为ad*4.2有穷自动机有穷自动机(也称有限自动机也称有限自动机)是一种识别装置是一种识别装置作用作用:能准确地识别正规集，即识别正规文法能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合所定义的语言和正规式所表示的集合意义意义:为词法分析程序的自动构造寻找特殊的为词法分析程序的自动构造寻找特殊的方法和工具。方法和工具。分类分类:确定的有穷自动机确定的有穷自动机(Deter
12、ministic Finite Automata)(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机(Nondeterministic Finite Automata)(Nondeterministic Finite Automata)4.3.1确定的有穷自动机（确定的有穷自动机（DFA）定义定义:一个一个DFA MDFA M是一个五元组是一个五元组:M=M=（K K，f f，S S，Z Z）1.1.K K是一个有穷集，它的每个元素称为一个状态是一个有穷集，它的每个元素称为一个状态2.2.是是一一个个有有穷穷字字母母表表，它它的的每每个个元元素素
13、称称为为一一个输入字符个输入字符3.3.f f是是 一一 个个 从从 KKKK的的 单单 值值 部部 分分 映映 射射。f(kf(ki i,a,a)=)=k kj j意意味味着着当当前前状状态态为为k ki i、输输入入字字符符为为a a时，将转换到下一状态时，将转换到下一状态k kj j4.4.SKSK，是是唯一唯一的初态的初态5.5.Z Z K,K,是是一一个个终终态态集集，终终态态也也称称为为可可接接受受状状态或结束状态。态或结束状态。例例DFA M=DFA M=（SS，U U，V V，Q,aQ,a，b,f,S,Qb,f,S,Q）其中其中f f定义为：定义为：f f（S S，a a）=U
14、=Uf f（S S，b b）=V=V f f（V V，a a）=U=Uf f（V V，b b）=Q=Q f f（U U，a a）=Q=Qf f（U U，b b）=V=V f f（Q Q，a a）=Q=Qf f（Q Q，b b）=Q=QDFA表示成状态转换图表示成状态转换图(TransitionDiagram)每个状态对应图中的一个结点：每个状态对应图中的一个结点：初态为唯一初态结点，用初态为唯一初态结点，用=标记；标记；终态对应终态结点，用双圈表示。终态对应终态结点，用双圈表示。若若有有f(ki,a)=kj，则则从从结结点点ki到到结结点点kj画画标标记记为为a的弧。的弧。例例DFA M=DF
15、A M=（SS，U U，V V，Q,aQ,a，b,f,S,Qb,f,S,Q）f f（S S，a a）=U=Uf f（S S，b b）=V=V f f（V V，a a）=U=Uf f（V V，b b）=Q=Q f f（U U，a a）=Q=Qf f（U U，b b）=V=V f f（Q Q，a a）=Q=Qf f（Q Q，b b）=Q=Q状态转换图表示为状态转换图表示为:bSUVQaaabab，bDFA表示成状态转换矩阵表示成状态转换矩阵例例DFA M=DFA M=（SS，U U，V V，Q,aQ,a，b,f,S,Qb,f,S,Q）f f（S S，a a）=U=Uf f（S S，b b）=V=V
16、 f f（V V，a a）=U=Uf f（V V，b b）=Q=Q f f（U U，a a）=Q=Qf f（U U，b b）=V=V f f（Q Q，a a）=Q=Qf f（Q Q，b b）=Q=Q字符字符状态状态0001行表示状态，用行表示状态，用双箭头双箭头“=”标标明初态；否则第明初态；否则第一行即是初态一行即是初态列表示输入字符列表示输入字符相应状态行和输相应状态行和输入字符列下的新入字符列下的新状态，即状态，即k k行行a a列列为为f(k,a)f(k,a)的值的值相应终态行在表相应终态行在表的右端标以的右端标以1 1，非终态标以非终态标以0 0DFA识别识别(接受接受)的字符串的字
17、符串对于对于*中的任何字符串中的任何字符串t，若存在一条从初态若存在一条从初态结到某一终态结的通路，且该通路上所有弧的结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于标记符连接成的字符串等于t，则称则称t可以为可以为DFAM所识别所识别若若DFAM的初态结同时又是终态结，则的初态结同时又是终态结，则可为可为M所识别。所识别。bSUVQaaaba，bbbaab为为DFA所接受所接受DFA MDFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M).L(M).结论：结论：上一个符上一个符号号串集串集V V 是正规的，当是正规的，当且仅当存在一个且仅当存在一个 上的确定
18、有穷自动机上的确定有穷自动机M M，使得使得 V=L(M)V=L(M)确定性确定性表现在表现在:转换函数转换函数f:KKf:KK是一个是一个单值单值函数，也就是说，对任何状态函数，也就是说，对任何状态kKkK，和输和输入符号入符号aa，f(k,a)f(k,a)唯一地确定了下一唯一地确定了下一个状态。个状态。4.3.2不确定的有穷自动机（不确定的有穷自动机（NFA）NFA的定义的定义一个不确定的有穷自动机一个不确定的有穷自动机M M是一个五元组：是一个五元组：M=M=（K K，f f，S S，Z Z），），其中其中1.1.K K是一个有穷集，它的每个元素称为一个状态；是一个有穷集，它的每个元素称
19、为一个状态；2.2.是是一一个个有有穷穷字字母母表表，它它的的每每个个元元素素称称为为一一个输入字符；个输入字符；3.3.f f是一个从是一个从KK*至至K K的子集的子集的映射；的映射；4.4.S S K K，是一个非空初态集是一个非空初态集5.5.Z Z K K，是一个终态集。是一个终态集。例例 NFA M=NFA M=（SS，P P，Z,0Z,0，1,f,S1,f,S，P,ZP,Z）其中其中 f f（S S，0 0）=P =P f f（S S，1 1）=S=S，ZZ f f（Z Z，0 0）=P=P f f（Z Z，1 1）=P=P f f（P P，1 1）=Z=Z矩阵表示矩阵表示:01
20、SP S,ZPZZP P001SPZ00,1111状态图表示状态图表示:说明：因为说明：因为NFANFA的的转换函数转换函数f f为为K K *到到K K的子集的一种映射，所以的子集的一种映射，所以NFANFA中可以中可以有有 转移转移例：例：123abcNFA识别的字符串识别的字符串对对于于*中中的的任任何何字字符符串串t，若若存存在在一一条条从从某某一一初初态态结结到到某某一一终终态态结结的的通通路路，且且该该通通路路上上所所有有弧弧的的标标记记字字依依次次连连接接成成的的串串（不不理理睬睬那那些些标标记记为为的弧）等于的弧）等于t，则称则称t可以被可以被NFAM所识别。所识别。若若M的的
21、某某个个初初态态结结又又是是终终态态结结，或或者者存存在在一一条条从从某某个个初初态态结结到到某某个个终终态态结结的的通通路路，那那么么为为M所识别。所识别。123abcNFA M NFA M 所能识别的符号串的全体记为所能识别的符号串的全体记为L(M)L(M)NFANFA与与DFADFA的等价性的等价性DFADFA是是NFANFA的特例的特例对对于于任任何何两两个个有有穷穷自自动动机机 M M和和MM，如如果果L(M)=L(M)L(M)=L(M)，则称则称M M与与MM是等价的是等价的对对于于每每个个NFA NFA M M，存存在在一一个个与与其其等等价价的的DFA MDFA M4.3.3N
22、FA到到DFA的转换的转换从从NFA构造构造DFA的算法的算法子集法子集法字符字符状态状态000101SP S,ZPZZP PDFA的状态转换矩阵的状态转换矩阵NFA的状态转换矩阵的状态转换矩阵1.基本思想基本思想:让让DFA 的每个状态对应的每个状态对应NFA 的一个状态集合。的一个状态集合。即即DFA用它的一个状态记录在用它的一个状态记录在NFA读入一个输读入一个输入符号后可能达到的所有状态。入符号后可能达到的所有状态。001合并合并如果有如果有，则把，则把S2状态合状态合并到并到S1状态。状态。S1S2ijkmaban（a）i,jmkaabn（b）2.转换需解决的问题：转换需解决的问题：
23、状态合并状态合并0123aabc（a）01,23abc（b）3.对状态集合对状态集合I的有关运算：的有关运算：状态集合状态集合I的的闭包闭包_closure(I)是状态集是状态集I I中的任何状态中的任何状态S S以及经任意以及经任意条条弧而能到达的状态的集合。弧而能到达的状态的集合。IIS2S2S1S1S3S3_ Closure(I)以下将以下将_closure(I)简写为简写为Closure(I)Closure(I)=I Sk|存在存在 Sj Sk，Sj Closure(I)，Sk Closure(I)注意：这是一个递归定义，通过多条注意：这是一个递归定义，通过多条边边才能到才能到达的状态
24、也将被合并到达的状态也将被合并到closure中中if I=0,the _closure(I)=Example:NFA 100124536789ababb74,2,1,0,Ia子集。子集。I是是状状态态集集，由由I中中的的状状态态出出发发，经经过过一一条条a弧可能到达的状态的集合称为弧可能到达的状态的集合称为Move（I，a），），则则Ia=_closure(Move(I,a)Ib =_closure(Example:NFA 100124536789ababbif I=0,1,2,4,7 thenIa =_closure()3,8=3,8,6,7,1,2,4 5 6,)=5,7,2,1,44.
25、4.NFANFA确定化算法确定化算法假设假设NFA N=(K,NFA N=(K,f,K,f,K0 0,K,Kt t)按如下办法构造一个按如下办法构造一个DFA M=(S,DFA M=(S,d,S,d,S0 0,S,St t)，使得使得L(M)=L(N)L(M)=L(N)：1)1)M M的状态集的状态集S S由由K K的一些子集组成。用的一些子集组成。用 S S1 1 S S2 2.S Sj j 表示表示S S的元素，其中的元素，其中S S1 1,S,S2,2,.,.S Sj j是是K K的状态。的状态。2)2)M M和和N N的输入字母表是相同的，即是的输入字母表是相同的，即是；3)3)转换函
26、数转换函数d(d(S S1 1 S S2,2,.S Sj j,a,a)=R)=R1 1R R2 2.R Rt t 其其中中 R R1,1,R R2,2,.,R Rt t =-closure(moveclosure(move(S S1 1,S,S2,2,.,.S Sj j,a,a)4)4)S S0 0=-closure(K-closure(K0 0)为为M M的开始状态；的开始状态；5)5)S St t=S Si i S Sk k.S Se e，其中其中 S Si i S Sk k.S Se e S S且且 S Si i,S Sk k,.,.S Se e K Kt t 5.5.构造构造DFADF
27、A的状态集的算法的状态集的算法 假设假设NFA N=(K,F,KNFA N=(K,F,K0 0,K,Kt t)构造的构造的DFADFA为为 M=(C,D,CM=(C,D,C0 0,C,Ct t)，状态集状态集C=(TC=(T1 1,T,T2 2,T,Ti i),),其中其中T T1 1,T,T2 2,T,Ti i都是状态集都是状态集K K的的子集。子集。1.1.开始，令开始，令_closure(K_closure(K0 0)为为C C中唯一成员，并且中唯一成员，并且它是未被标记的。它是未被标记的。2.2.whilewhile（C C中存在尚未被标记的子集中存在尚未被标记的子集 T T）dodo
28、 标记标记 T T；for for（每个输入字符每个输入字符aa）dodo U:=Ta;U:=Ta;（即（即_closure(Move(T,a)_closure(Move(T,a)）if if（U U不在不在C C中）中）thenthen将将U U做为未被标记的子集加入做为未被标记的子集加入C C中中 0,1,7,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T110,5,6,7,1,2,410,5,6,7,1,2,48,3,6,7,1,2,4=T19,5,6,7,1,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,49,5,6,7,1,2
29、,48,3,6,7,1,2,4=T18,3,6,7,1,2,45,6,7,1,2,48,3,6,7,1,2,4IbIaI100124536789ababbT0T1T2T3T40000140b213bbaaababaRename the sets of states of DFA,we get0,1,7,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T110,5,6,7,1,2,410,5,6,7,1,2,4=T48,3,6,7,1,2,4=T19,5,6,7,1,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T15,6,7,1,2,49,5,6,7,1,2,4=
30、T38,3,6,7,1,2,4=T18,3,6,7,1,2,45,6,7,1,2,4=T28,3,6,7,1,2,4=T1IbIaIT0T1T2T3T4000014.3.4确定有穷自动机的化简确定有穷自动机的化简化简的任务化简的任务:去掉多余状态，合并等价状态去掉多余状态，合并等价状态多余状态多余状态：从开始状态出发无法到达的状态。：从开始状态出发无法到达的状态。等价状态等价状态：两个状态：两个状态s和和t等价的条件是等价的条件是:1.一致性条件一致性条件状态状态s和和t必须同为可接受状态必须同为可接受状态或不可接受状态或不可接受状态2.蔓延性条件蔓延性条件对于对于所有所有输入符号输入符号,状
31、态状态s和状和状态态t必须转换到等价的状态里必须转换到等价的状态里可可区区别别状状态态：不不等等价价状状态态。如如终终态态与与非非终终态态是是可区别的。可区别的。aCDBAEFSbaaaaabbbbbab例例C C和和F F同是终态同是终态,C,C和和F F读入读入a a都到达都到达C,C,读入读入b b都到达都到达E,E,所以所以 C C和和F F等价等价S S和和C C不等价，因为不等价，因为C C是终态，而是终态，而S S不是终态不是终态“分割法分割法”DFADFA的最小化算法的最小化算法:把一个把一个DFA(DFA(不含多余状态不含多余状态)的状态分成一些不相的状态分成一些不相交的子集
32、，使得任何不同的两子集的状态都是交的子集，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状态都是可区别的，而同一子集中的任何两个状态都是等价的等价的.例例DBASaaabbbba,CDBAEFSbaaaaaabbbbbba1.1.将将M M的状态分成非终态和终态集的状态分成非终态和终态集 S,A,B C,D,E,FS,A,B C,D,E,F2 2 寻找子集中不等价状态寻找子集中不等价状态S,A,B=SA,B=SABS,A,B=SA,B=SABC,D,E,FC,D,E,F3 令令D代表代表C,D,E,F a bS A BA C BB A DC C ED F DE F DF C E
33、P=S,A,B,DP=S,A,B,D在等价状态子集中选一状态在等价状态子集中选一状态做代表，消去其他状态，把做代表，消去其他状态，把从消去状态射出和射入的弧从消去状态射出和射入的弧都引到代表状态，子集中有都引到代表状态，子集中有初态，则代表状态也是初态初态，则代表状态也是初态4.3 4.3 正规式和有穷自动机的等价性正规式和有穷自动机的等价性等价性等价性1.1.对于对于上的一个上的一个NFA MNFA M，可以构造一个，可以构造一个上的上的正规式正规式R,R,使得使得L(R)=L(M)L(R)=L(M)。2 2.对于对于上的一个正规式上的一个正规式R R，可以构造一个，可以构造一个上上的的NF
34、A MNFA M，使使的的L L(M)=L(R)(M)=L(R)。从从正规式正规式构造构造NFANFA“语法制导语法制导”法法:按正规式的语法结构指引构造过程按正规式的语法结构指引构造过程正规式的基本语法结构的构造规则正规式的基本语法结构的构造规则对于正规式对于正规式 ,构造的构造的NFANFA为为:yx 对于正规式对于正规式x,x x,x 构造的构造的NFANFA为为:yxx xyx对于正规式对于正规式,构造的构造的NFANFA为为:复合正规式复合正规式e的构造规则的构造规则先构造如下的先构造如下的NFAyxe e然后按下述三种情况进行分解，直至每条弧上然后按下述三种情况进行分解，直至每条弧
35、上标记一个字符标记一个字符e e1 1Xye=e1|e2e e2 2X1e e1 1ye2e=e1e2X1ye1e=e1*例：为例：为 R=(a|b)*abb构造构造 NFA M，使得使得L(M)=L(R)X(a|b)*abbYX (a|b)*1a 2bb 3 YX 4 1 b 3 a 2 b a|b YX 4 1 b 3 a 2 b a b Y4.4正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换从从正规文法正规文法到到NFA的转换方法的转换方法设文法设文法G=(VG=(VN N,V,VT T,P,S),P,S)相应相应NFA M=(K,f,KNFA M=(K,f,K0 0,Z),Z
36、)则则1.1.=V=VT T2.2.K K0 0=S=S3.3.增加一个新的状态增加一个新的状态T T作为终态，作为终态，Z=T,Z=T,4.4.K=VK=VN NTT5.5.f f由以下方法求得：由以下方法求得：若若P P中有中有AaBAaB，则有则有f(A,a)=Bf(A,a)=B；若若P P中有中有AaAa，则有则有f(A,a)=Tf(A,a)=T；若若P P中有中有AA，则有则有f(A,)=Tf(A,)=T；例：设文法例：设文法G=(S,A,B,a,b,P,S)G=(S,A,B,a,b,P,S)，则有自动机则有自动机M=(S,A,B,T,a,b,f,S,T)M=(S,A,B,T,a,b
37、,f,S,T)产生式产生式转换函数转换函数SaAf(S,a)=Af(S,a)=ASbBf(S,b)=Bf(S,b)=BS f(S,f(S,)=T)=TAaBf(A,a)=Bf(A,a)=BAbAf(A,b)=Af(A,b)=ABaSf(B,a)=Sf(B,a)=SBbAf(B,b)=Af(B,b)=AB f(B,f(B,)=T)=T正规文法正规文法,正规表达式正规表达式,有穷自动机有穷自动机三者可等价相互转换三者可等价相互转换描述工具描述工具识别工具识别工具4.5词法分析程序的设计词法分析程序的设计1.1.确定词法分析器的接口确定词法分析器的接口2.2.确定单词分类和确定单词分类和TokenT
38、oken结构结构3.3.特殊问题的处理特殊问题的处理4.4.用用状态转换图构造词法分析程序状态转换图构造词法分析程序回顾回顾:词法分析的主要任务是：从左到右逐个词法分析的主要任务是：从左到右逐个字符地扫描源程序，产生一个个单词字符地扫描源程序，产生一个个单词(Token)(Token)，同时检查源程序中的词法错误。同时检查源程序中的词法错误。执行词法分析的程序称为执行词法分析的程序称为词法分析程序词法分析程序或或扫描程序扫描程序(Scanner)。单词是语言中具有独立意义的最小单位，单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符包括保留字、标识符、运算符、标点符号和常量
39、等。号和常量等。1.确定词法分析器的接口确定词法分析器的接口确定词法分析器是作为语法分析的一个子程确定词法分析器是作为语法分析的一个子程序还是作为独立一遍序还是作为独立一遍词法分析作为独立一遍词法分析作为独立一遍将字符流的源程序变成单词序列，输出到一将字符流的源程序变成单词序列，输出到一个中间文件上，做为语法分析的输入。个中间文件上，做为语法分析的输入。词法分析作为语法分析的子程序词法分析作为语法分析的子程序每当语法分析程序需要一个单词时，则调用每当语法分析程序需要一个单词时，则调用该子程序，从源程序中分析和返回一个单词该子程序，从源程序中分析和返回一个单词独立词法分析器独立词法分析器语法分析
40、语法分析Token序列序列源程序源程序附属词法分析器附属词法分析器语法分析语法分析调用调用Token源程序源程序2.确定单词分类和确定单词分类和TokenToken结构结构设计词法分析器的首要任务是，对于源语言的单设计词法分析器的首要任务是，对于源语言的单词进行仔细的分析，并列出所有可能的不同单词，词进行仔细的分析，并列出所有可能的不同单词，然后再确定单词的内部表示然后再确定单词的内部表示 程序设计语言中的大部分单词，一般可分为以下程序设计语言中的大部分单词，一般可分为以下几类：几类：1基本字（关键字）：如基本字（关键字）：如 begin，end，if等等2标识符：用来表示常量、变量、过程等名
41、字标识符：用来表示常量、变量、过程等名字3常常数数：各各种种类类型型的的常常数数，如如 15，3.14，TRUE4运算符：如运算符：如+，*，/5界符：如逗号，分号，括号等界符：如逗号，分号，括号等单词的机内表示单词的机内表示二元式（二元式（单词种别单词种别，单词自身的值单词自身的值）种别是语法分析需要的信息种别是语法分析需要的信息自身值是编译其他阶段需要的信息自身值是编译其他阶段需要的信息种别编码种别编码(常用整数编码常用整数编码)方方法法一一：按按单单词词的的5大大种种类类每每种种一一个个码码，例例如如标标识识符符为为l，常常数数为为2，基基本本字字为为3，运运算算符为符为4，界符为，界符
42、为5。方方法法二二：每每个个基基本本字字一一个个编编码码；所所有有标标识识符符为为一一个个编编码码；常常数数按按类类型型分分类类，每每类类一一个个编编码码；每每个个运运算算符符一一个个编编码码；每每个个界界符符一一个个编编码。码。单词自身值单词自身值对对常常数数,基基本本字字,运运算算符符,界界符符就就是是他他们们本本身身的的值值对对标标识识符符,将将标标识识符符的的名名字字登登记记在在符符号号表表中中,“自自身身值值”是是指指向向该该标标识识符符所所在在符符号号表表中中位位置的指针置的指针.例如例如源程序源程序ifi=5thenx:=y;种别编码：标识符为种别编码：标识符为l，常数为常数为2
43、，基本字为，基本字为3，运算符为，运算符为4，界符为，界符为5词法分析后输出的单词序列是词法分析后输出的单词序列是:(3,if)(1,指向指向i的符号表入口的符号表入口)(4,=)(2,5)(3,then)(1,指向指向x的符号表入口的符号表入口)(4,:=)(1,指向指向y的符号表入口的符号表入口)(5,;)3.特殊问题的处理特殊问题的处理v标识符和保留字的区分标识符和保留字的区分事先构造保留字表，拼出的标识符单词先查事先构造保留字表，拼出的标识符单词先查保留字表，若有，则把它做为保留字处理保留字表，若有，则把它做为保留字处理v空格符和制表符空格符和制表符(Tab)(Tab)以及换行符的处理
44、以及换行符的处理1.1.无用的空格符和制表符要删掉；无用的空格符和制表符要删掉；2.2.字符串内的空格不能删；字符串内的空格不能删；3.3.换行符不能删，对于错误处理起作用。换行符不能删，对于错误处理起作用。v复合型特殊符，如复合型特殊符，如“:=”:=”的处理的处理读到读到“:”:”时不能判断是否为冒号，必须读下时不能判断是否为冒号，必须读下一字符。一字符。v括号类配对：括号类配对：“”和和“”、左注释符和右注释符的配对。、左注释符和右注释符的配对。也可以把也可以把begin end,if then,(begin end,if then,()等等语法配对在词法分析中进行处理语法配对在词法分析
45、中进行处理处理方法：处理方法：1.1.对每类括号设置一个计数器（初值对每类括号设置一个计数器（初值=0=0）2.2.每当遇到左括号，则计数器加每当遇到左括号，则计数器加1 13.3.每当遇到右括号时，计数器减每当遇到右括号时，计数器减1 14.4.词法分析结束时，如果计数器词法分析结束时，如果计数器 0 0，则表明括号，则表明括号不匹配。不匹配。可通过状态转换图来实现词法分析程序的构可通过状态转换图来实现词法分析程序的构造，步骤：造，步骤：画状态转换图。画状态转换图。由正规文法构造状态转换图由正规文法构造状态转换图由正规表达式构造状态转换图由正规表达式构造状态转换图将正规文法或正规表达式转换成
46、将正规文法或正规表达式转换成DFADFA（经历经历NFANFA的构造，将的构造，将NFANFA确定化，确定化，DFADFA最小化的过程）最小化的过程），将，将DAFDAF以以状态转换图的形式表现出来。状态转换图的形式表现出来。4.用状态转换图构造词法分析程序用状态转换图构造词法分析程序按状态转换图写出词法分析程序按状态转换图写出词法分析程序对对于于状状态态图图中中的的每每一一状状态态构构造造一一段段代代码码具体构造程序时：具体构造程序时：开始结点开始结点开开始始结结点点是是一一个个单单词词识识别别的的开开始始，单单词词开开始始符符是是非非空空白白字字符符，首首先先把把非非空空白白字字符符读读入
47、入ch，再再按按该该字字符符的的特特征征进进入入不不同同种种类类单单词词的的识识别别GetChar()；/*从从输输入入串串读读一一个个字字符符，放放入入 ch中中*/GetBC()；/*检检查查ch中中字字符符是是否否空空白白，若若是是则调用则调用GetChar，直至直至ch中为非空白字符中为非空白字符*/If(ch=)beginendelseif(ch=)beginend else错误处理；错误处理；不含回路的分叉结点，对应不含回路的分叉结点，对应switch语句或一组语句或一组ifthenelse语句语句ijk数字数字字母字母/l例：状态结点例：状态结点 i对应的程序段对应的程序段Get
48、Char()；If(IsLetter()状态状态 j的对应程序段的对应程序段;elseIf(IsDigit()状态状态 k的对应程序段的对应程序段;elseIf（ch=/）状态状态 l的对应程序段的对应程序段;else错误处理错误处理;其中：其中：IsLetter和和IsDigit：布尔函数，布尔函数，分别判别分别判别ch字符是否为字母或数字字符是否为字母或数字终态结点，一般对应一个终态结点，一般对应一个return(code，value)语语句句，code是是单单词词种种别码别码，value是单词自身值，意为返回调用者：是单词自身值，意为返回调用者：v当当词词法法分分析析作作为为语语法法分分
49、析析的的子子程程序序，返返回回到到语语法分析法分析v当当词词法法分分析析作作为为独独立立一一遍遍，返返回回进进行行新新的的单单词词识别识别4.6词法分析程序的自动构造工具词法分析程序的自动构造工具1.自动构造工具的基本思想自动构造工具的基本思想上述构造过程由计算机来完成就称为词法分上述构造过程由计算机来完成就称为词法分析程序的自动构造。析程序的自动构造。能完成上述任务的程序称为词法分析程序的能完成上述任务的程序称为词法分析程序的自动构造工具。自动构造工具。单单词词结结构构的的正规式描述正规式描述NFADFA状状态态转转换换表表 控制程序控制程序（词法分析程序）（词法分析程序）（源程序）（源程序
50、）2.LEXLex是词法分析器的自动生成器是词法分析器的自动生成器作用作用:构造各种语言的词法分析程序。构造各种语言的词法分析程序。lex指的是指的是LEX的编译系统的编译系统LEX源程序源程序LEX编译系统编译系统词法分析器词法分析器（C语言形式）语言形式）输入串输入串词法分析器词法分析器单词符号串单词符号串LEX源程序是对一个词法分析程序的说明和描述，在逻辑源程序是对一个词法分析程序的说明和描述，在逻辑上分成两部分：上分成两部分：一组正规式：表示单词构成规则。一组正规式：表示单词构成规则。每个正规式相应的每个正规式相应的“动作动作”（C代码）：识别出单词时应代码）：识别出单词时应采取的动作