文法与语言详解PPT课件

1、第二章第二章 文法与语言文法与语言 讨论问题：讨论问题： 文法和语言的概念和定义文法和语言的概念和定义 文法和语言的分类文法和语言的分类 文法等价变换文法等价变换 句型分析句型分析第1页/共112页简单回顾简单回顾 对程序的理解对程序的理解 程序是计算机执行的一系列指令；程序是计算机执行的一系列指令； 程序是计算任务的程序是计算任务的 处理对象和处理规则的描述。处理对象和处理规则的描述。 对程序设计语言的理解对程序设计语言的理解 程序设计语言是程序的书写规范；程序设计语言是程序的书写规范； 程序设计语言的要素：程序设计语言的要素： 一组一组记号记号(符号符号)和一组和一组规则规则。 程序设计语

2、言程序是程序设计语言程序是 程序设计语言之符号集合上的、程序设计语言之符号集合上的、 按一定规则组成的符号串。按一定规则组成的符号串。第2页/共112页语言是一切句子的集合； 程序设计语言是一切程序的集合； 把程序看做程序设计语言的句子。 程序是( (程序设计）语言的句子 如何系统地构造程序？或者，一般地， 如何为一个( (程序设计) )语言生成句子？ 第3页/共112页2.1 2.1 符号串与符号串集合符号串与符号串集合 语言实际上是一个符号串集合；语言实际上是一个符号串集合； 文法规定语言中句子的构造规则。文法规定语言中句子的构造规则。 句子是一个语言之字母表上按一定规则构造的符号串。句子

3、是一个语言之字母表上按一定规则构造的符号串。 2.1.1 字母表字母表 字母表字母表: 有穷非空的符号集合。有穷非空的符号集合。 例例 A= a, b, c = 0,1 C语言字母表语言字母表= 字母，数字，界限符字母，数字，界限符 不同的语言有不同的字母表。不同的语言有不同的字母表。 字母表上的元素（即符号）组成符号串。字母表上的元素（即符号）组成符号串。第4页/共112页2.1.2 符号串: :1. 符号串及其长度 符号串:由字母表上的符号所组成的有穷序列。 字母表A=a,b,cA=a,b,c上的符号串： a,b,c,ab,ba,aaa,aab,baa,abcab,a,b,c,ab,ba,

4、aaa,aab,baa,abcab,( (空串) ) 注意：顺序是重要的, abba, abba C C语言字母表上的符号串？ 长度：|aabcaca|=7 |=0|aabcaca|=7 |=0第5页/共112页2. 子符号串 若u=xvy ，其中 |v|0 （ |u|=|v|） 则v是u中的子符号串。（非空符号串）例 a+(b-c)/d中的子符号串3. 符号串的头与尾（前缀、后缀） abc的头： a, ab, abc, x=t abc的尾： c, bc, abc, x=t 第6页/共112页4. 对符号串的运算 联结（或并置）： x=ab y=ba xy=abba yx=baab 对任何符号

5、串x， 有 x=x =x。 方幂： xn=xxx (x自身联结n次) xn=xn-1x=xxn-1 x0= x3=(ab)3=ababab |xy|=|x|+|y| |xn|=n |x| |x0|=0第7页/共112页2.1.3 符号串集合（语言）1. 符号串集合的定义1)它是一切元素都是某字母表上的符号串的集合。 2)表示法 枚举法 1，11，111，1111 省略法 1，11，111，1111， 描述法 1i | i1 或x |x全由1组成,|x|1 注意：一定不能涉及含义, 如 x |x=10i 。第8页/共112页 字母表字母表上的一个语言就是上的一个语言就是上的一些符号串组成的集合。

6、上的一些符号串组成的集合。 空集空集 是一个语言，仅含一个空符号串集合是一个语言，仅含一个空符号串集合 也是一个语言。特别需要指出的是，也是一个语言。特别需要指出的是， 和和 是不同的语言。是不同的语言。第9页/共112页2. 对符号串集合的运算 乘积：AB= xy | x A 且 y B 1,0 a,b,c=? 对任何符号串x有 x=x =x，A0= 因此， A=A =A，但A=A=。 方幂： An =AAA (n 个A乘积） An=An-1A=AAn-1 特例，字母表A的方幂 ，xAn, | x |=n 1,03=? 1,0n=?第10页/共112页3. 字母表的闭包与正闭包 闭包 A*

7、*=A0A1An 0，1，2* * 正闭包 A+= A1 An = A*- 0，1，2+ xA+, 则|x|=1 xA* *, 则|x|=0 任何一个语言是其字母表之正闭包的真子集。 如何找出此真子集？或说，如何找出其句子？第11页/共112页2.2 2.2 文法与语言的形式定义文法与语言的形式定义 2.2.1 文法的形式定义1. 重写规则 （产生式规则） 定义： 有序对（U，u) 或 U:=u A A （或（或A:=A:=） 其中，其中，A是一个符号，称为产生式规则的左部，而是一个符号，称为产生式规则的左部，而 是有穷是有穷非空符号串，称为产生式规则的右部，非空符号串，称为产生式规则的右部，

