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

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

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

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

3、子的构造规则。文法规定语言中句子的构造规则。句子是一个语言之字母表上按一定规则构造的句子是一个语言之字母表上按一定规则构造的符号串。符号串。2.1.1 2.1.1 字母表字母表 字母表字母表:有穷非空的符号集合。有穷非空的符号集合。例例 A=a,b,c =0,1 A=a,b,c =0,1 C C语言字母表语言字母表=字母，数字，界限符字母，数字，界限符 不同的语言有不同的字母表。不同的语言有不同的字母表。字母表上的元素（即符号）组成符号串。字母表上的元素（即符号）组成符号串。符号串符号串: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-c)/d中的子符号串中的子符号串3.符号串的头与尾（前缀、后

5、缀）符号串的头与尾（前缀、后缀）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.符号串集合的定义符号串集合的定义1)它是它是一切元素都是某字母表上的符号串的集合。一切元素都是某字母表上的符

6、号串的集合。2)表示法表示法 枚举法枚举法 1，11，111，1111 省略法省略法 1，11，111，1111，描述法描述法 1i|i1 或或x|x全由全由1组成组成,|x|1 注意：一定不能涉及含义注意：一定不能涉及含义,如如 x|x=10i。字母表字母表上的一个语言就是上的一个语言就是上的一些上的一些符号串组成的集合。符号串组成的集合。空集空集 是一个语言，仅含一个空符是一个语言，仅含一个空符号串集合号串集合 也是一个语言。特别需要指也是一个语言。特别需要指出的是，出的是，和和 是不同的语言。是不同的语言。2.对符号串集合的运算对符号串集合的运算 乘积：乘积：AB=xy|x A 且且 y

7、 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=?3.字母表的闭包与正闭包字母表的闭包与正闭包 闭包闭包 A*=A0A1An 0，1，2*正闭包正闭包 A+=A1 An =A*-0，1，2+xA+,则则|x|=1 xA*,则则|x|=0 任何一个语言是其任何一个语言是其字母表字母表之之正闭包正闭包的真子集。的真子集。如何找出此真子集？或说，如何找出其句子？如何找出此

8、真子集？或说，如何找出其句子？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 终结符号，（不会出现在规则左部）终结符号，（不会出现在规则左部）终结符号集终结符号集VT （VN VT=V=VN VT）单规则：右部是单个非终结符单规则：右部是单个非终结符 用于指定重复次数:=05 内中符号至多出现一次:=+|-()提公因子E:=E+T|E-T 可改写为E:=E(+|-)T

