编译原理chpt4文法和语言

1、1第四章第四章 文法和语言文法和语言u本章内容：本章内容：文法和语言的形式定义文法和语言的形式定义 文法的类型文法的类型上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法的句型分析上下文无关文法的句型分析语法-一组规则-文法 语言语义静态：类型匹配、作用域、动态：功能对程序设计语言给出精确无二义的对程序设计语言给出精确无二义的语法描述（严谨、简洁、易读）语法描述（严谨、简洁、易读）2预备知识预备知识 -语言概述语言概述z 任何一种语言都是由该语言的基本符号（字母表）组成的符号串（句子）的集合。z 汉语-所有符合汉语语法的句子的全体z 英语-所有符合英语语法的句子的全体z 程序设计语

2、言-所有该语言的程序的全体z 句子是无限的，但句子都是有结构的，其构成是有规律的（句型），可用规则严格定义-可用有限规则（文法），刻画无限句子。例如： 我是学生、你学习英语、他喜欢运动、3z 语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。z 如果不考虑语义，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。4预备知识 -有关定义和记号z符号：可以相互区别的记号（元素）。z字母表：

3、符号（元素）的非空有穷集合。z符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。特别空符号串。z符号串s的前缀、符号串s的后缀、符号串s的子串 对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。 z符号串s的真前缀、真后缀、真子串x是s的前缀，后缀或子串，并且 s x5z 符号串的运算y符号串s的长度|s|，的长度为0y连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy，如x=ab,y=cd，则xy=abcd，特别a = a y方幂：符号串自身连接n次得到的符号串an ：a1=a,a2=aa，a0=z 符号串集合：字母表上的z 两个符号串集合A和B的

4、乘积定义为AB =xy|xA且yB 若集合A=ab,cde，B = 0,1，则 AB=ab1,ab0,cde0,cde1z *称为的闭包，表示上的一切符号串(包括)组成的集合z 上的除外的所有符号串组成的集合+ ，称为的正闭包。.2*.32*6z语言：字母表上的一个语言是上的一些符号串的集合 (上的每个语言是*的一个子集)。 例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 集合ab,aabb,anbn,或w|w*且w=anbn,n1为字母表上的一个语言。 特别、 即 都是语言。 7语言语言上上的运算的运算若设L 和M是上的语言： z 语言L和M的并LM ，交，差，补是一

5、个语言z 语言L和M的连接是一个语言，记为 LM=st |sL且 tM有L = L=L。 L的n次连接Ln= LL.L z 语言L的 闭包记为 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1= Ln-1 L,n1z 语言L的正 闭包记为 L+， L+= L1 L2 L3 . L+= LL*= L*L，L*= L+ 若L1=a,b, y,z， M1=1,28,9 ， 则L1(L1M1)*=所有字母打头的字母和数字符号串81 1 文法和语言的形式定义文法和语言的形式定义如何来描述一种语言？如何来描述一种语言？有穷语言（只含有穷个句子），可以逐一列举有穷语言（只含有穷个句子）

6、，可以逐一列举无穷语言，找出语言的有穷表示。有两个途经：无穷语言，找出语言的有穷表示。有两个途经： 生成方式生成方式 （文法）：每个句子可用严格定义的规则来构造（文法）：每个句子可用严格定义的规则来构造 识别方式识别方式（自动机）：用一个过程，当输入的串属于语言时，（自动机）：用一个过程，当输入的串属于语言时，该过程经有限次计算后就会停止并回答该过程经有限次计算后就会停止并回答“是是”，否则，要，否则，要么能停止并回答么能停止并回答“不是不是”，要么永远继续下去。，要么永远继续下去。9文法定义定义文法G定义为四元组(VN，VT，P，S )，其中 VN:非终结符号(语法实体)集；VT:终结符号集