8、“ “ ”和和“:=”表表示示“定义为定义为”或或“由由组合成的组合成的”或或“生成生成”，其含义是，其含义是左部符号用右部的符号串定义或左部符号生成右部符号串。左部符号用右部的符号串定义或左部符号生成右部符号串。产生式规则可合写，如：产生式规则可合写，如： A 和和 A 可写为可写为A | 第12页/共112页1. 重写规则 （产生式规则）规则表示法：通常的 E:=E+T E:=T 或 E:=E+T | T 扩充的 E:=T+T 术语：非终结符号， 非终结符号集VN 终结符号，（不会出现在规则左部） 终结符号集VT （ VN VT= V= VN VT ） 单规则：右部是单个非终结符第13页/

9、共112页 用于指定重复次数 := 05 内中符号至多出现一次 := +|- ( ) 提公因子 E:=E+T|E-T 可改写为 E:=E(+|-)T第14页/共112页15规则构造的例子规则构造的例子C C语言标识符的规则：语言标识符的规则： :=:= := := := := := := A|Z := := a|z := := _ := := 0|9第15页/共112页16用规则产生句子的例子用规则产生句子的例子如：用标识符产生式规则产生句子如：用标识符产生式规则产生句子area. a a ea ea rea rea area 其中，其中，“=”=”为推导。为推导。第16页/共112页2. 文

10、法的定义 文法GZ是非空有穷的重写规则集合，其中Z是识别符号（或称开始符号），G是文法名。例G1E：E:=E+T E:=T T:=T* *F T:=F F:=(E) F:=i G2E：E:=E+T |T T:=T* *F|F F:=(E) F:=i GE：E:=T+T T:=F* *F F:=(E) | i文法的四要素：VN，VT，P，ZP有穷非空的重写规则集，识别符号Z VN第17页/共112页3. 应用文法产生语言的句子 G: 1. :=2. :=3. :=4. :=5. :=Peter 6. :=Berry7. :=river8. :=swims9. :=in第18页/共112页例例 试

11、以文法试以文法G 为例考察如何应用文法为例考察如何应用文法 来生成句子。来生成句子。 替换为替换为句子句子=主语主语 谓语谓语 状语状语 (规则规则1) =名词名词 谓语谓语 状语状语 (规则规则2) =Peter 谓语谓语 状语状语 (规则规则5) =Peter 动词动词 状语状语 (规则规则3) =Peter swims 状语状语 (规则规则8) =Peter swims 介词介词 名词名词 (规则规则4) =Peter swims in 名词名词 (规则规则9) =Peter swims in river (规则规则7)第19页/共112页应用文法生成句子的步骤： 步骤1 1 以识别符号

12、为当前符号串； 步骤2 2 对当前符号串中的一个非终结符号进行替换，把它替换为以此非终结符号为左部的规则之右部符号串，生成新的当前符号串； 步骤3 3 重复步骤2,2,直到当前符号串中不包含非终结符号，最终不包含非终结符号的符号串就是所生成的句子。说明： 每步的当前符号串将称为句型， 最终的终结符号串称为句子。 第20页/共112页 按上述步骤应用各个规则，可生成： Berry swims in riverBerry swims in river 甚至可生成：river swims in Peterriver swims in Peter 表明：语法上的正确性不能保证语义上的正确性。 对当前句

13、型中任一非终结符号进行替换，都将生成新的句型，最终生成句子。但宜用系统的方式进行推导，如，每步对最左的或最右的非终结符号进行替换。这时，分别称为最左推导与最右推导。 引进句子生成中的两个重要概念：推导与归约。第21页/共112页直接推导 ： = xUy = xuy 句子 = 主语 谓语 状语 主语 谓语 状语 = 名词 谓语 状语 名词 谓语 状语 = Peter 谓语 状语 Peter 谓语 状语 = Peter 动词 状语 Peter 动词 状语 = Peter swims 状语 Peter swims 状语 = Peter swims 介词 名词 Peter swims 介词 名词 =

14、Peter swims in 名词 Peter swims in 名词 = Peter swims in river 第22页/共112页直接推导时，给定 v=xUy, 找到规则U:=u， 把u代替U， 得到 w=xuy称v直接推导到w，记为：v = w 或 xUy = xuy第23页/共112页推导（直接推导序列）：=+ = 主语 谓语 状语 = 名词 谓语 状语 = Peter 谓语 状语 = Peter 动词 状语 = Peter swims 状语 = Peter swims 介词 名词 = Peter swims in 名词 = Peter swims in river 推导时，给定符

15、号串v, 找到 v=u1=u2=un-1=w, 得到符号串w,称v推导到w，记为：v =+ w。 一般，从识别符号开始推导，例如， =+ Peter 谓语 状语 =+ Peter swims in river 推导长度：直接推导的步数。第24页/共112页直接推导 : = 直接推导时，给定v=xUy， 在其中找出U，应用规则U:=u, 得到 w=xuy，称v直接推导到w, 或w直接归约到v,记为 v = w 一般，总有： U:=u xUy = xuy推导: =+ 推导时，给定符号串v, 找出直接推导序列： v=u1=u2=un-1=w得到符号串w, 称v推导到w, 或w归约到v,记为: v =

