第二章文法和形式语言
《编译原理》课程组
计算机工程学院
第二章文法和形式语言
2.1 文法的直观概念
2.2 符号和符号串
2.3 文法和语言的形式定义
2.4 文法的类型
2.5 上下文无关文法机器语法树
2.6 句型分析
2.7 文法的实用限制
第2章文法和语言
【学习目标】
本章目的是为语言的语法描述寻求工具
◇掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一——文法。
◇对形式语言的理论有一个初步基础
◇根据语言文法的特点指导语法分析的过程
本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。
第2章文法和语言
【教学重点】
概念：文法，推导，直接推导，最左(右)推导，产生式，句型，短语，直接短语，句柄，语法树，规范推导，二义文法等
4种文法的定义、文法的构造和文法的推导
语法树的构造和最左（右）推导；
二义文法、二义性的证明；
句型分析；
2.1 文法的直观概念
一、语言概述
语言是由符合语法的句子组成的集合。
–汉语-- 所有符合汉语语法的句子的全体
–英语-- 所有符合英语语法的句子的全体
–程序设计语言-- 所有该语言的程序的全体
每个句子构成的规律
研究语言每个句子的含义
每个句子和使用者的关系
一、语言概述（续1）
研究程序设计语言
每个程序构成的规律
每个程序的含义
每个程序和使用者的关系
语言研究的三个方面
语法Syntax
语义Semantics
语用Pragmatics
一、语言概述（续2）
语法：指语言的一组规则，用它可以形成和产生一个合适的程序。
–如何由基本字符构成一个个单词；
–如何由一系列单词构成程序
语法只定义什么样的符号序列是合法的，而不表达这些符号及符号序列的含义 语义：明确程序各部分的含义
–静态语义：由一系列限定规则组成，并确定哪些合乎语法的程序是合适的；
–动态语义：表明程序要做些什么，要计算什么
一、语言概述（续3）
形式语言：只考虑语法而不考虑语义的符号语言。
每种语言具有两个可识别的特性，
–语言的形式
–该形式相关联的意义
“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。
语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。
二、文法的直观概念
表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述
例：汉语句子的构成规则：
〈句子〉∷=〈主语〉〈谓语〉
〈主语〉∷=〈代词〉|〈名词〉
〈代词〉∷= 我| 你| 他
〈名词〉∷= 王明| 大学生| 工人| 英语
〈谓语〉∷=〈动词〉〈直接宾语〉
〈动词〉∷= 是| 学习
〈直接宾语〉∷=〈代词〉|〈名词〉
二、文法的直观概念（续2）
推导：“我是大学生”是汉语的一个句子
〈句子〉?〈主语〉〈谓语〉
?〈代词〉〈谓语〉
?我〈谓语〉
?我〈动词〉〈直接宾语〉
?我是〈直接宾语〉
?我是〈名词〉
?我是大学生
2.2 符号和符号串
程序设计语言中的单词是基本语法成分，单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造.
一. 符号、字母表和符号串
符号：可以相互区别的基本记号（元素），如字母，数字，标点符号。
字母表：符号（元素）的非空有穷集合，常用Σ表示。
例：V={0,1}，Σ={a, b, c, … , x,y, z}
2.2 符号和符号串
符号串：由字母表中的符号构成的有穷序列叫符号串。
例：字母表∑={a,b,c,d} 则有符号串:a,b,c,d,aa,ddd,acc…
字母表∑ =｛0，1｝上的符号串0，1，00，11，10
注意：ε表示空符号串,它表示不包含任何符号串，不是空格符。符号串中的符号是有顺序的。
符号串集合：字母表上若干个符号串组成的集合.
例：字母表∑={a,b,c,d} 的符号串集合A={ab,acc,da,a};
约定：小写字母a,b,…,r表示符号.
小写字母: s,t,…,z表示字符串;
2.2 符号和符号串
符号串s的头（前缀）和尾（后缀）：
–如果z=xy 是一符号串，那么x 是z 的头，y 是z 的尾。如果x 是非空的，那么y 是固有尾；同样如果y 非空，那么x 是固有头。
–前缀：移走符号串s 尾部的零个或多于零个符号得到的符号串。
如：设z=abc, 那么z 的头是ε,a,ab,abc
–后缀：删去符号串s 头部的零个或多于零个符号得到的符号串。
如：z =abc 的尾是ε,c,bc,abc，z 的固有尾是ε,c,bc。
2.2 符号和符号串
符号串s的子串：
–从s中删去一个前缀和一个后缀得到的符号串.
–如:ana是符号串banana的一个子串.
对于每个符号串s，s和ε两者都是符号串s的前缀、后缀和子串。
符号串s的真前缀，真后缀，真子串：
–任何非空符号串x，相应地，是s 的前缀，后缀或子串，并且s ≠ x
2.2 符号和符号串
二. 符号串的运算
符号串相等：
符号串x，y，如果两者诸符号依次相等，则两符号相等。
符号串的长度：符号串中包含符号的个数。
|abc|=3；| ε |=0；
符号串的连结：
x，y是字母表上的两个字符串，把y的所有符号相继写在x的符号之后所得到的符号串称为x 与y的连结，用xy表示。
X=abc，y=def 则xy=abcdef；yx=defabc；xy yx，ε x=x ε =x；
符号串的逆：设x是字母表上的符号串，其逆为符号串x的倒置，记为x。x=abcd；x=dcba；2.2 符号和符号串
符号串集合的乘积：
设A、B为两个符号串集合，其乘积为AB={xy|x ∈A，y∈B}；
eg：A={aa，bb}，B={cc，dd}，则
AB={aacc，aadd，bbcc，bbdd}
{ε }A=A {ε }=A；
空集：
不含任何元素的集合称为空集。记为φ；
对任何集合A：A φ= φA= φ; 注意：ε?φ
2.2 符号和符号串
符号串的幂：
x是字母表上的符号串，则x的幂运算为：
x0= ε ; x1= x; x2= xx;… x n= x n-1x=x x n-1 (n>0)
x n表示n个x相连结。
eg：x=ok；
则x0= ε ; x1= ok; x2= okok; … x n=okok…ok(n个ok连结）
符号串集合的幂：
A为符号串集合，则符号串集合A的幂运算为：
A0={ε}; A1=A; A2=AA;... A n= A n-1A=AA n-1;(n>0)
A={aa，bb}，则A0={ε}；A1={aa，bb}；
A2=AA={aaaa，aabb，bbaa，bbbb};...
2.2 符号和符号串
符号串集合的闭包和正闭包
集合A的闭包表示为A*（亦称为自反闭包或星闭包）具体定义为：
A*=A0? A1? A2? A3?…=?A k，k≥0
正闭包表示为A+具体定义为
A+=A1? A2? A3?…=?A k，k≥1
由定义可以看到A*= A0 ?A+
例：Σ={a,b}
Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}
2.2 符号和符号串
三. 语言
语言是由句子组成的集合，是由一组符号所构成的集合。字母表∑上的一个语言是∑上的一些符号串的集合(字母表∑上的每个语言是∑*的一个子集)。
例如：字母表Σ={a,b}，Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
–集合{ab,aabb,aaabbb,…,a n b n,…} 或表示为{w|w∈Σ*且w=a n b n,n≥1}为
字母表∑上的一个语言。
–集合{a,aa,aaa,…} 或表示为{w|w∈Σ*，且w=a n，n≥1} 为字母表∑上的一个语言。——Σ*的子集。
{ε}是一个语言。
Φ即{}是一个语言。
2.3 文法和语言的形式定义
规则的定义
文法的定义
推导的定义
句型、句子、语言的定义
2.3 文法和语言的形式定义（续1）
如何来描述一种语言？
如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示
如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：
?生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。
?识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该
过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回
答“不是”，（要么永远继续下去。）
一、规则（重写规则、产生式或生成式）
规则，也称重写规则、产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，
其中
α∈V+，β∈V*中的一个符号
α称为规则的左部
β称作规则的右部。
例：< 句子> → < 主语> < 谓语>
文法可利用规则来描述。
二、文法的定义
1、文法G定义为四元组(V N，V T，P，S )其中
V N ：非终结符号集;
V T：终结符号集；
P：产生式( 也称规则) 的集合；
V N，V T和P是非空有穷集。
S：开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。
V N ∩V T = φ
V=V N ∪V T，V称为文法G 的字汇表
二、文法的定义（续1）
例2.1：文法G=(V N，V T，P，S)，其中
V N={S}，
V T={0，1}，
P={S→0S1，S→01}。
例2.2：非负整数的文法G[N]= (V N，V T，P，S)，其中，
V N ={N，D}，
V T ={0，1，2，3，4，5，6，7，8，9}，
P={N →D|ND，
D→0|1|2| (9)
S=N
二、文法的定义（续2）
例2.3：文法G=(Vn，V T，P，S),其中
Vn={标识符，字母，数字}
V T={a,b,c,...，x,y,z,0,1, (9)
P ={〈标识符〉→〈字母〉
〈标识符〉→〈标识符〉〈字母〉
〈标识符〉→〈标识符〉〈数字〉
〈字母〉→a
〈字母〉→b
…
〈字母〉→z
〈数字〉→0
〈数字〉→1
…
〈数字〉→9}
S =〈标识符〉
二、文法的定义（续3）
文法G习惯上只将产生式写出。有如下约定：
–第一条产生式的左部是识别符号；
–用尖括号括起来的是非终结符号，否则为终结符，或者用大写字母表示非终结符号，小写字母表示终结符号。
–将G写成G[S]，其中S是识别符号，
例2.1还可以写成：
G：S→0S1
S→01
或G[S]：S→0S1
S→01
二、文法的定义（续4）
为书写简洁，常把相同左部的产生式，形如
A→α1
A→α2
…
A→αn
缩写为：
A→α1|α2|…|αn
这里的元符号"|"读做"或"。
二、文法的定义（续5）
一个文法的几种写法
①G=({S,A}，{a,b}，P，S)
其中P：S→aAb
A→ab
A→aAb
A→ε
②G：S→aAb
A→ab
A→aAb
A→ε
③G[S]：S →aAb A→ab A→aAb A→ε
④G[S]：S→aAb A→ab |aAb |ε
三、推导的定义
用文法定义语言的中心思想是：从文法的开始符号出发，反复连续使用产生式，对非终结符施行替换和展开。
1、直接推导
–用“?”表示，在一个句型中用产生式的右部替换产生式的左部
–例：α→β是文法G的产生式，若有v，w满足：
v =γαδ，w = γβδ, 其中γ∈V*,δ∈V*。则称v直接推导到w,记作 v?w，或w直接归约到v
例：G：S→0S1，S→01
S?0S1 ?00S11，00S11 ?000S111，
000S111 ?00001111
若v= 0S1，w=0011，则有直接推导v ? w
三、推导的定义（续1）
2、推导
如果存在直接推导的序列：
v=W0? W1? W2…? W n=w,(n＞0)
则称v推导出(产生)w(推导长度为n)，或称w归约到v。记作v w。
若有v w，或v=w，则记作v w ，(n＞=0)
三、推导的定义（续2）
例：G：S→0S1，S→01
0S1 ?00S11
00S11 ?000S111
000S111 ?00001111
S ?0S1 ?00S11 ?000S111 ?00001111
S ?00001111
S ?S ? 00S11 ?000S111
三、推导的定义（续3）
3、规范推导
最左(最右)推导：在推导的任何一步α?β，其中α、β是句型，都是对α中的最左（右）非终结符进行替换
最右推导被称为规范推导。
例：G[E]：E→E+T|T
T→T*F|F
F→(E)|a
E?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a（最左推导）E?E+T ?E+T*F ?E+T*a ?E+F*a ?E+a*a
?T+a*a ?F+a*a ?a+a*a （最右推导）
四、句型、句子和语言的定义
句型
有文法G，若S => x，则称x是文法G的句型。
句子
有文法G ，若S => x ，且x∈V T*，则称x 是文法G 的句子。（句子是句型的特殊，x 中只包含终结符。）
例：G：S→0S1 ，S→01
S ?0S1 ?00S11 ?000S111 ?00001111
G 的句型S, 0S1 ,00S11 ,000S111,00001111
G 的句子00001111
四、句型、句子和语言的定义（续1）
语言的定义
由文法G生成的语言记为L(G)，它是文法G的一切句子的集合: L(G)={x|S => x，其中S为文法的开始符号，且x ∈V T*}
从定义看出两点：
–符号串x 可从识别符号推出，也即x 是句型。
–x 仅由终结符号组成，即x 是文法G 的句子。
文法描述的语言是该文法一切句子的集合。
例：G：S→0S1，S→01
L(G)={0n1n|n≥1}
四、句型、句子和语言的定义（续2）
例：G[E]：E→E+T|T
T→T*F|F
F→(E)|a
E?E+T ?T+T ?F+T ?a+T ?a+T*F
?a+F*F ?a+a*F ?a+a*a
句子：用符号a ，+ ，* ，( 和) 构成的算术表达式
四、句型、句子和语言的定义（续3）
例文法G[S]：
（1）S→aSBE
（2）S→aBE
（3）EB→BE
（4）aB→ab
（5）bB→bb
（6）bE→be
（7）eE→ee
S?a n B n E n? a n b n e n
则L（G）={ a n b n e n | n≥1 }
五、语言和文法
给定一个文法，能从结构上唯一确定其语言
给定一个语言，不能唯一确定其文法
已知语言描述，写出文法，应满足：
–所描述的语言的任何句子都能由该文法产生
–该文法推导不出不是已知语言的任何句子
已知文法，写出语言的描述，应满足：
–该文法能推导出任何句子都包含在所描述的语言中
–所描述的语言中不包含该文法推导不出的句子
五、语言和文法（续1）
已知语言描述，写出文法
–例：已知语言L(G)={ab n a|n>=1}构造其文法
已知文法，写出语言描述
例：G[E] ：E→E+T|T
T→T*F|F
F→(E)|a
六、文法的等价
若L（G1）=L（G2），则称文法G1和G2是等价的。
如文法G1[A]：A→0R 与G2[S]：S→0S1 等价
A→01 S→01
R→A1
七、递归规则和递归文法
1、递归与递归定义
–递归是指同一个操作或一组操作的连续重复
–递归定义是指在定义某种事物时又用到其本身
2、递归规则
–左部和右部具有相同的非终结符号的规则
例：文法中的规则U?xUy
x=ε时，则有U?Uy，为左递归规则
y=ε时，则有U?xU，为右递归规则
3、递归文法
–直接递归文法
–间接递归文法
4、递归文法的作用
–用有限的规则定义无限的语言
2.4 文法的类型
一、文法分类
通过对产生式施加不同的限制，Chomsky将文法分为四种类型：设有文法G=(V N，V T，P，S);
0型文法：（短语结构文法）
对任一产生式α→β，都有α∈(V N∪V T)+，且α至少包含一个非终结符，β∈(V N∪V T)*
1型文法：（上下文有关文法）
对任一产生式α→β，都有|β|≥|α|，仅仅 S→ε除外，并且S不出现在其他产生式的右部。
即α1Aα2→α1βα2, ，α 1 、α2和β∈(V N∪V T)*
一、文法分类（续1）
文法G[S]是1型文法
S→aSBC| aBC
CB →DB
DB →DC
DC→BC
aB→ab
bB→bb
bC→bc
cC→cc
S?aSBC ?aaBCBC ?aabCBC ?aabbcc
一、文法分类（续2）
2型文法：（上下文无关文法）
对任一产生式α→β，都有α∈V
N ，β∈(V
N
∪V
T
)*
3型文法：（正规文法）–右线性文法
所有产生式的形式都为A→aB或A→a，其中A∈V
N ，B∈V
N
，a∈V
T
(a可为ε)
–左线性文法
所有产生式的形式都为A→Ba或A→a，其中A∈V
N ，B∈V
N
，a∈V
T
(a可为ε)
一、文法分类（续3）
例：G[E]：E→E+T|T
T→T*F|F
F→(E)|a
例文法G=({S,A,B},{0,1},P,S)，其中P由下列产生式组成：S→0A A→1B
S→1B B→1B
S→0 B→1
A→0A B→0
A→0S
显然G是正规文法。
一、文法分类（续4）
例：定义标识符的3型（正规）文法
文法G[I]：I →lT
I →l
T →lT
T →dT
T →l
T → d
其中l表示a～z中的任何一英文字母，d表示0～9中的任一数字。
一、文法分类（续5）
例：定义标识符的3型（正规）文法
–文法G[I]：I →Tl| I d| l 为左线性文法
3型（正规）文法变换
若A→αB 或 A→α，其中A∈V N，B∈V N，α∈V T
如当α=ab时，
则A→αB 即 A→abB 可写为： A→aD D→bB
A→α即 A→ab 可写为： A→aD D→b
一、文法分类（续6）
0型文法（短语结构文法）
0型文法的能力相当于图灵机(Turing)。或者说，任何0型语言都是递归可枚举的；
反之，递归可枚举集必定是一个0型语言。
1型文法（上下文有关文法）
上下文有关文法的产生式的形式描述为α1Aα2→α1βα2，只有A出现在α1和α2的上下文中，才允许用β取代A。其识别系统是线性界限自动机
一、文法分类（续7）
2型文法（上下文无关文法）
2型文法的产生式表示为形如：A→β，β取代非终结符A时，与A所在的上下文无关。其识别系统是不确定的下推自动机。
3型文法（正规文法）右/左线性文法
识别系统是有穷自动机，即所产生的语言由有穷自动机接受。
二、四类文法之间的关系
四种文法之间的逐级“包含”关系
二、四类文法之间的关系
四种文法之间的关系是将产生式做进一步限制而定义的。
语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。
2.5 上下文无关文法及其语法树
上下文无关文法有足够的能力描述程序设计语言的语法结构 例:文法G[E]：E→i|E+E|E*E|(E)
E表示算术表达式,
i表示程序的“变量”，
该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构
一、语法树
G[E]：E→E+T|T
T→T*F|F
F→(E)|a
E?E+T ?T+T ?F+T ?a+T ?a+T*F
?a+F*F ?a+a*F ?a+a*a
E?E+T ?E+T*F ?E+T*a ?E+F*a ?E+a*a
?T+a*a ?F+a*a ?a+a*a
一、语法树
设G=( V
,V T,P,S)为一上下文无关文法，若一棵树满足下列4个条件，则此树称作G的语N
法树(推导树，派生树）：
1. 每个结点都有一个标记，此标记是V的一个符号
2. 根的标记是S
3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定A∈V N
4. 如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，…，n k，其标记
分别为A1，A2，…，A k，那么A→A1A2，…，A k一定是P中的一个产生式
语法树的结果：
从左到右读出叶子的标记而构成的行谓之
语法树---句型推导的直观表示
给定文法G=(V N,V T,P,S)，对于G的任何句型都能构造与之关联的语法树
(推导树)
定理：
G为上下文无关文法，
对于α≠ε，有S =>α，当且仅当
文法G有以α为结果的一棵语法树(推导树)
一、语法树
G[E]：E→E+T|T
T→T*F|F
F→(E)|a
E?E+T ?T+T ?F+T ?a+T ?a+T*F
?a+F*F ?a+a*F ?a+a*a
一、语法树
用于描述上下文无关文法句型推导的直观方法
一、语法树
推导过程中施用产生式的顺序
一、语法树（续5）
例：G[E]：E→E+T|T
T→T*F|F
F→(E)|a
试给出表达式a+a*a的推导，并画出语法树。
E?E+T ?T+T ?F+T ?a+T ?a+T*F
?a+F*F ?a+a*F ?a+a*a
E?E+T ?E+T*F ?E+T*a ?E+F*a ?E+a*a
?T+a*a ?F+a*a ?a+a*a
E?E+T ?T+T ?T+T*F ?F+T*F ?F+F*F
?a+F*F ?a+F*a ?a+a*a
一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?
二、文法的二义性
例：G[E]:
E → i
E → E+E
E → E*E
E → (E)
二、文法的二义性
若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的
文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G
和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。
判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件
二义文法改造为无二义文法
G[E]: E → i G[E]：E → T|E+T
E → E+E T → F|T*F
E → E*E
F →（E）|i
E → (E) 规定优先顺序和结合律
如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。
对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。
2.6 句型的分析
句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。
在语言的编译实现中，完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。
从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。句型的分析算法分类
分析算法可分为：
自上而下分析法：
从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。
自下而上分析法：
从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。
两种方法反映了两种不同的语法树的构造过程。
句型的分析算法分类
两种方法反映了两种语法树的构造过程。
自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串
自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树
自上而下的语法分析
例：文法G：S →cAd
A →ab
A →a
识别输入串w=cabd是否为该文法的句子
自下而上的语法分析
例：文法G：S →cAd
A →ab
A →a
识别输入串w=cabd是否该文法的句子
句型分析的有关问题
1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？
假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？
2）在自下而上的分析方法中如何识别可归约的串？
在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”
3）存在确定和不确定分析，本课只讨论确定的分析法。
短语、直接短语、句柄的定义
文法G[S]
句型的短语
S => αAδ且 A =>β，则称β是句型αβδ相对于非终结符A的短语
句型的直接短语
若有A β，则称β是句型αβδ相对于非终结符A 的直接短语
句型的句柄
一个句型的最左直接短语称为该句型的句柄
短语、直接短语、句柄的定义
例1：考虑文法G[E]: E→T|E+T
T→F|T*F
F→(E)|i
分析i+i*i中的短语、直接短语和句柄
例2：给定文法G[E]: E→ET+|T
T→TF*|F
F→FP^|P
P→(E)|i
试根据语法树求句型TF*PP^+短语、直接短语和句柄
2.7 文法的实用限制
文法中不含有有害规则和多余规则
有害规则：形如U→U 的产生式。会引起文法的二义性
多余规则：指文法中任何句子的推导都不会用到的规则
文法中不含有不可到达和不可终止的非终结符
1 ）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可
到达。
2 ）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不
可终止。
2.7 文法的实用限制
对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：
1. A必须在某句型中出现
即有S => αAβ，其中α，β属于V*
2. 必须能够从A 推出终结符号串t 来
即A => t ，其中t∈V T*
化简文法
例：G[S] ：1) S→Be
2) B→Ce
3) B→Af
4) A→Ae
5) A→e
6) C→Cf C为不可终止
7) D→f D为不可到达
产生式2），6），7）为多余规则应去掉。
上下文无关文法中的ε规则
具有形式A→ε，的规则称为ε规则
因为ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现
两种定义的唯一差别是ε句子在不在语言中
第二章文法和形式语言 《编译原理》课程组 计算机工程学院 第二章文法和形式语言 2.1 文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4 文法的类型 2.5 上下文无关文法机器语法树 2.6 句型分析 2.7 文法的实用限制 第2章文法和语言 【学习目标】 本章目的是为语言的语法描述寻求工具 ◇掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一——文法。 ◇对形式语言的理论有一个初步基础 ◇根据语言文法的特点指导语法分析的过程 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 第2章文法和语言 【教学重点】 概念：文法，推导，直接推导，最左(右)推导，产生式，句型，短语，直接短语，句柄，语法树，规范推导，二义文法等 4种文法的定义、文法的构造和文法的推导 语法树的构造和最左（右）推导； 二义文法、二义性的证明； 句型分析； 2.1 文法的直观概念 一、语言概述 语言是由符合语法的句子组成的集合。 –汉语-- 所有符合汉语语法的句子的全体 –英语-- 所有符合英语语法的句子的全体 –程序设计语言-- 所有该语言的程序的全体
每个句子构成的规律 研究语言每个句子的含义 每个句子和使用者的关系 一、语言概述（续1） 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法Syntax 语义Semantics 语用Pragmatics 一、语言概述（续2） 语法：指语言的一组规则，用它可以形成和产生一个合适的程序。 –如何由基本字符构成一个个单词； –如何由一系列单词构成程序 语法只定义什么样的符号序列是合法的，而不表达这些符号及符号序列的含义 语义：明确程序各部分的含义 –静态语义：由一系列限定规则组成，并确定哪些合乎语法的程序是合适的； –动态语义：表明程序要做些什么，要计算什么 一、语言概述（续3） 形式语言：只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性， –语言的形式 –该形式相关联的意义 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。 语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。 二、文法的直观概念 表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述 例：汉语句子的构成规则： 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷= 我| 你| 他 〈名词〉∷= 王明| 大学生| 工人| 英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷= 是| 学习 〈直接宾语〉∷=〈代词〉|〈名词〉
第二章文法和语言的概念和表示 本章概述 本章中，我们将概述高级程序语言的结构和主要的共同特征，并介绍程序语言的语法描述方法。 主要学习内容：程序设计语言的定义，高级语言的一般特性，高级语言的语法描述，上下文无关文法，语法分析树和二义性，乔姆斯基文法体系。 学习目标：理解程序语言的词法、语法和语义等概念，进一步掌握高级程序设计语言的一般结构和主要共同特征，使学生具有必要的基础知识；理解文法和语言的一些基本概念，如文法的定义和构造、句型、句子、语言、推导、语法树等。 学习重点和难点：语法，语义，文法的构造。 2.1 概述 显然，用高级语言编程比用低级语言来得方便，但要解决两个问题： 1.计算机怎样懂得高级语言程序，这就需要一个翻译程序实现从源程序到目标程序的转换。 2.用什么方法来精确定义高级语言，即怎样精确描述高级语言。 要构造一个编译程序，应深刻理解被编译的源语言的结构（即词法和法）及其含义（即语义），同时要弄清源语言的语法规则和语义规则是采用什么理论或什么方法来描述的。 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。 任何语言均可看作一个集合。这个集合中的每个元素都是在一定符号集（字母表）上的一个符号串。 对于自然语言来说，它们是定义在某个字母表上的句子的集合。 对于程序语言来说，它们也是定义在某个字母表上的句子的集合。这里的句子，就是一个源程序。 通常，源程序是由关键字、标识符、常数、运算符以及一些界限符组成。这些语法成分统称为单词或单词符号。 单词符号是语言中具有独立意义的最基本单位。语言的单词符号是由词法规则所确定的，即词法规则规定了单词符号的形成规则。 “我是大学生”是汉语的一个句子。 用语法来描述： 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他 〈名词〉∷=王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉 有了这一组规则以后，按照如下方式用它们导出句子： 开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成： 〈句子〉?〈主语〉〈谓语〉， 然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉?〈代词〉〈谓语〉， 重复做下去，这样句子“我是大学生”的导出的全部动作过程是： 〈句子〉?〈主语〉〈谓语〉 ?〈代词〉〈谓语〉