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

2022/12/211第三章第三章文法和语言文法和语言 课前思考 高级语言有哪些一般特性？你所见到的程序设计语言的手册或语言标准是怎样陈述语言的语法和语义的？学习编译程序为什么要研究语言的描述问题？2022/12/212学习目标本章目的是为语言的语法描述寻求工具 掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一文法。熟练使用文法定义程序设计语言的单词和语法成分 对形式语言的理论有一个初步基础2022/12/213学习指南 什么是文法,什么是它定义的语言？在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？什么是语法分析？语法分析方法的分类？2022/12/214难重点l关于文法和语言的概念是形式语言的理论基础，形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。这里介绍的语言的语法描述工具正是这样的系统。2022/12/215知识结构2022/12/216引言和预备知识l高级语言程序语言是一个记号系统语法语义l语法任何语言程序都可以看成是一定字符集（字母表）上的字符串语法使得这串字符形成一个形式上正确的程序语法=词法规则+语法规则l例如：0.5*x1+c0.5、x1、c、*、+是语言的单词符号0.5*x1+c是语言的语法单位l词法单词符号l语言中具有独立意义的最基本结构词法规则l词法规则规定了字母表中哪些字符串是单词符号l单词符号一般包括：常数、标识符、基本字、算符、界限符等我们用正规式和有限自动机理论来描述词法结构和进行词法分析l语法单词符号语法单位l表达式、子句、语句、函数、过程、程序语法规则l规定了如何从单词符号来形成语法单位l现在多数程序语言使用上下文无关文法来描述语法规则l语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据例，对于一个PASCAL程序来说，一个上下文无关文法可以定义 A:=B+C 是合乎语法的，而A:=B+是不合乎语法的。l语义对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义离开语义，语言只是一堆符号的集合各种语言中有形式上完全相同的语法单位，含义却不尽相同对某种语言，可以定义一个程序的意义的一组规则称为语义规则目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义l对于高级程序设计语言及其编译程序来说，语言的语法定义是很重要的。本章主要介绍语法结构的形式描述问题，编译原理的主要内容也可以归纳为应用形式语言理论，并将它贯穿于词法分析和语法分析两个阶段2022/12/21143.2 符号和符号串 任任何何一一种种语语言言都都是是由由该该语语言言的的基基本本符符号组成的符号串的集合。号组成的符号串的集合。l 基本符号集基本符号集l 任任何何语语言言的的单单词词符符号号就就是是定定义义在在它它的的字符集上的字符串字符集上的字符串l该该语语言言的的任任何何语语句句就就是是定定义义在在其其单单词词符符号集上的单词串号集上的单词串(符号串符号串)2022/12/2115l字母表字母表：是元素的非空有穷集合，把字母表中的元素称为符号，因此字母表也称符号集。例，a，b，c，+，就是含有5个元素的一个字母表。一般用和V来表示l符号符号：是语言当中最基本的不可再分的单位2022/12/2116l符号串符号串：字母表中的符号所组成的任何有穷序列。例，V=a，b，c是一个字母表，则a，b，c，aa，ab，bc，abc等等都是V上的符号串l空串空串：不含有任何符号的串称为空串，记作l句子句子：字母表上符合某种规则构成的串l语言：语言：字母表上句子的集合l注：约定用a,b,c表示符号；用,表示符号串；用A,B,C表示其集合2022/12/2118l符号串的长度符号串的长度：如果某符号串中有m个符号，则其长度为m，记为|=m。例，|abc|=3 的长度为0l符号串的连接符号串的连接：设和是符号串，它们的连接是把的符号写在的符号之后得到的符号串。例，若=NPU，=1108，则=NPU1108，=1108NPUl符号串的方幂符号串的方幂：设是符号串，把自身连接n次得到符号串，即=，称为符号串的方幂，写作=n。l符号串集合符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。2022/12/2119l两个符号串集合A和B的乘积（连接）：AB=|A且 B注：1）串集的自身乘积称作串集的方幂 2）A0=l字母表V的n次方幂是字母表V上所有长度为n的串集2022/12/21202022/12/2121l字母表字母表V的闭包的闭包V*和正闭包和正闭包V+：字母表上的语言，是字字母表上的语言，是字母表上正闭包的子集。母表上正闭包的子集。2022/12/21223.1 文法的直观概念 文文法法的的定定义义 对对语语言言结结构构的的描描述述和和定定义义，即即在在形形式式上上用用来来描描述述和和规规定定语语言言结结构的称为构的称为“文法文法”(或或“语法语法”)。比如：“我是大学生。”是汉语的一个句子汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语:=:=|:=我|你|他:=王明|大学生|工人|英语:=:=是|学习:=|2022/12/21232022/12/2124l一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找:=左端的带有句子的规则并把它表示成:=右端的符号串l规则中的“:=”也常用“”表示，含义是使用一条规则，代替=左边的某个符号，产生右端的符号串。l 注意文法中，描述某个特定的语法成分的规则可能不只一条。2022/12/2125得到句子得到句子“我是大学生我是大学生”的全部动作过程是：的全部动作过程是：我我 我我 我是我是 我是我是 我是大学生我是大学生2022/12/2126“我是大学生”的构成是符合上述规则“我大学生是”不符合上述规则这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。2022/12/21273.3 文法和语言的形式定义 前面已经对规则(或产生式)的概念进行了非形式化的说明，我们已经对其有了一个直观的了解。下面将对其进行形式化说明，并在此基础上抽象地定义文法和语言。2022/12/2128l文法文法G定义为四元组（定义为四元组（VN，VT，P，S）VN：非终结符集：非终结符集VT：终结符集：终结符集P：产生式（规则）集合：产生式（规则）集合S：开始符号（或识别符号）：开始符号（或识别符号）VNVT=，SVNV=VNVT，称为文法，称为文法G的文法符号集合的文法符号集合定义3.12022/12/2129l句子的语法结构，可以用一组规则来描述。l规则也称为“重写规则”、“产生式”或“生成式”，是形如或:=的(，)有序对，且V+，V*，V为某字母表。称为规则的左部(或产生式或产生式的左部的左部)称为规则的右部(或产生式或产生式的右部的右部)l这里使用的符号（:=）读作“定义为”2022/12/2130例例3.1 文法文法G=（VN，VT，P，S）VN=S,VT=0,1 P=S0S1,S01 S为开始符号为开始符号2022/12/2131例例3.2 文法文法G=（VN，VT，P，S）VN=标识符，字母，数字标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,zz 0,9 S=2022/12/2132l习惯上不用将文法习惯上不用将文法G的四元组显示地表示出的四元组显示地表示出来，只将产生式写出。并有如下约定：来，只将产生式写出。并有如下约定：第一条产生式的左部是开始符号第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符者大写字母表示非终结符，小写字母表示终结符G可写成可写成GS，S是开始符号是开始符号 G：S0S1 S01 GS：S0S1 S012022/12/2133l有时，为书写简洁，常把相同左部的产生式，有时，为书写简洁，常把相同左部的产生式，形如形如 A a1，Aa2 Aan 缩写缩写为：为：Aa1|a2|.|an 注意：元符号注意：元符号“|”读作读作“或或”2022/12/2134l一个文法的几种写法一个文法的几种写法例：例：G=（S，A，a,b，P，S）其中：其中：P：SaAb Aabab AaaAb A G：SaAb Aab AaAb A GS：Aabab AaaAb A SaaAb GS：Aabab|a aAb|SaaAb2022/12/2135l直接推导直接推导“”定义定义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，可以给可以给出直接推导的一些例子如下：出直接推导的一些例子如下：lv=0S1，w=0011，直接推导：，直接推导：0S1 0011，使用的规则：使用的规则：S01，这里这里=0，=1。lv=S，w=0S1，直接推导：直接推导：S 0S1，使用的，使用的规则：规则：S0S1，这里这里=，=lv=0S1，w=00S11，直接推导：，直接推导：0S1 00S11，使用的规则：使用的规则：S0S1，这里这里=0，=1。2022/12/2136对于例对于例3.2的文法的文法G，直接推导的例子有：，直接推导的例子有：lv=，w=，直接推导：，直接推导：，使用的规则：，使用的规则：，这里，这里=lv=，w=，直接推导：，直接推导：，使用的规则：，使用的规则：。这里这里=，。lv=abc，w=abc5，直接推导：，直接推导：abc abc5,使用的规则：使用的规则：5，这里，这里=abc，=2022/12/21372022/12/2138定义定义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，也可记作，也可记作0S1 00001111对例对例3.2的文法，存在直接推导序列的文法，存在直接推导序列v=x x1=w，即即 x1，也可记作，也可记作 x12022/12/21392022/12/2140文法的句型、句子的定义文法的句型、句子的定义l句型句型有文法有文法GS，若，若S x，则称，则称x是文法是文法G的句型。的句型。l句子句子有文法有文法GS，若，若S x，且，且xVT*，则称，则称x是文是文法法G的句子。的句子。例：例：G：S0S1，S01S 0S1 00S11 000S111 00001111S，0S1，000111都是文法都是文法G的句型，其中的句型，其中00001111是是G的句子。的句子。2022/12/2141定义定义3.6 由文法由文法G所产生的语言记为所产生的语言记为L(G)，它是文法，它是文法G的一切句子的集合的一切句子的集合:L(G)=x|S x，其中，其中S为文法的开始符号，为文法的开始符号，且且x VT*例例：G：S0S1，S01 L(G)=0n1n|n12022/12/2142l例例3.3 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee2022/12/2143 S aSBE (SaSBE)aaSBEBE (SaSBE)aaaBEBEBE (SaBE)aaaBBBEEE (EBBE)aaabBBEEE (aBab)aaabbBEEE aaabbbEEE （bBbb)aaabbbeEE （bEbe)aaabbbeeE aaabbbeee （eEee)L（G）=anbnen|n1 2022/12/2144文法的等价文法的等价l若若L(G1)=L(G2)，则称文法，则称文法G1和和G2是等价的。是等价的。如文法如文法G1A：A0R 与与G2S：S0S1 等价等价 A01 S01 RA12022/12/21453.4 文法的类型文法的类型lChomsky将文法分为四种类型：将文法分为四种类型：l0型文法：型文法：G=(VN，VT，P，S)对任一产生式对任一产生式 ，都有都有(VNVT)*，且至少含有一个非终结符，且至少含有一个非终结符，(VNVT)*l0型文法（短语文法）的能力相当于图灵型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且机，可以表征任何递归可枚举集，而且任何任何0型语言都是递归可枚举的型语言都是递归可枚举的2022/12/2146 有限控制器有限控制器磁头磁头 带带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an l1型文法（上下文有关文法）：设型文法（上下文有关文法）：设G=(VN，VT，P，S)为一文法，若为一文法，若P中的每一个中的每一个产生式产生式 ，都有，都有|，仅仅仅仅 S 除外除外l1型文法也可描述为型文法也可描述为 1A 2 12，其其中中 1、2和和 都在都在V*中，中，A在在VN中。中。即只有即只有A出现在出现在 1和和 2的上下文中时，才的上下文中时，才允许允许 取代取代A。2022/12/21472022/12/2148l例：例：1型（上下文有关）文法型（上下文有关）文法 文法文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEeel2型文法（上下文无关文法）：型文法（上下文无关文法）：设设G=(VN，VT，P，S)，若，若P中的每一个中的每一个产生式产生式 满足：满足：是一非终结符，是一非终结符，(VNVT)*l有时将有时将2型文法的产生式表示为形如：型文法的产生式表示为形如：A 其中其中AVN，也就是说用，也就是说用 取代非取代非终结符终结符A时，与时，与A所在的上下文无关，因所在的上下文无关，因此取名为上下文无关文法。此取名为上下文无关文法。2022/12/21492022/12/2150l例：例：2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SaB|bAAa|aS|bAABb|bS|aBB 文法文法GS：S0A|1B|0A0A|1B|0SB1B|1|0l3型文法（正规文法）：设型文法（正规文法）：设G=(VN，VT，P，S)，若，若P中的每一个产生式的形式都中的每一个产生式的形式都是是AaB或或Aa，其中，其中A和和B都是非终结都是非终结符，符，a是终结符，则是终结符，则G是是3型文法或正规文型文法或正规文法。法。2022/12/21512022/12/2152l例：定义标识符的例：定义标识符的3型（正规）文法型（正规）文法 文法文法GI：I iTI iT iTT dTT iT d2022/12/2153文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1型文法或上下文有关文法（型文法或上下文有关文法（CSG）产生的语言）产生的语言称为称为1型语言或上下文有关语言（型语言或上下文有关语言（CSL）2型文法或上下文无关文法（型文法或上下文无关文法（CFG）产生的语言）产生的语言称为称为2型语言或上下文无关语言（型语言或上下文无关语言（CF L）3型文法或正则（正规）文法（型文法或正则（正规）文法（RG）产生的语）产生的语言称为言称为3型语言正则（正规）语言（型语言正则（正规）语言（RL）2022/12/21542022/12/21553.5 上下文无关文法及其语法树上下文无关文法及其语法树l上下文无关文法有足够的能力描述现今程上下文无关文法有足够的能力描述现今程序设计语言的语法结构序设计语言的语法结构算术表达式算术表达式语句语句l赋值语句赋值语句l条件语句条件语句l读语句读语句l2022/12/2156例：算术表达式上下文无关文法表示例：算术表达式上下文无关文法表示l文法文法G=(E，+，*，i，(，)，P，E P:E iE E+EE E*EE (E)若若E1和和E2是算术表达式，是算术表达式，则则E1+E2，E1*E2和和(E1)也是算术表达式。也是算术表达式。l描述语句的产生式：描述语句的产生式：|l描述一种简单赋值语句的产生式为：描述一种简单赋值语句的产生式为：i:=El描述条件语句的产生式：描述条件语句的产生式：ifthen|ifthenelse2022/12/2157上下文无关的语法树上下文无关的语法树2022/12/2158l用于描述上下文无关文法的用于描述上下文无关文法的句型推导句型推导的直观方法的直观方法l给定文法给定文法G=(VN，VT，P，S)，对于，对于G的任何句型的任何句型都能构造与之关联的都能构造与之关联的语法树语法树（推导树推导树）。）。l定义：定义：用来表示语言句子结构的树用来表示语言句子结构的树l作用：使用语法树可以使得语法分析过程直观、形作用：使用语法树可以使得语法分析过程直观、形象。易于判断文法二义性象。易于判断文法二义性语法树满足下列语法树满足下列4个条件：个条件：每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号。的一个符号。根的标记是根的标记是S。若一结点若一结点n至少有一个它自己除外的子孙，并且标至少有一个它自己除外的子孙，并且标记记A，则，则A肯定在肯定在Vn中。中。如果结点如果结点n的直接子孙，从左到右的次序是结点的直接子孙，从左到右的次序是结点n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak一定是一定是P中的一个产生式。中的一个产生式。2022/12/21592022/12/2160 例例:GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的语法树（推导树）的语法树（推导树）叶子结点：树中没有子孙的结点。叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型从左到右读出推导树的叶子标记，所得的句型aabbaa称为推导树的结果。也把该推导树称为称为推导树的结果。也把该推导树称为句型句型aabbaa的语法树。的语法树。2022/12/2161l推导过程中施用产生式的推导过程中施用产生式的顺序顺序 例例:GS:SaASASbAASSSaAba S a A S S b A a a b aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa2022/12/2162l最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步 ，其中，其中、是句型，都是对是句型，都是对 中的最中的最左（右）非终结符进行替换左（右）非终结符进行替换l最右推导被称为最右推导被称为规范推导规范推导l由规范推导所得的句型称为由规范推导所得的句型称为规范句型规范句型2022/12/2163二义性l问题：一个句型是否对应唯一的一棵语问题：一个句型是否对应唯一的一棵语法树？法树？l例：例：GE:GE:E iE iE E+EE E+EE E*EE E*EE (E)E (E)E E E+E E+E E*E i E*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 i*i+E i*i+i2022/12/2164l若一个文法存在某个句子对应两棵不同的语法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是树，则称这个文法是二义二义的。的。或者，若一个文法存在某个句子有两个不同的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。最左（右）推导，则称这个文法是二义的。l文法的二义性和语言的二义性是两个不同的概文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法念。因为可能有两个不同的文法G和和G，其中，其中G是二义的，但是却有是二义的，但是却有L(G)=L(G)，也就是说，也就是说，这两个文法所产生的语言是相同的。这两个文法所产生的语言是相同的。l产生某上下文无关语言的每一个文法都是二义产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。的，则称此语言是先天二义的。2022/12/2165注：注：l二义性会给语法分析带来不确定性二义性会给语法分析带来不确定性l文法的二义性是不可判定的，即不存在算法，文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为能够在有限步数内确切判定一个文法是否为二义文法二义文法l若要证明是二义性，只要举出一例若要证明是二义性，只要举出一例2022/12/2166l若能控制文法的二义性，即加入人为的附加若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事条件，则二义文法的存在并非坏事l二义文法改造为无二义文法二义文法改造为无二义文法GE:E i GE：E T|E+T E E+E T F|T*F E E*E F (E)|i E (E)规定优先顺序和结合律规定优先顺序和结合律2022/12/21673.6 句型的分析句型的分析l句型分析句型分析 就是识别一个符号串是否为某文法就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。的句型，是某个推导的构造过程。l在语言的编译实现中，把完成句型分析的程序在语言的编译实现中，把完成句型分析的程序称为称为分析程序分析程序或或识别程序识别程序。分析算法又称。分析算法又称识别识别算法算法。l从左到右的分析算法从左到右的分析算法，即总是从左到右地识别，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。进而依次识别右边的一个符号。2022/12/2168l分析算法可分为：分析算法可分为：l自上而下分析法自上而下分析法：从文法的开始符号出发，反复使用各种产从文法的开始符号出发，反复使用各种产生式，寻找与输入符号生式，寻找与输入符号匹配匹配的推导。的推导。l自下而上分析法自下而上分析法：从输入符号串开始，逐步进行从输入符号串开始，逐步进行归约归约，直至，直至归约到文法的开始符号。归约到文法的开始符号。l两种方法反映了两种不同的语法树的构造两种方法反映了两种不同的语法树的构造过程过程2022/12/2169自上而下的语法分析自上而下的语法分析l例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的句子是否该文法的句子SSScAdcAd a b推导过程：推导过程：S cAd cabd2022/12/2170自下而上的语法分析自下而上的语法分析l例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的句子是否该文法的句子SAA c a b d c a b d c a b d 归约过程：归约过程：S cAd cabd2022/12/2171句型分析的有关问题句型分析的有关问题1）如何选择使用哪个产生式进行推导？）如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是V，且有，且有n条规则：条规则：VA1|A2|An，那么如何确定，那么如何确定用哪个右部去替代用哪个右部去替代V？2）如何识别可归约的串？）如何识别可归约的串？在自下而上的分析方法中，在分析程序工在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串串，将它归约到某个非终结符号，该子串称为称为“可归约串可归约串”2022/12/2172句型分析句型分析l短语、直接短语、句柄的定义：短语、直接短语、句柄的定义：l令令G是一文法，是一文法，S是文法的开始符号，是文法的开始符号，是文法是文法G的一个句型。如果有：的一个句型。如果有：S A 且且A 则称则称 是句型是句型相对于非终结符相对于非终结符A的的短语短语。若有。若有A 则称则称 是句型是句型相对于该相对于该规则规则A 的的直接短语（简单短语）直接短语（简单短语）。一。一个句型的最左直接短语称为该句型的个句型的最左直接短语称为该句型的句柄句柄。2022/12/2173子树与短语、句柄子树与短语、句柄l子树：在一棵语法树中，由某一结点及子树：在一棵语法树中，由某一结点及其所有分支组成的部分称为原树的一棵其所有分支组成的部分称为原树的一棵子树。子树。l一棵子树的所有叶子自左至右排列起来一棵子树的所有叶子自左至右排列起来形成一个相对子树根的短语。（如上例）形成一个相对子树根的短语。（如上例）l一个句型的句柄是这个句型的分析树中一个句型的句柄是这个句型的分析树中最左那棵只有父子两代的子树的所有叶最左那棵只有父子两代的子树的所有叶子的自左至右排列。子的自左至右排列。2022/12/2174句型分析句型分析 E E T T F F i1 *i2 +i3短语：短语：直接短语：直接短语：句柄：句柄：GE：EE+T|T TT*F|F F(E)|i句型：句型：i1*i2+i3TFi1*i2+i3，i1*i2，i1，i2，i3i1，i2，i3i12022/12/2175例：设文法例：设文法GS：S aAS|a A SbA|SS|ba则则aabbaa是该文法的一个句子，求此句子的短语是该文法的一个句子，求此句子的短语和句柄和句柄短语：短语：1、a1a2b1b2a3a42、a2b1b2a33、a44、a25、b2a3句柄：句柄：a2S1a1A1S2S3b1A2a4a2b2a32022/12/21763.7 有关文法实用中的一些说明有关文法实用中的一些说明l有关文法的实用限制有关文法的实用限制l上下文无关文法中的上下文无关文法中的 规则规则2022/12/21773.7.1 有关文法的实用限制有关文法的实用限制l文法中不得含有文法中不得含有有害规则有害规则和和多余规则多余规则有害规则：形如有害规则：形如UU的产生式。会引起文法的产生式。会引起文法的二义性的二义性多余规则：指文法中任何句子的推导都不会用多余规则：指文法中任何句子的推导都不会用到的规则到的规则l1）文法中某些非终结符不在任何规则的右部出现，）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达该非终结符称为不可到达l2）文法中某些非终结符，由它不能推出终结符号）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的串来，称为不可终止的l文法简化的步骤文法简化的步骤查找有无形如查找有无形如PP的产生式，若有则删除的产生式，若有则删除若某个产生式在推导过程中永远不会被用到，若某个产生式在推导过程中永远不会被用到，删除它删除它若某个产生式在推导过程中不能从中导出终若某个产生式在推导过程中不能从中导出终结符，删除它结符，删除它最后，整理所有剩余产生式，就得到简化的最后，整理所有剩余产生式，就得到简化的文法文法2022/12/2179化简文法化简文法例：例：GS 0)SBe*1)SEc 2)AAe 3)Ae*4)AA*5)BCe 6)BAf *7)CCf（不可终止的）（不可终止的）*8)Df（不可到达的（不可到达的）(0)SBe(1)BAf(2)AAe(3)Ae2022/12/2180l对于文法对于文法GS，为了保证任一非终结符，为了保证任一非终结符A在在句子推导中出现，必须满足如下两个条件：句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。必须在某句型中出现。2）必须能从必须能从A推出终结符号串推出终结符号串t来。来。l即即1）文法）文法GS，对某两个符号串，对某两个符号串 和和：S A 2）A t，tVT*2022/12/21813.7.2 上下文无关文法中的上下文无关文法中的 规则规则l具有形式具有形式A 的规则称为的规则称为 规则，其中规则，其中AVNl某些著作和讲义中限制这种规则的出现。某些著作和讲义中限制这种规则的出现。因为因为 规则会使有关文法的一些讨论和证规则会使有关文法的一些讨论和证明变得复杂明变得复杂复习重点复习重点l文法的概念文法的概念字母表、符号串和集合的概念及运算字母表、符号串和集合的概念及运算 文法的定义（四元组表示）文法的定义（四元组表示）什么推导什么推导 l句型、句子的概念句型、句子的概念l语言的形式定义语言的形式定义l等价文法等价文法l文法的类型文法的类型l最左（右）推导最左（右）推导规范推导规范推导规范句型规范句型规范归约规范归约l二义性二义性l短语、句柄、直接短语短语、句柄、直接短语