编译原理C2-文法(1)

1、编译原理第二章：文法陈飞，南区943复习：绪论词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查和处理程序源程序目标代码程序语言设计：引例程序语言设计：引例语言概述n语言是由句子组成的集合，是由一组记号所构成的集合。n汉语-所有符合汉语语法的句子的全体n英语-所有符合英语语法的句子的全体n程序设计语言-所有该语言的程序的全体n 每个句子构成的规律n研究语言 每个句子的含义n 每个句子和使用者的关系语言概述n语言研究的三个方面:q语法 （Syntax ） - 表示构成语言句子的各个记号之间的组合规律q语义 （Semantics） - 表示按照各种表示方

2、法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）q语用（Pragmatics） - 表示在各个记号所出现的行为中，它们的来源、使用和影响。（不做进一步的介绍）语言概述n形式(Formal)语言理论 是一种从语法上研究语言的理论。它是抽象的数学系统，着重研究符号串集合的表示法、结构及其特性。该理论是程序设计语言语法分析研究的基础。n形式语义（formal semantics）语言的3种表示方式n枚举n在一个基本符号集上制定（有限的）规则来产生全部（可能是无限的）的句子q文法n设计一个算法，判断基本符号集上的任一符号串是否为合法句子q自动机文法的定义文法的定义几个基本概念n字

3、母表或符号集n符号串及相关操作q串长与空串q前、后缀及子串q连接和方幂n符号串集及相关操作q、与q串集的和与积q串集的幂与闭包nA0, A*, A+文法的直观概念n句子的产生n:=n:=|n:=我|你n:=大学生|编译原理n:=n:=是|学习n:= | 文法的直观概念（用 “ ”表示推导） 你 你 你是 你是 你是大学生归纳抽象出n非终结符n终结符n开始符号n规则文法的定义n定义定义2.1 一个文法GS可表示成如（VN，VT，P，S）的四元组，其中VN，VT，P都是非空有限集，分别称为非终结符集、终结符集和产生式集，SVN称为文法的开始符号，并且VNVT= ，V=VNVT称为文法的字母表或字汇

4、表。n定义实质是？问题n对前述文法例子，按定义写出它的四元组表示。（例子复述如下）q:=q:=|q:=我|你q:=大学生|编译原理q:=q:=是|学习q:= | n结合自身编程体验，写出“for循环语句”和“四则运算表达式”的文法推导的定义n非形式化说明q直接推导：如果可以直接使用某条规则从符号串得到符号串q推导：如果使用若干条规则后，可以从符号串得到符号串n推导长度（使用规则个数）n形式化定义qP20；定义2.2和定义2.3推导定义定义的实质？推导例子 你 你 你是 你是 你是大学生是否存在其它推导？句型与句子的定义n非形式化说明q句型：能从开始符号S推导出的符号串q句子：仅由终结符号组成的

5、句型n形式化定义：P20：定2.4n例子：前述例子存在什么句型和句子？语言的定义n非形式化说明q所有句子组成的集合n形式化定义qP21，定义2.5复习问题n文法的定义是什么n直接推导的定义是什么n推导的定义是什么n句型的定义是什么n句子的定义是什么n语言的定义是什么文法的定义n定义2.1 一个文法GS可表示成如（VN，VT，P，S）的四元组q其中VN，VT，P都是非空有限集，分别称为非终结符集、终结符集和产生式集qSVN称为文法的开始符号，并且VNVT= ，V=VNVT称为文法的字母表或字汇表(Vocabulary)。推导、句型、句子与语言的定义n非形式化说明q直接推导：直接使用某条规则从得到

6、q推导：使用若干条规则从得到n推导长度（使用规则个数）q句型：能从开始符号S推导出的符号串q句子：仅由终结符号组成的符号串q语言：所有句子组成的集合递归文法n有限的规则/产生式产生无限的语言n定义定义2.6 A是文法G的一个产生式，如果具有A的形式，其中、不同时为，则称产生式A是是直接递归的；若存在推导A* A ，则称产生式A是递归的。同时，把上述两种情况中的A分别称为直接递归和递归的非终结符。特别地，当=而时，我们将产生式A分别称为直接左递归和左递归的产生式。类似可定义直接右递归和右递归的产生式和非终结符。如果一个文法中至少含有一个递归的非终结符，则将此文法称为递归文法。n如 等等价文法n文

