第二章文法和语言.ppt

《第二章文法和语言.ppt》由会员分享，可在线阅读，更多相关《第二章文法和语言.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 文法和语言,2.1文法的基本概念 符号和符号串 文法和语言的形式定义 推导与递归 文法的分类2.2句型的分析 语法树 文法的约定 句型的分析方法,主要内容,本章讨论与编译实现相关的形式语言理论基本概念，主要内容有：文法与语言的形式定义Chomsky文法及其分类上下文无关文法的主要特性文法的等价变换句型分析的概念,文法与语言,一个程序设计语言的确切定义是构造编译程序的重要前提。文法被用来精确而无歧义地描述语言的构成方式.文法描述语言的时候不考虑语言的含义。,2.1 语言和文法的直观概念,程序设计语言的定义语言是一个记号系统。汉语-符合汉语语法的句子的全体英语-符合英语语法的句子的全体程序

2、设计语言-该语言的程序的全体程序设计语言由语法和语义定义： 语法：定义每个程序构成的规则 语义：定义每个程序的意义,程序设计语言包括:语法和语义语法(syntax)定义: 是一组规则，用它可以形成和产生一个合适的程序描述工具:文法作用: 定义什么样的符号序列是合法的，与符号的含义无关。,语义(semantics)分类:静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的动态语义：表明程序要做什么描述工具: 指称语义,操作语义等作用: 检查类型匹配，变量作用域等,文法的直观概念,如何来描述一种语言？文法是描述语言的语法（形式）结构的形式规则。如果语言是有穷的（只含有有穷多个句子），可以将句子

3、逐一列出来表示如果语言是无穷的，要找出语言的有穷表示。 有两个途经：生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。,例:“我是大学生”是汉语的一个句子,用EBNF来表示汉语句子的构成规则：句子=主语谓语主语=代词名词代词= 我你他名词= 王明大学生工人英语谓语=动词直接宾语动词= 是学习直接宾语=代词名词,由规则推导句子,方法: 用一条规则=的右端符号串代替:=的左端.表示: 用“ = ”表示推导,含义是,使用一条规则,代替

4、=左边的某个符号,产生=右端的符号串.,例如:句子“我是大学生”的推导过程如下：句子 主语谓语 代词谓语 我谓语 我动词直接宾语 我是直接宾语 我是名词 我是大学生,形式语言,Chomsky于1956年提出了一种用来描述语言的数学系统。人们把用一组数学符号和规则来描述语言的方式称为形式描述，而把所用的数学符号和规则称为形式语言。形式语言，只是从语法上研究语言。它是抽象的数学系统，用于模拟程序设计语言的语法，或者是并不很成功地模拟自然语言如英语的语法。形式语言理论是编译理论的重要基础，它主要研究组成符号语言的符号串的集合及它们的表示法、结构与特性。,形式语言和编译理论中的最基本概念符号串和符号串

5、集合,基本定义它们的运算,2.2 符号和符号串,字母表定义:元素的非空有穷集合例：=01 =ab,c元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。,符号串定义:由字母表中的符号组成的任何有穷序列例： 0,00,10是字母表=01上的符号串 a,ab,aaca是=ab，c上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任何符号的符号串称为空串，用表示注意:并不等于空集合 符号串长度: 符号串中含有符号的个数如: |abc|=3| |=0,子符号串,设有非空符号串u=xvy,其中符号串 ，则称v为符号串u的子符号串。,V,例

6、如 符号串x=a+b*(c+d),则 a, a+b*, 与(c+d)等都是x的子符号串，且 其长度分别为|a|=1, |a+b*|=4, |(c+d)|=5,符号串的头与尾,如果z=xy是一个符号串，则x是z的头，而y是z的尾。如果y非空，则x是z的固有头；如果x非空，则y是z的固有尾。,例如：字母表A=a,b,c上的符号串x=abc, 则x的 头：, a, ab, abc, 尾:, c, bc, abc 固有头: , a, ab, 固有尾:, c, bc,符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在 x的符号之后得到的符号串xy例如 x=ST，y=abu ，则 xy

7、=STabu 显然x = x=x符号串的方幂：把符号串a自身连接n次得到的符号串an = aaaa例如 a1=a a2=aa a0=,符号串集合：定义: 若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为:AB =xy|xA且yB，即AB是由A中的串x和B中的串y连接而成的串xy组成的集合。若集合A = ab,cde B = 0,1 则 AB = ab0,ab1,cde0,cde1显然 A = A = A,符号串集合的方幂: 设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0 = A1 = A

