2第二章-文法与语言详解

资源描述

《2第二章-文法与语言详解》由会员分享，可在线阅读，更多相关《2第二章-文法与语言详解（112页珍藏版）》请在金锄头文库上搜索。

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

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

3、号串集合；文法规定语言中句子的构造规则。文法规定语言中句子的构造规则。句子是一个语言之字母表上按一定规则构造的句子是一个语言之字母表上按一定规则构造的符号串。符号串。2.1.12.1.1字母表字母表字母表字母表: :有穷非空的符号集合。有穷非空的符号集合。例例 A=a,b,c=0,1A=a,b,c=0,1CC语言字母表语言字母表=字母，数字，界限符字母，数字，界限符不同的语言有不同的字母表。不同的语言有不同的字母表。字母表上的元素（即符号）组成符号串。字母表上的元素（即符号）组成符号串。符号串符号串: :1. 符号串及其长度符号串及其长度符号串符号串:由字母表上的符号所组成的有穷序列

4、。由字母表上的符号所组成的有穷序列。字母表字母表A=a,b,cA=a,b,c上的符号串：上的符号串： a,b,c,ab,ba,aaa,aab,baa,abcab,a,b,c,ab,ba,aaa,aab,baa,abcab,( (空串空串) ) 注意：顺序是重要的注意：顺序是重要的, abba, abba C C语言字母表上的符号串？语言字母表上的符号串？长度：长度：|aabcaca|=7 |=0|aabcaca|=7 |=02. 子符号串子符号串若若u=xvy ，其中，其中 |v|0 （ |u|=|v|）则则v是是u中的子符号串。（非空符号串）中的子符号串。（非空符号串）例例 a+(b

5、-c)/d中的子符号串中的子符号串3. 符号串的头与尾（前缀、后缀）符号串的头与尾（前缀、后缀） abc的头：的头： a, ab, abc, x=t abc的尾：的尾： c, bc, abc, x=t 4. 对符号串的运算对符号串的运算联结（或并置）联结（或并置）： x=ab y=ba xy=abba yx=baab 对任何符号串对任何符号串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 符号串集合（语言）符号串集合（语言）1

6、. 符号串集合的定义符号串集合的定义1)它是它是一切元素都是某字母表上的符号串的集合。一切元素都是某字母表上的符号串的集合。 2)表示法表示法枚举法枚举法 1，11，111，1111 省略法省略法 1，11，111，1111，描述法描述法 1i | i1 或或x |x全由全由1组成组成,|x|1 注意：一定不能涉及含义注意：一定不能涉及含义, 如如 x |x=10i 。字母表字母表上的一个语言就是上的一个语言就是上的一些上的一些符号串组成的集合。符号串组成的集合。空集空集是一个语言，仅含一个空符是一个语言，仅含一个空符号串集合号串集合也是一个语言。特别需要指也是一个语言。特别需要指

7、出的是，出的是，和和是不同的语言。是不同的语言。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的方幂的方幂，x An, | x |=n 1,03=? 1,0n=?3. 字母表的闭包与正闭包字母表的闭包与正闭包闭包闭包 A* *=A0 A1 An 0，1，2* * 正闭包正闭包 A+= A1 An = A*

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

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

10、终结符号集终结符号集VT （ VN VT= V= VN VT ）单规则：右部是单个非终结符单规则：右部是单个非终结符用于指定重复次数:=05内中符号至多出现一次:=+|-()提公因子E:=E+T|E-T可改写为E:=E(+|-)T16规则构造的例子规则构造的例子C C语言标识符的规则：语言标识符的规则： :=:= := := := := := := A|Z := := a|z := := _ := := 0|917用规则产生句子的例子用规则产生句子的例子如：用标识符产生式规则产生句子如：用标识符产生式规则产生句子area. a a ea ea rea rea area 其中，其中，“=”=

11、”为推导。为推导。2. 文法的定义文法的定义文法文法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 VN3.应用文法产生语言的句子应用文法产生语言的句子 G: 1. :=

12、2. :=3. :=4. :=5. :=Peter 6. :=Berry7. :=river8. :=swims9. :=in例例试以文法试以文法G 为例考察如何应用文法为例考察如何应用文法来生成句子。来生成句子。替换为替换为句子句子=主语主语谓语谓语状语状语 (规则规则1) =名词名词谓语谓语状语状语 (规则规则2) =Peter 谓语谓语状语状语 (规则规则5) =Peter 动词动词状语状语 (规则规则3) =Peter swims 状语状语 (规则规则8) =Peter swims 介词介词名词名词 (规则规则4) =Peter swims in 名词名词 (规则规

13、则9) =Peter swims in river (规则规则7)应用文法生成句子的步骤：应用文法生成句子的步骤：步骤步骤1 1 以识别符号为当前符号串；以识别符号为当前符号串；步骤步骤2 2 对当前符号串中的一个非终结符号进行替换，对当前符号串中的一个非终结符号进行替换，把它替换为以此非终结符号为左部的规则之右部符号串，把它替换为以此非终结符号为左部的规则之右部符号串，生成新的当前符号串；生成新的当前符号串；步骤步骤3 3 重复步骤重复步骤2,2,直到当前符号串中不包含非终结直到当前符号串中不包含非终结符号，最终不包含非终结符号的符号串就是所生成的句符号，最终不包含非终结符号的符号串就

