编译原理第三章文法和语言.ppt

《编译原理第三章文法和语言.ppt》由会员分享，可在线阅读，更多相关《编译原理第三章文法和语言.ppt（83页珍藏版）》请在装配图网上搜索。

1、2020/7/22,1,第三章文法和语言,课前思考, 高级语言有哪些一般特性？ 你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的？ 学习编译程序为什么要研究语言的描述问题？,2020/7/22,2,学习目标,本章目的是为语言的语法描述寻求工具 掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一文法。 熟练使用文法定义程序设计语言的单词和语法成分 对形式语言的理论有一个初步基础,2020/7/22,3,学习指南, 什么是文法,什么是它定义的语言？ 在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？ 什么是语法分析？语法分析方法的分类？,202

2、0/7/22,4,难重点,关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。,2020/7/22,5,知识结构,2020/7/22,6,引言和预备知识,高级语言 程序语言是一个记号系统 语法 语义,语法 任何语言程序都可以看成是一定字符集（字母表）上的字符串 语法使得这串字符形成一个形式上正确的程序 语法=词法规则+语法规则 例如：0.5*x1+c 0.5、x1、c、*、+是语言的单词符号 0.5*x1+c是语言的语法单位,词法 单词符号 语言中具有独立

3、意义的最基本结构 词法规则 词法规则规定了字母表中哪些字符串是单词符号 单词符号一般包括：常数、标识符、基本字、算符、界限符等 我们用正规式和有限自动机理论来描述词法结构和进行词法分析,语法 单词符号 语法单位 表达式、子句、语句、函数、过程、程序 语法规则 规定了如何从单词符号来形成语法单位 现在多数程序语言使用上下文无关文法来描述语法规则 语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据,例，对于一个PASCAL程序来说，一个上下文无关文法可以定义 A:=B+C 是合乎语法的， 而A:=B+ 是不合乎语法的。,语义 对于一个语言来说，不仅要给

4、出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义 离开语义，语言只是一堆符号的集合 各种语言中有形式上完全相同的语法单位，含义却不尽相同 对某种语言，可以定义一个程序的意义的一组规则称为语义规则 目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义,对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归纳为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段,2020/7/22,14,3.2 符号和符号串,任何一种语言都是由该语言的基本符号组成的符号串的集合。 基本符号集 任何语言的单词符号就是

5、定义在它的字符集上的字符串 该语言的任何语句就是定义在其单词符号集上的单词串(符号串),2020/7/22,15,字母表：是元素的非空有穷集合，把字母表中的元素称为符号，因此字母表也称符号集。例，a，b，c，+，就是含有5个元素的一个字母表。一般用和V来表示 符号：是语言当中最基本的不可再分的单位,2020/7/22,16,符号串：字母表中的符号所组成的任何有穷序列。例，V=a，b，c是一个字母表，则a，b，c，aa，ab，bc，abc等等都是V上的符号串 空串：不含有任何符号的串称为空串，记作,句子：字母表上符合某种规则构成的串 语言：字母表上句子的集合 注：约定用a, b, c表示符号；用

6、, , 表示符号串；用A, B, C表示其集合,2020/7/22,18,符号串的长度：如果某符号串中有m个符号，则其长度为m，记为|=m。 例，|abc|=3 的长度为0 符号串的连接：设和是符号串，它们的连接是把的符号写在的符号之后得到的符号串。例，若=NPU， =1108，则=NPU1108， =1108NPU,符号串的方幂：设是符号串，把自身连接n次得到符号串，即=，称为符号串的方幂，写作=n。 符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。,2020/7/22,19,两个符号串集合A和B的乘积（连接）： AB=| A且 B 注：1）串集的自身乘

7、积称作串集的方幂 2）A0= 字母表V的n次方幂是字母表V上所有长度为n的串集,2020/7/22,20,2020/7/22,21,字母表V的闭包V*和正闭包V+：,字母表上的语言，是字母表上正闭包的子集。,2020/7/22,22,3.1 文法的直观概念,文法的定义对语言结构的描述和定义，即在形式上用来描述和规定语言结构的称为“文法”(或“语法”)。,比如：“我是大学生。”是汉语的一个句子 汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语 := :=| := 我 | 你 | 他 := 王明 | 大学生 | 工人 | 英语 := := 是 | 学习 :=|,2020/7/22,23