16、+ w n称为推导的长度。 广义推导： =* * 若 v =+ w 或 v=w，则称v广义推导到w, 或广义归约到v。第25页/共112页对照： 直接推导v= w (U:=u v=xUy w=xuy) (推导长度=1) 推导 v=+ w(v=u1=un-1=w) (推导长度 1) 广义推导v=* * w(v=+ w 或 v=w) (推导长度 0)通常考虑的都是从识别符号出发的推导： Z=* * x x (V(VN N V VT T) )+ + 直接归约 ：v= w w直接归约为v 归约 : v=+ w w归约为v 广义归约: v=* * w w广义归约为v 请对照比较推导与归约这两个概念。第2

17、6页/共112页重要概念：句型、句子 句型：Z=* * x, x (VNVT)+ 句子：Z=* * x, x VT+ 例 Peter swims in river注意：句子和在概念上的区别注意：应用文法生成句子仅是形式上的。 例 river swims in Peter注：句子也是句型，但句型不一定是句子。第27页/共112页文法产生句型和句子的例子文法产生句型和句子的例子 【例例】设有文法设有文法GZ: Z:=aZb| 有推导：有推导： Z =* Z =* aZb= aaZbb =* aaabbb 可见，符号串可见，符号串 ，aZb，aaZbb和和aaabbb都是文法都是文法GZ的句型，而的

18、句型，而 和和aaabbb才是文法才是文法GZ的句子。的句子。第28页/共112页29文法产生句型和句子的例子文法产生句型和句子的例子 【例例】设有文法设有文法GE: E := E+T|E-T|T T := T*F|T/F|F F : =(E)|i 试证明试证明i+i*i是它的一个句子。是它的一个句子。 分析：分析：只有证明只有证明i+i*i可由文法可由文法G从开始符号从开始符号E推导出，即推导出，即可证明可证明i+i*i是它的一个句子。是它的一个句子。 证明：证明： E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i 即有即有E E * i+i*i

19、 又因又因i+i*i中的每个符号均为终结符号，故中的每个符号均为终结符号，故i+i*i是它的一是它的一个句子。个句子。 第29页/共112页思考思考 设计编程语言时， 是先设计语言形式，还是先设计BNF形式的文法？ 例如要表示形如 i+i, i+i*i的表达式 建议： 学习时注意积累，何种典型文法可以得到某种典型的语言形式 考试考查：能够由文法写出语言，也能由语言设计出文法考试考查：能够由文法写出语言，也能由语言设计出文法第30页/共112页为什么有穷规则集合的文法能定义无穷的语言？文法GG： 1 1） :=:= 2 2） :=:= 3 3） :=:= 4 4） :=0 5) :=0 5) :

20、=1:=1 6 6） :=2 7) :=2 7) :=3:=3 8) 8) :=4 9) :=4 9) :=5:=5 10) 10) :=6 11) :=6 11) :=7:=7 11) 11) :=8 12) :=8 12) :=9:=9V VN N=,V VT T= 0,1,2,3,4,5,6,7,8,9 = 0,1,2,3,4,5,6,7,8,9 = = = =11=12=12=123=123第31页/共112页 = = = = = = 递归地定义规则，即，U:=U, 使得有穷个规则可能定义潜在地无穷的语言。第32页/共112页重要概念：短语、简单短语 已知w=xuy是文法G的句型, 短

21、语 u: Z=* * xUy UVN U =+ u 简单短语 u: Z=* * xUy UVN U = u 理解：句型w=xuy中 可(直接)归约且 (直接)归约后所得新符号串仍为句型 的子符号串u。例 句子 123 中, 1、2、3都是简单短语。 1、12、123、2、3都是短语。 句型 1122 中： 简单短语有：1 1、2 2 短语有： 11、1 1、 11 、2 2 句柄 : 句型中最左的简单短语。第33页/共112页 句柄是重要概念之一。归约是自底向上的语法分析关键，何时进行归约则必须依赖句柄。 分析句型时，要搞清楚哪些符号串能构成短语和直接短语。第34页/共112页35求短语、直接

22、短语和句柄的例子求短语、直接短语和句柄的例子 【例例】设有文法设有文法GE: 求出句型求出句型(F+i)T*(ET)的短语、简单短语和句柄。的短语、简单短语和句柄。 分析：分析：从句型的推导过程中找出其全部短语、直接从句型的推导过程中找出其全部短语、直接短语和句柄。短语和句柄。 第35页/共112页36 可以看出：可以看出： 句型句型(F+i)T*(ET)包含以下短语：包含以下短语： F，i，F+i，(F+i)，ET，( ET)，T*( ET)，(F+i)T*( ET)；简单短语有简单短语有：F，i， ET；句柄为句柄为F。注意：选择符号串判断是否短语时，必须同时满足注意：选择符号串判断是否短

