第第 4 4 讲讲西北农林科技大学本科教程西北农林科技大学本科教程 主讲教师：赵建邦主讲教师：赵建邦 第三章第三章 语法分析语法分析l3.1 3.1 文法和语言文法和语言l3.2 3.2 推导与语法树推导与语法树l3.3 3.3 自顶向下的语法分析自顶向下的语法分析l3.4 3.4 自底向上的语法分析自底向上的语法分析l3.5 3.5 规范规约的自底向上语法分析方法规范规约的自底向上语法分析方法u第三章第三章语法分析语法分析l3.1 3.1 文法和语言文法和语言l文法和语言的基本概念文法和语言的基本概念l形式语言分类（形式语言分类（4 4类）类）l正规表达式与上下文无关文法正规表达式与上下文无关文法u重点掌握重点掌握l正规表达式与上下文无关文法正规表达式与上下文无关文法本讲目标本讲目标 u定位定位语法分析是编译过程的第二个阶段，也是核心部分语法分析是编译过程的第二个阶段，也是核心部分u任务任务根据语言的根据语言的语法规则语法规则对单词序列进行语法分析，识别合法的对单词序列进行语法分析，识别合法的语法单位（如表达式、语句、程序段等），若不存在语法错语法单位（如表达式、语句、程序段等），若不存在语法错误则给出正确的语法结构误则给出正确的语法结构理论依据：理论依据：上下文无关文法上下文无关文法u方法方法自顶向下分析（自顶向下分析（推导推导：开始符号：开始符号 句子）句子）自底向上分析（自底向上分析（规约规约：句子：句子 开始符号）开始符号） 语法分析：语法分析：3.1 3.1 文法和语言文法和语言u文法文法(Grammar)是是程序语言的生成系统，用文法可以精确定义一程序语言的生成系统，用文法可以精确定义一个语言，并依据该文法构造出识别这个语言的个语言，并依据该文法构造出识别这个语言的自动机自动机u文法对程序语言和编译程序的构造具有重要意义，如程序语言的文法对程序语言和编译程序的构造具有重要意义，如程序语言的词法可用正规文法描述，语法可用上下文无关文法描述，而语义词法可用正规文法描述，语法可用上下文无关文法描述，而语义则要借助于上下文有关文法则要借助于上下文有关文法描述描述3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念1、语言、语言通常我们用通常我们用表示表示字母表字母表，字母表中的每个元素称为字符，字母表中的每个元素称为字符或符号。不同语言的字母表可能是不同的，或符号。不同语言的字母表可能是不同的，程序语言的字程序语言的字母表通常是母表通常是ASCII字符集字符集。由字母表由字母表中的字符所组成的有穷系列称为中的字符所组成的有穷系列称为上的上的字符串字符串或字或字，字母表，字母表上的所有字符串上的所有字符串( (包括空串包括空串) )组成的集合用组成的集合用* *表示。表示。那么，对字母表那么，对字母表来说来说，* *上上的任意一个子集都称为的任意一个子集都称为上上的一个的一个语言语言，记为，记为L( )L( )，该语言的每一个字符串称该语言的每一个字符串称为语言为语言L L的一个的一个语句或句子语句或句子。3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念1、语言、语言例如，设例如，设 = = a, b, ca, b, c，则，则: : L L = = , a, aa, ab, aaa, aab, aba, abb, , a, aa, ab, aaa, aab, aba, abb, 为为上的一个上的一个语言语言。 如果如果a a表示字母，表示字母，b b表示数字，表示数字，c c看做其它符号，则看做其它符号，则L L即即是程序语言中的是程序语言中的标识符集标识符集，其中的每个标识符就是标识，其中的每个标识符就是标识符集中的一个符集中的一个句子句子。3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念2、文法、文法 （定义）（定义）文法通常表示成文法通常表示成四元组四元组GS=(VT，VN，S，):(1) VT为终结符号集为终结符号集，这是一个非空有限集，它的每个元素，这是一个非空有限集，它的每个元素称为称为终结符号终结符号。(2) VN为非终结符号集为非终结符号集，它也是一个非空有限集，其每个元，它也是一个非空有限集，其每个元素称为素称为非终结符号非终结符号，且有且有VTVN=；(3) S为文法为文法开始符开始符，是一个特殊的非终结符号，即，是一个特殊的非终结符号，即SVN；3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念2、文法（文法中的基本概念）、文法（文法中的基本概念）终结符号：终结符号：是指语言是指语言不可再分的基本符号不可再分的基本符号，通常是一个语，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种言的字母表；终结符代表了语法的最小元素，是一种个体个体记号记号。非终结符号：非终结符号：也称语法变量，它代表语法实体或语法范畴；也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符非终结符代表一个一定的语法概念，因此，一个非终结符是是一个类、一个集合一个类、一个集合。 注意：注意：1、字母表可以称为文法中的、字母表可以称为文法中的终结符集终结符集2、非终结符不能是字母表中的字符、非终结符不能是字母表中的字符3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念2、文法、文法 （定义）（定义）文法通常表示成文法通常表示成四元组四元组GS=(VT，VN，S，):(4) 是产生式的非空有限集是产生式的非空有限集，其中每个产生式，其中每个产生式(或称规则或称规则)是是一序偶一序偶(，)，通常写作，通常写作 或或 :=读作读作“产生产生”、 “是是”或或“定义为定义为”。在此，。在此，为产为产生式的左部，而生式的左部，而为产生式的右部，为产生式的右部，、是由终结符和非终是由终结符和非终结符组成的符号串，结符组成的符号串，(VTVN) +且至少有一个非终结符，且至少有一个非终结符，而而(VTVN) *。3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念2、文法（文法中的基本概念）、文法（文法中的基本概念）文法开始符号文法开始符号S：是一个特殊的非终结符，它代表文法所定是一个特殊的非终结符，它代表文法所定义的语言中我们义的语言中我们最终感兴趣的语法实体最终感兴趣的语法实体，即语言的目标，即语言的目标，而其它语法实体只是构造语言目标的中间而其它语法实体只是构造语言目标的中间变量变量产生产生式：式： (也称产生规则或规则也称产生规则或规则)是定义语法实体的一种书是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。写规则。一个语法实体的相关规则可能不止一个。 P1P2 Pn如果：如果：P1 | 2 | | n其中，每个其中，每个i(i=1, 2, , n)称为称为P的一个的一个候选式候选式，直竖，直竖“ | ”读为读为“或或”，它与，它与“”一样是用来描述文法的元语言符一样是用来描述文法的元语言符号号(即不属于即不属于的字符的字符)。3.1 3.1 文法和语言文法和语言例如，定义一个仅包含加和乘运算的表达式的文法例如，定义一个仅包含加和乘运算的表达式的文法GE: GS=(VT，VN，S，): VT =+ * ( ) i VN = E, T, F S = E 为以下产生式的集合：为以下产生式的集合： EE + T | T TT * F | F F (E)|i两种文法都可以识别包含加和乘运算的表达式，它们的区两种文法都可以识别包含加和乘运算的表达式，它们的区别将在后面的课程中讲解别将在后面的课程中讲解VT =+ * ( ) iVN = ES = E: Ei| E+E| E*E |(E)3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念 关于文法表示的约定：关于文法表示的约定：在在此后的讨论中，用大写字母此后的讨论中，用大写字母A、B、S、E等表示非终结符等表示非终结符，用用小写字母小写字母a、b、i、j等表示终结符等表示终结符，并用，并用希腊字母等表示文希腊字母等表示文法符号串法符号串，即，即、等均属于等均属于(VTVN)*。2.3 2.3 正规表达式与优先自动机简介正规表达式与优先自动机简介例例3.1 试构造产生标识符的文法。试构造产生标识符的文法。解答解答 首先，标识符是以字母开头的首先，标识符是以字母开头的字母数字字母数字串，串， 用用L表示表示“字母字母”类类非终结符，非终结符， 用用D表表示示“数字数字”类非类非终结符，终结符， TL | D （单个的字母或数字字符）（单个的字母或数字字符）S T | ST （字母或数字串）（字母或数字串）其次，如果用其次，如果用S表表示示“字母数字串字母数字串”类类，则，则T是一字母或数字，是一字母或数字，ST也是字母数字串，即有也是字母数字串，即有 La | b | | zD0 | 1 | | 9 而用而用T表表示示“字母或数字字母或数字”类非类非终结符，则有：终结符，则有：其中，产生式其中，产生式ST | ST是一种左递归形式，由它可以产生一串是一种左递归形式，由它可以产生一串T课本例题课本例题最后，作为最后，作为“标识符标识符”的的非终结符非终结符I，它或者是一单个字，它或者是一单个字母，或者为一字母后跟字母数字串，即母，或者为一字母后跟字母数字串，即 I L | LS 因此，产生标识符的文法因此，产生标识符的文法GI为：为： GI = ( VT， VN， I，): = (a, b, , z, 0, , 9, I, S, T, L, D, I, ) : I L | LS S T | ST T L | D L a | b | | z D 0 | 1 | | 9课本例题课本例题解答解答 根据题意，我们可以将奇数划分为如图根据题意，我们可以将奇数划分为如图3-1所示的三个部所示的三个部分，即最高位允许出现分，即最高位允许出现19，用非终结符，用非终结符B表示；中间部分可以表示；中间部分可以出现任意多位数字出现任意多位数字09，每一位用非终结符，每一位用非终结符D表示；最低位只允表示；最低位只允许出现许出现1、3、5、7、9等奇数，用等奇数，用A表示。表示。例例3.2 写一文法，使其语言是奇数集合，但不允许出现以写一文法，使其语言是奇数集合，但不允许出现以0打头打头的奇数。的奇数。课本例题课本例题图图3-1 奇数划分示意奇数划分示意课本例题课本例题 GN = (0, 1, , 9, N, A, M, B, D, N, ) : NA | MA /*一位数字一位数字 | 多位数字多位数字*/ MB | MD /*仅两位数字仅两位数字(无中间位无中间位) | 多于两位数字多于两位数字*/ A1 | 3 | 5 | 7 | 9 B1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 D0 | B由于中间部分可出现任意位，所以另引入了一个非终结符由于中间部分可出现任意位，所以另引入了一个非终结符M，它包括最高位和中间位部分。假定开始符为它包括最高位和中间位部分。假定开始符为N，则可得到文法，则可得到文法GN为为课本例题课本例题3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念3、文法产生的语言、文法产生的语言设文法设文法GS=(VT, VN, S, )，且，且、(VTVN)*，如果存，如果存在产生式在产生式A(VTVN)*)，则称，则称A可直接推出可直接推出，即即其中其中 “=”表示表示直接直接推导推导，是应用产生规则进行推导的是应用产生规则进行推导的记号，记号，这里仅使用一次规则这里仅使用一次规则注意注意“=”与与“”不同，不同，“”是产生式中的定义记号。直是产生式中的定义记号。直接推导是指对文法符号串接推导是指对文法符号串A中的非终结符中的非终结符A用相应的产生用相应的产生式式A的右部的右部来替换，从而得到来替换，从而得到A=3.1 3.1 文法和语言文法和语言u推导的说明：推导的说明：(1)如果如果1可直接推出可直接推出2，2可直接推出可直接推出3，n-1可直接推可直接推出出n ，即存在一个自，即存在一个自1至至n的推导序列：的推导序列：1=2=3=n(n0)，则称，则称1可可推导推导出出n，记为，记为1 =n，它表示从，它表示从1出发经过一步或若干步可推导出出发经过一步或若干步可推导出n。(2) 如果记如果记1 = 1， 1 = n则则表示从表示从1出发，经过出发，经过0步或若干步或若干步可推导出步可推导出n；也即；也即1 = n，意味着或者，意味着或者1=n，或者或者 1 =n。这个概念叫做。这个概念叫做“广义推导广义推导” 显然：直接推导的长度是显然：直接推导的长度是1，推导的长度，推导的长度1， 广义推导的长度广义推导的长度0+0*+3.1 3.1 文法和语言文法和语言u推导的举例：推导的举例： 例如例如，对下面的文法，对下面的文法GE： EE+E | E*E | (E) | i (3.1)其中，惟一的非终结符其中，惟一的非终结符E可以看成是可以看成是代表一类算术表达式代表一类算术表达式。可以。可以从从E出发进行一系列的推导，如出发进行一系列的推导，如表达式表达式 i+i*i 的的推导如下推导如下：E=E+E = E+E*E = E+E*i = E+i*i =i+i*i注意：在每一步推导过程中，注意：在每一步推导过程中，只能对其中的一个非终结符只能对其中的一个非终结符用其对应用其对应的产生式右部的一个候选式来替换。的产生式右部的一个候选式来替换。3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念句型：句型：假定假定GS是一个文法，是一个文法，S是它的开始符号，如果是它的开始符号，如果S=，(VTVN)*，则称，则称是文法是文法GS的一个的一个句型；句型；句子：句子：如果如果 VT *，则称，则称是文法是文法GS的一个句子。的一个句子。仅含终仅含终结符的句型是一个句子结符的句型是一个句子。由由定义可知，开始符定义可知，开始符S本身只能是文法的一个句型而不可能本身只能是文法的一个句型而不可能是一个句子；是一个句子；句子是特殊的句型。句子是特殊的句型。上面推导出的上面推导出的i+i*i是文法是文法GE的的一个句子一个句子(当然当然也是一个句型也是一个句型)，而，而E+E、E+E*E、E+E*i和和E+i*i都是文法都是文法GE的的句型句型 思考：文法思考：文法 GS: SaB|Bb Ba|b 的句型和句子有多少个？的句型和句子有多少个？*3.1 3.1 文法和语言文法和语言u3.1.1 文法和语言的基本文法和语言的基本概念概念文法产生的语言：文法产生的语言：对于文法对于文法GS，它所产生，它所产生的的句子的全体句子的全体称称为为由由文法文法GS产生的语言，记为产生的语言，记为L(G)，即有：，即有： L(G)= | S=且且 VT *注意注意： (1) S至少进行一次推导；至少进行一次推导； (2) S所推导出的所推导出的必须全部由终结符必须全部由终结符组成；组成； (3) 当文法给定，语言也就唯一地确定，即当文法给定，语言也就唯一地确定，即G L(G) ； 给定一个语言，它所对应的文法不是唯一的；给定一个语言，它所对应的文法不是唯一的； (4) L(G)是是VT *的子集，属于的子集，属于VT *的符号串不一定属的符号串不一定属 于于L(G)； +3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类语言学家语言学家Noam Chomsky于于1956年首先建立了形式语言的描述，年首先建立了形式语言的描述，定义了定义了四类文法及相应的形式语言四类文法及相应的形式语言，它对程序语言的设计、它对程序语言的设计、编译方法、计算复杂性等方面都产生了重大编译方法、计算复杂性等方面都产生了重大影响：影响：0型文法与型文法与0型语言型语言(对应图灵机对应图灵机)1型文法与型文法与1型型语言语言(对应线性界限自动机，自然语言对应线性界限自动机，自然语言)2型文法与型文法与2型语言型语言(对应下推自动机，程序设计语言对应下推自动机，程序设计语言)3型文法与型文法与3型语言型语言(对应有限自动机对应有限自动机)*3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类1、0型文法与型文法与0型语言型语言 如果如果文法文法GS的每一个产生式具有下列形式的每一个产生式具有下列形式： 其中其中，V*VNV*(注：注：V=VNVT)，即即至少含有一个非终至少含有一个非终结符结符；V*；则称文法；则称文法GS为为0型文法或短语文法，记为型文法或短语文法，记为PSG(Phrase Structure Grammar)。0型文法相应的语言称为型文法相应的语言称为0型型语言或称递归可枚举集，它的识别系统是图灵语言或称递归可枚举集，它的识别系统是图灵(Turing)机。机。例如：例如： S S ACaB Ca ACaB Ca aaC aaC CB CB DB CB DB CB E E aD aD Da AD Da AD AC AC aE aE Ea AE Ea AE 3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类2、1型文法与型文法与1型语言型语言 文法文法GS的每一个产生式的每一个产生式，均在，均在0型文法的基础上增加了型文法的基础上增加了字符长度满足字符长度满足| | |的限制，则称文法的限制，则称文法GS为为1型文法或上下型文法或上下文有关文法，记为文有关文法，记为CSG。1型文法相应的语言称为型文法相应的语言称为1型语言或上型语言或上下文有关语言，它的识别系统是线性界限自动机。下文有关语言，它的识别系统是线性界限自动机。1型文法型文法的等价定义的等价定义 文法文法GS的每一个产生式具有下列形式：的每一个产生式具有下列形式： A其中，其中，、V*，AVN， V+ 。显然，它满足前述定显然，它满足前述定义的长度限制，但它更明确地表达了上下文有关的特性，即义的长度限制，但它更明确地表达了上下文有关的特性，即A必必须在须在、的上下文环境中才能被的上下文环境中才能被所替换。所替换。3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类3、2型文法与型文法与2型语言型语言 文法文法GS的每一个产生式具有下列形式：的每一个产生式具有下列形式：A其中其中，A VN ，V*，则称文法，则称文法GS为为2型文法或上下文无型文法或上下文无关文法，记为关文法，记为CFG。2型文法相应的语言称为型文法相应的语言称为2型语言或上下文型语言或上下文无关语言，它的识别系统是下推自动机。无关语言，它的识别系统是下推自动机。例例：GSGS=(a,b,=(a,b,S S S, S, S SaSb , aSb , S Sabab ) ) 产生的语言为：产生的语言为：3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类3、2型文法与型文法与2型语言型语言 上下文无关文法上下文无关文法有足够能力描述现今程序设计语言的语法结有足够能力描述现今程序设计语言的语法结构。构。 例如：产生条件句的文法片段例如：产生条件句的文法片段语句语句-if -if 条件条件 then then 语句语句 | | if if 条件条件 then then 语句语句 else else 语句语句 | | 其他语句其他语句3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类4、3型文法与型文法与3型语言型语言文法文法GS的每个产生式具有下列形式：的每个产生式具有下列形式：Aa 或或 AaB其中，其中，A、B VN ，a VT *，则文法，则文法GS称为称为3型文法、型文法、正规文法或右线性文法，记为正规文法或右线性文法，记为RG。3型文法相应的语言称为型文法相应的语言称为3型型语言或正规语言，它的识别系统是有限自动机。语言或正规语言，它的识别系统是有限自动机。3型文法还可以型文法还可以呈现左线性形式：呈现左线性形式：Aa 或或 ABa3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类4、3型文法与型文法与3型语言型语言文法文法GS的每个产生式具有下列形式：的每个产生式具有下列形式：Aa 或或 AaB其中，其中，A、B VN ，a VT *，则文法，则文法GS称为称为3型文法、型文法、正规文法或右线性文法，记为正规文法或右线性文法，记为RG。3型文法相应的语言称为型文法相应的语言称为3型型语言或正规语言，它的识别系统是有限自动机。语言或正规语言，它的识别系统是有限自动机。3型文法还可以型文法还可以呈现左线性形式：呈现左线性形式：Aa 或或 ABa3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类5、4类文法的关系与区别类文法的关系与区别关系：关系：(1) 从从0型文法到型文法到3型文法的限制逐渐增；型文法的限制逐渐增；(2) 13型文法都属于型文法都属于0型文法；型文法；(3) 2、3型文法型文法不一定不一定属于属于1型文法：因为型文法：因为1型文法不允许存型文法不允许存在在“A”形式的产生式，则：如果形式的产生式，则：如果2 2、3 3文法不含有类似产生文法不含有类似产生式，则该文法属于式，则该文法属于1 1型文法。型文法。3.1 3.1 文法和语言文法和语言u3.1.2 形式语言分类形式语言分类5、4类文法的关系与区别类文法的关系与区别区别区别：(1) 1型文法中不允许有形如型文法中不允许有形如“A”的产生式存在，而的产生式存在，而2、3型文法则允许形如型文法则允许形如“A”的产生式存在；的产生式存在；(2) 0、1型文法的产生式左部存在含有终结符号的符号串或型文法的产生式左部存在含有终结符号的符号串或两个以上的非终结符，而两个以上的非终结符，而2型和型和3型文法的产生式左部只允许是型文法的产生式左部只允许是单个的非终结符号。单个的非终结符号。3.1 3.1 文法和语言文法和语言u3.1.3 正规表达式与上下文无关文法正规表达式与上下文无关文法1. 正规表达式到上下文无关文法的转换正规表达式到上下文无关文法的转换正规表达式所描述的语言结构均可用上下文无关文法描述，正规表达式所描述的语言结构均可用上下文无关文法描述，反之则不一定反之则不一定正规表达式构造上下文无关文法：正规表达式构造上下文无关文法： (1)构造正规表达式的构造正规表达式的NFA； (2)若若0为初始状态，则为初始状态，则A0为开始符号；为开始符号； (3)如果存在映射关系如果存在映射关系f(i,a)=j，则定义产生式，则定义产生式Ai aAj； (4)如果存在映射关系如果存在映射关系f(i, )=j，则定义产生式，则定义产生式Ai Aj； (5)如果如果i为终态，则为终态，则定义产生式定义产生式Ai 例题：例题： 用上下文无关文法描述正规表达式用上下文无关文法描述正规表达式1(0|1)*101正规式1(0|1)*101相应的非确定自动机构造的上下文无关文法：构造的上下文无关文法：GA0:A0-1A1A1-0A1|1A1|1A2A2-0A3A3-1A4A4- 3.1 3.1 文法和语言文法和语言u3.1.3 正规表达式与上下文无关文法正规表达式与上下文无关文法2. 正规表达式与上下文无关文法描述的对象正规表达式与上下文无关文法描述的对象正规表达式描述词法：正规表达式描述词法： (1)词法规则简单，采用正规表达式足以描述；词法规则简单，采用正规表达式足以描述； (2)正规表达式的表示比上下文无关文法更加简洁、直观和正规表达式的表示比上下文无关文法更加简洁、直观和易于理解；易于理解； (3)有限自动机的构造比下推自动机简单且分析效率高；有限自动机的构造比下推自动机简单且分析效率高；正规表达式适于描述线性结构，如标识符、关键字等；正规表达式适于描述线性结构，如标识符、关键字等； 上下文无关文法适于描述具有嵌套（层次）性质的非线性上下文无关文法适于描述具有嵌套（层次）性质的非线性结构，如结构，如if-else、while 等。等。