编译原理与技术讲义-第3章.ppt

青岛大学信息工程学院,编译原理与技术,第3章 程序语言的语法描述,编译原理与技术,2,主要内容,文法和语言 文法的分类 文法的等价变换 语法分析概述,编译原理与技术,3,程序语言的语法描述,程序语言的定义 程序语言通常是一个能完整、准确和规则地表达人们的意图，并用以指挥或控制计算机工作的“符号系统”。它完整的定义包括语法、语义及语用三个方面。 一个程序语言的语法是指这样一组规则，使用它可以形成和产生一个合适的程序。这些规则一部分称为词法规则，另一部分称为语法规则（或产生规则）。,编译原理与技术,4,程序语言的语法描述,一个程序语言的语义是指这样一组规则，使用它可以定义一个程序的意义。静态语义是一系列限定规则，确定哪些合乎语法的程序是合适的；动态语义也称作运行语义或执行语义，表明程序要做些什么，要计算什么。 语用表示语言符号及其使用者之间的关系，涉及符号的来源、使用和影响。,编译原理与技术,5,3.1 文法和语言,文法的形式定义 定义3.1: 定义四元组G=(VN，VT，P，S)是一个文法。其中VN , VT和 P都是非空有限集合，分别称为非终结符号集合、终结符号集合及产生式集合。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共元素，即VNVT = 。通常用V表示VNVT，称为文法G的字母表。,编译原理与技术,6,3.1 文法和语言,例3.1：文法G1=(VN, VT, P, S)，其中VN =S，VT =0, 1，P=S0S1, S01。 该文法只有一个非终结符S，有两个终结符0和1，有两条产生式，开始符号是S。 很多时候，不用将文法G的四元组显式地表示出来，而只将产生式写出。一般约定，第一条产生式的左部是开始符号，用尖括号括起来的是非终结符号，不用尖括号括起来的是终结符号，或者用大写字母表示非终结符号，小写字母表示终结符号。另外也有一种习惯写法，将G写成GS，其中S是开始符号。因此，例3.1还可以写成： G：S0S1 或 GS：S0S1 S01 S01,编译原理与技术,7,3.1 文法和语言,有时，为书写简洁，常把相同左部的产生式，形如A1,A2,An，缩写为：A1|2|n。这里的元符号 | 读做“或”。 如，例3.1的产生式可以写成S 0S1 | 01。 注意元符号和源符号的区别： 文法中使用的元符号或 =表示左部由右部定义，| 表示定义同一个左部的几个可选择的右部。而源符号是指文法定义的语言中的符号，全部由文法的终结符构成。,编译原理与技术,8,3.1 文法和语言,例3.2：文法G2=(VN, VT, P, S )，其中 VN =标识符, 字母, 数字， VT =a, b, c, , x, y, z, 0, 1, , 9 ， P =标识符字母|标识符字母 |标识符数字 字母a | b | | z 数字0 | 1 | |9 S =标识符，这里使用尖括号 和 括起非终结符。,编译原理与技术,9,3.1 文法和语言,例3.3：一个文法的几种写法： G=( S, A, a, b, P, S ) 其中P= SaAb, Aab, AaAb, A G: SaAb Aab AaAb A, GS: Aab AaAb A SaAb GS: Aab |aAb | SaAb,编译原理与技术,10,3.1 文法和语言,推导与归约 定义3.2: 设是文法G=(VN，VT，P，S)的产生式，和是V*中的任意符号。若有符号串v，w满足：v = ，w = ，则说v直接产生w，或者说，w是v的直接推导。记作vw。也可以说w直接归约到v。归约是推导的逆过程。,编译原理与技术,11,3.1 文法和语言,对例3.1文法G，可以给出直接推导的一些例子如下： v = 0S1，w = 0011， 直接推导：0S10011， 使用的规则：S01，这里 =0， =1。 v = S，w = 0S1， 直接推导：S0S1， 使用的规则：S0S1，这里 = ， = 。 v = 0S1，w = 00S11， 直接推导：0S100S11， 使用的规则：S 0S1，这里 = 0， =1。,编译原理与技术,12,3.1 文法和语言,对例3.2文法G，直接推导的例子有： v =标识符，w =标识符字母， 直接推导：标识符标识符字母， 使用的规则：标识符标识符字母， 这里 = = 。 v =标识符字母数字， w =字母字母数字， 直接推导：标识符字母数字 字母字母数字， 使用的规则：标识符字母。 这里 = ， =字母数字。 v = abc数字，w = abc5， 直接推导：abc 数字 abc5, 使用的规则：数字5，这里 = abc, = 。,编译原理与技术,13,定义3.3: 如果存在直接推导的序列：v = w0 w1 w2 wn= w, (n0)，则称v推导出w，推导长度为n。或者称w归约到v。记作v w。若有v w，或v = w，则记作v w。 定义3.19: 设GS是一文法，如果符号串x是从开始符号推导出来的，即有S x，则称x是文法GS的句型。若x仅由终结符号组成，即S x，xVT*，则称x为GS的句子。,3.1 文法和语言,编译原理与技术,14,3.1 文法和语言,对例3.1文法，存在直接推导序列 v = 0S100S11 000S111 00001111= w， 即0S1 00001111，也可记作0S1 00001111。 对例3.2文法，存在直接推导序列 v =标识符 标识符数字 字母数字 x数字 x1= w， 即标识符 x1，也可记作标识符 x1。 S, 0S1, 000111都是例3.1的文法G的句型，其中000111是G的句子。标识符字母, 字母数字, a1等都是例3.2文法G的句型，其中a1是G的句子。,编译原理与技术,15,3.1 文法和语言,例3.4：终结符号串(i*i+i)是文法 EE+E | E*E | (E) | i 的一个句子。因为有从开始符号E至终结符号串(i*i+i ) 的一个推导： E (E) (E+E) (E*E+E) (i*E+E) (i*i+E) (i*i+i ) 而E, (E), (E*E+E)等是文法的句型。,编译原理与技术,16,3.1 文法和语言,定义3.4: 若推导过程中每一步都是替换最左（右）边的非终结符，则称该推导为最左（右）推导。句型的最右推导称为规范推导，其逆过程最左归约称为规范归约。 例3.5：文法GS: SAB AA0|1B B0|S1 给出句子101001的最左和最右推导。 解：最左推导： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推导： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001,编译原理与技术,17,3.1 文法和语言,文法产生的语言 定义3.5: 文法G的全部句子组成的集合称为G产生的语言，记为L(G)，即 L(G)= x | S x，其中S为开始符号，且xVT* 例3.1的文法G1 的语言是L(G)=0n1n | n1 。例3.2的文法G2的句子是字母打头的、由字母和数字组成的符号串，也就是程序设计语言中用于表示名字的标识符，因此产生的语言就是所有标识符的集合。,编译原理与技术,18,3.1 文法和语言,例3.6：考虑文法G1: S bA A aA | a 求它所定义的语言。 解：从开始符S出发，可以推出如下句子： SbA ba SbA baA baa SbA baA baaA baaa 因此，文法G1产生以b开头、后面跟一个或多个a的所有符号串， 从而L(G1)=ban | n1。,编译原理与技术,19,3.1 文法和语言,例3.7：设有文法G2: S P | aPb P ba | bQa Q ab 求语言L(G2)。 解：从开始符S出发，可以推出如下句子： SPba SP bQa baba SaPbabab SaPbabQabababab 文法G2共能产生4个句子，因此L(G2)=ba, baba, abab, ababab ,编译原理与技术,20,3.1 文法和语言,例3.8：设G3=(VN，VT，P，S)， VN=S,B,E， VT=a,b,e，P由下列产生式组成： (1) SaSBE (2) SaBE (3) EBBE (4) aBab (5) bBbb (6) bEbe (7) eEee 求语言L(G3)。 解： L(G3)=anbnen|n1。,编译原理与技术,21,3.1 文法和语言,语言的验证 一般来说，对“文法G产生语言L”的证明包括两部分： （1）证明由G产生的每个字符串都在L中。 （2）证明L中的每个字符串都能由G产生。,编译原理与技术,22,3.1 文法和语言,例3.9：验证文法G1 : S (S ) S | 产生语言L(G1) = 配对的括号串的集合。 证明：（1）按推导步数进行归纳证明：推出的是配对括号串 归纳基础： S 归纳假设：少于n步的推导都产生配对的括号串 归纳步骤：n步的最左推导如下 S (S )S (x) S (x) y 其中x、y是配对的括号串，从而(x) y也是配对的 括号串，即n步的推导也产生配对的括号串。 因此，由G1产生的每个字符串都是配对的括号串都在 L(G1)中。,编译原理与技术,23,3.1 文法和语言,（2）按符号串的长度进行归纳证明：配对括号串可由S推出 归纳基础： S 归纳假设：长度小于2n的配对括号串都可以从S推导出来 归纳步骤：考虑长度为2n(n1)的w = (x) y，其中w、x、y 均为配对括号串，有 S (S )S (x) S (x) y 即长度为2n的配对括号串都可以从S推导出来。 因此，L(G1)中的每个字符串都能由G1产生。 由（1）、（2）可知，文法G : S (S ) S | 产生语言L(G1) = 配对的括号串的集合。,编译原理与技术,24,例3.10：验证文法G2: EE + aa 产生的语言是所有由若干个“+”分隔开的a 组成的符号串，即 L(G2) = a, a + a, a + a + a, a + a + a + a, . . . 证明：(1) 按a 的数目n归纳证明：每个符号串a + a + . . .+ a L (G2)。 归纳基础：因为Ea，所以Ea， aL(G2)。即n=1时成立。 归纳假设：假设s = a + a + . + aL (G2)，且有n-1个a，则存在 推导E s。 归纳步骤：使用产生式EE + a一次，再利用归纳假设可得推 导：E E + a s + a。因此，s + aL (G2)，其中 有n个a。 因此，所有形如a + a + . . .+ a的符号串在L (G2)中。,3.1 文法和语言,编译原理与技术,25,(2) 按推导的长度n归纳证明：sL(G2)必满足格式a + a + . + a。 归纳基础：推导的长度为1时，只能为E a，而a是满足格式。 归纳假设：长度为n-1的推导能推出满足格式a + a + . + a。 归纳步骤：考虑长度为n1的推导E s。因为n 1，因此第一步 推导必然使用产生式EE + a，从而E E + a s+ a = s ， 其中推导E s 长度为n-1，由归纳假设可知s 满足格式。 因此，s=s+ a 也满足格式a + a + . + a。 因此，L(G2)中的所有符号串都满足格式a + a + . + a。 由（1）、（2）可知，文法G2 : EE + aa产生语言L(G2) = 配对的括号串的集合。,3.1 文法和语言,编译原理与技术,26,3.1 文法和语言,语言的文法表达 由已知语言求其文法描述，实际上就是讨论语言中的句子，根据句子的特点利用层次分析的方法，构造相应的文法。构造过程中经常会用到下面形式的产生式。 右递归（right recursive） 产生式： A aA | a 产生a+ ，A aA | 产生a* 左递归（left recursive） 产生式： A Aa | a产生a+ ，A Aa |产生a*,编译原理与技术,27,3.1 文法和语言,例3.11：试构造语言L1=anbnci | n1, i0=ab, aabb, , abc, aabbc, , abcc, aabbcc, 的文法。 解：L1中符号串的特点是：串中含一个或多个a并置，可以看作含有a+形式；串中含一个或多个b并置，可以看作含有b+形式；串中含有0个或多个c，可以看作是c*形式。因此，该语言可以看作是a+、b+与c*的连接。 使用A aA | a 可以产生a+，使用B bB | b 可以产生b+，使用C cC | 可以产生c*。而要表示它们的连接，只需将非终结符A、B、C连接起来即可。 因此，满足要求的文法为G(Z): Z ABC A aA | a B bB | b C cC | ,编译原理与技术,28,3.1 文法和语言,也可以使用左递归产生式，得到满足要求的另一个文法 G(Z): Z ABC A Aa | a B Bb | b C cC | 实际上，a+与b+的产生过程完全一致，可以将产生它们的产生式合并为A aAb | ab。则得到满足要求的另一个文法 G(Z): Z AB A aAb | ab B cB | 由此可以看出，已知语言求文法，文法不唯一，可以有不同的表达方法。,编译原理与技术,29,3.1 文法和语言,例3.12：已知语言L2=x | xa,b,c*, 且x是回文字=, aa, bb, cc, aba, aca, bab, bcb, cac, cbc, aabaa, ，写出该语言的文法。 解：L2中符号串的特点是：串中若包含符号，则以a开头必以a结束，以b开头必以b结束，串中符号对称出现。可以设计文法为 G(Z): Z aZa | bZb | cZc | a | b | c | 。,编译原理与技术,30,3.1 文法和语言,分析树与语法树 分析树（parse tree） 定义3.6: 语法分析树用来描述句型的结构，是句型推导的一种树型表示，简称分析树。 给定文法G=(VN, VT, P, S)，对于G的任何句型都能构造相应的分析树，这棵树满足下列条件： 每个结点都有一个标记。根结点的标记是开始符号S；非叶结点 的标记是非终结符；叶结点的标记是终结符或非终结符或。 如果一个非叶结点A有n个儿子结点，从左到右标记为A1，A2， ，Ak，则AA1A2Ak一定是P中的一个产生式。,编译原理与技术,31,3.1 文法和语言,例3.13：文法GS: S aAS | S A SbA | SS | ba 其句子aabbaa的语法分析树如图3.1所示。,图3.1 aabbaa的语法分析树,编译原理与技术,32,3.1 文法和语言,语法树表示了在推导过程中使用了哪个产生式和用在哪个非终结符上，它并没有表明施用产生式的顺序。 比如例3.13中句子aabbaa的推导过程可以列举3个： 推导过程1：S aAS aAa aSbAa aSbbaa aabbaa 推导过程2：S aAS aSbAS aabAS aabbaS aabbaa 推导过程3：S aAS aSbAS aSbAa aabAa aabbaa,编译原理与技术,33,3.1 文法和语言,语法树（syntax tree） 定义3.7: 抽象语法树用来表示程序层次结构，它把分析树中对语义无关紧要的成分去掉，是分析树的抽象形式，简称语法树，也称语法结构树或结构树。 语法树可看作分析树的浓缩，而分析树可看成具体语法树。,编译原理与技术,34,3.1 文法和语言,例3.14：条件语句产生式S if B-expr then S1 else S2的抽象语法树与语法分析树如图3.2所示。 (a) 语法树 (b) 分析树 图3.2条件语句的语法树与分析树 抽象语法树中，操作符和关键字都不作为叶结点出现，而是作为内部结点。,编译原理与技术,35,3.1 文法和语言,例3.15：赋值语句产生式为赋值语句 i := E， 表达式的产生式为 E E+E | E*E | -E | id， 则a := b* -c + b * -c的语法树与分析树如图3.3所示。 (a) 语法树 (b) 分析树 图3.3 赋值语句的语法树与分析树,编译原理与技术,36,3.2 文法和语言,文法的二义性 二义性文法 定义3.8: 给定一个文法G，如果其产生的语言L(G)中存在存在某个句子对应两棵或两棵以上分析树，则称文法G是二义性的。 或者说，若一个文法中存在某个句子，它有两个或两个以上不同的最左(最右)推导，则该文法是二义的。,编译原理与技术,37,3.1 文法和语言,例3.16：对于简单表达式文法 GE: EE+E | E-E | E*E | E/E | (E) | i 句子i*i+i有如下两个不同的最左推导，它们所对应的分析树如图3.4所示。 因此该文法是二义性文法。 推导一：E E+E E*E+E i*E+E i*i+E i*i+i 推导二：E E*E i*E i*E+E i*i+E i*i+i,(a) 推导一的分析树 (b) 推导二的分析树 图3.4 句子i*i+i两棵不同的分析树,编译原理与技术,38,3.1 文法和语言,注意文法二义性和语言二义性的区别： 这是两个不同的概念，因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说该语言是二义的。,编译原理与技术,39,3.1 文法和语言,文法二义性的消除 方法一：设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。这样的规则称作消除二义性规则（disambiguating rule）。 其优点为：无需修改文法（可能会很复杂）就可消除二义性； 其缺点为：语言的语法结构再也不能由文法单独提供。 方法二：将文法改变成一个强制正确分析树的构造的格式，就可以解决二义性。,编译原理与技术,40,3.1 文法和语言,为了消除例题3.16中简单表达式文法中的二义性，可以设置消除二义性规则，它建立了3个运算相互之间的优先关系。其标准解决办法是给予加法和减法相同的优先权，而乘法和除法则有高一级的优先权， 并按惯例规定它们都服从左结合。这样句子i*i+i相当于(i*i)+i，它有惟一的分析树为图3.4(a)。,编译原理与技术,41,3.1 文法和语言,现在来看重写文法以消除二义性的方法。为了处理文法中的运算优先权问题，就必须把具有相同优先权的算符归纳在一组中，并为每一种优先权规定不同的规则。 例如，将例3.11中文法分组为 EE+E | E-E | T TT*T | T/T | F F (E) | i 在这个文法中，加法和减法则被归在E规则下，乘法和除法被归在T规则下。由于T只能由E生成，这就意味着加法和减法在分析树和语法树中将被表现地“更高一些”（也就是更接近于根结点），因此它们的优先权就比乘法和除法低一级。这样将算符放在不同的优先权级别中的办法是在语法说明中使用BNF的一个标准方法。这种分组称作优先级联（precedence cascade）。,编译原理与技术,42,3.1 文法和语言,分组后的文法未指出算符的结合性而且仍有二义性。原因在于形如EE+E| E-E的产生式，它既是左递归又是右递归，若要得到符号串i+i-i，既可以先使用E+E再对第二个E使用E-E，也可以先使用E-E再对递一个E使用E+E。解决方法是强制匹配一边的递归，用EE+T | E-T | T代替EE+E| E-E | T，使加法和减法都服从左结合。若要使它们服从右结合，则可以改为ET+E| T-E | T。也就是说，左递归规则使得它的算符在左边结合，而右递归规则使得它们在右边结合。 这样，若统一规定服从左结合，则例3.16中文法可以修改为 EE+T | E-T | T TT*F | T/F | F F (E) | i,编译原理与技术,43,3.1 文法和语言,可以验证，该文法是一个无二义文法。句子i+i*i-i惟一的分析树与语法树如图3.5所示。 (a) 分析树 (b) 语法树 图3.5 句子i+i*i-i的分析树与语法树,编译原理与技术,44,下面介绍一种确定符号优先关系的方法，称简单优先关系。它规定文法G中任意两个符号的优先关系如下： （1）X Y，当且仅当有产生式 ABY，且有推导 B rX及Y a。 其中A、B为非终结符，X、Y为待定优先关系的两个任意符号，、和为由终结符和非终结符组成的任意符号串，可以是空串。a是终结符。,3.1 文法和语言,编译原理与技术,45,3.1 文法和语言,悬挂else问题 考虑下面条件语句的文法： statement if-stmt | other if-stmt if (exp) statement | if (exp) statement else statement exp 0 | 1 该文法是二义的，符号串if (0) if (1) other else other两棵分析树，如图3.6所示。,编译原理与技术,46,3.1 文法和语言,图3.6符号串if (0) if (1) other else other两棵不同的分析树（一）,编译原理与技术,47,3.1 文法和语言,图3.6 符号串if (0) if (1) other else other两棵不同的分析树（二）,编译原理与技术,48,3.1 文法和语言,第一棵分析树将else部分与第一个if语句结合；第二棵分析树将else与第2个if语句结合。这种二义性称作悬挂else问题（dangling else problem)。 一般的程序语言中，条件语句的else部分总是与没有else部分的最近的if语句结合。这个消除二义性的规则被称为用于悬挂else问题的最近嵌套规则（most closely nested rule）。,编译原理与技术,49,3.1 文法和语言,解决悬挂else二义性比处理前面的二义性困难，修改后为： statement matched-stmt | unmatched-stmt matched-stmt if (exp) matched-stmt else matched-stmt | other unmatched-stmt if (exp) statement | if (exp) matched-stmt else unmatched-stmt exp 0 | 1 if语句中只允许有一个matched-stmt出现在else之前，这样就迫使尽可能快地匹配所有的else部分。使用消除二义性后的文法，符号串if (0) if (1) other else other的分析树如图3.7所示。,编译原理与技术,50,3.1 文法和语言,图3.7 消除二义性后的分析树,编译原理与技术,51,3.2 文法的分类,形式语言的分类 Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类： 0型文法 1型文法 2型文法 3型文法,编译原理与技术,52,3.2 文法的分类,0型文法 定义3.9: 文法G=(VN，VT，P，S)，如果它的每个产生式形如，其中V*VNV*，V*，则G是一个0型文法。其中V= VNVT。 0型文法也称为短语文法（PSG, phrase structure grammars）。由定义可知，0型文法的产生式左端是由终结符和非终结符组成的字符串，并且至少含有一个非终结符。产生式右端是由终结符和非终结符组成的任意字符串。,编译原理与技术,53,3.2 文法的分类,例3.17：文法G0S： SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 则该文法是一个0型文法，产生的语言为 L0=| iI+= aa, aaaa, aaaaaaaa, 由0型文法生成的语言称为0型语言（或递归可枚举语言）。它可由图灵（Turing）机识别。,编译原理与技术,54,3.2 文法的分类,1型文法 对于程序设计语言来，0型文法有很大的随意性，还须加以限制。对0型文法产生式的形式进一步加以限制，可以得到1型文法。 定义3.10: 文法G=(VN，VT，P，S)，如果它是0型文法，并且每个产生式形如1A2 12，其中1,2V*，V+，AVN，则G是一个1型文法。 1型文法也称为上下文有关文法（CSG, context-sensitive grammars）。只有当非终结符A的前后分别为1,2 时，才能将A替换为。即对非终结符进行替换时，务必考虑上下文，这也是称之为上下文有关文法的原因。并且一般不允许替换成空串。,编译原理与技术,55,3.2 文法的分类,1 型文法还有另一种定义形式： 定义3.11: 文法G=(VN，VT，P，S)，如果它是0型文法，并且每个产生式满足|（产生式S例外，但S不得出现在任何产生式的右部），则G是一个1型文法。其中| 和| |分别为和的长度。 由该定义可知，1型文法除了可能有S外，其余产生式右端的符号串长度大于等于左端符号串长度。 上述两种定义是等价的。即任一种形式定义的文法产生的语言都可由另一种形式定义的文法产生。需要注意的是，根据定义，含有产生式的文法不是1型文法。由于实际需要，我们将S作为1型文法的特例接受。,编译原理与技术,56,3.2 文法的分类,例3.18：文法G1S： S | A AaABC AabC CBBC bBbb bCbc cCcc 则该文法是一个1型文法，产生的语言为 L1=ai bi ci | i0=, abc, aabbcc, 1型文法产生的语言称为上下文有关语言CSL，它可由线性限界自动机识别。,编译原理与技术,57,3.2 文法的分类,2型文法 对1型文法的产生式进一步限制，可得2型文法。 定义3.12: 文法G=(VN，VT，P，S)，如果它是1型文法，并且每个产生式A满足AVN，V+，（产生式S例外），则G是一个2型文法。 2型文法也称为上下文无关文法（CFG, context-free grammars）。用取代非终结符A时，与A所在的上下文无关，因此取名为上下文无关文法。 由定义可知，2型文法所有产生式左端的符号都是单个的非终结符。除了可能有产生式S外，其余产生式右端不能是空串。,编译原理与技术,58,3.2 文法的分类,例3.19：文法G2S： SaSb Sab 则该文法是一个2型文法，产生的语言为 L2=ai bi | i1=ab, aabb, aaabbb, 程序设计语言的文法是上下文无关的，如C，Pascal。2型文法产生的语言称为上下文无关语言CFL，它可由下推自动机识别。,编译原理与技术,59,3.2 文法的分类,3型文法 对2型文法的产生式进一步限制，可得3型文法。 定义3.13: 文法G=(VN，VT，P，S)，如果它是2型文法，并且仅含有形如AaB或Aa 的产生式，则称G为右线性文法。若仅含有形如ABa或Aa 的产生式，则称G为左线性文法。其中A,B VN ，a VT。左线性文法和右线性文法都称为3型文法。 3型文法也称正规文法（RG, regular grammars）。,编译原理与技术,60,3.2 文法的分类,例3.20：文法G3S： S lA | l，A 0A | 0 该文法是一个右线性文法，产生的语言为 L3=1 0i | i0=1, 10,100, 1000, 例3.21：文法G4S： S Bc|Sc，B Ab| Bb，A Aa|a 该文法是一个左线性文法，产生的语言为 L4=ai bj ck | i, j, k1 例3.22：定义标识符的3型（正规）文法为 GI: I lT | l，T lT | dT | l | d 其中l是英文字母l，表示az中的任何一英文字母，d表示09中的任一数字。,编译原理与技术,61,3.2 文法的分类,3型文法产生的语言称为3型正规语言（或正规语言），它可由有限自动机识别。正规语言可用正规表达式表示。 四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。它们之间是逐级“包含”的关系，由四种文法产生的语言也是逐级“包含”的关系。,编译原理与技术,62,3.2 文法的分类,上下文无关文法 上下文无关文法拥有足够强的表达力来表示大多数程序设计语言的语法。比如描述算术表达式，描述各种语句等等。实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另外，上下文无关文法足够简单，可以构造有效的分析算法来检验一个给定符号串是否是由某个上下文无关文法产生。,编译原理与技术,63,3.2 文法的分类,例3.23：文法G=(E, +,*, i , ( , ) , P, E )，其中 P=E E+E | E*E | (E) | i 该文法是上下文无关文法。这里的非终结符E表示一类算术表达式。i表示程序设计语言中的“变量”，该文法定义了(描述了)由变量、+、 *、 ( 和 ) 组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+ E2、E1*E2和 (E1) 也是算术表达式。 例3.24：描述语句的产生式： 语句条件语句|赋值语句|循环语句 简单赋值语句的产生式为：赋值语句 i := E 条件语句的产生式： 条件语句 if条件then语句 | if条件then语句else语句 它们都符合上下文无关文法CFG的产生式要求。,编译原理与技术,64,3.2 文法的分类,正规文法和正规式 一个正规语言可以由正规文法定义，也可以由正规式定义，对任意一个正规文法，存在一个定义同一个正规语言的正规式；反之，对每个正规式，存在一个生成同一语言的正规文法，有些正规语言很容易用文法定义，有些语言更容易用正规式定义，现在介绍两者间的转换，从结构上建立它们的等价性。,编译原理与技术,65,3.2 文法的分类,将上的一个正规式转换成正规文法G=(VN，VT，P，S) 。 令VT=，确定产生式和VN的元素的方法如下： 对任何正规式r，选择一个非终结符S生成产生式Sr，为区别文法中的产生式，把这个产生式叫做正规产生式，并将S定为G的开始符号。 若x和y都是正规式，对形如Axy的正规产生式，重写成：AxB，By两个正规产生式，其中B是新选择的非终结符，即BVN。,编译原理与技术,66,3.2 文法的分类,对已形成的形如Ax* y的正规产生式，引入新的非终结符B，重写为： AxB | y BxB | y 对形如Ax|y的正规产生式，重写为： Ax，Ay 不断利用上述规则做变换，直到每个产生式都符合三型文法的要求。,编译原理与技术,67,3.2 文法的分类,例3.25：将R=a(a|d)* 转换成相应的正规文法。 解：令S是文法的开始符号，首先形成Sa(a|d)*，然后形成SaA和A(a|d)*，重写第二条产生式形成 SaAA(a|d)B AB(a|d)B B 进而变换为正规文法： SaABaB AaBBdB AdBB A,编译原理与技术,68,3.2 文法的分类,将正规文法转换成正规式。 基本上是上述过程的逆过程，转换规则列于表3.1 表3.1 正规文法到正规式的转换规则,编译原理与技术,69,3.2 文法的分类,例3.26：文法GS: SaASa AaAAdA Aa Ad 写出其对应的正规式。 解：先有S=aA|aA=(aA|dA)|(a|d)，再将A的正规式变换为A=(a|d)A|(a|d)，据表中规则2变换为：A=(a|d)*|(a|d)，再将A 右端代入S的正规式得：S=a(a|d)*|a(a|d)|a，再利用正规式的代数变换可依次得到S=a(a|d)*|(a|d)|)，S=a(a|d)*。 a(a|d)* 即为所求。,编译原理与技术,70,3.3 文法的等价变换,定义3.14: 若L(G1)=L(G2)，则称文法G1和G2是等价的。 也就是说，如果两个文法定义的语言相同，则称这两个文法是等价的。 例如：下列两个文法G1A与G2S等价 G1A：A0R A01 RA1 G2S：S0S1 S01 L(G1) = L(G2) = 0n1n|n1。,编译原理与技术,71,3.3 文法的等价变换,定义3.15: 对文法进行变换，使变换后的文法满足某种要求并与原文法等价，这种变换称为文法的等价变换。 不存在一个能判定两个文法是否等价的算法。但是ji我们经常使用下列等价变换： 增广文法 消除回溯 消除左递归,编译原理与技术,72,3.3 文法的等价变换,增广文法 对任一文法G1均可构造文法G2，使得L(G1)=L(G2)，并且G2的初始符号不出现于产生式的右部。 定义3.16: 设文法GS= (VN,VT, P, S)，构造文法GS = (VNS,VT,P,S )，其中 P=A| APSS， 显然L(G)=L(G)，称G为文法G的增广文法。 例3.27： G1Z: ZabZA|a，Ab 经过等价变换后可得到增广文法G2Z: Z Z Z abZA|a A b,编译原理与技术,73,3.3 文法的等价变换,提取左因子 定义3.17: 若文法中有产生式 P 1 | 2 | . | n， 则称该文法含有左因子。 其中P VN，, 1 , 2 , ., n ( VN VT)*。 假设P有产生式 P 1 | 2 | . | n | 1 | 2 | . | n 其中i (i=1,2, . ,n)不以开头。则可将其改写为 P P | 1 | 2 | . | n P 1 | 2 | . | n,编译原理与技术,74,3.3 文法的等价变换,例3.28：文法GS: S i E t S | i E t S e S | a E b 提取左因子后，该文法变为： GS: S i E t S S | a S e S | E b 反复提取左因子，可以消除某些文法的回溯。相应付出的代价是，引进了较多新的非终结符。,编译原理与技术,75,3.3 文法的等价变换,消除左递归 定义3.18: 若文法中存在推导P P，则称该文法含有左递归。 若存在产生式P P，则称文法含有直接左递归。 若存在产生式P P1，P1 P2，Pn-1 Pn，Pn P，则称文法含有间接左递归。 其中P, P1, ., Pn VN，, ( VN VT)*。 左递归会导致推导过程中出现大量的死循环，因此需要消除文法中的左递归。,编译原理与技术,76,3.3 文法的等价变换,直接左递归的消除 假设非终结符P存在产生式P P | ，其中是不以P开头的字符串。 (1) 删除左递归产生式P P； (2) 引入新的非终结符消除文法中的左递归，得： P P P P | 一般地，若非终结符有产生式 P P1 | P2 | . | Pm | 1 | 2 | . | n 其中i (i=1,2, . ,m)，i (i=1,2, . ,n)不以P开头。则消除左递归之后为 P 1P | 2P | . |nP P 1P | 2P | . |mP | ,编译原理与技术,77,3.3 文法的等价变换,例3.29: 文法GE：E E+T | T T T*F | F F (E) | i 消除左递归之后得到如下文法： G E：ETE E +TE | T FT T *FT | F (E) | i 间接左递归的消除 (1) 将间接左递归转化成直接左递归； (2) 消除直接左递归； (3) 化简文法，删除含有从开始符号无法到达的非终结符的产生式。,编译原理与技术,78,3.3 文法的等价变换,例3.30: 文法GS: S Aa | a A Bb | b B Sc | c 将B Sc | c代入A Bb | b得A Scb | cb | b，代入S Aa | a得S Scba | cba | ba | a。得到含直接左递归文法： G1S: S Scba | cba | ba | a A Scb | cb | b B Sc | c 消除直接左递归得： G2S: S cbaS | ba S | a S S cbaS | A Scb | cb | b B Sc | c 其中A、B均不能由开始符号S推出，因此删除无用产生式后得： G S: S cbaS | ba S | a S S cbaS | 选择其他的代入顺序也可以得到消除左递归后的文法，所得的文法都是等价的。,编译原理与技术,79,3.3 文法的等价变换,算法3.1 消除左递归 输入： 无回路且无空产生式的文法GS 输出： 不含左递归的文法G S 以某种顺序将文法非终结符排列P1 , P2, , Pn for i = 1 to n do for j= 1 to i-1 do if Pj 1 | 2 | | k then 将Pi Pj改写为Pi 1 | 2 | | k end for； 消除Pi的直接左递归 end for； 化简得到的文法,编译原理与技术,80,3.4 语法分析概述,语法分析是编译过程的核心部分。 语法分析的任务是： 按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成做准备。执行语法分析任务的程序称为分析程序，也称为语法分析器，它是编译程序的主要子程序之一，在编译程序中的地位如图3.14所示。 图3.8 语法分析器在编译程序中的地位,编译原理与技术,81,3.4 语法分析概述,典型的语法分析方法有三类： 通用方法，能分析任何文法。 但这类方法在生成编译器时效率太低。 自顶向下的分析方法 自底向上的分析方法 这两类方法通常只能处理文法的一些子类，而这些子类中的某些文法足以用来描述程序语言的大部分语法结构，如LL文法和LR文法。,编译原理与技术,82,3.4 语法分析概述,自顶向下的语法分析 自顶向下的语法分析是从文法的开始符号出发，反复使用各种产生式，推导出句型，并一个符号一个符号地与给定终结符号串进行匹配，寻找匹配于输入串的推导。如果全部匹配成功，表示开始符号可推导出给定终结符号串，由此判定给定的终结符号串是文法的句子。,编译原理与技术,83,3.4 语法分析概述,例3.30: 文法GZ: Z aBb | aD B b | bB D d | bD 用自顶向下分析法判断终结符号串 abbd 是否是文法 G 的一个句子。 解：从文法的开始符号Z出发可以得到如下推导 Z aD abD abbD abbd 这样就找到了匹配于输入串abbd的推导，所以终结符号串abbd 是文法 G 的一个句子。,编译原理与技术,84,3.4 语法分析概述,例3.31: 考虑文法GS: S cAd A ab | a 识别输入串w=cabd是否该文法的句子。 解：由开始符号S开始，试着为cabd建立一棵分析树，如图3.9(a)所示。在第一步，只有唯一的一个产生式ScAd可施用，可得直接推导ScAd。 从S向下画分析树，如图3.9(b)所示。这棵树的最左叶子标记为c，已和w的第一个符号匹配，考虑下一个叶子，标记A，可用A的第一个候选产生式Aab去扩展A，则会得到如图3.9(c)所示的分析树，得到的直接推导为cAdcabd。这时输入符号串w的第二个符号a得到了匹配，第三个输入符号为b，将它与下一叶子标记b相比较，得以匹配，叶子d匹配了第四个输入符号，这时可以宣布识别过程结束。所得到的推导过程为：ScAdcabd 。,编译原理与技术,85,3.4 语法分析概述,图3.9 自顶向下的分析步骤,编译原理与技术,86,3.4 语法分析概述,自底向上的语法分析 自底向上分析就是从输入串开始，逐步进行归约，直至归到文法的开始符号。或者说，从语法树的未端开始，步步向上归约，直到根结点。若不能到达开始符号或根结点，则说明此输入串不是该文法的句子。 例3.32: 文法GZ: Z aBb | aD B b | bB D d | bD 用自底向上分析法判断终结符号串abbd是否为文法G的一个句子。,编译原理与技术,87,3.4 语法分析概述,解: 句型 归约规则 abbd Dd abbD DbD abD DbD aD ZaD Z 说明: 先将句型 abbd 中的 d 按照产生式规则归约成 D，形成句型 abbD，再将新产生的句型 abbD 中的 bD 按照产生式规则归约成 D，形成句型 abD ，然后将abD 中的 bD 规约成 D ，形成句型 aD ，最后将句型 aD 归约成 Z，即文法的开始符号。因为能归约为文法的开始符号 Z，所以终极符串 abbd 是文法G的一个句子。,编译原理与技术,88,3.4 语法分析概述,仍使用例3.31中的文法来为输入符号串cabd构造推导或分析树，所采用的是自底向上的方法。 首先从输入符号串开始。扫描cabd，从中寻找一个子串，该子串与某一产生式的右端相匹配。子串a和子串ab都是合格的，假若我们选用了ab，用产生式(2)的左端A去替代它，即把ab归约到了A，得到了串cAd。构造了一个直接推导cAd cabd，即从cabd叶子开始向上构造语法树，如图3.10(b)所示。接下去，在得到的串cAd中又找到了子串cAd与产生式(1)的右端相匹配，则用S替代cAd，或称将cAd归约到S，得到了又一直接推导ScAd，形成了图3.10(c)所示的语法树，符号串cabd的推导序列为：S cAd cabd。,编译原理与技术,89,3.4 语法分析概述,图3.10 自底向上的分析,编译原理与技术,90,3.4 语法分析概述,语法分析的基本问题 （1）如何选择使用哪个产生式进行推导？ 假定要被替换的最左非终结符号是B，而有n条产生式：BA1|A2|An，那么如何确定用哪个右部去替换B？ 有一种解决办法是从各种可能的选择中随机挑选一种，并希望它是正确的。如果以后发现它是错误的，我们必须退回去，再试另外的选择，这种方式称为回溯。显然这样做代价极高，效率很低。这个问题我们将在第四章中具体解决。,编译原理与技术,91,3.5 语法分析概述,（2）如何识别可归约的串？ 在自底向上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。问题是，每一步如何确定这个“可归约串”？ 这是自底向上分析的关键问题，需要精确定义“可归约串”。事实上，存在种种不同的方法刻画可归约串。对这个概念的不同定义形成了不同的自底向上分析方法。我们将在第五章中详细介绍。,