8、 , A2 = A AAK = AA.A(k个),集合的闭包闭包集合的闭包 *定义如下： * = 0 1 2 3例：设有字母表=0，1则*=012=,0,1,00,01,10,11,000,即*表示上所有有穷长的串的集合。,正闭包+ = 123称为的正闭包。 + 表示上的除外的所有用穷长串的集合* = 0+ = * = * ,字母表上的一个语言是上符合某种规则的一些符号串的集合 ，是*的一个子集。例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab,1. 集合ab,aabb,aaabbb,anbn,或w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或w|

9、w*且w=an,n1为字母表上的一个语言。是一个语言。即 是一个语言。,小结,1 符号与字母表2 符号串3 符号串的运算4 符号串集合5 集合的闭包6 字母表的闭包,2.3 文法和语言的形式定义,1文法的定义2文法形式上的约定3推导与归约4句型、句子、语言的定义5文法的等价,“我是大学生”是汉语的一个句子,用:=表示的汉语句子的构成规则：句子=主语谓语主语=代词名词代词= 我你他名词= 王明大学生工人英语谓语=动词直接宾语动词= 是学习直接宾语=代词名词,句子“我是大学生”的推导过程如下：从句子出发，反复把规则中的”:=”左边的成分替换成右边的成分。句子 主语谓语 代词谓语 我谓语 我动词直接

10、宾语 我是直接宾语 我是名词 我是大学生,文法介绍,包括四个组成部分：一组终结符号（不能被替换的符号，单词符号）一组非终结符号（能够被替换为终结符号或非终结符号，语法单位）一个开始符号（从这个符号开始替换，最大语法单位-程序）一组产生式（替换规则，把左边的字符串替换为右边的字符串）,关键思路,从文法的开始符号出发，反复使用产生式，对非终结符进行替换（展开），直到整个字符串中不在包含非终结符。这时，得到了这个文法的一个句子（一个程序）这个过程称为推导,1文法的形式定义,产生式（规则）产生式是一个有序对(,)，通常写作 （或:= ）文法定义:文法G(Grammar)定义为四元组（VN，VT，P，S

11、）VN (Nonternimal)：非终结符集VT (Terminal)：终结符集P (Production)：产生式（规则）集合S：开始符号或识别符号,说明:V=VNVT，V称为文法G的字母表P中产生式形如：,其中V+且至少含一个非终结符，V*VN,VT和P是非空有穷集VNVT=S是一个非终结符，且至少要在一条产生式的左部出现非终结符代表一个语言中的语法成分，如，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符是组成程序的具体的符号。,2 文法形式定义上的约定,文法习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号,或用GS表示S是开始符号用尖括号括起的是非终

12、结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，S是开始符号希腊字母代表由终结符号和非终结符号组成的符号串 、左部相同的产生式A,A可以记为A|，其中“|”是“或”的意思，,分别称为侯选式,如：对于文法 G：S0S1 可写成 GS：S0S1 S01 S01例：文法G=(VN,VT,P,S)其中：VN=S，VT=0，1，P=S0S1,S01开始符为S,例：文法G=(VN,VT,P,S)VN =标识符，字母，数字，VT =a,b,c,x,y,z,0,1,9，P=， ， a, , z，0,9 ，S=例如:文法GS： SA|SA|SDAa|b|zD0|1|9,3. 推导(

13、Derivation)与归约(Reduction),直接推导和直接归约： 是文法G的产生式，若有v，w满足：v=,w=, 其中,V* 则称v直接推导出w,也称w直接归约到v,记作 v w直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程,例 文法G： S0S1，S01 有直接推导： S 0S1（ S0S1 ）0S1 00S11（ S0S1 ） 00S11 000S111（ S0S1 ） 000S111 00001111（ S01 ）,推导例题1,文法G1：S-bA, A-aA|a定义了一个什么样的语言？S=bA=baS=bA=baA=baaS=bA

14、=baA=baaA=baaaS=bA=baA=baaL(G1)=ban|n=1 L(G1) = 以b开头后跟一个或多个a的串,推导例题2,e.g. 文法产生的语言,文法G4对句子aaabb的推导：S = A B S A B = a A B A a A = a a A B A a A = a a a B A a = a a a b B B b B = a a a b b B b,A= aB = abA= Ab = ab,e.g. 文法产生的语言,文法G5对句子aaaabbbb的推导：S = a S b S a S b = a a S b b S a S b = a a a S b b b S a

