第三章编译原理

1、1第三章文法和语言v3.1 文法的直观概念v3.2 符号和符号串v3.3 文法和语言的形式定义v3.4 文法的类型v3.5 上下无关文法及其语法树v3.6 句型的分析v3.7 有关文法实用中的一些说明23.1 文法的直观概念 请看下面的文法: | 我 | 你 | 他 王明 | 大学生 | 工人 | 英语 是 | 学习 | 3v几个符号的含义: : 非终结符 (变量) |: 或者 : 定义为 终结符终结符: 组成句子的符号.(常量) 这三个符号称为元语言符号元语言符号,用来说明文法符号之间的关系.4 终结符和非终结符称为文法符号文法符号. 产生式产生式( (规则规则) ) 左部左部 右部右部 文

2、法的开始符号文法的开始符号下面是句子 ”我是大学生” 的生成过程:53.2 符号和符号串字母表字母表:字母表是元素的非空有穷集合.符号串符号串:由字母表中的符号组成的任何有穷序 列称为符号串. 例 ： 符号串具有有序性 空符号串 符号串的长度 6符号串的运算符号串的运算: 符号串的连接 符号串的方幂 7符号串集合符号串集合: 若集合A中的一切元素都是定义在某字母表上的符号串,则称A为该字母上的符号串集合. 例:符号串集合的乘积符号串集合的乘积: 设A,B为两个符号串集合,A和B的乘积 AB= xy | xA, yB 例:8闭包闭包:定义在字母表上的任意长的符号串的集合,用*表示. 例:正正闭包

3、：闭包：+ + *93.3 文法和语言的形式定义v定义3.1 文法G定义为四元组（, ）其中：是非终结符集是终结符集为规则的集合 称开始符号，是它是一个非终结符，至 少要在一条规则中作为左部出现显然，称为文法的字母表10v例：约定约定：第一条产生式的左部为文法的开始符号：，表示非终结符， 表示终结符， ，表示符号串把文法写成, 其中为文法的开始符号11v定义3.2如果是文法G的一条产生式，*，若有符号串，满足 ，则说直接产生，或说是的直接推导，或称直接规约到，记作最左推导、最右推导、最左归约、最右归约12vv定义3.5 设GS是一文法，如果符号串x是从识别符推导出来的，即有x，则称x是GS的句

4、型若x仅由终结符号组成，即x，x，则称x是GS的句型子13v定义3.6文法所产生的语言定义为集合x x,其中s为文法识别符号，且x，用(G)表示该集合v定义3.7若(G1)=L(G2),则称文法G1和文法G2是等价的143.4文法的类型v型文法：设G= （, ），如果它的每一个产生式满足： （），且至少含有一个非终结符，且（），则是一个型文法v型文法：设G= （, ）为一0型文法，且中每一条产生式均满足|，仅仅除外，则文法是型文法或上下文有关文法15v型文法：设G= （, ）为一1型文法，且中每一个产生式均满足：是一个非终结符， （），则称文法G是型的或上下文无关的v型文法：设G= （, ）为

5、一2型文法，若中每一个产生式的形式都是： 或，其中和都是非终结符，*，则是型文法或正规文法16.上下文无关文法及其语法树语法树：用树的形式表示一个推导过程。 给定一个文法，一个句型，可画出该句型对应的该句型对应的语法树。语法树的画法：.树根为文法的开始符号。.末端结点从左到右连成的符号串是给定的句型。对内部结点或根结点A，若有产生式 Ak，则A的儿子从左到右为 ，2， ，k， 。 17例：给定句型 SaAS, ASbA, ASS, Sa, Aba 画出句型 aabbaa 对应的语法树。18 v给定文法: E E + T | T T T * F | F F P F | P P （E）| i 画出

6、下列句型对应的语法树。 i * ( E ) + T * P F T * F * F * ( E ) T + T + T * T * i19v给定文法: S aAaB | bAbB A S | db B bB | a 画出下列句型对应的语法树。 abAbBabbbB20v给定文法: A aA A ABe | B dB B bB | 画出下列句型对应的语法树。 aaAdbBe21v文法的二义性：一棵语法树表示了一个句型的种种可能的不同推导过程，但是，一棵句型是否只对应唯一的一棵语法树呢？一棵句型是否只有唯一的一个最左（最右）推导呢？不是v例： Ei, EE+E, EE*E, E(E) 句型 i *

7、 i + i 的最左推导有两个：推导 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 E E E + E E * E E * E i I E + E i i i i 推导的语法树推导的语法树 22v如果一个文法的某个句子对应两棵不同的语法树，则说这个文法是二义的v文法的二义性，在程序设计语言中应当避免，但是，要判断一个上下文无关文法是否是二义的，这个问题是递归不可解的，我们所能做的就是为无二义性寻找一组充分条件v例：二义性文法：无二义性的文法：文法=(E,+,*,I,(,),P,E)其中为： Ei, EE+E,ET|E+T

8、, T F|T*F EE*E, E(E) F(E)|i233.6 句型的分析v句型的分析就是识别一个符号串是否为某文法的句型(句子). 从左到右逐个识别输入符号, 看该符号串是给定文法的句子吗?v有两类分析方法: 1. 自上而下分析法 2 .自下而上分析法.24v3.6.1 自上而下的分析方法: 从文法的开始符号出发,反复使用各种产生式,寻找“匹配”输入符号串的推导.例:文法GS ScAd Aab Aa 识别输入串w=cabd是否该文法的句子解：构造的推导过程为：S cAd cabd可以看出输入符号串w是该文法的句子25v3.6.2 自下而上的分析方法从输入符号串开始，逐步进行“归约”，直到归

9、约到文法的开始符号例:文法GS ScAd Aab Aa 识别输入串w=cabd是否该文法的句子解： S A A c a b d c a b d c a b d可以看出输入符号串w是该文法的句子26v句型分析的有关问题：v在自上而下分析方法中的主要问题是：假若要被代换的最左非终结符号是，且有n条规则：V a1|a2|an那么如何确定用哪一个右部去替代呢？有一种解决办法是从所有可能的选择中随机挑选一种，并且希望它是正确的，如果以后发现它是错误的，我们必须退回去，再试另外的选择，这种方法称为回溯v在自下而上的分析方法中，在分析工作的每一步，都要从当前串中选择一个子串，将它归约到某个非终结符号，这个子

10、串称为“可归约串”问题是每一步如何确定这个“可归约串”在一种“规范归约”的分析中，这种“可归约串”称做“句柄”27v定义3.8令是一文法，是文法的开始符号，是文法的一个句型如果有：S A且A 则称是句型相对与非终结符A的短语特别的，如果有 A 则称则称是句型相对与规则A 的直接短语（也称简单短语）一个句型的最左直接短语称为该句型的句柄从句型的推导树上很容易找出句型的短语和直接短语设是句型的某一子树的根，其中是形成此子树的末端结点的符号串，则其中是句型相对于的短语若这棵子树只有一层分支，则是句型的直接短语*+283.7 有关文法实用中的一些说明v3.7.1有关文法的实用限制v在实用中，我们将限制文法中不得含