10、16规则构造的例子规则构造的例子C C语言标识符的规则：语言标识符的规则：:=:=:=:=:=:=:=:=A|Z :=:=a|z :=:=_ :=:=0|917用规则产生句子的例子用规则产生句子的例子如：用标识符产生式规则产生句子如：用标识符产生式规则产生句子area.a a ea ea rea rea area 其中，其中，“=”=”为推导。为推导。2.文法的定义文法的定义 文法文法GZ是非空有穷的重写规则集合，其中是非空有穷的重写规则集合，其中Z是识别符号（或称开始符号），是识别符号（或称开始符号），G是文法名。是文法名。例例G1E：E:=E+T E:=T T:=T*F T:=F F:=(

11、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.:=2.:=3.:=4.:=5.:=Peter 6.:=Berry7.:=river8.:=swims9.:=in例例 试以文法试以文法G 为例考察如何应用文法为例考察如何应用文法 来生成句子。来生成句子。替换为替换为句子句子=主语主语 谓语谓语 状语状语 (规则规则1)=名词名词 谓语谓语 状

12、语状语 (规则规则2)=Peter 谓语谓语 状语状语 (规则规则5)=Peter 动词动词 状语状语 (规则规则3)=Peter swims 状语状语 (规则规则8)=Peter swims 介词介词 名词名词 (规则规则4)=Peter swims in 名词名词 (规则规则9)=Peter swims in river (规则规则7)应用文法生成句子的步骤：应用文法生成句子的步骤：步骤步骤1 1 以识别符号为当前符号串；以识别符号为当前符号串；步骤步骤2 2 对当前符号串中的一个非终结符号进行替换，对当前符号串中的一个非终结符号进行替换，把它替换为以此非终结符号为左部的规则之右部符号串，

13、把它替换为以此非终结符号为左部的规则之右部符号串，生成新的当前符号串；生成新的当前符号串；步骤步骤3 3 重复步骤重复步骤2,2,直到当前符号串中不包含非终结直到当前符号串中不包含非终结符号，最终不包含非终结符号的符号串就是所生成的句符号，最终不包含非终结符号的符号串就是所生成的句子。子。说明：说明：每步的当前符号串将称为句型，每步的当前符号串将称为句型，最终的终结符号串称为句子。最终的终结符号串称为句子。按上述步骤应用各个规则，可生成：按上述步骤应用各个规则，可生成：Berry swims in riverBerry swims in river 甚至可生成：甚至可生成：river swim

14、s in Peterriver swims in Peter 表明：语法上的正确性不能保证语义上的正确性。表明：语法上的正确性不能保证语义上的正确性。对当前句型中任一非终结符号进行替换，都将生成对当前句型中任一非终结符号进行替换，都将生成新的句型，最终生成句子。但宜用系统的方式进行推导，新的句型，最终生成句子。但宜用系统的方式进行推导，如，每步对如，每步对最左最左的或的或最右最右的非终结符号进行替换。这时，的非终结符号进行替换。这时，分别称为最左推导与最右推导。分别称为最左推导与最右推导。引进句子生成中的两个重要概念：推导与归约。引进句子生成中的两个重要概念：推导与归约。直接推导直接推导：=x

15、Uy=xuy 句子句子=主语主语 谓语谓语 状语状语 主语主语 谓语谓语 状语状语=名词名词 谓语谓语 状语状语 名词名词 谓语谓语 状语状语 =Peter 谓语谓语 状语状语 Peter 谓语谓语 状语状语 =Peter 动词动词 状语状语 Peter 动词动词 状语状语 =Peter swims 状语状语 Peter swims 状语状语 =Peter swims 介词介词 名词名词 Peter swims 介词介词 名词名词=Peter swims in 名词名词 Peter swims in 名词名词=Peter swims in river 直接推导时，给定直接推导时，给定 v=xU

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

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

18、u2=un-1=w得到符号串得到符号串w,称称v推导到推导到w,或或w归约到归约到v,记为记为:v=+w n称为推导的长度。称为推导的长度。广义推导广义推导：=*若若 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

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

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

21、推导出，即可证明明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 又因又因i+i*i中的每个符号均为终结符号，故中的每个符号均为终结符号，故i+i*i是它的一个句子。是它的一个句子。思考设计编程语言时，是先设计语言形式，还是先设计BNF形式的文法？例如要表示形如 i+i,i+i*i的表达式建议：学习时注意积累，何种典型文法可以得到某种典型的语言形式考试考查：能够由文法写出语言，也能由语言设考试考查：能够由文法写出语言，也能由语言设计出文法计出文法为什么有穷规则集合

22、的文法能定义无穷的语言？为什么有穷规则集合的文法能定义无穷的语言？文法文法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 =递归地定义规则，即，递归地定义规则，即，U:=U,使得有穷个规则使得有穷个规则可

23、能定义潜在地无穷的语言。可能定义潜在地无穷的语言。重要概念：短语、简单短语 已知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 句柄:句型中最左的简单短语。句柄是重要概念之一。归约是自底向上的语法分析关键，何时进行归约则必须依赖句柄。分析句型时，要搞清楚哪些符号串能构成短语和直接短语。36求短语、直接短

24、语和句柄的例子求短语、直接短语和句柄的例子 【例例】设有文法设有文法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。注意：选择符号串判断是否短语时，必须同时满足两个注意：选择符号串判断是否短语时，必须同时满足两个条件：条件：1

25、）可归约；）可归约；2）归约后仍是句型（即可由识别符号推导出）归约后仍是句型（即可由识别符号推导出）概括文法文法G:有穷非空的重写规则集合有穷非空的重写规则集合 四要素：四要素：VN，VT，P，Z句型：句型：Z=*t,t(V(VN NVVT T)+句子：句子：Z=*t,t VVT T+概念：推导，归约概念：推导，归约 简单短语，简单短语，短语，短语，句柄句柄4.文法句子之生成的实现 实质是推导的构造。实质是推导的构造。要点是推导在计算机内的存储表示要点是推导在计算机内的存储表示。文法符号序号文法符号序号 后继符号结点指针后继符号结点指针其中包含两类结点，一类结点结构形如：其中包含两类结点，一类

26、结点结构形如：另一类结点结构形如：另一类结点结构形如：这易于用这易于用C C语言结构类型实现，例如，对第一类，语言结构类型实现，例如，对第一类，typedef struct 直接推导链首结点直接推导链首结点 struct 符号结点符号结点 *句型首符号结点指针；句型首符号结点指针；struct 直接推导链首结点直接推导链首结点 *下一直接推导链头指针；下一直接推导链头指针；直接推导链首结点类型；直接推导链首结点类型；句型首符号结点指针句型首符号结点指针 下一直接推导链头指针下一直接推导链头指针 显然每一显然每一“列列”（垂直链）中各结点相应的符号组（垂直链）中各结点相应的符号组成一个句型。成一

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

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

29、文法的存储表示：一种是数组表示一种是数组表示 一种是链表表示一种是链表表示 例例 GE：E:=E+T E:=T T:=T*F T:=F F:=(E)F:=i 数组表示：数组表示：左部左部 右部符号串右部符号串 右部长度右部长度C语言数据结构定义：语言数据结构定义：typedef struct 符号符号 左部符号；左部符号；符号符号 右部符号串右部符号串MaxRightPartLength+1;int 右部长度；右部长度；规则规则;规则规则 文法文法MaxRuleNum+1;其中，其中，typedef char 符号符号MaxLength+1；符号符号 非终结符号集非终结符号集MaxVnNum+

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

31、储表示：文法文法2：101，0，102，1 TVT：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 VT+一个文法确定唯一的语言。反之？一个文法确定唯一

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

33、右递归于：:=:=:=if()else 因此，因此，=+也可以说，也可以说，C语言文法递归于语言文法递归于 =+为语言构造文法为语言构造文法 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 a a a a b b b b c c cc A A A B B S SG1S:S:=Sc|Bc B:=Bb|Ab A:=Aa|a注：同一种语言可设计出不同的文法；注意扩展！注：同一种语言可设计出不同的文法；注意扩展！L2=ai bi ck|i,k1 aa a b

34、 b b c c c A A A S SG2S:S:=Sc|Ac A:=aAb|ab 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 Ca:=aaC CB:=DB CB:=E aD:=Da AD:=AC aE:=Ea AE:=56文法产生语言的例子文法产生语言的例子【例例1 1】设有文法设有文法GZ:Z:=aaZbb|ab 求该文法所描述的语言。求该文法所描述的语言。分析：分析：语言：语言：57文法产生语言的例子文法产生语言的例子【例例2 2】设有文法

35、设有文法GZ:求该文法所描述的语言。求该文法所描述的语言。分析：分析：由括号组成的终结符号，且左右括号匹配。由括号组成的终结符号，且左右括号匹配。【例例3 3】设有文法设有文法GZ:求该文法所描述的语言求该文法所描述的语言。分析：分析：1后面紧跟的符号必为后面紧跟的符号必为0或为空，即该文法产生或为空，即该文法产生的是不包括两个相邻的是不包括两个相邻1 1的所有的所有0、1串。串。语言：语言：概括概括1.程序设计语言是一切程序的集合；程序设计语言是一切程序的集合；程序是在程序设计语言字母表上按一定规则构造的符程序是在程序设计语言字母表上按一定规则构造的符号串；号串；程序设计语言是其字母表正闭包

36、的真子集。程序设计语言是其字母表正闭包的真子集。2.文法是重写规则的集合文法是重写规则的集合 文法四要素：文法四要素：VN、VT、P、Z 文法的句型：由识别符号推导所得的符号串。文法的句型：由识别符号推导所得的符号串。文法的句子：全由终结符号组成的句型。文法的句子：全由终结符号组成的句型。3.语言是一切句子的集合；语言是一切句子的集合；文法确定，则语言确定，文法确定，则语言确定，语言给定，但可为该语言构造若干文法。语言给定，但可为该语言构造若干文法。递归，使有穷多个规则能定义无穷的语言。递归，使有穷多个规则能定义无穷的语言。4.重要概念重要概念 句型、句子句型、句子 推导、归约推导、归约 短语

37、、简单短语、句柄短语、简单短语、句柄 递归（规则递归、文法递归）递归（规则递归、文法递归）应用文法生成句子的步骤：应用文法生成句子的步骤：步骤步骤1 以识别符号为当前句型以识别符号为当前句型 步骤步骤2 对当前句型进行直接推导对当前句型进行直接推导 （把其中一个非终结符号替换为以其为左部的规把其中一个非终结符号替换为以其为左部的规 则之右部符号串）则之右部符号串）步骤步骤3 重复步骤重复步骤2，直到无非终结符号可被替换。，直到无非终结符号可被替换。通常应以系统的有规则的方式进行替换通常应以系统的有规则的方式进行替换 对最左的非终结符号进行替换（最左推导）对最左的非终结符号进行替换（最左推导）对

38、最右的非终结符号进行替换（最右推导）对最右的非终结符号进行替换（最右推导）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 Chomsky文法类和语言类文法类和语言类1.Chomsky分类法分类法 对文法四要素概括与抽象。对文法四要素概括与抽象。定义：定义：Chomsky文法文法G=（VN,VT,P,Z)VN VT P Z文法及例

39、：文法及例：GS:S:=Sc|Bc B:=Bb|Ab A:=Aa|a G1=（VN,VT,P1,S1)VN=S1,A,B VT=a,b,c P1:S1:=S1c|Bc B:=Bb|Ab A:=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,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