15、 S b = a a a a b b b b S a b,直接推导序列和广义推导,直接推导序列： 或 + 若存在v =u0 u1 . un=w, (n0) 则称v + w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。广义推导： 或 * 若有v + w 或 v=w， 则记为v * w，v广义推导出w，w广义规约到v（可以包含0步推导）,+,*,三种推导的比较,直接推导（）的长度为1直接推导序列（ +）的长度n1广义推导（ *）的长度0,规范推导与规范规约,考虑两种特殊推导：最右推导和最左推导，即 对于一个推导序列中的每一步直接推导，都是对最左（最右）非终结符进行替换。

16、最右推导也称规范推导，它的逆过程称为最左规约，也称规范规约。 .若用表示规约，设Aa是文法G中的一个规则，则对于 xAy xay 有 . xay xAy,举例,例1: 文法GS: SAB AA0|1B B0|S1 请给出句子101001的最左和最右推导。 最左推导： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推导： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001,例2 文法G：EE+T|T TTF|F F（E）|i句子i+ii的推导过程如下：最左推导：E=E+T=T+T=F+T=i+T=i+TF=i+F

17、F =i+iF=i+ii最右推导：E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii,递归规则,借助于自身来定义的规则，称为递归规则。如 := 递归规则的存在，使得能用有穷个规则来定义无穷的语言。如果一个规则形如U:=U（或UxUy），则该规则是递归的； 如果规则形如U:=U （或UUy），则称左递归的； 如果规则形如U:=U （或UxU），则称右递归的。例：:=, （左递归规则） :=! （右递归规则）,文法的递归性,定义：对于某文法，存在UVN， 如果U + U.， 则称该文法递归于U； 如果U + U，则称该文法左递归于U； 如果U + U，则称该文法右

18、递归于U。例1：C语言中： + (文法右递归于)例2： UVx VUy|z （都不递归） 有 U + Uxy，所以该文法是左递归的。注：描述程序设计语言的文法必定都是递归的。,4句型、句子、语言的定义,句型和句子设有文法GS，若符号串是从开始符推导出来的,即 S =* ，则称是文法G的句型。若仅由终结符组成,即 S =* ，且VT*，则称是文法G的句子。例 文法GS： S0S1， S01因为S 0S1 00S11 000S111 00001111所以S,0S1 ,00S11 ,000S111,00001111都是G的句型00001111是G的句子由规范推导所得的句型称为规范句型,语言的定义由文

19、法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x，且 xVT* 例 文法G： S0S1， S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n1文法和语言的关系：文法G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,根据文法，可以通过推导得到该文法相应的语言；例：GE：EE+T|TTTF|FF(E)|aEE+T T+T F+T a+T a+TF a+FF a+aF a+aa表示一切能用符号a，+，(，)构成的算术表达式有了语言的要求，也可以为该语言设计文法例：若语言由0、1符号串组成，串中0和1的个数相同，

20、构造其文法为：A 0B|1CB 1|1A|0BBC 0|0A|1CC,5文法的等价,若L(G1)=L(G2)，则称文法G1和G2是等价的。例如 文法G1A：A0R A01 RA1 G2S：S0S1 S01所定义的语言都是0n1n两文法等价,2.4 文法的类型,Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG） 0型语言或短语结构语言1型文法（CSG） 1型语言或上下文有关语言2型文法（CFG） 2型语言或上下文无关语言3型文法（RG）3型语言或正则（正规）语言,如果对于某文法G，P中每个规则具有下列形式： 其中V+ ， V*，则该文法G为（Chomsky）0型

21、文法或短语结构文法，缩写为PSG。相应的语言称为0型语言或短语结构语言。如文法G，其中VN=A,B,S VT=0,1 P= S0AB 1B0 BSA|01 A1SB1 A0S0B L0(GS)= ,0型文法,1型文法(上下文有关)：它是0型文法的特例，对P中的任一产生式，都|， 仅仅 S除外,但S不得出现在任何产生式的右部。例 文法GS： SaSBE SaBEEBBEaBab bBbb bEbe eEee1型文法产生式的一般形式是 A， , V* ，AVN , V ，它表示当A的上文为且下文为时可把A替换成，因此称1型文法为上下文有关文法。,2型文法（上下文无关文法） ：它是1型文法的特例，对