14、是所生成的句子。子。说明：说明：每步的当前符号串将称为句型，每步的当前符号串将称为句型，最终的终结符号串称为句子。最终的终结符号串称为句子。按上述步骤应用各个规则，可生成：按上述步骤应用各个规则，可生成： Berry swims in riverBerry swims in river 甚至可生成：甚至可生成：river swims in Peterriver swims in Peter 表明：语法上的正确性不能保证语义上的正确性。表明：语法上的正确性不能保证语义上的正确性。对当前句型中任一非终结符号进行替换，都将生成对当前句型中任一非终结符号进行替换，都将生成新的句型，最终生成句子

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

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

17、语状语状语 = 名词名词谓语谓语状语状语 = Peter 谓语谓语状语状语 = Peter 动词动词状语状语 = Peter swims 状语状语 = Peter swims 介词介词名词名词 = Peter swims in 名词名词 = Peter swims in river 推导时，给定符号串推导时，给定符号串v, 找到找到 v=u1=u2=un-1=w, 得到符号串得到符号串w,称称v推导到推导到w，记为：，记为：v =+ w。一般，从一般，从识别符号识别符号开始推导，例如，开始推导，例如， =+ Peter 谓语谓语状语状语 =+ Peter swims in ri

18、ver 推导长度：直接推导的步数。推导长度：直接推导的步数。直接推导直接推导 : = 直接推导时，给定直接推导时，给定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 =+ w n称为推导的长度。称为推导的长

19、度。广义推导广义推导： =* * 若若 v =+ w 或或 v=w，则称，则称v广义推导到广义推导到w, 或广义归或广义归约到约到v。对照对照：直接推导直接推导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 归约归约 :

20、 v=+ w w归约为归约为v 广义归约广义归约: v=* * w w广义归约为广义归约为v 请对照比较请对照比较推导推导与与归约归约这两个概念。这两个概念。重要概念重要概念：句型、句子：句型、句子句型句型：Z=* * x, x (VN VT)+ 句子句子：Z=* * x, x VT+ 例例 Peter swims in river注意：注意：句子句子和和在概念上的区别在概念上的区别注意：应用文法生成句子仅是形式上的。注意：应用文法生成句子仅是形式上的。例例 river swims in Peter注：句子也是句型，但句型不一定是句子。注：句子也是句型，但句型不一定是句子。文法产生句型和句

21、子的例子【例例】设有文法设有文法GZ:Z:=aZb|有推导：有推导：Z=*=*Z=*Z=*aZb=aaZbb=*=*aaabbb可见，符号串可见，符号串，aZb，aaZbb和和aaabbb都都是文法是文法GZ的句型，而的句型，而和和aaabbb才是文才是文法法GZ的句子。的句子。30文法产生句型和句子的例子文法产生句型和句子的例子【例例】设有文法设有文法GE:E:=E+T|E-T|TT:=T*F|T/F|FF:=(E)|i试证明试证明i+i*i是它的一个句子。是它的一个句子。分析：分析：只有证明只有证明i+i*i可由文法可由文法G从开始符号从开始符号E推导出，即可证推导出，即可证明明i+i*i

22、是它的一个句子。是它的一个句子。证明：证明：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i 即有即有E E *i+i*i 又因又因i+i*i中的每个符号均为终结符号，故中的每个符号均为终结符号，故i+i*i是它的一个句子。是它的一个句子。思考设计编程语言时，是先设计语言形式，还是先设计BNF形式的文法？例如要表示形如i+i,i+i*i的表达式建议：学习时注意积累，何种典型文法可以得到某种典型的语言形式考试考查：能够由文法写出语言，也能由语言设考试考查：能够由文法写出语言，也能由语言设计出文法计出文法为什么有穷规则集合的文法能定义无穷的语言？为什么有穷规则集合的

23、文法能定义无穷的语言？文法文法GG： 1 1） :=:= 2 2） :=:= 3 3） :=:= 4 4） :=0 5) :=0 5) :=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 = = = = = = 递归地定义规则，即，递归地定义规则