23、语时，必须同时满足两个条件：两个条件：1）可归约；）可归约； 2）归约后仍是句型（即可由识别符号推导出）归约后仍是句型（即可由识别符号推导出） 第36页/共112页概括概括文法G: 有穷非空的重写规则集合 四要素：VN，VT，P，Z句型：Z=* * t, t (V(VN NVVT T) )+ +句子：Z=* * t, t VVT T+ +概念：推导，归约 简单短语， 短语， 句柄第37页/共112页4. 4. 文法句子之生成的实现文法句子之生成的实现 实质是推导的构造。实质是推导的构造。 要点是推导在计算机内的存储表示要点是推导在计算机内的存储表示。第38页/共112页 文法符号序号 后继符号

24、结点指针其中包含两类结点，一类结点结构形如：另一类结点结构形如：这易于用C C语言结构类型实现，例如，对第一类， typedef struct 直接推导链首结点 struct 符号结点 *句型首符号结点指针； struct 直接推导链首结点 *下一直接推导链头指针；直接推导链首结点类型； 句型首符号结点指针 下一直接推导链头指针第39页/共112页 显然每一显然每一“列列”（垂直链）中各结点相应的符号组（垂直链）中各结点相应的符号组成一个句型。成一个句型。 这易于用这易于用C C语言结构类型实现。以最左推导的建立语言结构类型实现。以最左推导的建立为例，程序控制流程示意图如下。为例，程序控制流程

25、示意图如下。第40页/共112页 建立最左推导 置初值 把识别符号置为当前句型, 建立一“列”结点 当前句型中包含 N 非终结符号 Y 复制当前句型一“列”结点， 把所复制的作为当前句型，并 建立与原有当前句型的链接 取到当前句型的最左非终 结符号U相应的结点 以U为左部的 Y 规则仅一个 N 显示以U为左部的各规则 用户选择一个规则， k=规则序号 关于规则k的右部生成结 点链，代替U相应的结点出口k=规则序号第41页/共112页 由于推导过程中，进行替换的非终结符号可能作为多个规则的左部，在尚未讨论分析技术的情况下，宜于采用交互方式由用户自己选择进行直接推导的规则。这涉及到文法规则在计算机

26、内的存放。 文法的存储表示： 一种是数组表示 一种是链表表示 例 GE： E:=E+T E:=T T:=T* *F T:=F F:=(E) F:=i第42页/共112页 数组表示： 左部 右部符号串 右部长度C语言数据结构定义：typedef struct 符号 左部符号； 符号 右部符号串MaxRightPartLength+1; int 右部长度； 规则;规则 文法MaxRuleNum+1;其中， typedef char 符号MaxLength+1； 符号 非终结符号集MaxVnNum+1; 符号 终结符号集MaxVtNum+1; 第43页/共112页为便于处理，以符号的序号代替符号本身

27、：typedef struct int 左部符号序号； int 右部符号串MaxRightPartLength+1; int 右部长度； 规则;规则 文法MaxRuleNum+1;为区分非终结符与终结符，将非终结符的序号+100第44页/共112页文法1中的规则E:=E+T, ,在计算机内的存储表示: : 文法1： 101， 0，101， 1， 102 ， 3 文法2中的规则E:=T，在计算机内的存储表示： 文法2： 101， 0，102 ， 1 TVT：T在VT中的序号 UVN：U在VN中的序号+100 注意：C语言数组元素的下标值从0开始，已把0号 元素弃之不用。第45页/共112页文法的

28、链式表示：文法的链式表示：第46页/共112页文法文法GEGE的数据结构的数据结构GE：E:=E+T E:=T T:=T*F T:=F F:=(E) F:=i第47页/共112页2.2.2 2.2.2 语言的定义语言的定义程序设计语言L是一切程序P的集合。 P L L + （ =VT ） 语言是相应文法一切句子的集合。 L(GZ)= x | Z=* * x, x VT+ 一个文法确定唯一的语言。反之？ L(G)= P | =* * P, PVT+ 语言可能是有穷的，也可能是无穷的。第48页/共112页重要概念：递归规则递归 规则左递归：U:= U 一般递归： U:= U 规则右递归：U:= U

29、 文法递归 文法左递归: U =+ U 一般递归： U =+ U 文法右递归：U =+ U递归，使有穷多个规则定义的语言可以是无穷的。第49页/共112页C语言中的规则递归和文法递归 规则左递归有： := 规则右递归有： :=! 文法右递归于： := := := if()else 因此， =+ 也可以说，C语言文法递归于 =+ 第50页/共112页为语言构造文法 L1= ai bj ck| i, j, k1 a a a a b b b b c c cc A B C A B C A B C SG1 S: S:=ABC A:=Aa|a B:=Bb|b C:=Cc|c第51页/共112页 a a a

30、 a b b b b c c cc A A A B B S SG1S: S:=Sc|Bc B:=Bb|Ab A:=Aa|a注：同一种语言可设计出不同的文法；注意扩展！注：同一种语言可设计出不同的文法；注意扩展！第52页/共112页L2= ai bi ck| i, k1 aa a b b b c c c A A A S SG2S: S:=Sc|Ac A:=aAb|ab 第53页/共112页L3= ai bi ci| i 1 G3S: S:=abC | aSBC CB:=CD CD:=BD BD:=BC bB:=bb bC:=bc cC:=ccL4= a2i | i 1 G4S: S:=ACaB