8、,2020/7/22,24,一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找:=左端的带有句子的规则并把它表示成:=右端的符号串 规则中的“:=”也常用“”表示，含义是使用一条规则，代替=左边的某个符号，产生右端的符号串。 注意文法中，描述某个特定的语法成分的规则可能不只一条。,2020/7/22,25,得到句子“我是大学生”的全部动作过程是： 我 我 我是 我是 我是大学生,2020/7/22,26,“我是大学生”的构成是符合上述规则 “我大学生是”不符合上述规则 这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里

9、仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。,2020/7/22,27,3.3 文法和语言的形式定义,前面已经对规则(或产生式)的概念进行了非形式化的说明，我们已经对其有了一个直观的了解。下面将对其进行形式化说明，并在此基础上抽象地定义文法和语言。,2020/7/22,28,文法G定义为四元组（VN，VT，P，S） VN ：非终结符集 VT ：终结符集 P：产生式（规则）集合 S：开始符号（或识别符号） VNVT= ， SVN V=VNVT，称为文法G的文法符号集合,定义3.1,2020/7/22,29,句子的语法结构，可以用一组规则来描述。 规则也称为“重写规则”、“产生式”或“生成

10、式”，是形如或:=的(，)有序对，且V+， V* ，V为某字母表。 称为规则的左部(或产生式的左部) 称为规则的右部(或产生式的右部) 这里使用的符号（:=）读作“定义为”,2020/7/22,30,例3.1 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号,2020/7/22,31,例3.2 文法G=（VN，VT，P，S） VN =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S=,2020/7/22,32,习惯上不用将文法G的四元组显示地表示出来，只将产生式写出。并有如下约定： 第一条产

11、生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 G可写成GS，S是开始符号 G：S0S1 S01 GS： S0S1 S01,2020/7/22,33,有时，为书写简洁，常把相同左部的产生式，形如 A a1，Aa2 Aan 缩写为：Aa1|a2|.|an 注意：元符号“|”读作“或”,2020/7/22,34,一个文法的几种写法 例：G=（S，A，a,b，P，S） 其中： P：SaAb Aab AaAb A G：SaAb Aab AaAb A GS： Aab AaAb A SaAb GS：Aab |aAb | SaAb,2020/7/2

12、2,35,直接推导“” 定义3.2：如是文法G=(Vn，VT，P，S)的规则（或说是P中的一产生式），若有符号串v，w满足：v=，w= ，其中V*，V* 则称v直接推导出w，记作 v w 或w直接归约到v,对于例3.1的文法G:S0S1，S01 ，可以给出直接推导的一些例子如下： v=0S1，w=0011，直接推导：0S1 0011，使用的规则：S01，这里=0，=1。 v=S，w=0S1，直接推导：S 0S1，使用的规则：S0S1，这里=，= v=0S1，w=00S11，直接推导：0S1 00S11，使用的规则：S0S1，这里=0，=1。,2020/7/22,36,对于例3.2的文法G，直接

13、推导的例子有： v=，w= ，直接推导： ，使用的规则： ，这里= v= ，w= ，直接推导： ，使用的规则： 。这里=， 。 v=abc ，w=abc5，直接推导：abc abc5, 使用的规则： 5，这里=abc，=,2020/7/22,37,2020/7/22,38,定义3.3 如果存在直接推导的序列： v w0 w1 . wn=w (n0) 则称v 推导出（产生）w（推导长度为n）， 或称w归约到v。记作v w 定义3.4 若有v w，或v=w， 则记为v w,对例3.1的文法，存在直接推导序列v=0S1 00S11 000S111 00001111=w， 即0S1 00001111，