24、，即，U:=U, 使得有穷个规则使得有穷个规则可能定义潜在地无穷的语言。可能定义潜在地无穷的语言。重要概念：短语、简单短语已知w=xuy是文法G的句型, 短语 u: Z=* xUy UVN U =+ u 简单短语 u: Z=* xUy UVN U = u 理解：句型w=xuy中可(直接)归约且 (直接)归约后所得新符号串仍为句型的子符号串u。例句子 123 中, 1、2、3都是简单短语。 1、12、123、2、3都是短语。句型 12 中：简单短语有：1、2 短语有：1、1、1、2 句柄 : 句型中最左的简单短语。句柄是重要概念之一。归约是自底向上的语法分析关键，何时进行归约则必须依

25、赖句柄。分析句型时，要搞清楚哪些符号串能构成短语和直接短语。36求短语、直接短语和句柄的例子求短语、直接短语和句柄的例子【例例】设有文法设有文法GE:求出句型求出句型(F+i)T*(ET)的短语、简单短语和句柄。的短语、简单短语和句柄。分析：分析：从句型的推导过程中找出其全部短语、直接从句型的推导过程中找出其全部短语、直接短语和句柄。短语和句柄。 37 可以看出：可以看出：句型句型(F+i)T*(ET)包含以下短语：包含以下短语：F，i，F+i，(F+i)，ET，(ET)，T*(ET)，(F+i)T*(ET)；简单短语有简单短语有：F，i，ET；句柄为句柄为F。注意：选择符号串判断是否短

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

27、符号序号后继符号结点指针后继符号结点指针其中包含两类结点，一类结点结构形如：其中包含两类结点，一类结点结构形如：另一类结点结构形如：另一类结点结构形如：这易于用这易于用C C语言结构类型实现，例如，对第一类，语言结构类型实现，例如，对第一类， typedefstruct直接推导链首结点直接推导链首结点struct符号结点符号结点*句型首符号结点指针；句型首符号结点指针；struct直接推导链首结点直接推导链首结点 *下一直接推导链头指针；下一直接推导链头指针；直接推导链首结点类型；直接推导链首结点类型；句型首符号结点指针句型首符号结点指针下一直接推导链头指针下一直接推导链头指针显然每一显然

28、每一“列列”（垂直链）中各结点相应的符号组（垂直链）中各结点相应的符号组成一个句型。成一个句型。这这易易于于用用C C语语言言结结构构类类型型实实现现。以以最最左左推推导导的的建建立立为例，程序控制流程示意图如下。为例，程序控制流程示意图如下。建立最左推导建立最左推导置初值置初值把识别符号置为当前句型把识别符号置为当前句型,建立一建立一“列列”结点结点当前句型中包含当前句型中包含N非终结符号非终结符号Y复制当前句型一复制当前句型一“列列”结点，结点，把所复制的作为当前句型，并把所复制的作为当前句型，并建立与原有当前句型的链接建立与原有当前句型的链接取到当前句型的最左非终取到当前句型的最左非终

29、结符号结符号U相应的结点相应的结点以以U为左部的为左部的Y规则仅一个规则仅一个N显示以显示以U为左部的各规则为左部的各规则用户选择一个规则，用户选择一个规则，k=规则序号规则序号关于规则关于规则k的右部生成结的右部生成结点链，代替点链，代替U相应的结点相应的结点出口出口k=规则序号规则序号由于推导过程中，进行替换的非终结符号可能作为由于推导过程中，进行替换的非终结符号可能作为多个规则的左部，在尚未讨论分析技术的情况下，宜于多个规则的左部，在尚未讨论分析技术的情况下，宜于采用交互方式由用户自己选择进行直接推导的规则。这采用交互方式由用户自己选择进行直接推导的规则。这涉及到文法规则在计算机内的存

30、放。涉及到文法规则在计算机内的存放。文法的存储表示：文法的存储表示：一种是数组表示一种是数组表示一种是链表表示一种是链表表示例例GE：E:=E+TE:=TT:=T* *FT:=FF:=(E)F:=i数组表示：数组表示：左部左部右部符号串右部符号串右部长度右部长度C语言数据结构定义：语言数据结构定义：typedefstruct符号符号左部符号；左部符号；符号符号右部符号串右部符号串MaxRightPartLength+1;int右部长度；右部长度；规则规则;规则规则文法文法MaxRuleNum+1;其中，其中，typedefchar符号符号MaxLength+1；符号符号非终结符号

31、集非终结符号集MaxVnNum+1; 符号符号终结符号集终结符号集MaxVtNum+1; 为便于处理，以符号的序号代替符号本身：为便于处理，以符号的序号代替符号本身：typedefstructint左部符号序号；左部符号序号；int右部符号串右部符号串MaxRightPartLength+1;int右部长度；右部长度；规则规则;规则规则文法文法MaxRuleNum+1;为区分非终结符与终结符，将非终结符的序号+100文法文法1中的规则中的规则E:=E+T, ,在计算机内的存储表示在计算机内的存储表示: : 文法文法1：101，0，101，1，102，3文法文法2中的规则中的规则E:=T，在计算