40、,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型文法（短语结构文法型文法（短语结构文法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型文法（型文法（

41、正则文法正则文法RG）：）：U:=VT 或或 U:=T U,VVN,TVT 相应地有相应地有4类类Chomsky语言：语言：0型语言（短语结构语言型语言（短语结构语言PSL）1型语言（上下文有关语言型语言（上下文有关语言CSL）2型语言（型语言（上下文无关语言上下文无关语言CFL）3型语言（型语言（正则语言正则语言RL）注意：注意：有时对有时对2型文法，扩充有型文法，扩充有规则与规则与句子句子 规则规则：U:=句子句子：Z =*形式语言与自动机形式语言与自动机 Chomsky语言类和自动机的对应关系：语言类和自动机的对应关系：3型语言型语言 有穷状态自动机有穷状态自动机 FA 2型语言型语言

42、下推自动机下推自动机 PDA 1型语言型语言 线性界限自动机线性界限自动机LBA 0型语言型语言 图灵机图灵机TM 2.3.3 形式语言的分类与程序设计语言形式语言的分类与程序设计语言 1.程序设计语言一般用程序设计语言一般用上下文无关文法上下文无关文法定义定义：U:=u 2.但语言一般是上下文有关的但语言一般是上下文有关的 (1):=:=goto:=goto :=:(标识符由所在上下文确定是否标号标识符由所在上下文确定是否标号)(2)()=(标识符由后跟符号确定是函数标识符、数组变量还是变量标识符由后跟符号确定是函数标识符、数组变量还是变量)3.通常：词法通常：词法 正则文法正则文法 语法语