7、法与语言将不存在一一对应关系q一个文法对应一个语言q一个语言对应多种文法（等价文法）n定义定义2.7 设G1和G2为两个文法，若它们所产生的语言相等，即L(G1)=L(G2)，则称G1和G2等价。n如qSaSa，Sa、 SaaS，Sa、 SSaa，Sa、SaA，AaS, Sa等等价变换引理n把左部变量为A的产生式称为A-产生式。n引理引理2.1 设G=(VN，VT，P，S)为一文法，并设AB是P中一个产生式，而B1， B2，Bk是P中全部B-产生式，又设 G1=(VN，VT，P1，S)是这样的文法，其中P1是从P中删去AB并添加产生式A1， A2，Ak所组成的集合，则L(G1)=L(G)。练习

8、n课本P39q2-2的4)至6)小题q2-3的3)至5)小题句型分析句型分析句型分析n判断给定符号串是否为文法的句型（句子）n自顶向下q从开始符号 - 给定符号串：推导q例： - 我学习编译原理n自底向上q从给定符号串 - 开始符号：归约q例：我学习编译原理 - 规范推导1/2n从 到 “我学习编译原理”有不同的推导序列n最左推导，左句型q替换最左边的非终结符q * xUy xuy * ，其中xUy xuy表示这个推导序列中的任一步直接推导，并且总有xVT*规范推导2/2n最右推导（规范推导），右（规范）句型q替换最右边的非终结符q总有yVT*n句子必有最左、右推导；句型未必n推导与回溯q如果

9、存在 U u1| u2| | un|，那么应如何选？规范归约n归约：推导的逆过程n最左归约(规范归约) = 最右推导(规范推导)n“我学习编译原理”如何规范归约到?n如何确定规范归约子串：最左直接短语文法n句子的产生n:=n:=|n:=我|你n:=大学生|编译原理n:=n:=是|学习n:= | 语法树1/4n树的概念q结点、根、内部结点、叶子、双亲、孩子、前驱、后继、路径、无环、连通、子树n语法树（分析树、推导树）q每个结点均有标记VNVTn根的标记为开始符号Sn内部结点标记VNq若以A为标记的结点有k个孩子分别标记为X1, X2, , Xk, 则AX1X2Xk必然是G的一个产生式语法树2/4

10、n请画出“我学习编译原理”的语法树q:=、:=|、q:=我我|你、你、:=大学生大学生|编译原理编译原理q:=、:=是是|学习学习q:= | n如果有如下文法（产生式）qEE+T|TqTT*F|FqF(E)|idn请画出id+id*id的语法树q即initial + rate * 60q考虑为什么要用T和F语法树3/4n文法的二义性：一个句子对应多个语法树n有如下文法qEE+E|E*E|(E)|idq请画出id+id*id的语法树nif then else 的嵌套q如果if语句定义为：nCif B then C | if B then C else C | Sqif B1 then if B2

11、 then S1 else S2的解释是？语法树4/4n设计程序设计语言应该避免二义性n上下文(前后文)无关文法的二义性是不可判的n文法兼有左、右递归是导致二义性的最常见原因n有些二义性可以通过等价变换消除qif then else 的就近原则q不能变换消除的则为先天二义性语言n上下文无关语言的先天二义性也是不可判的短语和句柄1/2n非形式化说明q子树叶子串是子树根的短语q两层子树的叶子串是子树根的直接短语n形式化定义q定义定义2.8：设是文法GS的一个句型，其中，V*，V+ ，若对于AVN有S*A 及A+ ，则称是句型相当于非终结符A的短语，特别地，若有S*A 及A ，则称是句型相当于产生式

12、A 的直接短语。短语和句柄2/2n“我学习编译原理”的短语和直接短语有哪些？nid+id*id呢？n无二义性的文法，句柄唯一句柄：最左直接短语n定义2.9 一个句型的最左直接短语称之为此句型的句柄。文法的化简与改造文法的化简与改造文法的化简无用符号和无用产生式的删除n符号X VNVT有用，指X至少出现在一个句子的推导过程中，也即X必须同时满足q可达：S*X，、V*q可终止： X * w，wVT*n否则X是无用的，包含无用符号的产生式是无用产生式。n目的：删除无用符号和产生式无用符号及产生式的删除n先找可终止的符号和产生式（算法2.1）n再找可达的符号和产生式（算法2.2）n思考为什么要按这个顺