31、Ca:=aaC CB:=DB CB:=E aD:=Da AD:=AC aE:=Ea AE:=第54页/共112页55文法产生语言的例子文法产生语言的例子【例例1 1】设有文法设有文法GZ: Z:=aaZbb|ab 求该文法所描述的语言。求该文法所描述的语言。 分析：分析：语言：语言：第55页/共112页56文法产生语言的例子文法产生语言的例子【例例2 2】设有文法设有文法GZ: : 求该文法所描述的语言。求该文法所描述的语言。 分析：分析：由括号组成的终结符号，且左右括号匹配。由括号组成的终结符号，且左右括号匹配。 【例例3 3】设有文法设有文法GZ: 求该文法所描述的语言求该文法所描述的语言

32、。 分析：分析：1后面紧跟的符号必为后面紧跟的符号必为0或为空，即该文法产生或为空，即该文法产生的是不包括两个相邻的是不包括两个相邻1 1的所有的所有0、1串。串。 语言：语言： 第56页/共112页概括概括1. 程序设计语言是一切程序的集合；程序设计语言是一切程序的集合； 程序是在程序设计语言字母表上按一定规则构造的符程序是在程序设计语言字母表上按一定规则构造的符号串；号串； 程序设计语言是其字母表正闭包的真子集。程序设计语言是其字母表正闭包的真子集。2. 文法是重写规则的集合文法是重写规则的集合 文法四要素：文法四要素：VN、VT、P、Z 文法的句型：由识别符号推导所得的符号串。文法的句型

33、：由识别符号推导所得的符号串。 文法的句子：全由终结符号组成的句型。文法的句子：全由终结符号组成的句型。3. 语言是一切句子的集合；语言是一切句子的集合； 文法确定，则语言确定，文法确定，则语言确定， 语言给定，但可为该语言构造若干文法。语言给定，但可为该语言构造若干文法。 递归，使有穷多个规则能定义无穷的语言。递归，使有穷多个规则能定义无穷的语言。第57页/共112页4. 重要概念 句型、句子 推导、归约 短语、简单短语、句柄 递归（规则递归、文法递归）第58页/共112页应用文法生成句子的步骤：应用文法生成句子的步骤： 步骤步骤1 以识别符号为当前句型以识别符号为当前句型 步骤步骤2 对当

34、前句型进行直接推导对当前句型进行直接推导 （ 把其中一个非终结符号替换为以其为左部的规把其中一个非终结符号替换为以其为左部的规 则之右部符号串）则之右部符号串） 步骤步骤3 重复步骤重复步骤2，直到无非终结符号可被替换。，直到无非终结符号可被替换。通常应以系统的有规则的方式进行替换通常应以系统的有规则的方式进行替换 对最左的非终结符号进行替换（最左推导）对最左的非终结符号进行替换（最左推导） 对最右的非终结符号进行替换（最右推导）对最右的非终结符号进行替换（最右推导）第59页/共112页2.3.1 Chomsky文法类和语言类1. Chomsky分类法 对文法四要素概括与抽象。 定义：Chom

35、sky文法G=（VN, VT, P, Z) VN VT P Z文法及例： GS: S:=Sc |Bc B:=Bb |Ab A:=Aa |a第60页/共112页2.3 2.3 语言的分类语言的分类2.3.1 Chomsky文法类和语言类1. Chomsky分类法 对文法四要素概括与抽象。 定义：Chomsky文法G=（VN, VT, P, Z) VN VT P Z文法及例： GS: S:=Sc |Bc B:=Bb |Ab A:=Aa |a第61页/共112页G1=（VN, VT, P1, S1) VN=S1, A, B VT=a, b, c P1: S1:=S1c|Bc B :=Bb |Ab A

36、 :=Aa |a L(G1)=ai bj ck|i, j, k1G2=（S2, A, a, b, c, P2, S2) P2: S2:=S2c |Ac A :=aAb|ab L(G2)=ai bi ck|i, k1第62页/共112页G3=(S3, B, C, D, a, b, c, P3, S3 ) P3: S3 :=abC | aS3BC CB:=CD CD:=BD BD:=BC bB:=bb bC:=bc cC:=cc L(G3)=ai bi ci|i1G4=(S4, A, B, C, D, E, a, P4, S4) P4 : S4 :=ACaB Ca:=aaC CB:=DB CB:=

37、E aD:=Da AD:=AC aE:=Ea AE:= L(G4)= a2i | i 1 第63页/共112页分类：按规则的定义形式对文法分类 0型文法（短语结构文法PSG）： u:=v u (VNVT)+, v (VNVT)* * 1型文法（上下文有关文法CSG）： xUy:=xuy UVN, x, y(VNVT)* *, u(VNVT)+ 2型文法（上下文无关文法CFG）： U:=xuy UVN, x, y(VNVT)* *, u(VNVT)+ 3型文法（正则文法RG）： U:=VT 或 U:=T U, VVN, TVT第64页/共112页相应地有4类Chomsky语言： 0型语言（短语结