7、；P: 规则的集合 S VN ，称作识别符号或开始符号。 VN，VT和P是非空有穷集且VN VT = V=VN VT ，称为文法G的字母表或字汇表 规则（产生式规则（产生式或生成式）生成式）形如，其中V+， V*。例：文法例：文法G=（VN，VT，P，S）VN = S , VT = 0, 1 , P= S0S1, S01 例例: 文法文法G=（VN，VT，P，S）VN =标识符，字母，数字标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P= | a|z z 00|9 9 S=习惯上，只将产生式写出，第一条产生式的左部是开始符号；习惯上，只将产生式写出，第一条产生式的左部是开始符号；

8、大写字母表示非终结符，小写字母表示终结符大写字母表示非终结符，小写字母表示终结符 GS:GS: Aab |aA Aab |aAb | | SaS SaSb|A注意到递归11推导、归约的定义推导、归约的定义直接推导直接推导“” 是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w=,v=,w=, 其中其中VV* *,V,V* * 则称则称v v直接直接推导推导到到w w（w w直接直接归约归约到到v v）, ,记作记作 v v w w若存在若存在v =w0 w1 . wn=w (n0)， 则记为则记为v w，称作，称作v推导出推导出w，或，或w归约到归约到v 若有若有

9、v w或或 v=w， 则记为则记为v w例例G G：S0S1， S01 S 0S1 00S11000S11100001111 简写为S 00001111*12句型、句子的定义句型、句子的定义z 有文法有文法GS，若，若S x，则称，则称x是文法是文法G的句型。的句型。z 有文法有文法GS，若，若S x，且，且xVVT T* *，则称，则称x是文法是文法G的句子。的句子。例：例：GE E：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a G的句型E E，E+T，T+T，F+T，a

10、+T，a+T*F，a+F*F，a+a*F， a+a*a G的句子a+a*a *程序就是句子13语言的定义语言的定义L(G)=x | S x，其中S为文法的开始符号，且x VT* 例G：S0S1 | 01 L(G)=0n1n|n1例GS：（1）SaSBE | aBE （2）EBBE （3）aBab （4）bBbb （5）bEbe （6）eEee L（G）= anbnen | n1 G生成的每个串都在L(G)中，L(G)中的每个串确实能被G生成*S an-1S(BE)n-1 = an(BE)n = anB(EB)n-1E = anB(BE)n-1E = anB2(EB)n-2E2 anBnEn a

11、nbnEn anbnen*14z 已知语言描述，写出文法 例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法 A 0B | 1CB 1 | 1A | 0BBC 0 | 0A | 1CCz 已知文法，写出语言描述例：GE：EE+T|T TT*F|F F(E)|az 若L(G1)=L(G2)，则称文法G1和G2是等价的。 如G1A：A01|0E EA1与G2S：S0S1|01 等价152 2 文法及其语言的分类文法及其语言的分类通过对产生式通过对产生式施加不同的限制，施加不同的限制，Chomsky将文法分为四将文法分为四种类型，相应产生四类语言：种类型，相应产生四类语言：0型文法：对任

12、一产生式型文法：对任一产生式，都有，都有(V(VN NVVT T) )+ +且至少且至少含一个非终结符，含一个非终结符，(V(VN NVVT T) )* * -0型语言型语言1 1型文法：型文法：对任一产生式对任一产生式，都有，都有|， 仅仅仅仅 SS除外除外-上下文有关语言上下文有关语言2 2型文法：型文法：对任一产生式对任一产生式，都有，都有VVN N，(V(VN NVVT T) )* * 3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa， 其中其中AVAVN N ，BVBVN N ，aVaVT T * * -正则语言右线形应注意到，上下文无关文法的定

13、义等价于应注意到，上下文无关文法的定义等价于BNF表示法表示法16例：例：1 1型（上下文有关）文法型（上下文有关）文法 GSGS：SCDSCDAbbAAbbA CaCA|bCB CaCA|bCB BaaBBaaB ADaD ADaD BbbBBbbB BDbD BDbD CaCa AabD AabD DbDb例：例：2 2型（上下文无关）文法型（上下文无关）文法 GSGS：SABSAB ABS|0 ABS|0 BSA|1 BSA|1例：例：3 3型文法型文法 GS： S0A|1B|00A|1B|0 A0A|1B|0S0A|1B|0S B1B|1|01B|1|017文法的类型文法的类型2型文法

