《编译原理cha》PPT课件.ppt

第二章,学习本章的目的 2.1 文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4 文法的类型 2.5 上下文无关文法及其语法树 2.6 句型的分析 2.7 有关文法实用中的一些说明,文法和语言,一个程序设计语言是一个记号系统，包括语法和语义两方面。语法是一组规则，用它可以形成和产生一个合适的程序，它只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系，这些与符号含义有关的用语法分析无法解决的问题属于语义分析的工作。语义分为两种：静态语义和动态语义。静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的；动态语义表明程序要做什么，要计算什么。 阐明语法的一个工具是文法，是形式语言理论的基本概念之一,学习本章的目的,构造编译程序的算法是从研究源程序及目标程序产生的，首先找到源语言的形式描述（常用的有语法描述图或扩充的巴科斯-瑙尔范式（即EBNF），根据这种描述，构造出相应的分析加工程序。 语言分语法，语义和语用。程序语言语法的形式描述是很好用的，语义的形式描述不那么好用，但它推动语言理论的发展。,文法的直观概念,有无穷句子的语言，无法列出全部句子，可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，这些规则成为判别句子结构合法与否的依据，可以看成是一种元语言，用来描述语言，仅仅涉及语言句子的结构描述，这样的语言描述称为文法。（例） 有了规则，可以用它们去推导或产生句子（例） 文法作为工具，严格地定义了句子的结构，也能够用适当条数的规则把语言的全部句子描述出来，是以有穷集合刻划无穷集合的工具。,含有无穷句子的语言如何给出它的有穷表示？,字母表 符号串 一. 符号串的定义 二. 术语 三. 符号串的运算 四. 符号串集合的运算,符号和符号串,程序设计语言是一切程序所组成的集合，程序是由类似if,begin,end的符号、字母和数字这样一些基本符号所组成，每个程序都是一个“基本符号”串。设有一基本符号集，那么程序设计语言可看成是在这个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。不同的程序设计语言可以有不同的符号集。,字母表是元素（符号）的非空有穷集合。任何程序语言都有自己的字母表，例如: 1.计算机语言：由符号“0”和“1”组成的字 母表,=0，1 2. ASCII字符集； 3. Pascal字母表为： = AZ, az, 09, +, -, *, /, , :, , ; ，.， , (, ), , , , ，各种保留字 ,字母表（符号集）,一. 符号串的定义 (1) （空符号串）是上的一个符号串。 (2) 若x是上的符号串，而a是的元素, 则xa是上的符号串。 (3) y是上的符号串,当且仅当它由(1)和 (2)导出。 由字母表中的符号所组成的的任何有穷 序列被称之为该字母表上的符号串,也称作 “字“。,符号串,符号串中，符号是有顺序的,设s是符号串 头：移走s的尾部的零个或多于零个符号 尾：删去s的头部的零个或多于零个符号 子串: 从s中删去一个头和一个尾 固有头（或固有尾）： 若x是s的头（或尾），且xs。 真子串： x是s的子串，且xsx 长度：是该符号串中的符号的数目。例如|aab|=3,|=0。,二术语,：符号串s=banana 头：,b,ba,ban,bana,banan,banana 尾：banana,anana,nana,ana,na,a, 子串: banana,anana,banan,anan, 固有头： ,b,ba,ban,bana,banan 固有尾： anana,nana,ana,na,a, 真子串: anana,banan,anan，ba,ban 长度：banana=6,例,当我们对符号串z=xy头感兴趣而对其余部分不感兴趣时，可以采用省略写法：z=x; 如果只是为了强调x在符号串z中的某处出现，则可表示为：z=x; 符号t是符号串z的第一个符号，则表示为：z=t,约定,1.连接：设x和y是符号串，它们的连接 xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana. 2.方幂：设x是符号串，把x自身连接n次得到的符号串。x0= ; x1=x; x2=xx; ;xn=xn-1x; 例如, x=ba, x1= ba, x2=baba, x3=bababa,.,三.符号串的运算,符号串集合：若集合L中的一切元素都是某字母表上的符号串，则称L为该字母表上的符号串集合。 设L和M是两个符号串集合，则 1.合并：LMs|sL or sM 2.连接（乘积）：LM st|sL and tM 3.方幂： L0=， L1L， L2LL, ., LnLn-1L,四. 符号串集合(语言）的运算,四. 符号串集合(语言）的运算（续）,4. 语言L的Kleene闭包，记作L*， L*Li(i=0) =L0L1L2L3 这里，L表示一个字母表，L*表示L上的所有有穷长的串的集合。 5语言L的正闭包，记作L+（L+L L*） L+Li(i =1) =L1L2L3L4 对任意L，一定有L+吗？,L=AZ,az D=09 1LD=AZ,az ,09 2LD是由所有用一个字母后跟一个数字 组成的符号串所构成的集合。 3L4是由所有的四个字母的符号串构成 的集合。 4L（LD)* 是由所有的字母打头的字母和数字组成的符号串所构成的集合. 5D+是由所有的长度大于等于1的数字串所构成的集合.,例3.1,文法和语言的形式定义,一. 文法的定义 二. 推导 三. 语言,终结符，是构成语言文法的单词，是语法成分的最小单位(比如赋值符等）。 非终结符，是一个语法成分，在书写语言程序时并不出现，它是终结符和非终结符串、或终结符串定义的（比如赋值语句，表达式等）。 规则（重写规则、产生式或生成式），是形如-或:=的（,）有序对，其中是某个字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称为规则的右部。,一 文法的定义,文法G定义为四元组（VT，VN ,S, P ），其中： VT是一个非空有穷终结符号集合； VN是一个非空有穷的非终结符号集合， 且VTVN； P是一个产生式的非空有穷集合（注意：产生式左部至少含有一个非终结符）； S VN ，称为开始符号，且S至少必须在某个产生式的左部出现一次 。 通常用V表示VN VT,V称为文法G的字母表或字汇表.,G=(a,+,*,(,),， ， ，P ) P： * （ ) a 或G(E): E E+T T T T*F F F ( E ) a (3.1),例3.2 算术表达式的文法G:,例3.3：文法G=VN，VT，P，S 其中 VN=S VT=0，1 P=S-0S1，S-01,例3.4：文法G=VN，VT，P，S 其中 VN=标识符，字母，数字 VT=a,b,c,x,y,z,0,1,9 P= - | | - a|b|c|z - 0|1|2|9 S= ,在描述文法时,文法四元组可以不显示地表示出来,而只将产生式写出。 这里约定，第一条产生式的左部是识别符号(即开始符号)；用尖括号括起来的是非终结符，不用尖括号括起来的是终结符，或者用大写字母表示非终结符，用小写字母表示终结符。以S为开始符号的文法G，习惯写成GS。,为简洁，常把相同左部的产生式，即形如 A- 1 A- 2 A-n 缩写为: A-1|2|n,上述例3.3文法可以写成： G：S-0S1 S-01 或写成： GS：S-0S1 S-01 或写成； GS：S-0S1 | 01,令G=(VT,VN,S,P), 若AP, 且,(VTVN)*,若有符号v,w满足:v= A,w= ,则称w是v的直接推导 A直接推出, 或说直接归约到A, 表示成A 例 如果存在一个直接推导序列： 012 n（n0） 表示成 0 n 0 n 或者0=n或者0 n 例,+ ,+ ,* ,二. 直接推导和推导的定义,例：E E+T T+T F+T a+T a+F a+a,设文法 G（VT，VN，S,P）。如果S , V*，则称是一个句型。仅含终结符号的句型是一个句子。语言 L(G）是由文法G产生的所有句子所组成的集合： L(G)|S 且VT* 例 例3.5 考虑一个文法 G(a,b,S,S，P）其中P：SaSb ab SaSb aaSbb a3Sb3 an-1Sbn-1 anbn L(G)=anbn|n=1,* ,三. 语言的定义,* ,对于较简单的文法，比较容易确定哪些符号串可以推导出来，如上例；但一般来说，确定文法将产生什么可能是比较困难的，如下例： 设G=(VT=a,b,VN=S,A,B,S,P P由下列产生式组成: SaB|bA Aa|aS|bAA Bb|bS|aBB L(G)=w|wa,b+,且w中有相同个数的a和b。,文法等价,若L（G1）=L（G2），则称文法G1和G2是等价的。 例：文法G（A）： A-aR A-ab R-Ab 该文法和例3.5的文法等价 这里告诉我们：不同文法可以产生相同语言，或说同一种语言可以由不同文法描述。,文法的类型,逐渐对产生式施加限制 四种类型： 0型，1型，2型，3型 0型：G=(VT,VN,S,P) 规则形式 ： , (VTVN)*, 中至少有一个非终结符 1型（上下文有关） ：,仅S- 除外 规则形式 ： A A VN, ， (VTVN)*, 例 2型（上下文无关）：规则形式 ： A A VN， (VTVN)* 例 3型（右线性）： A aB 或 A a A,B VN （左线性） A Ba 或 A a a VT,例,四个文法类型的定义是逐渐增加限制的，因此是正规文法，就是上下文无关文法，就是上下文有关文法,就是0型文法。 上述四类文法产生的语言依次称为正规语言、上下文无关语言、上下文有关语言和0型语言。,上下文无关文法 及其语法树,上下文无关文法有足够能力描述现今程序设计语言的语法结构(例)，因此我们关心它形成的语言的句子的分析和分析方法的研究。语法树(推导树)是描述上下文无关文法的句型推导的直观方法,给定文法G，对于G的任何句型都能构造与之关联的语法树。,语法树定义,设G=（VT，VN，S，P）,G的一棵语法树满足如下条件： 1. 每一个结点有一个标记，此标记是VTVN中的符号。 2根的标记是S。 3如果一个结点是内部结点，且有标记A,那么A必在VN中。 4如果编号为n的结点有标记A,结点n1,n2,nk 是结点n的从左到右的儿子，并分别有标记X1,X2,Xk，则AX1X2Xk必是P中的产生式 5. 如果结点n有标记，那么结点n是叶子，且是它父亲唯一的儿子。,例3.5 G=(VT,VN,S,P), 其中 P: SaASa A SbA SS ba,上图是文法G的句型aabbaa的语法树,1.语法树表示了在推导过程中使用了哪个产生式和施用在哪个非终结符上，但并没有表明使用产生式的顺序。 2.若文法是无二义性的，对于一个句子的多种推导过程，画出的分析树是一样的。语法树并未描述推导过程。 3. 若文法是二义性的，一棵语法树未必能表示一个句型的所有不同推导过程，后面还会看到，一个句型也不一定只对应唯一的一个语法树，一个句型也不一定只有唯一的最左（最右）推导。 4.在书中，用画语法树的过程解释语法分析过程，用语法树图解语法结构。,关于语法树的几点说明,如果在推导的任何一步 ，其中、是句型，都是对 中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。 在形式语言中，最右推导常被称为规范推导。由规范推导得到的句型称为规范句型。,最左（右）推导,例如，GE（例3.2）和w=a+a * a EE+T T+T F+T a+T a+T*F a+F *F a+a *F a+a*a（ 最左） 特点：A (A) ， VT* EE+T E+T *F E+ T *a E+F*a E+a*a T+a*a F+a*a a+a*a （最右） 特点：A (A)， VT*,最左（最右）推导实例,文法的二义性的定义,如果一个文法存在某个句子对应两棵不同的语法树,或者说,若一个文法中存在某个句子,它有两个不同的最左(最右)推导,则说这个文法是二义的. 例3.7表达式文法 GE,其产生式如下： EE+EE*E (E) a 对于句子a+a*a, 有如下两个最左推导： EE+E a+E a+E*E a+a*E a+a*a E E*E E+E*E a+E*E a+a*E a+a*a,EE+E a+E a+E*E a+a*E a+a*a,E E*EE+E*E a+E*Ea+a*E a+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,最左推导,EE+E E+E*E E+E*a E+a*a a+a*a,E E*EE*a E+E*aE+a*a a+a*a,E,E,+,E,E,*,E,a,a,a,E,E,*,E,+,E,E,a,a,a,最右推导,文法的二义性和语言的二义性是两个不同概念。因为有可能文法G和A不同，但L（G）=L（A），G是二义的，A是无二义的。 如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。我们总是希望一个程序设计语言的文法是无二义的，因为我们希望对它的每个句子的分析是唯一的。 不存在一个算法，能在有限步骤内确切判定任给的一个文法是否为二义的或是否产生一个先天二义的语言，我们能做的是为无二义性寻找一组充分条件，从而构造出一个无二义的文法。如例3.2和例3.7两文法产生的语言是相同的，即它们是等价的。,句型分析,句型分析问题，就是识别一个符号串是否为某文法的句型，是个推导的构造过程，也即当给定一个符号串时，试图按照文法的规则为该符号串构造推导树，以此识别出它是否为该文法的句型；当符号串是终结符号串时，就是识别句子或说是句子分析。 对于程序设计语言来说，程序是定义程序设计语言的文法的句子，这时的句型分析是一个识别输入符号串（其实就是你的源程序）是否为语法上正确的程序的过程。,句型分析,在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序,分析算法称为识别算法。 介绍的识别算法都是从左至右的分析算法，分为两大类，即自上而下和自下而上的分析法。 自上而下分析法,是从文法开始符号出发,反复使用各种产生式,逐步进行推导，直至推导出输入符号串。 自下而上分析法，是从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 从语法树的建立方式可以很好地帮助我们理解这两类方法的区别。,根据推导序列，对每步推导画相应分枝,A,S,a,S,b,S,A,a,a,b,a,aSbAS,aabAS,aabbaS,aabbaa,aAS,S,如何画出语法树 (1.自上而下）,例 G=(VT,VN,S,P), 其中 P: SaASa A SbA SS ba 采用自上而下方法分析句型aabbaa如上,即：自上而下方法是从文法识别符号开始，将它作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。,根据归约序列，对每步归约画相应分枝,A,S,a,S,b,S,A,a,a,b,a,aAa,aSbAa,aSbbaa,aabbaa,aAS,S,如何画出语法树 (2.自下而上）,即：自下而上方法是从输入符号串开始，以它作为语法树的末端结点，自底向上地构造语法树，使语法树的根结点正好是文法的开始符号。,例 G=(VT,VN,S,P), 其中 P: SaASa A SbA SS ba 采用自下而上方法分析句型aabbaa如上,句型分析的有关问题,在自上而下分析法中的关键问题是: 假定要被代换的最左非终结符号是A,且有n条产生式:A a1|a2|an,那么如何确定用哪个产生式右部去替代A? 例 （回溯可解决该问题，但不是最好的方法,解决该问题的手段不同形成不同的自上而下分析法） 在自下而上分析法中的关键问题是: 因为分析工作的每一步都是从当前串中选择一个子串,将它归约到某个非终结符,暂且把这个子串称为可归约串,问题是,每一步如何确定这个可归约串? 例 (存在不同的方法来决策“可归约串”，决策方法不同形成不同的自下而上分析法) 在规范归约的分析法中,可归约串称作句柄.,令GS是一个文法，如果有S A 且A ,则称是一个关于非终结符号A的，句型的短语。其次如果有 S A 且 A，则称是句型相对于规则A直接短语。一个句型的最左直接短语称为该句型的句柄。 对例3.2的文法的一个句型 a1*a2+a3 ， 短语：a1,a2,a3，a1*a2,a1*a2+a3 直接短语:a1，a2 ,a3 句柄:a1 问：a2+a3是所给句型的短语吗？,+ ,* ,* ,短语、直接短语、句柄,一棵语法树中一个特有的结点连同它的全部后裔，连接这些后裔的边以及这些结点的标记，称为子树。例如：,S,A,b,S,a,S,b,a,A,a,a,子树,短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。 直接短语：仅有父子两代的一棵子树，它的 所有叶子自左至右排列起来所形成的符号串。 句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。 例如，对表达式文法GE和句子a1+a2*a3，请指出其的短语，直接短语，句柄，见下页图示。,用子树解释短语，直接短语，句柄:,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,例,G(E): E E+T T T T*F F F ( E ) a,a1+a2*a3,E,E+T,E+T*F,E+T*a3,E+F* a3,E+a2 * a3,T+a2 * a3,F+a2 * a3,E,E,+,T,T,F,a1,T,*,F,F,a2,a3,a1+a2 *a3,例,用句柄进行归约,有关文法实用中的一些说明,一.有关文法的实用限制 在实用中,限制文法中不得含有有害规则和多余规则. 有害规则是指形为U-U的产生式。会引起文法二义性。 多余规则是指文法中那些任何句子推导都用不到的规则,包括两种规则,即不可到达的和不可终止的。 不可达到的：不在文法的任何规则右部出现的非终结符。 不可终止的：文法中那些不能从其推出终结符号串的非终结符。,对文法G来说,为保证任一个非终结符A在句子推导中出现,必须满足如下两个条件: 1)S aAb,其中a,b属于(VN VT)* 2)A t,其中t属于VT*,+ ,例：文法GS：1）S-Be 2)B-Ce 3)B-Af 4)A-Ae 5)A-e 6)C-Cf 7)D-f 请指出上述文法的多余规则？,* ,有关文法实用中的一些说明,二.上下文无关文法中的规则 在我们定义的上下文无关文法中,某些规则可具有形如A-,其中A VN,称这种规则为规则. 但很多书籍中,却限制这种规则的出现,因为规则会使得有关文法的一些讨论和证明变得复杂. 其实,两种定义没有本质差别,唯一差别是句子在不在语言中.即若语言L是一个有穷描述,则L 同样有一个有穷描述.且，若L是上下文有关语言、上下文无关语言和正规语言，则L和L-也分别是上下文有关语言、上下文无关语言和正规语言。 P46的两个上下文无关文法的定义,典型例题及解答,1.证明文法G=(E,O,(,),+,*,v,d,P,E)是二义的。E-EOE|(E)|v|d O- + | * 解 只要给出一个句子（如v*v+d）的语法树不只一棵即可。 讨论：没有通用的办法可以消除上下文无关文法的二义性。但在编译系统构造的实践中形成了一些比较实用的技术，可以用于将某些二义性文法变换为无二义文法。比如，利用优先级规则，左、右结合性规则和最近嵌套规则等，本例即可用此方法变换为无二义性的。 E-E+T|T T-T*F|F F-(E)|v|d,2.考虑下述两个语言： L1=anb2ncm|n,m=0 L2=anbmc2m|n,m=0 通过分别给出上述语言的文法来证明这些语言都是上下文无关的。 解 对于L1，存在如下的上下文无关文法： S-AB A-|aAbb B-|cB 对于L2，存在如下的上下文无关文法： S-AB A-|aA B-|bBcc,汉语句子规则的EBNF表示： := :=| :=我|你|他 :=王明|大学生|工人|英语 := :=是|学习 :=|,句子“我是大学生”的推导过程： = = =我 =我 =我是 =我是 =我是大学生 符号=的含义是，使用一条规则，代替=左边某个符号，产生=右端的符号串,推导过程1：S =aAS =aAa =aSbAa =aSbbaa =aabbaa 推导过程2：S =aAS =aSbAS =aabAS =aabbaS =aabbaa 推导过程3：S =aAS = aSbAS =aSbAa =aabAa =aabbaa,例3.5 G=(VT,VN,S,P), 其中 P: SaASa A SbA SS ba,对文法G的句型aabbaa的上述三种推导过程，与它们相联的语法树是相同。另外，除了上述三种推导过程，还有其他的不同推导过程,正规文法示例： 文法G=（