38、构语言PSL） 1型语言（上下文有关语言CSL） 2型语言（上下文无关语言CFL） 3型语言（正则语言RL）注意： 有时对2型文法，扩充有规则与句子 规则 ： U := 句子 ： Z =* * 第65页/共112页2.3.2* * 形式语言与自动机 Chomsky语言类和自动机的对应关系： 3型语言 有穷状态自动机 FA 2型语言 下推自动机 PDA 1型语言 线性界限自动机LBA 0型语言 图灵机TM 第66页/共112页2.3.3 形式语言的分类与程序设计语言 1. 程序设计语言一般用上下文无关文法定义 ： U:=u 2. 但语言一般是上下文有关的 (1) := := goto :=got

39、o :=: (标识符由所在上下文确定是否标号) (2) ( ) = (标识符由后跟符号确定是函数标识符、数组变量还是变量) 3. 通常：词法 正则文法 语法 上下文无关文法 语义 口语第67页/共112页2.3.4 对上下文无关文法的进一步讨论1* *. 上下文无关文法的自嵌套特性 如果一个上下文无关文法G G中存在具有下列特性的非终结符号U U： U =U =* * xUy xUy其中x, yV+，则称U为自嵌套的非终结符号，包含自嵌套非终结符号的文法G称为自嵌套的上下文无关文法。 若一个上下文无关文法G不是自嵌套的，则L(G)是一个正则语言。 对任何一个正则语言，必定可构造不是自嵌套的文法

40、。一个严格的上下文无关语言，必不能构造非自嵌套的文法。自嵌套特性把正则语言与严格的上下文无关语言区别开来。 第68页/共112页2. 与推导有关的特性 对于CFG，若存在句型x=x1x2xn,有 x1x2xn=* * y, 则必存在y1, y2, , yn，使得 xi =* * yi (i=1,2,n), Z 且 y=y1y2yn。 设x=* * y, 若x的首符号VT, X1 X2 Xn 则y的首符号也VT 。 反之，y的首符号VN, 则 y1 y2 yn x的首符号也VN 。 第69页/共112页3. 规则 规则 ： U:= Chomsky 2型文法U:=u中，uVT+, 不包含规则，但有

41、时让uVT* *, 例如进行文法等价变换，便引进规则 。 引进规则 ，便可能产生句子： Z=* * 对于所有非0型的语言，包括上下文无关语言，删去或添加一个句子，不改变原来的语言类。第70页/共112页4* *. 上下文无关语言的可判定性 对于一个程序设计语言来说，重要的是能机械且高效地在有限的时间内判定一个符号串是否是语法上正确的程序，换句话说，就是判定一个符号串是否是属于该( (程序设计) )语言的句子。这就是可判定性问题。 一般地，可判定性问题可以这样描述： 设集合L L是集合S S的一个子集，而x x是S S的一个任意元素, , 问: :是否可能机械而高效地判定x x是否L L的一个成

42、员? ? 对于上下文无关语言，这问题的答案是肯定的。 第71页/共112页2.4 文法等价和等价变换文法等价和等价变换2.4.1 文法等价的概念文法等价的概念 文法文法G1与与G2等价，若等价，若L(G1)=L(G2)。1. 例例 L1= ai bj ck| i, j, k1 G1 S: S:=ABC A:=Aa|a B:=Bb|b C:=Cc|c G1S: S:=Sc|Bc B:=Bb|Ab A:=Aa|a G1与与G1等价。等价。第72页/共112页2. 文法等价变换的必要性 文法等价变换的概念：对文法进行变换，使得变换后的文法满足某种要求，并且与原文法等价，这种变换称为文法的等价变换。