43、法 上下文无关文法上下文无关文法 语义语义 口语口语2.3.4 对上下文无关文法的进一步讨论对上下文无关文法的进一步讨论1*.上下文无关文法的自嵌套特性上下文无关文法的自嵌套特性 如果一个上下文无关文法如果一个上下文无关文法G G中存在具有下列特性的非终中存在具有下列特性的非终结符号结符号U U：U=U=*xUy xUy其中其中x,yV+，则称，则称U为自嵌套的非终结符号，包含自嵌为自嵌套的非终结符号，包含自嵌套非终结符号的文法套非终结符号的文法G称为自嵌套的上下文无关文法。称为自嵌套的上下文无关文法。若一个上下文无关文法若一个上下文无关文法G不是自嵌套的，则不是自嵌套的，则L(G)是是一个正

44、则语言。一个正则语言。对任何一个正则语言，必定可构造不是自嵌套的文对任何一个正则语言，必定可构造不是自嵌套的文法。一个严格的上下文无关语言，必不能构造非自嵌套法。一个严格的上下文无关语言，必不能构造非自嵌套的文法。自嵌套特性把正则语言与严格的上下文无关语的文法。自嵌套特性把正则语言与严格的上下文无关语言区别开来。言区别开来。2.与推导有关的特性与推导有关的特性 对于对于CFG，若存在句型，若存在句型x=x1x2xn,有有 x1x2xn=*y,则必存在则必存在y1,y2,yn，使得使得 xi=*yi(i=1,2,n),Z 且且 y=y1y2yn。设设x=*y,若若x的首符号的首符号VT,X1 X

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

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

47、判定x x是否是否L L的一个成员的一个成员?对于上下文无关语言，这问题的答案是肯定的。对于上下文无关语言，这问题的答案是肯定的。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等价。等价。2.文法等价变换的必要性文法等价变换的必要性 文法等价变换的概念：文法等价变换的概念：对文法进行变换，使得变换对文法进行

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

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

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

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

52、 =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 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是多余