22、任一产生式，都有VN ， (VNVT)*例 文法GS：SAB ABS|0 BSA|12型文法产生式的一般形式是: A，它表示不管A的上下文如何都可把A替换成，因此被称为上下文无关文法。通常程序设计语言的文法，可用2型文法来描述，因此我们重点研究2型文法。如C，Pascal,3型文法(正规文法)：它是2型文法的特例，任一产生式的形式都为 AaB或Aa，其中A ，BVN ，aVT例如 文法GS：S0A|1B|0A0A|1B|0SB1B|1|0在程序设计语言中，3型文法通常用来描述单词的结构。,四种文法之间的逐级“包含”关系,2.5 上下文无关文法及其语法树,1上下文无关文法(Context-Fre

23、e Grammar)自然语言是上下文有关的。 上下文无关文法有足够的能力描述现今程序设计语言的语法结构例：算术表达式：Ei|E+E|E*E|（E）i:=Eif then | if then else 我们更关心上下文无关文法产生的句子的分析,2.语法树(推导树Parse Tree)作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树,语法树的概念,定义：语法树是这样的一个语法结构，它的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。引入

24、语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。,语法树的相关概念,结点：每个树的结点对应于一个符号。结点的名字就是该符号。边：两个结点之间的连线。根结点：没有边进入的结点。分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）子树：语法树的某个结点和它向下射出的部分末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。,语法树的特征,给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征：1、根结点的标记是开始符号S；2、每个

25、结点的标记都是V中的一个符号；3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2AR，那么 A:=A1A2.AR一定是P中的一条规则；4、若一标记为A的结点至少有一个除它以外的子孙，则AVN5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。,从推导构造语法树,方法：把识别符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。,例如：推导S AB AcBd Accdd abccdd,S,B,B,d,b,a,A,c,d,c,语法树的构造过程,S AB

26、 AcBd Accdd abccdd,S,S,B,A,S,B,B,d,A,c,S,B,B,d,A,c,d,c,S,B,B,d,b,a,A,c,d,c,（1）,（2）,（3）,（5）,（4）,从语法树构造推导,方法：从分支建立直接推导，然后从语法树中剪去之这个分支，直到无分支可剪。语法树表明了在推导过程中使用了哪条规则和使用在哪个非终结符号上，但它并没有表明使用规则的顺序。一棵语法树可能对应不止一种推导。,从语法树构造推导的过程,例如文法GS： S:=AB A:=aAb|ab B:=cBd|cd 存在下面的推导可能：S AB AcBd (4) (3) Accdd abccdd (2) (1)S

27、AB abB abcBd abccdd（从后往前看）,S,B,B,d,b,a,A,c,d,c,(1),(2),(3),(4),例：文法G：EE+T|TTTF|F F（E）|i句型T+TF的推导过程与语法树,E=E+T,E=E+T,=E+TF,=T+TF,=T+T,=T+TF,从语法树中看不出句型中的符号被替代的顺序,从左到右读出叶子结点得到的符号串，为文法的句型。也把该语法树称为该句型的语法树。,文法G：EE+E|EE|（E）|i句子 ii+i 对应的语法树,两个不同的最左推导：推导1：E E+E EE+E iE+E ii+E ii+i推导2：E EE iE iE+E ii+E ii+i,4.

28、文法的二义性(Ambiguity),定义:如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的。二义性文法存在某个句子,它有两个不同的最左（右）推导,文法G1：EE+E| EE|（E）| i,文法G2：ET|E+TTF|TFF(E)| i,为什么要避免文法产生二义性？,二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。,如何消除文法的二义性？(1),方法一：不改变文法中原有的语法规则，仅加进一些语法的非形式规定。如1

29、：对于文法 GE: E i E E+E E E*E E (E) 规定运算符优先顺序和结合律，即*优先于+，+、*服从左结合。 如2：Pascal中二义性的消除是通过约定，如在符合if 语句中，else子句总是属于最近的尚无else子句的那个if语句。,如何消除文法的二义性？(2),方法二：构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。如文法 GE: E i E E+E E E*E E (E) 将运算符的优先顺序和结合规则加到原有文法中，则可构造无二义性的文法 GE: E T|E+T T F|T*F F （E）|i,二义性文法的改造,文法的二义性是不可判定的

30、：注意：文法的二义性性与语言二义性的区别 因为可能有两个不同的文法G1和G2，其中有一个是二义性的，但却有L(G1)=L(G2)。如果产生某上下文无关语言的每个文法都是二义性的，则说明该语言是先天二义性的，即该语言是二义性的。,2.6 句型的分析,任务: 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。它是一种推导或语法树的构造过程。对于一个给定的符号串，试图按照文法的规则构造其对应的推导，或语法树。,从左到右的分析算法，即总是从左到右地识别输入符号串.句型分析算法采用从左到右的分析算法句型的