43、文法等价变换的必要性 使文法类与语言类一致 消去二义性 使文法适用于某种分析技术 特殊需要 文法等价变换的种类： 压缩文法等价变换 消去左递归文法等价变换 消除单规则文法等价变换 增广文法等价变换 第73页/共112页2.4.2 压缩文法等价变换1. 压缩了的文法 目的： 使文法中任一规则都能用来生成文法的句子，使文法中无多余规则。 多余规则：U:=U形规则 不满足下列条件的规则:=u ： 条件=* * U (U出现在句型中） 条件 u=* * t tVT+ (可推导到终结符号串） 概念：若文法中任一规则都满足上述条件和条件2 2, 则称压缩了的文法。 Z=* * xUy = xuy =* *

44、 t t VT+, 即，t是句子。第74页/共112页75文法压缩（化简文法压缩（化简 ）的基本思想）的基本思想条件条件1 1） 若一符号不能出现在文法的任何句型中，则该符号是无用的若一符号不能出现在文法的任何句型中，则该符号是无用的。 条件条件2 2） 若一个非终结符不能推导出终结符号串，则该非终结符是无用的。若一个非终结符不能推导出终结符号串，则该非终结符是无用的。 从识别符号开始或从终结符号开始。从识别符号开始或从终结符号开始。删除这些规则，不会改变文法描述的语言删除这些规则，不会改变文法描述的语言第75页/共112页2.无用规则的判别算法算法步骤如下: 步骤 规则展开成非缩写形式并删除

45、U:=U形规则; 步骤 判别条件，删除不满足条件的规则; 步骤 判别条件，删除不满足条件的规则; 步骤 重复步骤和步骤，直到无规则被删除。 实现：采用加标记的算法。 第76页/共112页采用加标记的算法。 对条件1： U:=xVy中，若规则左部U加过标记，则对右部非终结符号V加标记。 对条件2： U:=xVy, 若规则右部全由终结符号和加过标记的非终结符号组成, 则对左部非终结符号加标记。 对于文法GZ： Z =Be A =AeAe B =CeAf C =Cf D =f 步骤1 展开并删除U:=U形规则成： Z =Be A =Ae A =e B =Ce B =Af C =Cf D =f第77页

46、/共112页 步骤2 判条件1，加标记： * * * * * * * * * * * * * * Z =Be A =Ae A =e B =Ce * * * * * * * * B =Af C =Cf D =f规则D =f 是多余的, 应删除。从而得到文法 GZ： Z =Be A =Ae A =e B =Ce B =Af C =Cf第78页/共112页 步骤3 判条件2，加标记： * * * * * * * * * * Z =Be A =Ae A =e * * * * B =Ce B =Af C =Cf 规则B =Ce与C =Cf是多余的，应删除。 重复判条件1与2，最终得到与文法GZ等价的压缩

47、了的文法GZ: Z =Be A =Ae A =e B =Af第79页/共112页 压缩文法等价变换的规范步骤：步骤 规则展开成非缩写形式并删除U:=U形规则;步骤 判别条件，删除不满足条件的规则;步骤 判别条件，删除不满足条件的规则;步骤 重复步骤和步骤，直到无规则被删除。3.* * 实现之考虑第80页/共112页2.4.32.4.3消去左递归的文法等价变换 左递归的存在将导致自顶向下语法分析失败 自顶向下：即从识别符号出发，使用不同规则进行推导。 左递归可使分析陷入无穷循环，导致栈溢出 U=Ux=Uxx=Uxxx= 因此，对自顶向下分析技术，需要消除左递归。第81页/共112页2.4.3 消

48、去左递归的文法等价变换1. 规则左递归的消去 (U:=Ux|y) U=Ux=Uxx=Uxxx=yxxxx例 GE：E:=E+T|T U T:=T* *F|F F:=(E)|i E=E+T=E+T+T= U =T+T+T+T+T Ua. 改成右递归 T+T+T+T+T U:=Ux| y U:=yU U:= xU | E 例 E:=TE E:=+TE| E E T:=FT T:= * *FT| E第82页/共112页一般情况下，U:=Ux1|Ux2|Uxm|y1|y2|yn U:=Ux1|Ux2|Uxm|y1|y2|yn U:=U(x1|x2|xm) |(y1|y2|yn) U :=(y1|y2|

49、ym) U U:=(x1|x2|xn) U | b. 用扩充表示法 U:=Ux| y U:=y x 一般情况下， U:=Ux1|Ux2|Uxn|y1|y2|ym U:=U(x1|x2|xn) |(y1|y2|ym) U:=(y1|y2|ym) x1|x2|xn第83页/共112页2. 文法左递归的消去 （间接的规则左递归） 基本思想:对非终结符号排序成U1、U2、Un后文法等价变换成呈下形: U1:=Ui1 (或 U1:=T) i11 U2:=Ui2 (或 U2:=T) i22 Uj:=Uij (或 Uj:=T) ijj Un-1:=Un (或 Un-1:=T) Un:=T TVVT T一般地

50、，对于Ui:=Uj必有：ji, 从而不可能产生U =+ UU-Ua文法左递归第84页/共112页 消去文法左递归的算法步骤: 步骤 把非终结符号排序成U1,U2,Un 步骤 以上列顺序执行下列程序： for (i=1; i=n; i+) for (j=1; j=i-1; j+) 把形如Ui:=Ujr的规则改写成: Ui:=xj1r|xj2r|xjkr 其中Uj:=xj1|xj2|xjk是对于Uj的一切规则 消除关于Ui的规则左递归; 第85页/共112页消去文法左递归等价变换的解题规范：步骤1 识别是规则左递归还是文法左递归步骤2 进行相应的文法等价变换步骤3 给出消去了左递归的等价文法第86

51、页/共112页例 设有文法GS： GS： S =SaTbcTd T =Segh 试消去其文法左递归。第87页/共112页 GS： S =SaTbcTd T =Segh解: 步骤1 排序：U1=S U2=T (n=2) 步骤2 执行循环： i=1，j=1：ji1，不执行关于j的循环，消去关于U1=S的规则左递归（改写成右递归）： S =(Tbc|Td)S S =aS| i=2，j=1：有规则T =Se|gh，呈U2:=U1形，把S =(Tbc|Td)S 代入，得 T =(Tbc|Td)Se|gh因此, T =T(bc|d)Se)|gh 消去关于U2=T的规则左递归如下: T =ghT T =(b

52、c|d)SeT |第88页/共112页最后得到文法GS： GS： S =SaTbcTd T =Segh消去了左递归的等价文法GS： S =T (bcd) S S =aS | T =ghT T =(bc|d) SeT |第89页/共112页例 设有文法GA： GA: A =Ba|Cb|c B =dA|Ae|f C =Bg|Ah试消去该文法的左递归。第90页/共112页 GA: A =Ba|Cb|c B =dA|Ae|f C =Bg|Ah解：首先判别知，该文法存在文法左递归。 步骤1 排序成：U1=A，U2=B, U3=C； 步骤2 执行循环： i=1, j=1: ji1，不执行关于j的循环，且关

53、于U1=A不存在规则左递归。 i=2, j=1: 有规则B =Ae|dA|f，呈U2:=U1形，把规则A =Ba|Cb|c代入，得 B =(Ba|Cb|c) e| dA| f或 B =BaeCbecedAf消去关于U2= B的规则左递归，所以, B =(Cbe|ce|dA|f)B B:=ae B| 第91页/共112页 i=3, j=1: 有规则C:=Ah|Bg ，呈U3:=U1形，把规则A:=Ba|Cb|c 代入, C:=(Ba|Cb|c)h|Bg或 C:=B(ah|g)|(Cb|c)h i=3, j=2: 由规则C =B (ah|g) | (Cb|c)h,呈U3:=U2形，把规则B = (

54、Cbe|ce|dA|f)B 代入，得 C:=(Cbe|ce|dA|f)B(ah|g)|(Cb|c)h或 C:=C(beB(ah|g)|bh) | (ce|dA|f)B(ah|g)|ch消去关于U3=C的规则左递归，得到 C =(ce|dA|f) B(ah|g)|ch) C| C:= (beB(ah|g)|bh) C |第92页/共112页最后得到消去了左递归的等价文法 GA: A =BaCbc B =(Cbe|ce|dA|f)B B:=ae B| C =(ce|dA|f) B(ah|g)|ch) C| C:= (beB(ah|g)|bh) C |3.* * 实现之考虑 要点: : 识别文法是规

