第3章-词法分析.ppt

1 词法分析是编译的第一个阶段，它的词法分析是编译的第一个阶段，它的主要任务是从左到右逐个字符地对源程序主要任务是从左到右逐个字符地对源程序进行扫描，产生一个个单词序列。进行扫描，产生一个个单词序列。词法分析阶段设计的主要问题是字符词法分析阶段设计的主要问题是字符串（单词）的识别问题。具体说，如何判串（单词）的识别问题。具体说，如何判定任意的一个字符串是否为合法字符串定任意的一个字符串是否为合法字符串(单单词词)的问题。的问题。第1页/共68页2 字符串（单词）集合可用不同的工具来字符串（单词）集合可用不同的工具来表示，常见的有：表示，常见的有：因此，要研究如何从正规表达式或自动因此，要研究如何从正规表达式或自动机构造出相应的单词识别器的问题。这种识机构造出相应的单词识别器的问题。这种识别器在编译器中称为别器在编译器中称为词法分析器词法分析器。单词的描述技术：正规式。单词的描述技术：正规式。识别机制：有穷自动机（有限自动机）。识别机制：有穷自动机（有限自动机）。第2页/共68页3 构造词法分析器的前提是给出语言中单构造词法分析器的前提是给出语言中单词结构的定义。不同语言的单词类别和结构词结构的定义。不同语言的单词类别和结构不完全相同，因此不同语言的词法分析器也不完全相同，因此不同语言的词法分析器也不尽相同，但是其构造原理是类似的。不尽相同，但是其构造原理是类似的。v构造方法：构造方法：有穷自动机有穷自动机(有限自动机有限自动机)。正规式正规式(正规集正规集)。第3页/共68页4本章重点本章重点v首先需要描述和刻画程序设计语言中的原首先需要描述和刻画程序设计语言中的原子单位子单位单词，其次需要识别单词和执单词，其次需要识别单词和执行某些相关的动作。行某些相关的动作。v程序设计语言的词法的程序设计语言的词法的描述机制描述机制是正则表是正则表达式，达式，识别机制识别机制是有穷状态自动机。是有穷状态自动机。单词的描述工具单词的描述工具单词的识别系统单词的识别系统第4页/共68页53.1 有穷自动机有穷自动机第5页/共68页6 有穷自动机有穷自动机(也称有限自动机也称有限自动机)作为一种识别装置，作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。语言和正规式所表示的集合。引入有穷自动机这个理论，正是为词法分析程序引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。的自动构造寻找特殊的方法和工具。确定的有穷自动机确定的有穷自动机(Deterministic Finite Automata)不确定的有穷自动机不确定的有穷自动机(Nondeterministic Finite Automata)第6页/共68页7关于关于有穷自动机将讨论以下问题有穷自动机将讨论以下问题v一、确定的有穷自动机一、确定的有穷自动机DFAv二、不确定的有穷自动机二、不确定的有穷自动机NFAv三、具有三、具有动作的动作的FAv四、四、NFA到到DFA的变换的变换第7页/共68页8一、确定的有穷一、确定的有穷 自动机自动机DFA第8页/共68页9确定的有穷自动机确定的有穷自动机DFA的定义的定义 一个确定的有穷自动机（一个确定的有穷自动机（DFA）M是一是一个五元组：个五元组：M=（Q，S，Z）其中）其中 1.Q是一个有穷集，它的每个元素称为一是一个有穷集，它的每个元素称为一个状态；个状态；2.是一个有穷字母表，它的每个元素称是一个有穷字母表，它的每个元素称为一个输入符号；为一个输入符号；第9页/共68页103.是转换函数，是在是转换函数，是在QQ上的单值上的单值映射，如映射，如 （p，a）=q，（，（pQ，qQ）意味着，当前状态为）意味着，当前状态为P，输入符，输入符为为a时，将转换为下一个状态时，将转换为下一个状态Q，我们，我们把把q称作称作p的一个后继状态；的一个后继状态；4.SQ是唯一的一个初态；是唯一的一个初态；5.Z Q是一个终态集，终态也称可接受是一个终态集，终态也称可接受状态或结束状态。状态或结束状态。第10页/共68页11对定义的解释对定义的解释v所谓自动机不是一台实际的机器，而是一种数所谓自动机不是一台实际的机器，而是一种数学模型，来模拟计算机的识别功能。学模型，来模拟计算机的识别功能。v所谓确定性是指所谓确定性是指(p,a)q，q是唯一的。是唯一的。v用上述定义中的用上述定义中的5条来识别一个序列是否可被机条来识别一个序列是否可被机器接收。器接收。接收接收 格式正确格式正确第11页/共68页12DFA 的例子的例子 DFA M=（S，U，V，Q，a，b，S，Q）其中）其中定义为：定义为：（S，a）=U （V，a）=U（S，b）=V （V，b）=Q（U，a）=Q （Q，a）=Q（U，b）=V （Q，b）=Q 以上定义不直观，以上定义不直观，DFA有两种较直观的表示方法有两种较直观的表示方法。第12页/共68页13DFA的表示方法的表示方法1（状态转换图）（状态转换图）一个一个DFA可以表示成一个状态图可以表示成一个状态图(或称状态或称状态转换图转换图)。假定。假定DFA M含有含有m个状态，个状态，n个输入字个输入字符，那么这个状态图含有符，那么这个状态图含有m个结点，每个结点个结点，每个结点最最多多有有n个弧射出，每条弧用个弧射出，每条弧用中的中的一个不同输入一个不同输入字符字符作标记。作标记。整个图含有整个图含有唯一唯一一个初态结点和若干个终态一个初态结点和若干个终态结点，初态结点冠以双箭头结点，初态结点冠以双箭头“=”，终态结点用，终态结点用双圈表示，若双圈表示，若 (p,a)=q，则从状态结点，则从状态结点p到状态到状态结点结点q画标记为画标记为a的弧；的弧；第13页/共68页14 DFA 的状态图表示的状态图表示bSUVQaaaba，bb第14页/共68页15DFA 的表示方法的表示方法2（状态转换矩阵）（状态转换矩阵）一个一个DFA还可以用一个矩阵表示，该还可以用一个矩阵表示，该矩阵的行表示状态，列表示输入字符，矩矩阵的行表示状态，列表示输入字符，矩阵元素表示相应状态行和输入字符列下的阵元素表示相应状态行和输入字符列下的新状态，即新状态，即p行行a列为列为(p,a)的值。用双箭头的值。用双箭头“=”标明初态；否则第一行即是初态，标明初态；否则第一行即是初态，相应终态行在表的右端标以相应终态行在表的右端标以1，非终态标以，非终态标以0。第15页/共68页16状态转换矩阵表示状态转换矩阵表示字符字符状态状态0001第16页/共68页17DFA的识别功能的识别功能 对于对于*中的任何字符串中的任何字符串t，若存在一条，若存在一条从初态结到某一终态结的道路，且这条路从初态结到某一终态结的道路，且这条路上所有弧的标记符连接成的字符串等于上所有弧的标记符连接成的字符串等于t，则称则称t为为DFA M所接受（识别）。所接受（识别）。若若M的初态结同时又是终态结，则的初态结同时又是终态结，则可被识别。可被识别。第17页/共68页1800011110100011100000010001100第18页/共68页19 DFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)。对于任何两个有穷自动机。对于任何两个有穷自动机M和和M，如果，如果L(M)=L(M)，则称，则称M与与M是等价是等价的。的。DFA的等价的等价第19页/共68页20确定性确定性 DFA的确定性表现在转换函数的确定性表现在转换函数:QQ是一个单值函数，也就是说，是一个单值函数，也就是说，对任何状态对任何状态PK，和输入符号，和输入符号a，(p,a)唯一地确定了下一个状态。唯一地确定了下一个状态。从状态转换图来看，若字母表从状态转换图来看，若字母表含有含有n个输入字符，那末任何一个状态结点最个输入字符，那末任何一个状态结点最多有多有n条弧射出，而且每条弧以一个不同条弧射出，而且每条弧以一个不同的输入字符标记。的输入字符标记。第20页/共68页21二、非确定的有二、非确定的有 穷自动机穷自动机NFA第21页/共68页22不确定的有穷自动机不确定的有穷自动机NFA的定义的定义NFA M=Q，S，Z，其中，其中1.Q为状态的有穷非空集，为状态的有穷非空集，（与（与DFA相同）相同）2.为有穷输入字母表，为有穷输入字母表，（与（与DFA相同）相同）3.映射映射为为Q Q的的多值映射，多值映射，4.SQ是唯一的一个初态是唯一的一个初态，（与（与DFA相同）相同）5.Z Q为终止状态集。为终止状态集。（与（与DFA相同）相同）第22页/共68页23NFA的表示方法的表示方法1（状态转换图）（状态转换图）一个含有一个含有m个状态和个状态和n个输入字符的个输入字符的NFA可表示成一个状态转换图：这张图可表示成一个状态转换图：这张图含有含有m个状态结，每个结可射出个状态结，每个结可射出若干若干条条箭弧与别的结相连接，每条弧用箭弧与别的结相连接，每条弧用中的中的一个字符作标记，整个图含有一个初态一个字符作标记，整个图含有一个初态结和若干个终态结。结和若干个终态结。第23页/共68页24 NFA的识别功能的识别功能 对于对于 中的任何一个串中的任何一个串t，若存在一条，若存在一条从某一初态结到某一终态结的道路，且这从某一初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串条道路上所有弧的标记字依序连接成的串等于等于t，则称，则称t可为可为NFA M所识别所识别(读出或接读出或接受受)。NFA M所能接受的符号串的全体记为所能接受的符号串的全体记为L(M)。第24页/共68页25三、具有三、具有动作的动作的FA第25页/共68页26 前面在定义前面在定义NFA和和DFA时，对映射时，对映射的限制是仅当的限制是仅当FA扫视扫视中的一个字符时，中的一个字符时，才发生状态的转移。才发生状态的转移。如果弧上允许标记如果弧上允许标记，即允许，即允许FA对对也作状态的转移，则称此自动机为也作状态的转移，则称此自动机为自动自动机，记为机，记为 NFA。第26页/共68页27FA中映射中映射的扩充的扩充映射映射为为Q *到到Q的子集。的子集。对于对于 中的任何一个串中的任何一个串t，若存在一条，若存在一条从初态结到某一终态结的道路，且这条道从初态结到某一终态结的道路，且这条道路上所有弧的标记字依序连接成的串路上所有弧的标记字依序连接成的串(不理不理睬那些标记为睬那些标记为的弧的弧)等于等于t，则称，则称t可为可为NFA M所识别所识别(读出或接受读出或接受)。每个弧线用每个弧线用*中的一个中的一个字字作标记（字符串）作标记（字符串）第27页/共68页28 若若M的某些结既是初态结又是终态结，的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态结或者存在一条从某个初态结到某个终态结的道路的道路,其上所有弧的标记均为其上所有弧的标记均为，那么空，那么空字可为字可为M所接受。所接受。第28页/共68页29四、四、NFA到到DFA的的变换变换第29页/共68页30 在在NFA中，由于某些状态的转移须中，由于某些状态的转移须从若干个可能的后续状态中进行选择，从若干个可能的后续状态中进行选择，故一个故一个NFA对符号串的识别必然是一个对符号串的识别必然是一个试探的过程。试探的过程。这种不确定性给识别过程带来的反这种不确定性给识别过程带来的反复，无疑会影响到复，无疑会影响到FA的工作效率。的工作效率。子集法子集法将具有将具有动作的动作的NFA转换转换成接受同样语言的成接受同样语言的DFA。第30页/共68页31NFA的确定化（子集法）的确定化（子集法）所谓确定化是指所谓确定化是指NFA DFA的等价转的等价转化，用子集法来进行确定化。化，用子集法来进行确定化。为此，首先定义一个状态集合为此，首先定义一个状态集合 I 的的闭包的概念。闭包的概念。第31页/共68页32状态集合状态集合I I的几个有关运算的几个有关运算1.状态集合状态集合I的的-闭包闭包 表示为表示为-closure(I)，其中，其中I是是NFA的状态集的状态集的一个子集。的一个子集。若若s I，则，则s-closure(I)。状态集合状态集合I的任何状态的任何状态s都属于都属于-closure(I)。若若s I，那么从，那么从s出发经任意条出发经任意条弧而能到弧而能到达的任何状态都属于达的任何状态都属于-closure(I)。第32页/共68页332.状态集合状态集合I的的a弧转换，表示为弧转换，表示为move(I,a)定义为状态集合定义为状态集合J，即，即J=move(I,a)。其中其中J是所有那些可从是所有那些可从I中的某一状态经过中的某一状态经过一条一条a弧而到达的状态的全体。弧而到达的状态的全体。Ia=-closure(J)第33页/共68页34状态集合状态集合I的有关运算的例子的有关运算的例子I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；J=move(1,2,a)=Ia=-closure(5,3,4)=12534687aa a5,3,42,3,4,5,6,7,8；第34页/共68页35NFA确定化的步骤确定化的步骤设设a,b,则则NFA的确定化步骤如下：的确定化步骤如下：1、造一张表，包含三列，第一列为、造一张表，包含三列，第一列为I，余下，余下的两列为的两列为Ia，Ib。2、置首行首列为、置首行首列为_closureS。3、若某行首列对应子集已确定，则计算、若某行首列对应子集已确定，则计算Ia，以及以及Ib；新出现状态子集加入下行首列。；新出现状态子集加入下行首列。4、重复、重复3，直至状态子集收敛。，直至状态子集收敛。5、状态子集重新命名。、状态子集重新命名。第35页/共68页364Y35621X aaaabbbb第36页/共68页37 等价的等价的DFAa34215F0baaaaabbbbbab6第37页/共68页383.2 正规集、正规正规集、正规文法和正规式文法和正规式第38页/共68页39本节本节将讨论以下问题将讨论以下问题v一、正规式与正规集一、正规式与正规集v二、正规集与正规文法二、正规集与正规文法v三、正规文法和正规式三、正规文法和正规式第39页/共68页40一、正规式与一、正规式与正规集正规集第40页/共68页41正规式正规式 正规式也称正则表达式正规式也称正则表达式,正规表达式正规表达式（regular expression）是说明单词的模）是说明单词的模式的一种重要的表示法（记号），是定义式的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符正规集的数学工具。我们用以描述单词符号。号。程序设计语言的单词都能用正规式来程序设计语言的单词都能用正规式来定义。定义。下面是正规式和它所表示的正规集的下面是正规式和它所表示的正规集的递归定义。递归定义。第41页/共68页42设字母表为设字母表为：和和 都是都是 上的正规式，它们所表示的正规集分别上的正规式，它们所表示的正规集分别为为 和和；任何任何a ，a是是 上的一个正规式，它所表示的正规上的一个正规式，它所表示的正规集为集为a；假定假定e1和和e2都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集分别为集分别为L(e1)和和L(e2)，那么，那么，(e1),e1 e2,e1 e2,e1 也都是正规式也都是正规式,它们所表示的正规集分别为它们所表示的正规集分别为L(e1),L(e1)L(e2),L(e1)L(e2)和和(L(e1)。仅由有限次使用上述三步骤而定义的表达式才是仅由有限次使用上述三步骤而定义的表达式才是 上上的正规式，仅由这些正规式所表示的集合才是的正规式，仅由这些正规式所表示的集合才是 上的正规上的正规集。集。第42页/共68页43正规式中的符号正规式中的符号在不致混淆时，括号可省去，但规定算符在不致混淆时，括号可省去，但规定算符的优先顺序为的优先顺序为“”、“”、“”。连接符连接符“”一般可省略不写。一般可省略不写。“”、“”和和“”都是左结合的。都是左结合的。“”读为读为“或或”；“”读为读为“连接连接”；“”读为读为“闭包闭包”(任意有限次的自重复连接任意有限次的自重复连接)。第43页/共68页44令令=a，b，上的正规式和相应的正规集有：上的正规式和相应的正规集有：正规式正规式 正规集正规集 a a a b a,b ab ab(a b)(a b)aa,ab,ba,bb a ,a,a,任意个任意个a的的 串串第44页/共68页45 正规式正规式 正规集正规集 (a b),a,b,aa,ab 所所 有由有由a和和b组成的串组成的串(a b)(aa bb)(a b)上所有含有两上所有含有两 个相继的个相继的a或两个或两个 相继的相继的b组成的串组成的串 ba b,ba,baa,baaa,baaaa,第45页/共68页46两个正规式等价两个正规式等价 若两个正规式若两个正规式e1和和e2所表示的正规集相同，所表示的正规集相同，则说则说e1和和e2等价，写做等价，写做e1=e2。e1=(a b)e2=b a e1=b(ab)e2=(ba)b e1=(a b)e2=(a b)第46页/共68页47性质性质 r s=s r “或或”服从交换律服从交换律 r(s t)=(r s)t “或或”的可结合的可结合律律 (rs)t=r(st)“连接连接”的可结合律的可结合律 r(s t)=rs rt (s t)r=sr tr 分配律分配律 r=r r=r 设设r,s,t为正规式：为正规式：第47页/共68页48二、正规集与二、正规集与正规文法正规文法第48页/共68页49 正规文法是描述正规集的文法，它可正规文法是描述正规集的文法，它可以用来描述高级语言的词法部分。以用来描述高级语言的词法部分。在写正规集的文法时，要特别注意所在写正规集的文法时，要特别注意所给出的产生式形式必须满足正规文法的限给出的产生式形式必须满足正规文法的限制。制。第49页/共68页50三、正规文法三、正规文法和正规式和正规式第50页/共68页51 正规式与正规文法都用来描述程序语正规式与正规文法都用来描述程序语言的词法结构，它们有着相同的表达能言的词法结构，它们有着相同的表达能力。力。对于任意一个正规文法，存在一个对于任意一个正规文法，存在一个定义同一个语言的正规式；反之，对每定义同一个语言的正规式；反之，对每个正规式，都存在一个生成同一语言的个正规式，都存在一个生成同一语言的正规文法。正规文法。第51页/共68页52正规文法正规文法正规式正规式 首先求出正规文法首先求出正规文法G的各个产生式对的各个产生式对应的正规式方程式，获得一个联立方程组。应的正规式方程式，获得一个联立方程组。这些方程式中的变元是文法这些方程式中的变元是文法G中的非中的非终结符，各变元的系数是正规式。终结符，各变元的系数是正规式。然后求解这个正规式方程组，最后得然后求解这个正规式方程组，最后得到一个关于开始符号到一个关于开始符号S的解：的解：S=w，w VT*解正规式方程组的基本方法是用代解正规式方程组的基本方法是用代入法逐个替换方程式右部的各非终结符，入法逐个替换方程式右部的各非终结符，最后可得到关于开始符号最后可得到关于开始符号S的解。的解。第52页/共68页533.4 正规式与正规式与NFA第53页/共68页54正规式与正规式与FA在描述语言上的等价性在描述语言上的等价性v对于一个在输入字母表对于一个在输入字母表上的上的NFA M，一，一定能够构造一个定能够构造一个上的正规式上的正规式e，使得，使得L(e)=L(M)。v对于一个在输入字母表对于一个在输入字母表上的每一个正规上的每一个正规式式e，一定能够构造一个，一定能够构造一个上的上的NFA M，使得使得L(M)=L(e)。第54页/共68页55正规式正规式NFA的方法的方法1.由由e构造构造NFA M 把正规式把正规式e表示成拓广转换图，表示成拓广转换图，X Y e然后通过对然后通过对e进行分裂和加进新结的方法，逐步进行分裂和加进新结的方法，逐步把这个图转变为：把这个图转变为：每条弧的标记为每条弧的标记为的一个字符的一个字符或或。转换规则如下：。转换规则如下：第55页/共68页56转换规则转换规则szR1R2AsR1zR2szR1|R2zsR1R2sz R*s z RA第56页/共68页571（0|1）*1011（0|1）*101XY1X21Y（0|1）*134101X21Y13410501第57页/共68页58（a|b)*(aa|bb)(a|b)*XY（a|b)*X21Y（aa|bb)（a|b)*正规式（正规式（a|b)*(aa|bb)(a|b)*第58页/共68页594Y35621X aaaabbbbX4213Y aa bb a|b a|b第59页/共68页603.5 DFA的化简的化简第60页/共68页61 对于一个对于一个NFA，当把它确定化之后，得到，当把它确定化之后，得到的的DFA所具有的状态数可能并不是最小的。所所具有的状态数可能并不是最小的。所以，以，DFA的化简，是指状态数的最小化。的化简，是指状态数的最小化。定理：对于有同一接受集的定理：对于有同一接受集的FA，与之等价且，与之等价且有最小状态数的有最小状态数的DFA在同构意义下（即不顾在同构意义下（即不顾状态的命名）是唯一的。状态的命名）是唯一的。第61页/共68页62 等价状态和可区分状态等价状态和可区分状态两个状态两个状态s和和t等价等价：满足：满足兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从s出发读入某个出发读入某个a a和和 从从t出发出发读入某个读入某个a到达的状到达的状 态等价。态等价。第62页/共68页63等价状态的举例等价状态的举例aCDBAEFSbaaaaabbbbbabC和和F同是终态：同是终态：读入读入a都到达都到达C，读入读入b都到达都到达E。D和和E同是终态：同是终态：读入读入a都到达都到达F，读入读入b都到达都到达D。C和和D同是终态：同是终态：读入读入a分别到达分别到达C和和F，读入读入b分别到达分别到达D和和E。C和和F等价等价D和和E等价等价C和和D等价等价第63页/共68页64最小化的方法最小化的方法分割法分割法 把一个把一个DFA的状态分成一些的状态分成一些不相交不相交的子的子集，使得任何不同的两子集的状态都是可区集，使得任何不同的两子集的状态都是可区分的，而同一子集中的任何两个状态都是等分的，而同一子集中的任何两个状态都是等价的。价的。第64页/共68页65 DFA的最小化举例的最小化举例0:0:0,1,2 0,1,2 3,4,5,63,4,5,61:0,1,2 1:0,1,2 3,4,5,6 3,4,5,6 2:2:3421560baaaaaabbbbbba11 0,20,2b2 2 0 0 a3210aaabbbab第65页/共68页663.6 单词的分类单词的分类表示表示第66页/共68页67语法分析程序语法分析程序词法分析程序词法分析程序源程序（字符串）源程序（字符串）自左向右逐个字符地对自左向右逐个字符地对源程序进行扫描。源程序进行扫描。单词流单词流源程序源程序词法分析器词法分析器charToken 单词是以机内表示形式出单词是以机内表示形式出现的。现的。（单词类别，单词自身值）（单词类别，单词自身值）合法的句子合法的句子第67页/共68页68单词的分类单词的分类 在程序设计语言中，单词是具有独立在程序设计语言中，单词是具有独立意义的最小语法单位。意义的最小语法单位。通常分为通常分为5种类型，包括关键字、标种类型，包括关键字、标识符、常量、运算符、界限符。识符、常量、运算符、界限符。第68页/共68页