32、机内的存储表示：在计算机内的存储表示：文法文法2：101，0，102，1TVT：T在在VT中的序号中的序号UVN：U在在VN中的序号中的序号+100注意：注意：C语言数组元素的下标值从语言数组元素的下标值从0开始，已把开始，已把0号号元素元素弃之不用。弃之不用。文法的链式表示：文法GE的数据结构GE：E:=E+T E:=T T:=T*F T:=F F:=(E) F:=i2.2.2语言的定义程序设计语言程序设计语言L是一切程序是一切程序P的集合。的集合。 P L L + （ =VT ）语言是相应文法一切句子的集合。语言是相应文法一切句子的集合。 L(GZ)= x | Z=* * x, x V

33、T+ 一个文法确定唯一的语言。反之？一个文法确定唯一的语言。反之？ L(G)= P | =* * P, P VT+ 语言可能是有穷的，也可能是无穷的。语言可能是有穷的，也可能是无穷的。重要概念：递归重要概念：递归规则递归规则递归规则左递归：规则左递归：U:= U 一般递归：一般递归： U:= U 规则右递归：规则右递归：U:= U 文法递归文法递归文法左递归文法左递归: U =+ U 一般递归：一般递归： U =+ U 文法右递归：文法右递归：U =+ U递归，使有穷多个规则定义的语言可以是无穷的。递归，使有穷多个规则定义的语言可以是无穷的。C语言中的规则递归和文法递归语言中的规则递归和文

36、求该文法所描述的语言。求该文法所描述的语言。分析：分析：语言：语言：57文法产生语言的例子文法产生语言的例子【例例2 2】设有文法设有文法GZ: : 求该文法所描述的语言。求该文法所描述的语言。分析：分析：由括号组成的终结符号，且左右括号匹配。由括号组成的终结符号，且左右括号匹配。【例例3 3】设有文法设有文法GZ: 求该文法所描述的语言求该文法所描述的语言。分析：分析：1后面紧跟的符号必为后面紧跟的符号必为0或为空，即该文法产生或为空，即该文法产生的是不包括两个相邻的是不包括两个相邻1 1的所有的所有0、1串。串。语言：语言：概括概括1. 程序设计语言是一切程序的集合；程序设计语

37、言是一切程序的集合；程序是在程序设计语言字母表上按一定规则构造的符程序是在程序设计语言字母表上按一定规则构造的符号串；号串；程序设计语言是其字母表正闭包的真子集。程序设计语言是其字母表正闭包的真子集。2. 文法是重写规则的集合文法是重写规则的集合文法四要素：文法四要素：VN、VT、P、Z 文法的句型：由识别符号推导所得的符号串。文法的句型：由识别符号推导所得的符号串。文法的句子：全由终结符号组成的句型。文法的句子：全由终结符号组成的句型。3. 语言是一切句子的集合；语言是一切句子的集合；文法确定，则语言确定，文法确定，则语言确定，语言给定，但可为该语言构造若干文法。语言给定，但可为

38、该语言构造若干文法。递归，使有穷多个规则能定义无穷的语言。递归，使有穷多个规则能定义无穷的语言。4. 重要概念重要概念句型、句子句型、句子推导、归约推导、归约短语、简单短语、句柄短语、简单短语、句柄递归（规则递归、文法递归）递归（规则递归、文法递归）应用文法生成句子的步骤：应用文法生成句子的步骤：步骤步骤1 以识别符号为当前句型以识别符号为当前句型步骤步骤2 对当前句型进行直接推导对当前句型进行直接推导（把其中一个非终结符号替换为以其为左部的规把其中一个非终结符号替换为以其为左部的规则之右部符号串）则之右部符号串）步骤步骤3 重复步骤重复步骤2，直到无非终结符号可被替换。

39、，直到无非终结符号可被替换。通常应以系统的有规则的方式进行替换通常应以系统的有规则的方式进行替换对最左的非终结符号进行替换（最左推导）对最左的非终结符号进行替换（最左推导）对最右的非终结符号进行替换（最右推导）对最右的非终结符号进行替换（最右推导）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 |a2.3语言的分类2.3.1 Choms