14、也可记作0S1 00001111 对例3.2的文法，存在直接推导序列v= x x1=w， 即 x1，也可记作 x1,2020/7/22,39,2020/7/22,40,文法的句型、句子的定义,句型 有文法GS，若S x，则称x是文法G的句型。 句子 有文法GS，若S x，且xVT*，则称x是文法G的句子。 例：G：S0S1， S01 S 0S1 00S11 000S111 00001111 S，0S1，000111都是文法G的句型，其中00001111是G的句子。,2020/7/22,41,定义3.6 由文法G所产生的语言记为L(G)，它是文法G的一切句子的集合: L(G)=x|S x，其中S

15、为文法的开始符号，且x VT* 例：G： S0S1， S01 L(G)=0n1n|n1,2020/7/22,42,例3.3 文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee,2020/7/22,43,S aSBE (SaSBE) aaSBEBE (SaSBE) aaaBEBEBE (SaBE) aaaBBBEEE (EBBE) aaabBBEEE (aBab) aaabbBEEE aaabbbEEE （bBbb) aaabbbeEE （bEbe) aaabbbeeE aaabbbeee （eEee),L（G）= anb

16、nen | n1 ,2020/7/22,44,文法的等价,若L(G1)=L(G2)，则称文法G1和G2是等价的。 如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1,2020/7/22,45,3.4 文法的类型,Chomsky将文法分为四种类型： 0型文法：G=(VN，VT，P，S)对任一产生式，都有(VNVT)*，且至少含有一个非终结符， (VNVT)*,0型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的,2020/7/22,46,带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an,1型文法（上下文有关

17、文法）：设G=(VN，VT，P，S)为一文法，若P中的每一个产生式，都有|， 仅仅 S除外 1型文法也可描述为1A2 12，其中1、 2和都在V*中，A在VN中。即只有A出现在1和2的上下文中时，才允许取代A。,2020/7/22,47,2020/7/22,48,例：1型（上下文有关）文法 文法GS：SaSBE SaBE EBBE aBab bBbb bEbe eEee,2型文法（上下文无关文法）： 设G=(VN，VT，P，S)，若P中的每一个产生式满足：是一非终结符， ( VNVT )* 有时将2型文法的产生式表示为形如：A其中AVN，也就是说用取代非终结符A时，与A所在的上下文无关，因此取

18、名为上下文无关文法。,2020/7/22,49,2020/7/22,50,例：2型（上下文无关）文法 文法GS：SaB|bA Aa|aS|bAA Bb|bS|aBB 文法GS：S0A|1B|0 A0A|1B|0S B1B|1|0,3型文法（正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是AaB或Aa，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法。,2020/7/22,51,2020/7/22,52,例：定义标识符的3型（正规）文法 文法GI：I iT I i T iT T dT T i T d,2020/7/22,53,文法和语言,0型文法产生的语言称为