14、型文法1型文法型文法0型文法型文法四类四类文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。18文法和识别系统间的关系文法和识别系统间的关系0型文法（短语结构文法）的描述能力相当于图灵机，可以表型文法（短语结构文法）的描述能力相当于图灵机，可以表征任何递归可枚举集，而且任何征任何递归可枚举集，而且任何0型语言都是递归可枚举的型语言都是递归可枚举的任何能用图灵机描述的计算都能机械实现，任何能在现代计任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述算机上实

15、现的计算都能用图灵机描述 带带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁头磁头四类文法对应四种语言，每种语言被一种自动机所识别。四类文法对应四种语言，每种语言被一种自动机所识别。191型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。 2型文法（上下文无关文法）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合定理定理 设设G=（VN，VT，P，S）是3 3型文法，则存在

16、一个有穷自型文法，则存在一个有穷自 动机动机 M=(K, , f, A, Z)M=(K, , f, A, Z)，使得，使得L(M)=L(G)L(M)=L(G)；反之，；反之，已知一有穷自动机M=(K, , f, A, Z),存在有一个3型文法G= （VN，VT，P，S）,使得L(G)=L(M)203 3型文法型文法和有穷自动机（有穷自动机（FAFA）G： SaA | bB AbB | aD | a BaA | bD | b DaD | bD | a | bBASaaabbba,bDZababDBASaaabba,bb先把D看成非终态21对上的正规式r ,存在一个RG=(VN,VT,P,S)：L

17、(G)=L(r)初始， VT= ，S VN ，生成正规产生式 Sr(R.1) 对形如 Ar1r2的正规产生式：Ar1B，Br2 (R.2)对形如Arr1的正规产生式：ArB | r1 ，BrB | r1 不断应用(R.x)做变换，直到每个产生式右端至多有一个VN例 r=a(ad)(1) Sa(ad)(2) SaA，A(ad)A(ad)B | B(ad)B | Gs: SaA A | aB | dB BaB | dB | VT=a,d VN=S,A,B 22对RG=(VN,VT,P,S),存在一个 =VT上的正规式r：L(r)=L(G) AxB, By 形成正规式 A=xy AxAy 形成正规式

18、 A=xy Axy 形成正规式 A=xyGs: SaA | a AaAadAd A(ad)A(ad) A(ad)(ad) S=a(ad)(ad)a =a(ad)(ad)=a(ad) R=a(ad)233 3 上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构上下文无关文法有足够的能力描述程序设计语言的语法结构GE： EE+T|T TT*F|F F(E)|a对a+a*a，观察下列各种推导： EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aEE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*

19、a a+a*aEE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a24规范推导、规范句型规范推导、规范句型最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换。最右推导被称为规范推导。由规范推导所得的句型称为规范句型语法树语法树-句型推导句型推导的的直观表示直观表示25语法树语法树-句型推导句型推导的的直观表示直观表示设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1. 每个结点都有一个标记，此标记是V的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除

20、外的子孙，并且有标记A，则肯定AVN4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式26句型句型aabbaa的可能的可能推导推导序列和语法树序列和语法树 例例: GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)一棵语法树表示了一个句

21、型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?27例：例：G GE:E:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：E E+E E*E+E i*E+E i*i+E i*i+i推导推导2：E E*E i*E i*E+E

22、i*i+E i*i+I -导致语义上的二义性导致语义上的二义性 若一个文法存在某个句子对应两棵不同的语法树（或有两若一个文法存在某个句子对应两棵不同的语法树（或有两个不同的最左（右）推导），则称这个文法是个不同的最左（右）推导），则称这个文法是二义二义的的很显然，计算机很显然，计算机不喜欢二义性不喜欢二义性。28文法二义性的解决办法文法二义性的解决办法句子或句型含义的二义性是由文法的二义性引起的。句子或句型含义的二义性是由文法的二义性引起的。G GE: E iE: E i E E+E E E+E E E E E* *E E E (E) E (E)解决二义性的两种途径某些二义文法可变换为无二义的