31、分析算法分类自上而下分析法 (Top-Down parsing)自下而上分析法 (Bottom-Up parsing),2.6.1 自上而下的分析方法,定义:从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。,例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,S,推导过程：,=cabd,S,=cAd,自上而下方法的主要问题对输入串cabd自上而下构造语法树的另一过程,不成功，不成功的原因是选错产生式Aa,自上而下分析的主要问题是选择产

32、生式 :假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？,S,2.6.2 自下而上的分析方法,定义:从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。语法树的构造：从输入符号串开始，以它作为语法树的末端结点符号串，自底向上的构造语法树,例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子,归约过程：,用“|-”表示归约，下划线部分为被归约符号,cabd,|-cAd,|-S,自下而上分析的主要问题对输入串cabd的两种归约过程（1）cabd|-cAd|-S 归约到开始符（2）cabd|-cAbd 不能归约到开

33、始符在自下而上的分析方法中，每一步都是从当前串中选择一个子串加以归约，该子串暂称“可归约串”。如何确定“可归约串”是自下而上分析的主要问题。,为了刻划“可归约串”,引入下面的概念,短语，直接短语和句柄定义:设是文法GS中的一个句型，如果有S=*A且A=+，则称是句型相对于非终结符A的短语特别的如有A=，则称是句型相对于规则A的简单短语。一个句型的最左简单短语称为该句型的句柄(Handle)。句柄就是“可归约串”,用语法树求短语、句柄,短语：（子）树的末端结点形成的符号串是相对于(子)树根的短语。简单短语（直接短语）：简单子树的末端结点形成的符号串是相对于简单子树根的简单短语。句柄：最左简单子树

34、的末端结点形成的符号串是句柄。,例：对于文法GS：S:=AB A:=Aa|bB B:=a|Sb 求句型baSb的全部短语、直接短语和句柄？,baSb为句型baSb的相对于S的短语；ba为句型baSb的相对于A的短语；a为句型baSb的相对于B的短语,且为直接短语和句柄；Sb为句型baSb的相对于B的短语,且为直接短语。,例：文法GE: EE+T|T TTF|F F（E）| i 的一个句型是 TF+i，相应的语法树见右图：,. 因为E=* T+i 且 T=TF，所以TF是句型相对于T的短语，且是相对于TTF的直接短语 . 因为E=* TF+F 且 F=i，所以i是句型相对于F的短语，且是相对于F

35、i的直接短语 . 因为E=* E 且E=+ TF+i，所以TF+i是句型相对于E的短语 . TF是最左直接短语，即句柄,文法GE:EE+T|TTTF|FF（E）|i的一个句型 是TF+i,虽然F+i是句型TF+i的一部分，但不是短语，因为尽管有E=+ F+i，但是不存在从文法开始符E=* TE的推导,短语与语法树从句型的语法树上很容易找出句型的短语语法树中每棵子树的末端结点构成相对于子树根的短语 例：文法GE的句型TF+i语法树：,五棵子树对应三个短语T F，i，T F+i,两层子树的末端结点构成直接短语 两棵两层子树对应两个直接短语：TF，i位于最左边的两层子树的末端结点构成句柄：TF,2.

36、7 有关文法实用中的一些说明,有关文法的实用限制有害规则和多余规则,有害规则：UU ,无用且引起文法的二义多余规则：所有句子推导都用不到的规则，表现形式：不可到达：不在任何句型中出现的非终结符的规则，即除了开始符号外，U不出现在该文法的任何其他的规则的右部。不可终止：不可推出终结符号串的非终结符的规则，若在推导中使用该规则，则在也不能推出终结符号串。,例：文法GS：（1）SBe （2）BCe （3）BAf（4）AAe （5）Ae（6）CCf （7）Df 多余规则为： （7）不可到达 （6）不可终止 （2）也是多余的,第2章小结,1 形式语言基础 字母表、符号串、空串、 符号串的长度、连接、（正

37、则）闭包2 文法和语言的定义3 重要概念（规范）推导、（规范）规约、句子、语言、句型、短语、简单短语、句柄4 文法的表示5 文法和语言的分类,句型推导的语法树短语简单短语句柄,文法语言句子,认真看书，理解概念。,作业1：教材P25- 1题目作业2：教材P26- 5题目作业3 ：给出生成下述语言的上下文无关文法： (1) an bn am bm | n，m=0 (2) 1n 0m 1m 0n | n，m=0 ,作业4：设有文法G1 G1：SSaQ Q QQbR R RcSd e1证明句型 QbRae 是规范句型2给出句型 QbRae 的短语，直接短语和句柄。作业5 ：文法GS（1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb（6）bEbe （7）eEee 所定义的语言,