19、0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）,2020/7/22,54,2020/7/22,55,3.5 上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构 算术表达式 语句 赋值语句 条件语句 读语句 ,2020/7/22,56,例：算术表达式上下文无关文法表示,文法G=(E， +，*，i，(，)， P，E P:E i E E+

20、E E E*E E (E),若E1和E2是算术表达式， 则E1+ E2，E1*E2和(E1)也是算术表达式。,描述语句的产生式： | 描述一种简单赋值语句的产生式为： i:=E 描述条件语句的产生式： ifthen| ifthenelse,2020/7/22,57,上下文无关的语法树,2020/7/22,58,用于描述上下文无关文法的句型推导的直观方法 给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树（推导树）。 定义：用来表示语言句子结构的树 作用：使用语法树可以使得语法分析过程直观、形象。易于判断文法二义性,语法树满足下列4个条件： 每个结点都有一个标记，此标记

21、是V的一个符号。 根的标记是S。 若一结点n至少有一个它自己除外的子孙，并且标记A，则A肯定在Vn中。 如果结点n的直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式。,2020/7/22,59,2020/7/22,60,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型aabbaa称为推导树的结果。也把该推导树称为句型aabbaa的语法树。,2020/7/22,61,推

22、导过程中施用产生式的顺序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,2020/7/22,62,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换 最右推导被称为规范推导 由规范推导所得的句型称为规范句型,2020/7/22,63,二义性,问题：一个句型是否对应唯一的一棵语法树？,例：GE:E i E E+E E E*E E (E),E E + E

23、E * E i i i,E E * E i E + E 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 i*i+E i*i+i,2020/7/22,64,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。 产生某上下文无关语言的每一

24、个文法都是二义的，则称此语言是先天二义的。,2020/7/22,65,注： 二义性会给语法分析带来不确定性 文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法 若要证明是二义性，只要举出一例,2020/7/22,66,若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事 二义文法改造为无二义文法 GE: E i GE：E T|E+T E E+E T F|T*F E E*E F (E)|i E (E) 规定优先顺序和结合律,2020/7/22,67,3.6 句型的分析,句型分析 就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。 在语

25、言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法 ，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。,2020/7/22,68,分析算法可分为： 自上而下分析法：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。 两种方法反映了两种不同的语法树的构造过程,2020/7/22,69,自上而下的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,SSS cAdcAd a b

26、推导过程：S cAd cabd,2020/7/22,70,自下而上的语法分析,例：文法G：S cAd A ab A a识别输入串w=cabd是否该文法的句子,S AA c a b d c a b d c a b d 归约过程：S cAd cabd,2020/7/22,71,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？ 2）如何识别可归约的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,2020/7/

27、22,72,句型分析,短语、直接短语、句柄的定义： 令G是一文法，S是文法的开始符号， 是文法G的一个句型。如果有：S A且A 则称是句型相对于非终结符A的短语。若有A 则称是句型相对于该规则A 的直接短语（简单短语）。一个句型的最左直接短语称为该句型的句柄。,2020/7/22,73,子树与短语、句柄,子树：在一棵语法树中，由某一结点及其所有分支组成的部分称为原树的一棵子树。 一棵子树的所有叶子自左至右排列起来形成一个相对子树根的短语。（如上例） 一个句型的句柄是这个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。,2020/7/22,74,句型分析,E E T T F F

28、 i1 * i2 + i3 短语： 直接短语： 句柄：,GE：EE+T|T TT*F|F F(E)|i 句型：i1*i2+i3,T,F,i1*i2+i3，i1*i2，i1，i2，i3,i1，i2，i3,i1,2020/7/22,75,例：设文法GS： S aAS|a A SbA|SS|ba 则aabbaa是该文法的一个句子，求此句子的短语和句柄,短语： 1、a1a2b1b2a3a4 2、a2b1b2a3 3、a4 4、a2 5、b2a3 句柄： a2,2020/7/22,76,3.7 有关文法实用中的一些说明,有关文法的实用限制 上下文无关文法中的规则,2020/7/22,77,3.7.1 有

29、关文法的实用限制,文法中不得含有有害规则和多余规则 有害规则：形如UU的产生式。会引起文法的二义性 多余规则：指文法中任何句子的推导都不会用到的规则 1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达 2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的,文法简化的步骤 查找有无形如PP的产生式，若有则删除 若某个产生式在推导过程中永远不会被用到，删除它 若某个产生式在推导过程中不能从中导出终结符，删除它 最后，整理所有剩余产生式，就得到简化的文法,2020/7/22,79,化简文法,例：GS 0) SBe *1) SEc 2) AAe 3) Ae *4) AA

30、*5) BCe 6) BAf *7) CCf（不可终止的） *8) Df （不可到达的 ）,(0)SBe (1)BAf (2)AAe (3)Ae,2020/7/22,80,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。 即1）文法GS，对某两个符号串和： S A 2）A t ，tVT*,2020/7/22,81,3.7.2 上下文无关文法中的规则,具有形式A的规则称为规则，其中AVN 某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂,复习重点,文法的概念 字母表、符号串和集合的概念及运算 文法的定义（四元组表示） 什么推导 句型、句子的概念 语言的形式定义,等价文法 文法的类型 最左（右）推导 规范推导 规范句型 规范归约 二义性 短语、句柄、直接短语,