《编译原理语法分析》由会员分享，可在线阅读，更多相关《编译原理语法分析（114页珍藏版）》请在金锄头文库上搜索。
1、第3章 语法分析语法分析是编译过程的核心部分。语法分析的基本任务是在词法分析识别 出单词符号串的基础上，分析判断程序的语 法结构是否符合语法规则。语言的语法结构用上下文无关文法来描 述，因此，语法分析器的任务本质上是按上 下文无关文法的产生式，确定整个单词串是 否构成语法上正确的程序。语法分析的方法通常分为两类：自上而下分析法和自下而上分析法3.1 文法和语言 3.2 推导与语法树 3.3 自上而下分析方法 3.4 自下而上分析方法 3.5 LR分析法 3.1 文法和语言文法是程序语言的生成系统。自动机是程序语言的识别系统。用文法可精确定义一个语言,并依据 文法构造出识别该语言的自动机。因此,
2、 文法对程序语言和编译程序的构造具有 重要意义,如程序语言的词法可用正规文 法描述,语法可用上下文无关文法描述,而 语义可借助于上下文有关文法描述。3.1.1 文法和语言的概念1语言通常用表示字母表。由字母表中字符组成的有穷序列称 为上的字符串或字。字母表上的所有 字符串(包括空串)组成的集合用*表示。对于字母表, *上的任一子集称为 上的一个语言, 记为L, L*。语言L的每 个字符串称为语言L的一个语句或句子。2. 文法终结符是语言不可再分的基本符号, 通常为一个语言的字母表。终结符代表了 语法的最小元素,是一种个体记号。非终结符也称语法变量, 它代表语法 实体或语法范畴。一个非终结符是一
3、个类 、一个集合。例如, 变量、常量、+、* 等为终结符 ，而 “算术表达式”为非终结符, 它代表一 定算术式组成的类,如i*(i+i)、i+i+i等,即非 终结符代表由终结符组成且满足一定规则 的符号串的集合。文法可表示为四元组G=(VT,VN,S,), 其中(1) VT为非空终结符集;(2) VN为非空非终结符集,且VTVN=;(3) S为文法开始符, SVN;(4)是产生式的非空有限集, 其中每个产生式(规则)记作 或 := 左部(VTVN)+至少含一非终结符,右部(VTVN)*。产生式 (也称产生式规则或规则) 是 定义语法实体的一种书写规则。一个语 法实体的相关规则可能不止一个, 如
4、:P1, P2 , Pn相同左部的产生式可合并为一个:P 1| 2| n其中, i(i=1,2,n)称为P的候选式。例3.1 试构造产生标识符的文法。 分析: 用L表示字母,D表示数字,T表示字母或数字 , 则 LabzD019TLD用S表示字母数字串,则ST是字母数字串,即ST | ST标识符I或为单个字母, 或为一字母后跟字母数字串, 即ILLS解: 产生标识符的文法GI为：G=(a,b,z,0,9,I,S,T,L,D,I,)其中,: ILLSSTSTTLDLabzD019例3.2 写一文法, 使其语言是奇数集, 但不允许出现以0打头的奇数。 解: 将奇数划分为三个部分：最高位允许出现19
5、,用非终结符B表示;中间部分可出现任意多位数字09,每一位用非终结符D表示;最低位只出现1,3,5,7,9, 用A表示。由于中间部分可任意位,故需另引入一非终结符M,它包括最高位和中间部分。MB最 高 位中间位DDDA最 低 位解: 奇数集文法GN为:G=(0,1,9,N,A,M,B,D,N,): NA | MAMB | MDA1 | 3 | 5 | 7 | 9B1|2|3|4|5|6|7|8|9D0 | B3. 文法产生的语言设G=(VT,VN,S,)且, (VTVN)*,若存在产生式A, (VTVN)*，则称A可直接推出, 记为A 注意与的不同:是产生式中的定义记号,表示直接推导,是对文法
6、符号串A中A用产生式A的右部替换。关于推导的两点说明： (1)若1可直接推出2, 2可直接推出3,即存在一个自1至n的推导序列:12 3 n (n0)则称1可推导出n,记为1 n, 表示从1出发经1步或若干步可推导出n(2)若记1 1, 则1 n表示从1出发,经过0步或若干步可推导出n,即1 n意味着或1=n, 或1 n。+0*+例如,考虑算术表达式文法GE：EE+EE*E(E)i非终结符E代表一类算术表达式,从E出发可进行一系列推导,表达式 i+i*i 的推导如下：E E+E E+E*E E+E*i E+i*i i+i*I 注意: 在每一步推 导中,只能对其中一个非终结符用其对应的产生式右部
7、的一个候选式来替换。假定GS是一个文法, S是其开始符号, 若S , (VTVN)*, 则称是文法GS的一个句型 ; 若S , VT*， 则称是文法GS的一个句子。 由上述定义知：仅含终结符的句型是一个句子。开始符S是一个句型而不是一个句子 。i+i*i是一个句子, 也是一个句型,E+E*E、E+E*i和E+i*i是句型,但不是一个句子。*对于文法GS, 它所产生的句子的全 体称为由文法GS产生的语言,记为LG 。 L(G)= | S 且VT* 3.1.2 形式语言分类Chomsky于1956年定义了四类文法 及相应的四类形式语言, 它对程序语言的设计、编译方法、计算复杂性等方面都 产生了重大
8、影响。+1 0型文法与0型语言 (短语文法)若文法G的每个产生式具有下列形式:其中至少含一个非终结符，则称文法G为0型文法或短语文法,记为PSG。0型文法相应的语言称为0型语言,它的识别系统是图灵机。21型文法与1型语言 (对应自然语言)若文法G的每个产生式均满足| |则称文法G为1型文法或上下文有关文法, 记为CSG。1型文法相应的语言称为1型语言。1型文法的另一种定义: 文法G的每个产生式具有下列形式：A其中, ,V*, AVN, V+它更明确地表达了上下文有关的特性 。3 2型文法与2型语言 (对应程序设计语言 )若文法G的每个产生式具有下列形式：A其中, AVN, V*称文法G为2型文
9、法或上下文无关文法,记为CFG。2型文法相应的语言称为2型语言或上下文无关语言。它的识别系统是下推自动机。4 3型文法与3型语言 (对应有限自动机)若文法G的每个产生式具有下列形式：Aa 或 AaB其中，A,BVN，aVT*，则文法G称为3型文法或正规文法或右线性文法，记为RG。3型文法相应语言为3型语言或正规语言 。它的识别系统是有限自动机。3型文法还可呈左线性形式：Aa 或 ABa5. 四类文法的关系与区别从0型文法到3型文法逐步增加限制 。 一般地,13型文法属于0型文法，2,3 型文法属于1型文法,3型文法属于2型文法 。 四类文法的区别： (1)1型文法不允许有形如A的产生式,2,3
10、型文法允许形如A的产生式; (2)0,1型文法的产生式左部可以是含终结符的符号串或两个以上的非终结符,2,3型文法的产生式左部只允许是单个非终结符。anbncn|n1anbncm|m,n1ambnck|m,n,k1这说明对文法规则定义形式的限制虽 加强了, 但相应的语言反而更大了。因此, 不能主观认定文法限制越大则语言越小, 即下述结论不成立：3型语言 2型语言 1型语言 0型语言编译方法中通常用3型文法描述词法, 用FA识别单词; 利用2型文法描述语法,用 下推自动机PDA识别各种语法成分。例3.4 给出=a,b上具有奇数个a和奇数个b的所有字符串集合的正规文法。 解: 如图, 由S出发经奇
11、数个a到达A, 或经奇 数个b到达B。再由A出发经奇数个b到达C; 同样, 由B出发经奇数个a到达C。 正规文法GS如下:SaA | bBAaS | bCBbS | aCCbA | aB| bbbbaaaaSAB2 C3.1.3 正规式与上下文无关文法 1. 正规式到上下文无关文法的转换由正规式构造CFG的一种方法：(1)构造正规式的NFA；(2)若0为初始状态, 则A0为开始符；(3)若存在映射关系f(i,a)=j,则定义产生式Ai aAj；(4)若存在映射关系f(i,)=j，则定义产生式Ai Aj；(5) 若i为终态, 则定义产生式Ai 。例3.5 用CFG描述正规式(a|b)*abb 解
12、: 先构造识别(a|b)*abb的NFA M:0122 3ababbGA0: A0aA0bA0aA1A1bA2A2bA3A3由正规式构造CFG的另一种方法：通过分析正规式凭经验直接构造。 例如, 把(a|b)*abb看作(a|b)*和abb两部分,第 一部分是由0个或若干个a和b组成的字符 串,第二部分仅由abb字符串组成,由此得 到CFG GA0如下：GA0: AHTHaH|bH|Tabb2. 正规式与CFG描述的对象CFG既可描述语法,又可描述词法。基于下述原因,通常用正规式描述词法:(1)词法规则简单,用正规式已足以描述;(2)正规式的表示比CFG更简洁、直观和易于理解；(3) FA的构
13、造比PDA(下推自动机)的构造简单且效率高。 注意: (1)语言的描述和语言的识别是表示一 种语言的两个不同侧面, 二者缺一不可。(2)正规式通常适合于描述线性结构, 如标识符、关键字和注释等; 上下文无关 文法通常适合于描述具有嵌套(层次)性质 的非线性结构, 如 if-else语句、while语句。3.2 推导与语法树 3.2.1 推导与短语 1. 规范推导最右推导: 在推导过程中,若每一步推 导都是对句型中的最右非终结符用相应产 生式的右部进行替换, 则称这种推导为最 右推导。最左推导: 在推导过程中,若每一步推 导都是对句型中的最左非终结符用相应产 生式的右部进行替换, 则称这种推导为
14、最 左推导。例如, 考虑句子 i+i*i 按文法GE的推导最左推导: EE+Ei+Ei+E*E i+i*E i+i*i最右推导: EE+EE+E*EE+E*i E+i*ii+i*i 注意: 推导过程不唯一, 通常只考虑最左推导或最右推导。最右推导又称为规范推导。规范推导的逆过程称为规范归约。2. 短语如果S A且A ,则称是句型关于非终结符A的一个短语,简称是的一个短语。如果S A且A ,则称为句型的一个直接短语或简单短语。 注意: 短语的两个条件缺一不可。考虑i+i*i, E i+i, 但i+i不是短语 *+*+3. 句柄句型的最左直接短语称为句柄。注意, 一个句型的直接短语不唯一,但最左直
15、接短语唯一。例如, 对S A ,若为终结符串,则句型中的句柄为。将句型中的句柄用产生式的左部符号代替便得到新句型A, 这是一次规范归约, 恰与规范推导相反。*4. 素短语含有终结符的短语,如果它不存在具有同样性质的真子串,则该短语为素短语 。例如,在E E+E*i中, i、E*i、E+E*i是句型E+E*i的短语,其中, i为素短语, E*i虽含终结符, 但其真子串i含终结符, 故E*i不是素短语, 同样E+E*i也不是素短语。+3.2.2 语法树与二义性 1. 语法树对于程序语言, 有两个问题需要解决:(1)判别程序在语法上是否正确;(2)句子的识别或分析。为便于分析句子而引入语法树。语法树以图示化形式把句子分解成各个组成部分,以分析句子的