55、则左递归还是文法左递归 文法在计算机内的存储表示第93页/共112页2.5 语法分析树与句型分析语法分析树与句型分析 2.5.1 语法分析树的概念语法分析树的概念1. 语法分析树的引进语法分析树的引进 术语：术语： 结点结点 根结点根结点 末端结点末端结点 边边 分支分支 分支名字结点分支名字结点 分支结点分支结点 Berry swims in river 分支结点符号串分支结点符号串 子树子树 子树末端结点符号串子树末端结点符号串 树树 末端结点符号串末端结点符号串第94页/共112页语法分析树语法分析树 一个句型推导过程的树形表示称为语法分析树，或简称一个句型推导过程的树形表示称为语法分析

56、树，或简称语法树语法树。语法树的优点是：它有助于理解一。语法树的优点是：它有助于理解一个句子语法结构的层次。个句子语法结构的层次。 语法树通常表示成一棵倒立的树，根在上，树叶在下。语法树通常表示成一棵倒立的树，根在上，树叶在下。 语法树离不开句型，一棵语法树是相对于某个句型而存在，脱离句型的语法树是不存在的。语法树离不开句型，一棵语法树是相对于某个句型而存在，脱离句型的语法树是不存在的。第95页/共112页句子 Berry swins in river的推导：= = = Berry = Berry swins = Berry swins = Berry swins in = Berry swi

57、ns in river如何为它构造语法分析树？第96页/共112页2. 从推导构造语法分析树 从推导构造语法分析树的步骤如下. 步骤1 以识别符号为根结点，对应于第一个直接推导向下作分支。 步骤2 从第二个直接推导左边被替换的非终结符号相应的结点向下作分支, 对应于此直接推导。 步骤3 类似地对应于每个直接推导, 从左边被替换的非终结符号对应的结点向下作分支, 相应于此直接推导。如此继续，直到推导完。第97页/共112页重要性质： 分支的分支结点符号串是相应句型中相对于分支名字结点的简单短语。 Z=* * xUy = xuy U=u 子树的末端结点符号串是相应句型中相对于子树根结点的短语。 Z=* * xUy =+ xuy U=+ u利用语法分析树寻找句型中的简单短语和短语。第98页/共112页3. 从语法分析树构造推导 这是从推导构造语法分析树的逆过程。 E F* *i+i=i* *i+i T* *i+i=F* *i+i=i* *i+i E + T T* *F+i=T* *i+i=F* *i+i=i* *i+i T F E=E+T=T+T=T* *F+T =F*F+T=i* *F+T T * F i =i* *i+T=i* *i+F=i* *i+i F i 对照： 从推导构造语法分析树： i 不断添加分支的过程 从语法分析树构造推导： 不断剪去分支的过程第