23、根据提出的条件直接修改编译算法GEGE：E T|E+T E T|E+T T F|T T F|T* *F F F F （E E）|i|i直接修改编译算法：规定算符优先性和结合性规定算符优先性和结合性1229但也有一些上下文无关语言，它的每一个文法都是二义的，则但也有一些上下文无关语言，它的每一个文法都是二义的，则说此语言是先天二义的。说此语言是先天二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。先天二义的上下文无关语言，这两个问题是递归不可解的。在编译实践中形成了一些比较实用的

24、技术，可以为无二义性寻在编译实践中形成了一些比较实用的技术，可以为无二义性寻找一组充分条件，用于将二义性文法变换为无二义性文法。找一组充分条件，用于将二义性文法变换为无二义性文法。比如利用优先级规则，左结合或右结合规则和最近嵌套规则比如利用优先级规则，左结合或右结合规则和最近嵌套规则等。等。GSGS：S-S-if B then S | if B then S else S | Aif B then S | if B then S else S | AG GSS：S-S-C | UC | U C- C-if B then C else S | A if B then C else S | A U

25、- U-if B then Sif B then S就近匹配就近匹配304 4 句型的分析句型的分析句型分析就是识别一个符号串是否为某文法句型的过程。编译程序中，完成句型分析的模块称为分析程序或识别程序。两类分析方式： 自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析法：从输入串开始，进行归约，直至归约到开始符号 不同分析方式反映了语法树的的不同构造过程反映了语法树的的不同构造过程31(1) S cAd (2) A ab (3) A a自上而下的语法分析自上而下的语法分析识别输入串识别输入串w=cad是否为该

26、文法的是否为该文法的句子句子若S cAd 后选择(2)扩展A，S cAd cabd那将会？w的第二个符号可以匹配，但第三个符号却不能匹配？宣告分析失败，显然结论错误结论错误。 -错误的选择，导致分析的失败！这时应该回朔回朔，把A为根的子树剪掉，输入a退还回去，再用产生式（3）试探自下而上的语法分析自下而上的语法分析识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子对串cabd的分析中，如果不选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在c A b d中无法找到一个可归约串，最终就达不到归约到S的结果32短语、直接短语、句柄短语、直接短语、句柄文法GS，

27、S A且A ，则称是句型相对于非终结符A的短语。若有A 则称是句型相对于规则A 的直接短语。一个句型的最左直接短语称为该句型的句柄*GEGE：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|i F(E)|i句型：句型：i i* *i+ii+i 短语： 直接短语： 句柄： E E T T F T F F i1 * i2 + i3 33归约T intT + int | 移进T + | int移进int | * int + int移进int * | int + int移进|int * int + intE |归约E T + ET + E |归约E TT + T |移进T | + i

28、nt归约T int * Tint * T | + int归约 T intint * int | + intETE+int*intTintT文法文法GE：E T + E | TT int * T | int | (E)34z 自下而上语法分析的策略：移进-归约分析；z 移进就是将一个终结符推进栈z 归约就是将0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈z 移进-归约过程是自顶向下最右推导的逆过程（规范归约）z 我们如何决定什么时候移进，什么时候归约？我们如何决定什么时候移进，什么时候归约？y考虑考虑 int | * int + inty我们可以用我们可以用 T int进行归约，而得到

29、进行归约，而得到 T | * int + inty致命错误致命错误: 无法归约到开始符号无法归约到开始符号 Ey直觉: Want to reduce only if the result can still be reduced to the start symbolz 一般的移进一般的移进-归约策略：归约策略：y若若句柄句柄在栈顶出现，则归约在栈顶出现，则归约y否则移进否则移进35文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1） # abbcde# 移进移进 2） #a bbcde# 移进移进A 3） #ab bcde# 归约归约(Ab) 4） #aA bcde# 移进移进A 5） #aAb cde# 归约