13、序？算法2.1n1:置VN、P为空n2:若A，其中VT* ，令AVNn3:若AX1X2Xm，其中XiVTVN，令AVN n4:重复3直到VN 不再增大n5:若BY1Y2Ym中B和YiVTVN，令BY1Y2YmPn例：G=(S,U,V,W, a, b, c, P, S)，P=SaS, SW, SU, Ua, VbV, Vac, WaW算法2.2n1:置VN=S、 VT和P为空n2:若AVN，则将所有A产生式右部符号串i中的全部非终结符置于VN中，终结符至于VT中n3:重复2直到VN和VT都不再增大n4:将P中左右部仅含VNVT中符号的所有产生式置于P中n继续上例得到？-产生式的消除1/4n-产生

14、式：右部为的产生式n思想：q找出可能产生的非终结符（算法2.3）q将产生式右边，可能产生的非终结符A，分别用和A替换（算法2.4）q处理S * 的特殊情况（算法2.5）-产生式的消除2/4n算法2.3q令W1 = A| A Pq令WK+1 = Wk B | B P & Wk+, k1q直到Wi+1 = Win若Wi 为空，P不含-产生式n若S Wi ，L(G)；否则L(G)n例：SaA、ABC、BbB、CcC、 B、C，得到W=？-产生式的消除3/4n算法2.4q记算法2.3得到的集合Wi为Wq对任一AX1X2XmP，产生形如AY1Y2Ym的产生式：n若XiW，取Yi = Xi；n若X

15、iW，分别取Yi = Xi和Yi = 代入；q取步骤2产生的，除了A 外的所有产生式构成目标产生式集Pq继续上例，得到的产生式是？-产生式的消除4/4n算法2.5n引入新的S1VNVT为开始符号n令产生式集P=PS1 | SPn使用算法2.4消去P中的产生式n最后再添加S1n例子：ScS、SAB、AaAb、BBb、 A、 B；得到？文法的化简单产生式的消除n右部仅含一个非终结符的产生式，即形如AB的产生式称为单产生式。q利少害多，要消除。（特别的，AA无意义）n算法2.6q思想：若有AB，使用B可产生的符号串替换B算法2.6n1：设VN=A1, A2, , An，令W(Ai)=Ain2：重复W

16、(Ai)=W(Ai)D|CDP, CW(Ai), DVN直到W(Ai)不再增大n3：构造P=n例子：qG=(S,A,B,a,b,P,S, P=S AB, S A, S B, A aAb, A ab, B Bb, B bq思考算法可如何优化niNiiVAWBPBA1),(,|0型文法PSG1/2n若文法G中任一产生式都有一般形式 ，其中V+ V*，此外对， 不再加其它任何限制n由0型文法定义的语言称为0型（递归可枚举）语言。它可由图灵（Turing）机识别。0型文法PSG2/2文法GS SACaB CaaaC CBDB CBE aDDa ADAC aEEa AE 就是一个0型文法，它所产生的语言

17、为,|20aaaaaaaaaaaaaaIiaLi1型文法CSG 1/3n若一0型文法所有产生式具有形式（第1定义） 1A2 12 其中， 1,2V* V+ AVNn| 1A2 |(S为起始符）且S不出现在任何产生式的右侧。 n1型文法产生的语言称为前后文有关语言CSL，它可由线性限界自动机识别。1型文法CSG 2/3n根据定义，含有产生式的文法不是1型文法。但S-可作为1型文法的特例而被接受，条件是S不出现在所有产生式的右边。n例 文法G： S | A AaABC AabC CBBC bBbb bCbc cCcc1型文法CSG 3/3n1 型文法还有另一种定义形式（第2定义）： G的每个产生式

18、形为且满足： | | | | , V+n第2定义产生的语言=第1定义产生的语言-，即S-不可能存在于第二定义中。2型文法CFGn若一1型文法G中所有产生式具有形式: qA，其中V+， AVNn2型文法产生的语言称为前后文无关语言CFL，它可由下推自动机识别。n非严格CFG允许-产生式存在，即非严格CFG产生式形式为A，其中，V*，AVN n凡是能用BNF定义的语言都是前后文无关语言3型文法RG 1/2n若一2型文法G中仅含有形如AaB 或 Aa 的产生式，其中 A,B VN , a VT ，则称G为右线性文法。n类似地，若G中仅含有形如ABa 或 Aa的产生式，则称G为左线性文法。3型文法RG 2/2n3型文法产生的语言称为3型（正规）语言，它可由有限自动机识别。正规语言可用正规表达式表示。n3型文法还可拓广定义为 AB A （ VT +）四类语言之间的关系0123LLLL4类文法的识别：、RG、CFG、CSG、PSG练习n下面文法是否存在二义性？q