53、的，应删除。是多余的，应删除。重复判条件重复判条件1与与2，最终得到与文法，最终得到与文法GZ等价的等价的压缩了的文法压缩了的文法GZ:Z =Be A =Ae A =e B =Af 压缩文法等价变换的规范步骤：压缩文法等价变换的规范步骤：步骤步骤 规则展开成非缩写形式并删除规则展开成非缩写形式并删除U:=U形规则形规则;步骤步骤 判别条件，删除不满足条件的规则判别条件，删除不满足条件的规则;步骤步骤 判别条件，删除不满足条件的规则判别条件，删除不满足条件的规则;步骤步骤 重复步骤和步骤，直到无规则被删除。重复步骤和步骤，直到无规则被删除。3.*实现之考虑实现之考虑消去左递归的文法等价变换左递归

54、的存在将导致自顶向下语法分析失败自顶向下：即从识别符号出发，使用不同规则进行推导。左递归可使分析陷入无穷循环，导致栈溢出U=Ux=Uxx=Uxxx=U=Ux=Uxx=Uxxx=因此，对自顶向下分析技术，需要消除左递归。2.4.3 消去左递归的文法等价变换消去左递归的文法等价变换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

55、 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.用扩充表示法用扩充表示法 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.文法左递归的消去文法左递归的消去（间接的规则左递归）（间接的规则左递归）基本思想基本思想:

56、对非终结符号排序成对非终结符号排序成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一般地，对于一般地，对于Ui:=Uj必有：必有：ji,从而不可能产生从而不可能产生U=+UU-Ua文法文法左递归左递归 消去文法左递归的算法步骤消去文法左递归的算法步骤:步骤步骤 把非终结符号排序成把非终结符号排序成U1,U2,Un 步骤步骤 以上列顺序执行下列程序：以上列顺序执行下列程序：for(i=

57、1;i=n;i+)for(j=1;j=i-1;j+)把形如把形如Ui:=Ujr的规则改写成的规则改写成:Ui:=xj1r|xj2r|xjkr 其中其中Uj:=xj1|xj2|xjk是对于是对于Uj的一切规则的一切规则 消除关于消除关于Ui的规则左递归的规则左递归;消去文法左递归等价变换的解题规范：消去文法左递归等价变换的解题规范：步骤步骤1 识别是规则左递归还是文法左递归识别是规则左递归还是文法左递归步骤步骤2 进行相应的文法等价变换进行相应的文法等价变换步骤步骤3 给出消去了左递归的等价文法给出消去了左递归的等价文法例 设有文法GS：GS：S=SaTbcTd T=Segh 试消去其文法左递归

58、。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

59、c|d)SeT|最后得到文法最后得到文法GS：GS：S =SaTbcTd T =Segh消去了左递归的等价文法消去了左递归的等价文法GS：S =T(bcd)S S =aS|T =ghT T =(bc|d)SeT|例 设有文法GA：GA:A=Ba|Cb|c B=dA|Ae|f C=Bg|Ah试消去该文法的左递归。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的循环，

60、且关于的循环，且关于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|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 =

61、B(ah|g)|(Cb|c)h,呈呈U3:=U2形，把规则形，把规则B =(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|最后得到消去了左递归的等价文法最后得到消去了左递归的等价文法 GA:A =BaCbc B =(Cbe|ce|dA|f)B B:=ae B|C =(ce|dA|f)B(ah|g)|ch)

62、C|C:=(beB(ah|g)|bh)C|3.*实现之考虑实现之考虑 要点要点:识别文法是规则左递归还是文法左递归识别文法是规则左递归还是文法左递归 文法在计算机内的存储表示文法在计算机内的存储表示2.5 语法分析树与句型分析语法分析树与句型分析 2.5.1 语法分析树的概念语法分析树的概念1.语法分析树的引进语法分析树的引进 术语：术语：结点结点 根结点根结点 末端结点末端结点 边边 分支分支 分支名字结点分支名字结点 分支结点分支结点 Berry swims in river 分支结点符号串分支结点符号串 子树子树 子树末端结点符号串子树末端结点符号串 树树 末端结点符号串末端结点符号串语

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

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

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

66、 这是从推导构造语法分析树的逆过程。这是从推导构造语法分析树的逆过程。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.二义性二义性 概念：一个概念：一个句子句子，若可为它构造两个不同的语法分析，若可为它构造两个不同的语法分析树，称此句子是二义性的句子。树，称此句子是二义性的句子。包含二义性句子的文法称二义性文法。包含二义性句子的文法称二义性文法。例例 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 注意：二义性与多义性的区别。注意