编译原理_第二章

1、第二章第二章 高级语言及其语法描述高级语言及其语法描述引言：关于引言：关于形式语言形式语言2.1程序语言的定义程序语言的定义 1、词法规则词法规则、语法规则语法规则p12-132、语义语义P142.2高级语言的一般特性高级语言的一般特性P14-25(关于算符的优先顺序关于算符的优先顺序p23、名字的左值和右值名字的左值和右值p24）2.3 程序语言的语法描述程序语言的语法描述p252.3 程序语言的语法描述程序语言的语法描述一、符号和符号串一、符号和符号串字母表字母表：字母表：字母表是符号元素的是符号元素的非空非空集合。集合。符号符号：字母表中的元素。：字母表中的元素。 符号串符号串：字母表中

2、的符号所组成的任何：字母表中的符号所组成的任何有穷有穷序列。序列。 例如，若有字母表例如，若有字母表=a,b则则a，b是字母表是字母表中的元素中的元素(符号符号)；a，b，aa，ab，ba都是符号串。都是符号串。注意：符号串中注意：符号串中的符号与顺序有的符号与顺序有关，关，ab和和ba是不是不同的符号串同的符号串特别定义特别定义:空符号串空符号串不含任何符号的符号串，不含任何符号的符号串，用用 表示。表示。 设有字母表设有字母表=az, AZ,09, 各种运算符和其它特殊各种运算符和其它特殊符号，符号，则，由这些字母表中的元素则，由这些字母表中的元素(符号符号)可以组成不同可以组成不同的符号

3、串：的符号串：Program example;Var sum,I: integer;Begin Sum := 0;For I:=1 to 10 do sum:=sum+I;12345:=sum;End.Write(sum=,sum);A=符号串的运算符号串的运算：符号串的连接（联结、乘积）符号串的连接（联结、乘积）：符号串：符号串x和和y的连接是指的连接是指x和和y的符号按先后顺序排列在一起组成一个新的符号串，的符号按先后顺序排列在一起组成一个新的符号串，用用xy表示。表示。 例，若字母表例，若字母表=a,b，符号串符号串x=ab，y=ba则则xy=abba符号串的长度符号串的长度：符号串中符

4、号的个数为符号串的长度。：符号串中符号的个数为符号串的长度。 注意注意: (1)连接运算不满足交换律，即连接运算不满足交换律，即xyyx (2)任何符号串任何符号串x与空串与空串的连接都等于的连接都等于x，即即： x=x=x。 若若ab是符号串，则是符号串，则|ab|表示符号串的长度。表示符号串的长度。 |ab|=2同理：同理：|aabb|=4 注意：特别规定注意：特别规定 |=0。若有两个符号串若有两个符号串x=ab,y=cde那么，那么，|xy|=?5符号串的前缀与后缀符号串的前缀与后缀(头和尾头和尾)：若有符号串若有符号串 z=xy(x,y是符是符号串号串),我们称我们称x为为z的前缀的

5、前缀，y为为z的后缀。的后缀。例例z=abcd则：则：z的头有，的头有， , a , ab , abc , abcd z的尾有，的尾有， ,d , cd , bcd , abcd符号串的幂运算符号串的幂运算：设设X是一个符号串，则：是一个符号串，则： X0=，X1=X，X2=XX，Xn=XX=Xn例：若有符号串例：若有符号串x=ab，则：则：x0= ,x1= ab,x2= abab,x3= ababab显然，若显然，若n0,则则Xn=XXn-1 =Xn-1X。 即：符号串的幂运算服从结合律即：符号串的幂运算服从结合律 符号串符号串集合集合的运算的运算：符号串集合的乘积运算：符号串集合的乘积运算

6、：设设A、B为符号串集合（集合为符号串集合（集合中各元素都是字母表上的字符串），两个字符串集合中各元素都是字母表上的字符串），两个字符串集合的乘积定义为：的乘积定义为：AB=xy|xA , yB（笛卡儿乘积）笛卡儿乘积）设有字母表设有字母表=a,b,c,d，令令A=aa,bb，B=cc,dd则则AB=aacc,aadd,bbcc,bbdd， BA=ccaa,ccbb,ddaa,ddbb。显然显然 AB BA，即符号串集合乘积不满足交换律即符号串集合乘积不满足交换律。注意：因注意：因x = x=x故，故， A=AA=A=A =A 特别定义：空符号串集合：特别定义：空符号串集合： 空集合：空集合：

7、= A = A= 符号串集合的幂运算：符号串集合的幂运算：设设A为符号串集合，则集合的幂为符号串集合，则集合的幂运算定义如下运算定义如下:A0=A1=AA2=AAAn=AAAn个个=AAn-1=An-1A符号串集合的闭包：符号串集合的闭包：设设A为符号串集合，则集合的闭包为符号串集合，则集合的闭包定义如下定义如下:A的的正闭包正闭包： A+=A1A2A的的闭包：闭包： A*=A0A1A2设集合设集合A=a,b，则则 A+=a,b,aa,ab,ba,bb,aaa, A*=,a,b,aa,ab,ba,bb,aaa, 显然：显然： A*=A0A+ A+=AA*二、上下文无关二、上下文无关文法文法 (

8、p26)文法文法(Grammar):是描述语言的语法结构的形式是描述语言的语法结构的形式规则（即语法规则）。规则（即语法规则）。The big monkey ate a banana.规则规则：规则又叫：规则又叫产生式产生式(production rule)，它是，它是语法单位结构的一种表示，它引入了符号语法单位结构的一种表示，它引入了符号“:=:=”或或“”表示表示“由由组成组成”，上述句子的结构，上述句子的结构可以表示如下：可以表示如下： the big ate a monkey banana句子的推导句子的推导：用规则：用规则(产生式产生式)按一定方式去推导按一定方式去推导或产生句子的过

9、程。或产生句子的过程。 the big ate a monkey banana The The big The big monkey The big monkey The big monkey ate The big monkey ate The big monkey ate a The big monkey ate a banana The big monkey ate a banana语法树语法树(Parse Tree):句子结构的图形表示方式句子结构的图形表示方式monkeybigTheatebananaa归纳：什么是文法归纳：什么是文法 the big ate a monkey ban

10、ana三、文法和语言的形式定义三、文法和语言的形式定义定义定义2 文法文法是一个四元组：是一个四元组：GS=(VN, VT, P, S)其中：其中：VN为非终结符集合；为非终结符集合； VT为终结符集合；为终结符集合； VNVT =，一般令一般令 V= VNVT ，V中的符号称为文法符号；中的符号称为文法符号；(V字汇表）字汇表）P为产生式集合；为产生式集合； P中的每个产生式写为：中的每个产生式写为：或或 =。S为开始符号为开始符号(或称根符号，识别符号或称根符号，识别符号)。定义定义1 产生式产生式(或规则或规则)是一有序对是一有序对(A, )，通常写为：，通常写为： A 或或A = 其中

11、其中A是一个符号作为产生式左部，是一个符号作为产生式左部， 为有穷符号串作为产生为有穷符号串作为产生式的右部，式的右部，“ ”或或“ =”表示表示“定义为定义为”或或“由由组成组成”。另外：另外：GS也可简写为也可简写为G 在规则左部出现的在规则左部出现的符号称为非终结符，符号称为非终结符，它们的全体形成它们的全体形成VN在规则中只在右部在规则中只在右部出现的符号称为终出现的符号称为终结符，它们的全体结符，它们的全体形成形成VT例例 G1 =(N,0，1,N0N,N1N,N0,N1,N） 其中其中: 非终结符非终结符 VN =N终结符终结符VT =0，1V=N，0，1 P=N0N，N1N，N0

12、，N1开始符号开始符号S 为为N通常情况下，文法只用产生式集合表示：通常情况下，文法只用产生式集合表示：G1N: N0N N1N N0 N1定义定义3 符号串的符号串的推导与归约推导与归约：已给文法：已给文法G=(VN,VT,P,S)， V= VNVT，令令x,y,V* ，且且P，此时，由符号此时，由符号串串xy能够直接产生出符号串能够直接产生出符号串xy，我们称：我们称：符号串符号串xy是符号串是符号串xy的的直接推导直接推导；符号串符号串xy是符号串是符号串xy的的直接归约直接归约；记作记作: xy xy 对于上例中文法：对于上例中文法：G1N: N0N N1N N0 N1存在以下直接推导

13、：存在以下直接推导： N 1N 11xyxyx yx y若有若有1，2，nV* 且且1 2 ，n-1 n则称则称n是是1的推导的推导记作：记作： 1+n特别约定：若在推导关系特别约定：若在推导关系1n中允许中允许1=n，+则称则称n是是1 的广义推导记作的广义推导记作 1*nN +11N *N引用引用巴科斯范式巴科斯范式(BNF)表示文法：表示文法：对于具有相同左部的那些产生式，如：对于具有相同左部的那些产生式，如：Ux, Uy, Uz可以缩写为：可以缩写为：Ux|y|z (“|”可理解为可理解为“或或”)(1) (2) (3) (4) 0(5) 1(6) 2(7) 3(8) 4(9) 5(1

14、0) 6(11) 7(12) 8(13) 9(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|用此文法和直接推导的定义可以用此文法和直接推导的定义可以推导出任一无符号整数推导出任一无符号整数(56) 5 56可表示为可表示为:+56 V*，则称则称为文法为文法G的句型的句型 VT*，则称则称为文法为文法G的句子的句子 文法文法G所对应的语言，记作所对应的语言，记作L(G)=|VT*，且且S+例例:前面提到的文法前面提到的文法G = VN，VT，P，无符号整数无符号整数其中，其中，VT =0，1，2，3，4，5，6，7，8，9 VN =无符号整数，数字串，数字无

15、符号整数，数字串，数字 P： 0123456789 5 56 试给出该文法的试给出该文法的句型、句子举例，句型、句子举例，并说明它所确定并说明它所确定的语言。的语言。由此我们可以看出，文法和语言是密切相关的，根据文由此我们可以看出，文法和语言是密切相关的，根据文法可以推导出任一句型和句子，而所有句子的集合则为法可以推导出任一句型和句子，而所有句子的集合则为该文法所对应的语言，即该文法所对应的语言，即语言是所有句子构成的集合，语言是所有句子构成的集合，它是所有终结符号串所组成的集合它是所有终结符号串所组成的集合VT*的子集的子集：L(G) VT*定义定义4 句型和句子句型和句子:设设G=(VN,

16、VT,P,S)是一文法，若是一文法，若 S *那么，句型和句子的那么，句型和句子的区别是什么区别是什么?定义定义5 规范推导规范推导(归约归约):对于直接推导对于直接推导xy xy，如果如果y只只包含终结符号包含终结符号或为空符号串，那么就把这种直接推导称或为空符号串，那么就把这种直接推导称为规范为规范(最右最右)推导，跟其对应的归约称为规范推导，跟其对应的归约称为规范(最左最左)归约，归约，且记作：且记作：xy rxy下面的推导是否规范推导下面的推导是否规范推导： 5 56 6 6 56若推导：若推导：1+n中的每一步直接推导都中的每一步直接推导都是规范的，那么我们就是规范的，那么我们就把推

17、导：把推导：1+n称为是规范的，且记作：称为是规范的，且记作：1n+r+r56每次对符号串最右非终结每次对符号串最右非终结符号进行替换符号进行替换例例 文法文法GE : EE+E | E*E | (E) | i 给出句子给出句子i*i+ i的最右及最左推导的最右及最左推导 。例例2.1 p30例例2.2例例2.3同样，可给出最左推导的定义。同样，可给出最左推导的定义。p30-31形式语言理论可以证明以下两点：形式语言理论可以证明以下两点：(1)给定一个文法给定一个文法G，就可以从结构上唯一地确定其语言：就可以从结构上唯一地确定其语言：GL(G)(2)给定一种语言给定一种语言L，能确定其文法，但

18、这种文法可能不能确定其文法，但这种文法可能不是唯一的：是唯一的：LG1或或G2例例1：有文法：有文法GZ: (1)ZaZb (2)Z ab它确定的语言是什么？它确定的语言是什么？用用BNF表示：表示： Z aZb|ab由产生式由产生式(2)知：知： zab 故故ab是文法的一个句子是文法的一个句子用产生式用产生式(1)(2)：zaZba2b2 故故a2b2是文法的一个句子是文法的一个句子反复使用产生式反复使用产生式(1)： zaZba2Zb2 an-1Zbn-1 anbn所以，文法所确定的语言为：所以，文法所确定的语言为：L(GZ)=anbn | n 1例例2：已知语言为：已知语言为 L(G)

19、=abna | n 1 试给出其文法。试给出其文法。G1Z: Z aBa B bB|bG2Z: Z aBa B Bb|b定义定义6 等价文法等价文法：如果：如果L(G1)=L(G2) ，那么称那么称G1和和G2为等价文法。为等价文法。定义定义7 递归产生式和递归文法递归产生式和递归文法：设给定文法：设给定文法G=(VN,VT,P,S) 若若x=且且y,则称产生式则称产生式A是是左递归产生式左递归产生式；若若x且且y=,则称产生式则称产生式A是是右递归产生式右递归产生式。B BbB bB(1)若存在产生式若存在产生式AP 且有且有 A xAy成立，则称产生成立，则称产生式式A是递归产生式；是递归

20、产生式； *若若具有具有xAy形式形式,则称产生式则称产生式A是是直接递归产生式直接递归产生式。(2)递归文法：递归文法： 若文法中至少存在一条直接递归产生式则称该文法是若文法中至少存在一条直接递归产生式则称该文法是直接递归的文法直接递归的文法；否则；否则 若有若有A +xAy ，或，或A +Ay ，或，或A +xA则称文法为则称文法为间接递归的文法间接递归的文法。可见，对于文法中任一非终结符号，若能建立一个推导过可见，对于文法中任一非终结符号，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符号本身，程，在推导所得的符号串中又出现了该非终结符号本身，则文法是递归的。则文法是递归的。

21、应当注意，一般的文法都是递归的应当注意，一般的文法都是递归的，文文法法G只有递归定义，只有递归定义，L(G)中句子才是无穷的中句子才是无穷的 例：有文法例：有文法GS: S aB|bB B a|b是否是递归文法，确定什是否是递归文法，确定什么语言？么语言？非递归非递归文法，文法，L(GS)=aa,ab,ba,bb例：有文法例：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|该文法中有直接左递归产生式：该文法中有直接左递归产生式： 所以是递归文法。所以是递归文法。它是否为递归文法，确定的语言是什么？它是否为递归文法，确定的语言是什么？所确定的语言为：所

22、有无符号整数。所确定的语言为：所有无符号整数。L(G)=VT+若不用递归规则表示文法，就要用到无穷多条产生式：若不用递归规则表示文法，就要用到无穷多条产生式： | | |总之，总之，使用递归文法，可用有穷的产生式来描述无穷使用递归文法，可用有穷的产生式来描述无穷的语言的语言，反之，一个语言若是无穷的，则描述语言的，反之，一个语言若是无穷的，则描述语言的文法必定是递归的。文法必定是递归的。(程序设计语言一般是无穷的程序设计语言一般是无穷的)。 课堂练习课堂练习（见教案）（见教案）定义定义8 短语、简单短语和句柄短语、简单短语和句柄：设文法：设文法 G=(VN,VT,P,S) ， 且且 U VN，

23、x,y,u V*(1)若有若有SxUy*+xuy，则则u称为句型称为句型xuy的相对于的相对于U的的短语短语 ；(2)若有若有SxUy* xuy，则则u称为句型称为句型xuy的相对于的相对于U的的简单简单(直接直接)短语短语； 例例：有文法：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|因有：因有： *+6xyUyxuU= u= 6x,y= 6是句型是句型6相对于相对于的短语的短语(3)任一句型的任一句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄.因有：因有： *66是句型是句型6相对于相对于的短语，且为的短语，且为简单短语简单短语

24、xUyxyu说明：当句型有两个以上的简单短语同时存在时，说明：当句型有两个以上的简单短语同时存在时，我们把位于最左边的那个简单短语称为我们把位于最左边的那个简单短语称为“最左简最左简单短语单短语”，即该句型的句柄；若句型只有一个简，即该句型的句柄；若句型只有一个简单短语，那么，它就是最左简单短语，即句柄。单短语，那么，它就是最左简单短语，即句柄。例例1：在：在“6”中，中，6是句型是句型6中唯中唯一的一个简单短语，所以它是句柄一的一个简单短语，所以它是句柄.例例2：在：在“ 78”中，中， 、7和和8都都是是句型简单短语，所以位于左边的是是句型简单短语，所以位于左边的 是句柄是句柄.注意：可从

25、语法树的角度理解短语和句柄。注意：可从语法树的角度理解短语和句柄。p31例例：有文法：有文法G(1) (2) |(3) 0 |1 |2 |3 |4 |5 |6 |7 |8 |9|2.4语法树和文法的二义性语法树和文法的二义性语法树语法树: 设文法设文法G=(VN,VT,P,S) ，所谓语法树是一张图，这所谓语法树是一张图，这张图表示一个句型的推导过程。语法树结构是一棵倒立的张图表示一个句型的推导过程。语法树结构是一棵倒立的树结构，其中，结点的名字树结构，其中，结点的名字NV，根结点的名字根结点的名字S是文法是文法G的开始符号，树中的中间结点是句型推导过程中使用的的开始符号，树中的中间结点是句型

26、推导过程中使用的非终结符非终结符 ，树的端末结点自左向右排列就是所给句型。，树的端末结点自左向右排列就是所给句型。例例2.7 文法文法GE: EE+TT TT*FF FEi 句型句型E+F*i对应的语对应的语法树如右图所示：法树如右图所示： EE T+T *F F i可以看出，语法树的生成过程直观的给出了句型的推导过程。可以看出，语法树的生成过程直观的给出了句型的推导过程。子树子树：由语法树的某个结点：由语法树的某个结点(子树的根子树的根)连同它下面发出的连同它下面发出的部分组成语法树的子树。只含有单层分支的子树为简单子部分组成语法树的子树。只含有单层分支的子树为简单子树。树。EE T+T *

27、F F i子树与短语子树与短语：在句型所对：在句型所对应的语法树中，若某些符应的语法树中，若某些符号按从左到右的顺序组成号按从左到右的顺序组成某棵子树的末端结点，那某棵子树的末端结点，那么由这些末端结点所组成么由这些末端结点所组成的符号串是相对于子树根的符号串是相对于子树根结点的短语。结点的短语。例如：例如：F是句型相对于是句型相对于T的短语，且为简单短语的短语，且为简单短语; i是句型相对于是句型相对于F的短语，且为简单短语的短语，且为简单短语; F*i 是句型相对于是句型相对于T的短语的短语; E+F*i是句型相对于是句型相对于E的短语的短语.补充补充2个例子（教案个例子（教案P30-31

28、）原则上语法树有多原则上语法树有多少棵子树，就有多少棵子树，就有多少个短语少个短语哪个是句柄？哪个是句柄？文法的二义性文法的二义性：若一个文法存在某个句子对应两棵不同的：若一个文法存在某个句子对应两棵不同的语法树，则称此文法是二义性文法，运用文法描述程序设语法树，则称此文法是二义性文法，运用文法描述程序设计语言的语句成份，一般希望所给文法是非二义文法，但计语言的语句成份，一般希望所给文法是非二义文法，但是，有时候采用二义性文法比非二义文法要简单的多，所是，有时候采用二义性文法比非二义文法要简单的多，所以，经常用二义性文法描述程序设计语言。以，经常用二义性文法描述程序设计语言。 例例1： 文法文

29、法GE : EE+E | E*E | (E) | i 试为符号串试为符号串E*E+i构造语法树构造语法树. EEE+EE*iEEE*EE+i先乘后加先乘后加先加后乘先加后乘所以文法是二义性的。在进行语法分析时通所以文法是二义性的。在进行语法分析时通过人工干预过人工干预(规定算符的优先级规定算符的优先级)，确定归约，确定归约(分析分析)顺序顺序 例例2：if 语句语句(1)(2)(3)2.5文法的分类文法的分类 按照文法中产生式的不同情况，按照文法中产生式的不同情况，Chomsky把文法分把文法分成四种类型，四种类型的文法对应着四种类型的语言。成四种类型，四种类型的文法对应着四种类型的语言。0型

30、文法型文法： 产生式形式为产生式形式为: u v 且且 u V+ v V* u中应至少含有一个非终结符号，这种文法又叫短语文中应至少含有一个非终结符号，这种文法又叫短语文法，它所确定的语言称为法，它所确定的语言称为0型语言。型语言。1型文法型文法: 产生式形式为产生式形式为 xUy xuy 且且 U VN u V+ x,y V* 则称该文法为则称该文法为1型文法，也称为上下文敏感文法或上下文有型文法，也称为上下文敏感文法或上下文有关文法。关文法。 即只有在即只有在U的左部为符号串的左部为符号串x而右部为符号串而右部为符号串y时，才允时，才允许把非终结符许把非终结符U用符号串用符号串u来代替，即

31、来代替，即U必须在上下文必须在上下文xy中中才行。这种文法所对应的语言为才行。这种文法所对应的语言为1型语言。型语言。2型文法型文法: 产生式形式为产生式形式为 U u 且且 U VN u V* 则称该文法为则称该文法为2型文法，也称为上下文无关文法。型文法，也称为上下文无关文法。2型型文法所确定的语言为文法所确定的语言为2型语言，大部分程序设计语言都是型语言，大部分程序设计语言都是2型语言。型语言。例例: 文法文法G =（S，a,b，SaSb, Sab，S）3型文法型文法: 产生式形式为产生式形式为 UxV|y xV|y 或或 U Vx|y U Vx|y 且且 U,V VU,V VN N，x,yVx,yVT T+ + 则称该文法为则称该文法为3型文法，也称线性文法、型文法，也称线性文法、正则文法或正正则文法或正规文法规文法。这种文法所对应