41、b L(G2)=ai bi ck|i, k1G3=(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:=E aD:=Da AD:=AC aE:=Ea AE:= L(G4)= a2i | i 1 分类：按分类：按规则的定义形式规则的定义形式对文法分类对文法分类 0型文法（短语结构文法型文法（短语

42、结构文法PSG）：）： u:=v u (VN VT)+, v (VN VT)* * 1型文法（上下文有关文法型文法（上下文有关文法CSG）：）： xUy:=xuy U VN, x, y (VN VT)* *, u (VN VT)+ 2型文法（型文法（上下文无关文法上下文无关文法CFG）：）： U:=xuy U VN, x, y (VN VT)* *, u (VN VT)+ 3型文法（型文法（正则文法正则文法RG）：）： U:=VT 或或 U:=T U, V VN, T VT 相应地有相应地有4类类Chomsky语言：语言： 0型语言（短语结构语言型语言（短语结构语言PSL） 1型语言（上下文有

43、关语言型语言（上下文有关语言CSL） 2型语言（型语言（上下文无关语言上下文无关语言CFL） 3型语言（型语言（正则语言正则语言RL）注意：注意：有时对有时对2型文法，扩充有型文法，扩充有规则与规则与句子句子规则规则： U := 句子句子： Z =* * * * 形式语言与自动机形式语言与自动机 Chomsky语言类和自动机的对应关系：语言类和自动机的对应关系： 3型语言型语言有穷状态自动机有穷状态自动机 FA 2型语言型语言下推自动机下推自动机 PDA 1型语言型语言线性界限自动机线性界限自动机LBA 0型语言型语言图灵机图灵机TM 2.3.3 形式语言的分类与程序设计语言形

44、式语言的分类与程序设计语言 1. 程序设计语言一般用程序设计语言一般用上下文无关文法上下文无关文法定义定义： U:=u 2. 但语言一般是上下文有关的但语言一般是上下文有关的 (1) := := goto :=goto :=: (标识符由所在上下文确定是否标号标识符由所在上下文确定是否标号) (2) ( ) = (标识符由后跟符号确定是函数标识符、数组变量还是变量标识符由后跟符号确定是函数标识符、数组变量还是变量) 3. 通常：词法通常：词法正则文法正则文法语法语法上下文无关文法上下文无关文法语义语义口语口语2.3.4 对上下文无关文法的进一步讨论对上下文无关文法的进一步讨论1*

45、*. 上下文无关文法的自嵌套特性上下文无关文法的自嵌套特性如如果果一一个个上上下下文文无无关关文文法法G G中中存存在在具具有有下下列列特特性性的的非非终终结符号结符号U U： U =* xUyU =* xUy其中其中x,yV+，则称，则称U为自嵌套的非终结符号，包含自嵌为自嵌套的非终结符号，包含自嵌套非终结符号的文法套非终结符号的文法G称为自嵌套的上下文无关文法。称为自嵌套的上下文无关文法。若一个上下文无关文法若一个上下文无关文法G不是自嵌套的，则不是自嵌套的，则L(G)是是一个正则语言。一个正则语言。对任何一个正则语言，必定可构造不是自嵌套的文对任何一个正则语言，必定可构造不是自嵌套

46、的文法。一个严格的上下文无关语言，必不能构造非自嵌套法。一个严格的上下文无关语言，必不能构造非自嵌套的文法。自嵌套特性把正则语言与严格的上下文无关语的文法。自嵌套特性把正则语言与严格的上下文无关语言区别开来。言区别开来。 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的

47、首符号的首符号VN, 则则 y1 y2 yn x的首符号也的首符号也VN 。 3. 规则规则规则规则： U:= Chomsky 2型文法型文法U:=u中，中，u VT+, 不包含不包含规则，规则，但有时让但有时让u VT* *, 例如进行文法等价变换，便引进例如进行文法等价变换，便引进规则规则。引进引进规则规则，便可能产生，便可能产生句子：句子： Z=* * 对于所有非对于所有非0型的语言，包括上下文无关语言，删型的语言，包括上下文无关语言，删去或添加一个去或添加一个句子，不改变原来的语言类。句子，不改变原来的语言类。4* *. 上下文无关语言的可判定性上下文无关语言的可判定性对对

48、于于一一个个程程序序设设计计语语言言来来说说，重重要要的的是是能能机机械械且且高高效效地地在在有有限限的的时时间间内内判判定定一一个个符符号号串串是是否否是是语语法法上上正正确确的的程程序序，换换句句话话说说，就就是是判判定定一一个个符符号号串串是是否否是是属属于于该该( (程序设计程序设计) )语言的句子。这就是可判定性问题。语言的句子。这就是可判定性问题。一般地，可判定性问题可以这样描述：一般地，可判定性问题可以这样描述：设设集集合合L L是是集集合合S S的的一一个个子子集集，而而x x是是S S的的一一个个任任意意元元素素, , 问问: :是否可能机械而高效地判定是否可能机械而高效

50、行变换，使得变换对文法进行变换，使得变换后的文法满足某种要求，并且与原文法等价，这种变换后的文法满足某种要求，并且与原文法等价，这种变换称为文法的等价变换。称为文法的等价变换。文法等价变换的必要性文法等价变换的必要性使文法类与语言类一致使文法类与语言类一致消去二义性消去二义性使文法适用于某种分析技术使文法适用于某种分析技术特殊需要特殊需要文法等价变换的种类：文法等价变换的种类：压缩文法压缩文法等价变换等价变换消去左递归消去左递归文法等价变换文法等价变换消除单规则文法等价变换消除单规则文法等价变换增广文法等价变换增广文法等价变换 2.4.2 压缩文法等价变换压缩文法等价变换1

51、. 压缩了的文法压缩了的文法目的：目的：使文法中任一规则都能用来生成文法的句子，使文法使文法中任一规则都能用来生成文法的句子，使文法中无多余规则。中无多余规则。多余规则：多余规则：U:=U形规则形规则不满足下列条件的规则不满足下列条件的规则:=u ：条件条件=* * U (U出现在句型中）出现在句型中）条件条件 u=* * t t VT+ (可推导到终结符号串）可推导到终结符号串）概念：若文法中任一规则都满足上述条件和条件概念：若文法中任一规则都满足上述条件和条件2 2, 则称则称压缩了的文法压缩了的文法。 Z=* * xUy = xuy =* * t t VT+, 即，即，t是

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

53、则; 步骤步骤判别条件，删除不满足条件的规则判别条件，删除不满足条件的规则; 步骤步骤判别条件，删除不满足条件的规则判别条件，删除不满足条件的规则; 步骤步骤重复步骤和步骤，直到无规则被删除。重复步骤和步骤，直到无规则被删除。实现：采用实现：采用加标记加标记的算法。的算法。采用采用加标记加标记的算法。的算法。对条件对条件1： U:=xVy中，若中，若规则规则左部左部U加过标记，则加过标记，则对右部非终结符号对右部非终结符号V加标记。加标记。对条件对条件2： U:=xVy, 若规则若规则右部右部全由终结符号全由终结符号和加过标记的非终结符号组成和加过标记的非终结符号组成, 则对左部

54、非终结符号加则对左部非终结符号加标记。标记。对于文法对于文法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 步骤步骤2 判条件判条件1，加标记：，加标记： * * * * * * * * * * * * * * Z =Be A =Ae A =e B =Ce * * * * * * * B =Af C =Cf D =f规则规则D =f 是多余的是多余的, 应删除。从而得到文法应删除。从而得到文法 GZ： Z =Be A =Ae

55、A =e B =Ce B =Af C =Cf 步骤步骤3 判条件判条件2，加标记：，加标记： * * * * * * * * * Z =Be A =Ae A =e * * * * B =Ce B =Af C =Cf 规则规则B =Ce与与C =Cf是多余的，应删除。是多余的，应删除。重复判条件重复判条件1与与2，最终得到与文法，最终得到与文法GZ等价的等价的压缩了的文法压缩了的文法GZ: Z =Be A =Ae A =e B =Af 压缩文法等价变换的规范步骤：压缩文法等价变换的规范步骤：步骤步骤规则展开成非缩写形式并删除规则展开成非缩写形式并删除U:=U形规则形规则;步骤步骤判别条件，

56、删除不满足条件的规则判别条件，删除不满足条件的规则;步骤步骤判别条件，删除不满足条件的规则判别条件，删除不满足条件的规则;步骤步骤重复步骤和步骤，直到无规则被删除。重复步骤和步骤，直到无规则被删除。3.* * 实现之考虑实现之考虑消去左递归的文法等价变换左递归的存在将导致自顶向下语法分析失败自顶向下：即从识别符号出发，使用不同规则进行推导。左递归可使分析陷入无穷循环，导致栈溢出U=Ux=Uxx=Uxxx=U=Ux=Uxx=Uxxx=因此，对自顶向下分析技术，需要消除左递归。2.4.3 消去左递归的文法等价变换消去左递归的文法等价变换1. 规则左递归的消去规则左递归的消去 (U:=Ux|y)

57、 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一般情况下，一般情况下，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|ym) U U:=(x1|x2|xn) U | b. 用扩

58、充表示法用扩充表示法 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|xn2. 文法左递归的消去文法左递归的消去（间接的规则左递归）（间接的规则左递归）基本思想基本思想:对非终结符号排序成对非终结符号排序成U1、U2、Un后文后文法等价变换成呈下形法等价变换成呈下形: U1:=Ui1 (或或 U1:=T) i11 U2:=Ui2 (或或 U2:=T) i22 Uj:=Uij (或或 Uj:=T) ijj Un-1:=Un (或或 Un-1:

59、=T) Un:=T TVVT T一般地，对于一般地，对于Ui:=Uj必有：必有：ji, 从而不可能产生从而不可能产生U =+ UU-Ua文法文法左递归左递归消去文法左递归的算法步骤消去文法左递归的算法步骤: 步骤步骤把非终结符号排序成把非终结符号排序成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的一切规则的一切规则消除关于消除关于U

60、i的规则左递归的规则左递归; 消去文法左递归等价变换的解题规范：消去文法左递归等价变换的解题规范：步骤步骤1 识别是规则左递归还是文法左递归识别是规则左递归还是文法左递归步骤步骤2 进行相应的文法等价变换进行相应的文法等价变换步骤步骤3 给出消去了左递归的等价文法给出消去了左递归的等价文法例设有文法GS： GS： S=SaTbcTd T=Segh 试消去其文法左递归。 GS： S =SaTbcTd T =Segh解解: 步骤步骤1 排序：排序：U1=S U2=T (n=2) 步骤步骤2 执行循环：执行循环： i=1，j=1：ji1，不执行关于，不执行关于j的循环，消去关于的循环，消去关于U1

63、Cb|c代入，得代入，得 B =(Ba|Cb|c) e| dA| f或或 B =BaeCbecedAf消去关于消去关于U2= B的规则左递归，所以的规则左递归，所以, B =(Cbe|ce|dA|f)B B:=ae B| 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 = (Cbe|ce|dA|f)B 代入，得代入，得 C:=(C

64、be|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 |最后得到消去了左递归的等价文法最后得到消去了左递归的等价文法 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.* * 实现之考虑实现之考虑要点要点: : 识别文法

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

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

67、ins in river如何为它构造语法分析树？如何为它构造语法分析树？2. 从推导构造语法分析树从推导构造语法分析树从推导从推导构造语法分析树的步骤如下构造语法分析树的步骤如下. 步骤步骤1 以识别符号为根结点，对应于第一个直接推以识别符号为根结点，对应于第一个直接推导向下作分支。导向下作分支。步骤步骤2 从第二个直接推导左边被替换的非终结符号从第二个直接推导左边被替换的非终结符号相应的结点向下作分支相应的结点向下作分支, 对应于此直接推导。对应于此直接推导。步骤步骤3 类似地对应于每个直接推导类似地对应于每个直接推导, 从左边被替换从左边被替换的非终结符号对应的结点向下作分支的非终结

68、符号对应的结点向下作分支, 相应于此直接推导。相应于此直接推导。如此继续，直到推导完。如此继续，直到推导完。重要性质：重要性质：分支的分支结点符号串分支的分支结点符号串是相应句型中相对于分支是相应句型中相对于分支名字结点的名字结点的简单短语简单短语。 Z=* * xUy = xuy U=u 子树的末端结点符号串子树的末端结点符号串是相应句型中相对于子树是相应句型中相对于子树根结点的根结点的短语短语。 Z=* * xUy =+ xuy U=+ u利用语法分析树寻找利用语法分析树寻找句型句型中的简单短语和短语。中的简单短语和短语。3. 从语法分析树构造推导从语法分析树构造推导这是从推导构造语法

69、分析树的逆过程。这是从推导构造语法分析树的逆过程。 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 不断添加分支的过程不断添加分支的过程从语法分析树构造推导：从语法分析树构造推导：不断剪去分支的过程不断剪去分支的过程4. 二义性二义性概念：一个概念：一个句子句子，若可为

70、它构造两个不同的语法分析，若可为它构造两个不同的语法分析树，称此句子是二义性的句子。树，称此句子是二义性的句子。包含二义性句子的文法称二义性文法。包含二义性句子的文法称二义性文法。例例 GE: E:=E+E|E* *E|(E)|i 存在句子存在句子i+i* *i, 对于它存在两个不同的语法分析树，是对于它存在两个不同的语法分析树，是二义性句子。二义性句子。 E E E * * E E + E E + E i i E * * E i i i i 注意：二义性与多义性的区别。注意：二义性与多义性的区别。对对于于程程序序设设计计语语言言来来说说，重重要要的的是是：描描述述它它的的文文法法应是无二

71、义性的。应是无二义性的。如何知道它是无二义性的？如何知道它是无二义性的？不不存存在在一一种种算算法法，能能在在有有限限步步骤骤内内确确切切判判定定一一个个文文法是否是二义性的。法是否是二义性的。鉴鉴于于二二义义性性不不可可判判定定，所所能能做做的的是是寻寻找找一一组组充充分分条条件件，使使得得满满足足这这些些条条件件的的文文法法必必定定是是无无二二义义性性的的。注注意意，这些条件只是充分条件，未必是无二义性的必要条件。这些条件只是充分条件，未必是无二义性的必要条件。1E2E3+4T5T8T9* *10F6F11F13i7i12i5. 5. 语法分析树的存储表示与输出语法分析树的存储表示与

72、输出从从图图可可见见，语语法法分分析析树树上上任任一一结结点点的的位位置置可可由由其其父父结结点点、紧紧邻邻的的左左兄兄结结点点与与最最右右的的子子结结点点所所确确定定，因因此此，语法分析树的数据结构可设计如下。语法分析树的数据结构可设计如下。typedefstruct语法树结点语法树结点int结点序号结点序号;int文法符号序号文法符号序号;int父结点序号父结点序号;int左兄结点序号左兄结点序号;int右子结点序号；右子结点序号；语法树结点类型语法树结点类型;语法树结点类型语法树结点类型语法分析树语法分析树MaxNodeNum; 当输出语法分析树时，对照上述数据结构，按下列当输出语法

73、分析树时，对照上述数据结构，按下列表列形式输出：表列形式输出：结点序号结点序号文法符号文法符号父结点父结点左兄结点左兄结点右子结点右子结点 1E004 2E1053+120 4T13105T2066F5077i6008T40119*48010F491311F801212i110013i1000 2.5.2 句型分析句型分析 1. 句型分析句型分析的概念的概念句型分析：句型分析：识别一个符号串是否是某文法的句型。识别一个符号串是否是某文法的句型。对于程序设计语言，句子是程序，句型分析的问题对于程序设计语言，句子是程序，句型分析的问题就是识别一个输入符号串是否是语法上正确无误的程序。

74、就是识别一个输入符号串是否是语法上正确无误的程序。分析程序：分析程序：实现句型分析的程序实现句型分析的程序。分析算法：分析程序编写的依据。分析算法：分析程序编写的依据。分析技术：分析技术分析技术：分析技术实现思想决定分析算法。实现思想决定分析算法。 2. 分析技术分析技术自顶向下自顶向下: 实现思想：实现思想：以识别符号作为根结点，以识别符号作为根结点，试图试图向下构造语法分析树向下构造语法分析树,使得末端结点符号串正是输入符号串。使得末端结点符号串正是输入符号串。要解决的基本问题要解决的基本问题: 当按当按U展开展开(推导推导)时，时， U:=x1|x2|xk 确定按哪个确定按哪

75、个xi (1 i k)展开展开: Z =* * vUw= v ? w自底向上自底向上：实现思想：实现思想：以输入符号串作为末端结点符号串以输入符号串作为末端结点符号串, 试图试图向上构造向上构造语法分析树，使得根结点正是识别符号。语法分析树，使得根结点正是识别符号。要解决的基本问题：要解决的基本问题：确定要归约的短语，确定要归约的短语，并确定归约成哪个非终结符号。并确定归约成哪个非终结符号。 Z =* * v ？w= vuw (U1:=u U2:=u Uk:=u)例例 GS： S =AB A =aAbab B =cBdcd识别输入符号串识别输入符号串aabbcd是否是其句子。是否是其

76、句子。1. 自顶向下自顶向下2. 自底向上自底向上自顶向下自顶向下：自顶向下：不断进行直接推导的过程不断进行直接推导的过程。自底向上：自底向上：不断进行直接归约的过程不断进行直接归约的过程。3. 规范推导与规范归约规范推导与规范归约最左推导、最右推导、最左归约、最右归约最左推导、最右推导、最左归约、最右归约不难发现：不难发现：最左推导最左推导= =最右归约最右归约最右推导最右推导= =最左归约最左归约而且最左（右）归约中被直接归约的最左（右）简单短而且最左（右）归约中被直接归约的最左（右）简单短语，其右（左）边总是只包含终结符号。语，其右（左）边总是只包含终结符号。引进规范推导、

77、规范分析引进规范推导、规范分析如如果果某某直直接接推推导导xUy=xuy中中，y不不包包含含非非终终结结符符号号，则称该直接推导为规范的，记作则称该直接推导为规范的，记作 xUyxuy 如如果果某某推推导导v=+w中中，每每个个直直接接推推导导都都是是规规范范的的，则称该推导为规范的，记作则称该推导为规范的，记作v+w。 v v1 v2 vn-1 w 由规范推导得到的句型称为由规范推导得到的句型称为规范句型规范句型。相应地，有规范归约。相应地，有规范归约。规范推导与规范归约，统称规范分析。规范推导与规范归约，统称规范分析。规范推导规范推导= =最右推导，最左归约最右推导，最左归约= =

78、规范归约规范归约本章概要本章概要文法与语言的定义文法与语言的定义文法四要素文法四要素重要概念：字母表闭包与正闭包，句子、句型，重要概念：字母表闭包与正闭包，句子、句型，推导与归约，短语、简单短语与句柄等。推导与归约，短语、简单短语与句柄等。Chomsky文法与语言及其分类文法与语言及其分类按规则的定义形式而分类（按规则的定义形式而分类（4类），类），与编译程序的联系（与编译程序的联系（CFG、RG）。）。文法等价变换文法等价变换压缩文法与压缩文法与消去左递归消去左递归的文法等价变换。的文法等价变换。句型分析句型分析语法分析技术分类语法分析技术分类:自顶向下与自底向上；自顶向下与自底向上；重要工具：语法分析树（众多用途）；重要工具：语法分析树（众多用途）；二义性句子与二义性文法；二义性句子与二义性文法；相关概念：规范句型，规范分析。相关概念：规范句型，规范分析。

展开阅读全文

2第二章-文法与语言详解

最新文档