第二章 文法和语言
2.1 文法的基本概念一个程序设计语言是一个记号系统，如自然语言一样，
它的完整的定义应包括语法和语义两方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序，目前在程序设计语言的识别中广泛使用的是上下文无关的文法。在这理主要介绍文法和语言的概念。
例：设有文法：
<句子 >→ <主语 ><谓语 >
<主语 >→ <冠词 ><形容词 ><名词 >
<冠词 >→ the
<形容词 >→ big
<谓语 >→ <动词 ><直接宾语 >
<动词 >→ ate|caught
<直接宾语 >→ <冠词 ><名词 >
<名词 >→ mouse|cat
则：
<句子 >=><主语 ><谓语 >=><冠词 ><形容词 ><名词 ><谓语
>
=>the<形容词 ><名词 ><谓语 >=> the big<名词 ><谓语
>
=>the big cat <谓语 >=>the big cat <动词 ><直接宾语 >
=>the big cat ate<直接宾语 >=>the big cat ate<冠词 ><
名词 >=>the big cat ate the <名词 > =>the big cat ate the
mouse
2.1.1 符号和符号串定义 2.1
字母表是有穷非空集合。用 Σ表示。
例：无符号二进制数的字母表为 {0,1}
C语言的字母表为字母、数字和若干专用符号组成的符号集定义 2.2
符号串是由字母表中的符号组成的有穷序列，又称字符串、串。
例,a,b,c,ba,bbac,caacb,···等都是字母表 {a,b,c}上的符号串定义 2.3
不包含任何字符串的空符号串用 ε表示定义 2.4
符号串 x的长度，即符号串 x中的字符用 |x|表示 (读作 x的长度 )
例,|abc|=3 |a|=1 |ε|=0
定义 2.5
设非空符号串 u=xvy,其中 v≠ε,则称 v为 u的子串,若 |u|>
|v|则称 v为 u的真子串定义 2.6
如果 z=xy是一个符号串，则 x是 z和头，而 y是 z的尾。如果 x
是非空的，那么 y是固有尾；同样如果 y非空，那么 x是固有头。
例：设 z=abc，那么 z的头是 ε,a,ab,abc。除 abc外，其它都是固有头。 z的尾是 ε,c,bc,abc。 z的固有尾是 ε,c,bc
定义 2.7
设 x,y 是同一字母表上的两个符号串，把 y的符号写在 X的符号之后得到的符号串，称为的连接。记为 xy
例,x=ab,y=wabu 则
z=xy=abywabu
显然,|x|+|y|=|z|
εx=xε=x
定义 2.8
设 x是符号串，把 x自身连接 n次得到符号串 z,即 z=xx···xx(n
个 x)，称为符号串 x的方幂,记为 z=xn
例,x0=ε x1=x x2=xx x3=xxx ···
定义 2.9
符号串集合若集合 A中的一切元素都是其字母表上的符号串，则称 A为该字母表上的符号串集合。
注意,ε,{ε} 和 Φ （表示空集）的区别定义 2.10
两个符号串集合 A和 B的乘积 AB定义为：
AB={xy|x∈ A且 y∈ B}
例：设 A={a,bc},B=｛ b,c,da｝则集合
AB={ab,ac,ada,bcb,bcc,bcda｝。
注意：由于 εx=xε=x 因此 {ε}A=A{ε}=A,但 ΦA=AΦ=Φ
则：
A0={ε}
A1=A
A2=AA
An=An-1A=AAn-1（ n>0）
显然：
Σ1是字母表中的所有单个字符组成的字符串
Σ2是所有由字母表中二个的字符组成的字符串
Σ3是所有由字母表中三个的字符组成的字符串
Σn是所有由字母表中长度为 n的字符串集合定义 2.11
A的闭包 A*=A0∪ A1∪ A2∪ ···
A的正闭包 A+= A1∪ A2∪ A3∪ ···
显然 A+=AA*=A*A A*=A0∪ A+
由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上的某些符号串的集合，
因此，某个字母表上的语言是这个字母表上的正闭包的子集，
而且通常是真子集。
例：若 Σ={0,1},则 Σ*=｛ ε,0,1,00,01,10,11,000,001，
010,··· ｝
例：令 L={A,B,C,···,Z,a,b,···,z},D={0,1,··· 9}
1.L∪ D 2.LD 3.L4 4,L(L∪ D)* 5,D+ 6.D+∪ L*则分别代表什么集合？
1.字母或数字（包括 ε） 的集合
2.由字母开头后面跟一个数字的集合
3.由４个字母组成的字符串的集合
4.由字母开头后面是字母数字（可省略）的集合
5.数字串集合
6.数字串和字母串集合（包括 ε）
约定：当对符号串 z=xy的头感兴趣而对其余部分不感兴趣时，
可以采用省略写法,z=x···；如果只是为了强调 x在符号串 z中的某处出现，则可表示为,z=···x···；如果只是为了强调 x在符号串 z中的末尾出现，则可表示为,z=···x；
2.1.2 文法和语言的形式定义语言是字母表上的某些符号串集合，在这集合中的每个符号串都是按一定规则生成的。其规则最常用的是重写规则（又称产生式或生成式），它是形如 α→ β或 α：,=β（ α,β）的有序对，（读作 α定义为 β），其中 α称为规则的左部,β称为规则的右部。
定义 2.12
文法 G定义为四元组（ Vn,Vt,P,S）。
其中,
Vn为非终结符号（或语法实体，或变量）集； Vt为终结符号集；
P为产生式（也称规则）的集合；
S称作识别符号或开始符号。它是一个非终结符,至少要在一条规则中作为左部出现。
Vn,Vt和 P是非空有穷集，
显然,Vn和 Vt不含公共的元素，即 Vn∩ Vt =Φ
定义 2.13
用 V表示 Vn∪ Vt。 V称为文法 G的字汇表。
例,文法 G=（ Vn,Vt,P,S），其中 Vn={S},Vt={0,l｝,
P=｛ S→ OS1,S→ 01｝。这里，非终结符集中只含一个元素 S;
终结符集由两个元素 0和 1组成；有两条产生式；开始符号是 S。
例,文法 G=（ Vn,Vt,P,S）
其中,
Vn={<整数 >,<正负号 >,<无符号整数 >,<数字 >}
Vt={+,-,0,1,2,3,4,5,6,7,8,9}
P={<整数 >→ <正负号 ><无符号整数 >
<整数 >→ <无符号整数 >
<正负号 >→ +
<正负号 >→ -
<无符号整数 >→ <无符号整数 ><数字 >
<无符号整数 >→ <数字 >
<数字 >→ 0
<数字 >→ 1
<数字 >→ 2
<数字 >→ 3
<数字 >→ 4
<数字 >→ 5
<数字 >→ 6
<数字 >→ 7
<数字 >→ 8
<数字 >→ 9
}
S=<整数 >
约定：
1：用尖括号 <和 >括起的是非终结符，不用尖括号括起来的是终结符号；或者用大写字母表示非终结符号，小写字母表示终结符号
2：可用 G[Z]指出识别符号；如果文法 G没有明确指出识别符号，将第一条产生式的左部的非终结符号称为识别符号
3：如果 A→ α1,A→ α2,A→ α3,A → α4,··· A→ αk
是所有以 A为左部的产生式（称它们为 A的产生式），可以写成
A→ α1|α2|α3|α4··· |αk,称 α1,α2,α3,α4···,αk 为 A的选择
（或候选式）
例,<整数 >→ <正负号 ><无符号整数 >|<无符号整数 >
<正负号 >→ +|-
<无符号整数 >→ <无符号整数 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
定义 2.14
设 G是一文法，如果对于某些符号串 α1,α2能写现出
β1=α1Aα2,β2=α1γα2且 A → γ是 G中的一条规则，则说符号串 β1
直接推导到 β2,或说,β2是 β1的直接推导 (一步推导），或说，
β2归约到 β1，记作 β1=>β2
例,设有文法 G[<整数 >]:
<整数 >→ <正负号 ><无符号整数 >|<无符号整数 >
<正负号 >→ +|-
<无符号整数 >→ <无符号整数 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
试推导出 2006
<整数 >=><无符号整数 >=><无符号整数 ><数字 >=>
<无符号整数 ><数字 ><数字 >=><无符号整数 ><数字 ><数字 ><数字 >=><数字 ><数字 ><数字 ><数字 >=>2<数字
><数字 ><数字 >=>20<数字 ><数字 >=>200<数字
>=>2006
定义 2.15
如果存在直接推导的序列 α1=>α2=>α3=>α4··· =>αn,则称 α这个系列是从 α1至 αn 的一个推导，若存在一个从 α1至 αn
的一个推导，则称 α1可推导（长度推导,+推导）到 αn 或者说,αn 可归约到 α1，记作 α1=+=>αn
例,<整数 >=+=>2006
定义 2.16 如果对于符号串 α和 β有 α=+=>β或 α=β则记作
α=*=>β，称 α广义推导（ *推导）出 β
例,对文法 G[<整数 >]有 <整数 >=*=>2006
例：文法 G[<整数 >]有 <整数 >=*=><整数 >
例,<句子 >=*=>the big cat ate the mouse
定义 2.17
设 G[S]是一文法，如果符号串 α是从识别符号推导出来的，
即有 S=*=>α,α∈ （ Vt∪ Vn） *，则称 α是文法 G[S]的句型。若
α仅由终结符号组成，即 α∈ Vt*，则称 α为 G[S]的句子。
例,设有文法 G[<整数 >]:
<整数 >→ <数字串 >
<数字串 >→ <数字串 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
显然 0000,2006,123456789,<数字串 ><数字 ><数字 >都是 G[<整数 >]文法的句型,其中 0000,2006,123456789是 G
的句子而 3<数字串 >,<数字 ><整数 >不是句型定义 2.18
文法 G所产生的语言定义为：
L（ G） ={α|S=*=>α且 α∈ Vt*}。
例,L（ G[<整数 >]） ={一切包括前导零的无符号整数 }
定义 2.19
若 L（ G1） = L（ G2），则称 G1,G2是等价的例：设 G1[<整数 >]）：
<整数 >→ <数字串 >
<数字串 >→ <数字串 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
设 G2[<整数 >]）：
<整数 >→ <数字串 >
<数字串 >→ <数字串 > 0| <数字串 > 1| <数字串 > 2| <数字串 > 3| <数字串 > 4| <数字串 > 5| <数字串 > 6| <数字串 > 7|
<数字串 > 8| <数字串 > 9 |0|1|2|3|4|5|6|7|8|9
则 L（ G1） = L（ G2）
由此可以看出，文法描述的语言是该文法一切句子的集合。
从上还可以看出，一个语言是在某特定字母表上按一定的规则构成的符号串集合。显然不符合规则的符号串不能称为语言。
构成语言的三个要点：
1．字母表 也即字符集，它规定了语言中所允许的字符或基本符号
2．目标 这是一个语言最终要达到或处理的目标
3．规则 规则指如何从字母表中的字符或基本符号构成目标文法提供了三个要点。
1．在语言的设计和编译器的编写方面，文法都提供了极大的优点：
2．文法给出了精确的，也于理解的语言语法说明设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成真正的目标代码和错误诊断都是有用的。
3．语言也是逐步完善的，需要补充新的结构和完成附加任务。
如果存在以语法为基础的语言的实现，这些新结构的加入就更方便了。
语言的特征：
1．一种语言需借助于另一种语言来描述
2．语法是以有穷的方式来描述潜在无穷句子集合的手段
3．语法上的正确不能保证语义上的正确
2.1.３ 推导与递归定义 2.20
如果每次推导最左非终结符称最左推导，记为 α=l=>β
定义 2.21
如果每次推导最右非终结符称最右推导，最右推导又称为规范推导，记为 α=r=>β，由最右推导得出的句型称为右句型又称规范句型递归规则与递归文法由于语言通常是无穷的而文法是有限的，用有限的文法定义无穷的语就必须使用递归定义。
递归规则若文法中存在规则
A→ αAβ
这种左部和右部具有相同的非终结符号的规则称为直接递归规则或称递归规则。这种递归称为规则递归。
若 A→ Aα，即为左递归规则；
若 A→ αA，即为右递归规则；
若 A→ αAβ(α,β≠ε），即为自嵌套规则。
递归文法有时文法中不含有直接的递归规则，但通过若干推导仍能得到递归，这种递归称为间接递归或文法递归，含有递归的文法被称为递归文法。
如：
A→ Bα
B→ Aβ
则 A=>Bα=> Aβα
2.1.4 文法的分类形式语言自 1956年乔姆斯基（ Chomsky）进行描述以来，
得到了很大的发展。乔姆斯基从理论上讨论了语言和文法，按照文法规则的不同定义形式进行分类，并且为每一语言构造象自动机一样的识别器。形式语言的理论形成和发展对计算机科学有着深刻的影响，特别是对程序设计语言的设计技术、编译实现都有重大影响。
乔姆斯基把文法分成四种类型，即 0型,1型,2型和 3型文法。
设 G=（ Vn,Vt,P,S）如果它的每个产生式 α→ β是这样一种结构,α∈ （ Vn∪ Vt ） *且至少含有一个非终结符，而 β∈
（ Vn∪ Vt V） *，则 G是个 0型文法。
0型文法也称短语文法。一个非常重要的理论结果是,0型文法的能力相当于图灵机
（ Turing）。或者说；任何 0型语言都是递归可枚举的；反之，
递旧可枚举集必定是一个 0型语言。
设 G=（ Vn,Vt,P,S）为一文法，若 P中的每一个产生式
α→ β除 S→ ε外均满足 |β|≥|α|，则文法 G是 1型或上下文有关文法。
可以证明满足 |β|≥|α|的文法都存在规则均形如 αAβ→ αγβ的等价的文法,α,β不都空，意为非终结符 A在 α,β这样的上下文条件下，允许替换为 γ
设 G= （ Vn,Vt,P,S）,若 P中的每一个产生式 α→ β满足：
α是一非终结符，即,α∈ Vn,β∈ （ Vn∪ Vt ） * 则此文法称为 2
型的或上下文无关文法。
设 G= （ Vn,Vt,P,S）,若 P中的每一个产生式的形式都是
A→ aB或 A→ a，其中 A和 B都是非终结符,a是终结符，则 G是 3
型文法或正规文法。三型文法又分左线性和右线性的。如每一个产生式的形式都是 A→ aB或 A→ a 称为右线性的；如每一个产生式的形式都是 A→ Ba或 A→ a 称为左线性的。
0型文法,1型文法,2型文法,3型文法对应的自动机分别为图灵机、线性界限自动机、下推自动机、有限自动机显然,3型文法即 2型文法,1型文法,0型文法
2型文法即 1型文法,0型文法
1型文法即 0型文法例 1：写出语言 L={aibjck|i,j,k≥1}的文法
S→ aS|aB B→ bB|bC C→ cC|c
例 2：写出语言 L={aibick|i,k≥1}的文法
S→ AC A→ aAb|ab C→ cC|c
例 3：写出语言 L={aibici|i≥1}的文法
S→ aSBC|aBC
CB→ BC aB→ ab bB→ bb bC→ bc cC→ cc
注意：
虽然 3型文法是 0型文法的特例,但 0型文法描述的语言不一定比
3型文法描述的语言丰富
2.2 句型分析所谓句型分析是指给定一个字符串判定是否是文法上定义的句子。在日常生活中语言（无论中文、英文）都是上下文有关。实际上程序设计语言也是上下文有关的。如,GOTO <
标号 > → GOTO无符号整数 ;标识符的前说明后使用问题，但程序设计语言中的大部分规则是可以写成上下文无关文法，上下文无关文法有足够的能力描述现今程序设计语言的语法结构，
比如描述算术表达式，描述各种语句等等。
由于上下文无关文法不必考虑这所处的上下文，计算机实现比较方便，因而在程序设计语言的识别中较多地采用下文无关文法，今后如不特别指出的文法均为上下文无关的文法。
2.2.1 语法树如果把推导的过程用一种直观的图形表示就形成了一棵树，
即语法树．也称推导树或分析树。
例：设 G[S]：
S→ AB A→ aAb|ab B→ cBd|cd
关于句子的推导为：
s=>Ab=>AcBd=>Accdd=>abccdd
其构造语法树如下,
注意树中的概念和文法的关系：
1．结点 表示一个文法符号
2．根 表示识别符号
3．边 表示存在一个推导
4．分支 表示存在这样一条产生式
5．子树 表示若干推导
6．末端结点 表示相应的句型定义 2.22
如果对于某文法的同一句子存在不同的语法树，则称句子的二义性的。包含二义性句了的文法称为二义性文法，否同称该文法为无二义性的定义 2.23
如果对于某语言不存在无二义性文法，则称该语言是二义性的注意：目前人们已经证明，二义性部题是不可判定的。即，不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义 的,
例：设有文法 G[E]：
E→ E+E|E*E|（ E） |i
证明该文法是二义性的由于对于句子 i*i+i有可见，文法 G[E]的句子 i*i+i有两种不同的语法树，故该文法是二义性的注意：文法的二义性和语言的二义性是两个不同的概念。
因为 对于同一语言可能有两个不同的文法 G1和 G2，一个是二义性的，但另一个却不是二义性的。
例,G1[E]:
E→ E+E|E*E|(E)|i
G2[E]:
E→ E+T|T
T→ T*F|F
F→ (E)|i
对于非二义性文法来说，最左（最右）推导是唯一的。
消除二义性如果语言不是二义性的，那么就存在一组非二义性文法规则，
定义该语言，换句话说，有些文法是不能通过改造文法消支其二义性的，也有些文法的二义性是可以通过重写文法而消除二义性。
例,S→ if E then S|if E then S else S|b
对于句型
if E then E then S else S
存在二棵不同的语法树，故该文法是二义性的。
在实际应用中靠近的 then和 else先行匹配，为了识别方便可以消去二义性把该文法改写成：
S→ S1|S2
S1→ if E then S1 else S1|b
S2→ if E then S1|if E then S1 else S2
2.2.2 文法的约定文法虽然规定的语言的形成方法,但文法中有的规则会对分析带来麻烦,有会带来灾难，为此需对文法中的规则加以限制。
有害规则定义 2.23
文法 G中形如 U→ U的规则，称为有害规则。
这种规则没有增加句子的集合，给文法增加了二义性，给今后的分析带来不必要的麻烦，删除这样的规则没有形响到文法定义的语言。
例：设 G[S]：
S→ S|DS|D
D→ 0|1
删除有害规则 S→ S后的新文法
G'[S]：
S→ DS|D
D→ 0|1
显然有 L(G[S])=L(G'[S])，
定义 2.24
文法 G中某一规则，其右部的非终结符为 U，若满足下列条件之一，则称该规则为多余规则。
（ 1）不能从识别符号推导出使用 U的句型,即从除开始符号外不出现在该文法的任何其它的规则的右部,。
（ 2）若在推导中使用该规则，则不能推出终结符号串。
例：设 G[S]：
(1) S → Be
(2) B → Ce
(3) B → Af
(4) A → Ae
(5) A → e
(6) C → Cf
(7) D → f
由于非终结符 D不在规则右部出现，非终结符 C不能推导成终结符号串，故都是多余规则，应删除。（ 6）、（ 7）删除后（ 2）
也不能推导成终结符号串也删除。
故 G‘[S]：
(1) S → Be
(2) B → Af
(3) A → Ae
(4) A → e
当一个上下文无关的文法中不含有害规则和多余规则时，称这个文法是压缩了的文法，在以后各章中介绍的文法不特指都是压缩了的文法。
2.2.2 句型的分析方法对于一个上下文无关文法，语法树就是该文法上的句型的推导过程的几何表示。语法树能将所给句型的结构很直观地显示出来了。利用语法树可直接对句型进行分析。这里所说的句型分析问题，就是对所给定的符号串分析是否是文法定义的句型。句型的分析也就是否能构造出推导过程。进一步说，当给定一个符号串时，试图按照某文法的规则为该符号串构造推导或语法树，以此识别出它是该文法的一个句型；当符号串全部由终结符号组成时，就是识别输入符号串是否是某文法的一个句子。
对于程序设汁语言来说，要识别输入符号串是否是程序设计语言的程序。程序是定义实际上就是程序设计语言的文法的一个句子。句型分析是一个识别输入符号串是否为语法上正确的程序的过程、在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。
由于输入符号串是从左到右的，所以我们介绍的分析算法都称为从左到右的分析算法。 这种分析算法又可分成两大类：
即自顶向下的和自底向上的分析方法。
自顶向下的分析方法自顶向下的分析方法也称为自上而下的分析方法,它是从文法的开始符号出发，反复使用各种产生式，寻找,匹配,于输入符号串的推导至输入符号串。
例,G[S]：
S→ cAd
A→ ab
A→ a
识别输入串 w=cabd是否该文法的句子。
自底向上的分析方法自底向上的分析方法又称自下而上的方法，它是从输入符号用开始，逐步进行,归约,,直至归约到文法的开始符号。
例,设有文法
G[S]：
S→ cAd
A→ ab
A→ a
识别输入串 w=cabd是否该文法的句子。
句型分析的有关问题在自顶向下的分析方法中，需解决的问题是形如
A→ α1|α2|α3|α4···|αk的规则究竟选择那一个候选式。
在自底向上的分析方法中，需解决的问题是如在文法中存在形如 A→ α和 B→ α的规则，并在分析过程中发现形如 α的符号串是把它替换成 A还是 B？
例,设 G[S]:
S→ aBC
B→ ib|b
C→ DE|FG
D→ d
E→ eh
F→ de
G→ t
当分析句子 abdet时,对于 C规则很难确定先用 DE还是 FG
例,G[S]:S→ aAcBe
A→ b
A→ Ab
B→ b
识别输入符号串 abbbcbe
栈 输入符号串
a bbcde
ab bcde
aA bcde
aAb cde
aA cde
aAc de
aAcb e
aAcB e
aAcBe
S
定义 2.25
设 G[S]是一个文法,αβδ是文法 G的一个句型，如果有
S=*=>αAδ且 A=+=>β则称 β是句型 αβδ相对于非终结符 A的短语、特别是，如果有 A→ β则称 β是句型 αβδ相对于规则 A→ β的直接短语（简单短语）
上述定义的意思为某一句型中的子符号串归约后的符号串仍为句型即 S=*=>αAδ=+=>αβδ
定义 2.26
一个句型的最左直接短语称为该句型的句柄。
例：写出 G[<整数 >]:
<整数 >→ <数字串 >
<数字串 >→ <数字串 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
中的句型 <数字串 > <数字 >3的短语、简单短语和句柄短语,3 <数字串 > <数字 > <数字串 > <数字 > 3
简单短语,<数字串 > <数字 > 3
句柄 <数字串 > <数字 >
而 <数字串 >,<数字 > 3不是短语每次归约句柄的归约方式，称为规范归约，归范归约又称最左归约，它是最右推导的逆过程（其分析过程中均为右句型）。
在规范归约中，由于每次归约的是句柄，所在句柄后面不会出现非终结符号，基于这一点，在采用的所谓移入归约法中，
在移入归约过程中，一旦发现句柄即可用规则的左部替换，这种方法犹如,剪句柄,。归约过程实质上也是语法树的构造过程。
下面介绍语法树的特性：
（ 1）对于每棵语法树至少存在一个推导
（ 2）对于每个推导，都有一个相应的语法树，但不同的推导可能有相同的语法树
（ 3）树的每一分支表示一个直接推导，在此推导中，可用这一分支的结点取代这一分支的名字，这样在文法中存在这样的规则，其左部是分支的名字,而其右部是分支结点的符号
（ 4）树的末端结点形成所要推导的句型。
（ 5）设 A是句型 αβδ的某一子树的根，其中 β是形成子树的末端结点的符号串，因此,β是句型 αβδ相对于 A的短语，如果子树是单个分支时，那么就是简单短语定理若 L是由文法 G=（ Vn,Vt,P,S）产生的语言,P中的每一个产生式的形式均为 A→ α，其中 A∈ Vn,α∈ （ Vn∪ Vt） *（ α即可能为 ε），则 L能由这样的一种文法产生，即每一个产生式或者为 A→ β形式，其中 A为一非终结符，即 A∈ Vn,α∈
（ Vn∪ Vt） +，，或者为 S→ ε形式，且 S不出现在任何产生式的右边。
定理如果 G=（ Vn,Vt,P,S）是一个上下文有关文法，则存在另一个上下文有关文法 G1，它所产生的语言与 G产生的相同，其中 G1的开始符号不出现在 G1的任何产生式的右边。又如果 G是一个上下文无关文法，也能找到这样一个上下文无关文法 G1，
如果 G是一个正规文法，则也能找到这样一个正规文法 G1。
例,G[E]:E→ E+T|T
T→ T*F|F
F→ (E)|i
试求出句子 i+i*i+i的短语、
简单短语和句柄故短语为,i+i*i+i i+i*i i i*i i i i
简单 短语为 i i i i
句柄为 i
2.1 文法的基本概念一个程序设计语言是一个记号系统，如自然语言一样，
它的完整的定义应包括语法和语义两方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序，目前在程序设计语言的识别中广泛使用的是上下文无关的文法。在这理主要介绍文法和语言的概念。
例：设有文法：
<句子 >→ <主语 ><谓语 >
<主语 >→ <冠词 ><形容词 ><名词 >
<冠词 >→ the
<形容词 >→ big
<谓语 >→ <动词 ><直接宾语 >
<动词 >→ ate|caught
<直接宾语 >→ <冠词 ><名词 >
<名词 >→ mouse|cat
则：
<句子 >=><主语 ><谓语 >=><冠词 ><形容词 ><名词 ><谓语
>
=>the<形容词 ><名词 ><谓语 >=> the big<名词 ><谓语
>
=>the big cat <谓语 >=>the big cat <动词 ><直接宾语 >
=>the big cat ate<直接宾语 >=>the big cat ate<冠词 ><
名词 >=>the big cat ate the <名词 > =>the big cat ate the
mouse
2.1.1 符号和符号串定义 2.1
字母表是有穷非空集合。用 Σ表示。
例：无符号二进制数的字母表为 {0,1}
C语言的字母表为字母、数字和若干专用符号组成的符号集定义 2.2
符号串是由字母表中的符号组成的有穷序列，又称字符串、串。
例,a,b,c,ba,bbac,caacb,···等都是字母表 {a,b,c}上的符号串定义 2.3
不包含任何字符串的空符号串用 ε表示定义 2.4
符号串 x的长度，即符号串 x中的字符用 |x|表示 (读作 x的长度 )
例,|abc|=3 |a|=1 |ε|=0
定义 2.5
设非空符号串 u=xvy,其中 v≠ε,则称 v为 u的子串,若 |u|>
|v|则称 v为 u的真子串定义 2.6
如果 z=xy是一个符号串，则 x是 z和头，而 y是 z的尾。如果 x
是非空的，那么 y是固有尾；同样如果 y非空，那么 x是固有头。
例：设 z=abc，那么 z的头是 ε,a,ab,abc。除 abc外，其它都是固有头。 z的尾是 ε,c,bc,abc。 z的固有尾是 ε,c,bc
定义 2.7
设 x,y 是同一字母表上的两个符号串，把 y的符号写在 X的符号之后得到的符号串，称为的连接。记为 xy
例,x=ab,y=wabu 则
z=xy=abywabu
显然,|x|+|y|=|z|
εx=xε=x
定义 2.8
设 x是符号串，把 x自身连接 n次得到符号串 z,即 z=xx···xx(n
个 x)，称为符号串 x的方幂,记为 z=xn
例,x0=ε x1=x x2=xx x3=xxx ···
定义 2.9
符号串集合若集合 A中的一切元素都是其字母表上的符号串，则称 A为该字母表上的符号串集合。
注意,ε,{ε} 和 Φ （表示空集）的区别定义 2.10
两个符号串集合 A和 B的乘积 AB定义为：
AB={xy|x∈ A且 y∈ B}
例：设 A={a,bc},B=｛ b,c,da｝则集合
AB={ab,ac,ada,bcb,bcc,bcda｝。
注意：由于 εx=xε=x 因此 {ε}A=A{ε}=A,但 ΦA=AΦ=Φ
则：
A0={ε}
A1=A
A2=AA
An=An-1A=AAn-1（ n>0）
显然：
Σ1是字母表中的所有单个字符组成的字符串
Σ2是所有由字母表中二个的字符组成的字符串
Σ3是所有由字母表中三个的字符组成的字符串
Σn是所有由字母表中长度为 n的字符串集合定义 2.11
A的闭包 A*=A0∪ A1∪ A2∪ ···
A的正闭包 A+= A1∪ A2∪ A3∪ ···
显然 A+=AA*=A*A A*=A0∪ A+
由于一个字母表上的正闭包包含了该字母表中的符号所能组成的一切符号串，而语言是该字母表上的某些符号串的集合，
因此，某个字母表上的语言是这个字母表上的正闭包的子集，
而且通常是真子集。
例：若 Σ={0,1},则 Σ*=｛ ε,0,1,00,01,10,11,000,001，
010,··· ｝
例：令 L={A,B,C,···,Z,a,b,···,z},D={0,1,··· 9}
1.L∪ D 2.LD 3.L4 4,L(L∪ D)* 5,D+ 6.D+∪ L*则分别代表什么集合？
1.字母或数字（包括 ε） 的集合
2.由字母开头后面跟一个数字的集合
3.由４个字母组成的字符串的集合
4.由字母开头后面是字母数字（可省略）的集合
5.数字串集合
6.数字串和字母串集合（包括 ε）
约定：当对符号串 z=xy的头感兴趣而对其余部分不感兴趣时，
可以采用省略写法,z=x···；如果只是为了强调 x在符号串 z中的某处出现，则可表示为,z=···x···；如果只是为了强调 x在符号串 z中的末尾出现，则可表示为,z=···x；
2.1.2 文法和语言的形式定义语言是字母表上的某些符号串集合，在这集合中的每个符号串都是按一定规则生成的。其规则最常用的是重写规则（又称产生式或生成式），它是形如 α→ β或 α：,=β（ α,β）的有序对，（读作 α定义为 β），其中 α称为规则的左部,β称为规则的右部。
定义 2.12
文法 G定义为四元组（ Vn,Vt,P,S）。
其中,
Vn为非终结符号（或语法实体，或变量）集； Vt为终结符号集；
P为产生式（也称规则）的集合；
S称作识别符号或开始符号。它是一个非终结符,至少要在一条规则中作为左部出现。
Vn,Vt和 P是非空有穷集，
显然,Vn和 Vt不含公共的元素，即 Vn∩ Vt =Φ
定义 2.13
用 V表示 Vn∪ Vt。 V称为文法 G的字汇表。
例,文法 G=（ Vn,Vt,P,S），其中 Vn={S},Vt={0,l｝,
P=｛ S→ OS1,S→ 01｝。这里，非终结符集中只含一个元素 S;
终结符集由两个元素 0和 1组成；有两条产生式；开始符号是 S。
例,文法 G=（ Vn,Vt,P,S）
其中,
Vn={<整数 >,<正负号 >,<无符号整数 >,<数字 >}
Vt={+,-,0,1,2,3,4,5,6,7,8,9}
P={<整数 >→ <正负号 ><无符号整数 >
<整数 >→ <无符号整数 >
<正负号 >→ +
<正负号 >→ -
<无符号整数 >→ <无符号整数 ><数字 >
<无符号整数 >→ <数字 >
<数字 >→ 0
<数字 >→ 1
<数字 >→ 2
<数字 >→ 3
<数字 >→ 4
<数字 >→ 5
<数字 >→ 6
<数字 >→ 7
<数字 >→ 8
<数字 >→ 9
}
S=<整数 >
约定：
1：用尖括号 <和 >括起的是非终结符，不用尖括号括起来的是终结符号；或者用大写字母表示非终结符号，小写字母表示终结符号
2：可用 G[Z]指出识别符号；如果文法 G没有明确指出识别符号，将第一条产生式的左部的非终结符号称为识别符号
3：如果 A→ α1,A→ α2,A→ α3,A → α4,··· A→ αk
是所有以 A为左部的产生式（称它们为 A的产生式），可以写成
A→ α1|α2|α3|α4··· |αk,称 α1,α2,α3,α4···,αk 为 A的选择
（或候选式）
例,<整数 >→ <正负号 ><无符号整数 >|<无符号整数 >
<正负号 >→ +|-
<无符号整数 >→ <无符号整数 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
定义 2.14
设 G是一文法，如果对于某些符号串 α1,α2能写现出
β1=α1Aα2,β2=α1γα2且 A → γ是 G中的一条规则，则说符号串 β1
直接推导到 β2,或说,β2是 β1的直接推导 (一步推导），或说，
β2归约到 β1，记作 β1=>β2
例,设有文法 G[<整数 >]:
<整数 >→ <正负号 ><无符号整数 >|<无符号整数 >
<正负号 >→ +|-
<无符号整数 >→ <无符号整数 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
试推导出 2006
<整数 >=><无符号整数 >=><无符号整数 ><数字 >=>
<无符号整数 ><数字 ><数字 >=><无符号整数 ><数字 ><数字 ><数字 >=><数字 ><数字 ><数字 ><数字 >=>2<数字
><数字 ><数字 >=>20<数字 ><数字 >=>200<数字
>=>2006
定义 2.15
如果存在直接推导的序列 α1=>α2=>α3=>α4··· =>αn,则称 α这个系列是从 α1至 αn 的一个推导，若存在一个从 α1至 αn
的一个推导，则称 α1可推导（长度推导,+推导）到 αn 或者说,αn 可归约到 α1，记作 α1=+=>αn
例,<整数 >=+=>2006
定义 2.16 如果对于符号串 α和 β有 α=+=>β或 α=β则记作
α=*=>β，称 α广义推导（ *推导）出 β
例,对文法 G[<整数 >]有 <整数 >=*=>2006
例：文法 G[<整数 >]有 <整数 >=*=><整数 >
例,<句子 >=*=>the big cat ate the mouse
定义 2.17
设 G[S]是一文法，如果符号串 α是从识别符号推导出来的，
即有 S=*=>α,α∈ （ Vt∪ Vn） *，则称 α是文法 G[S]的句型。若
α仅由终结符号组成，即 α∈ Vt*，则称 α为 G[S]的句子。
例,设有文法 G[<整数 >]:
<整数 >→ <数字串 >
<数字串 >→ <数字串 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
显然 0000,2006,123456789,<数字串 ><数字 ><数字 >都是 G[<整数 >]文法的句型,其中 0000,2006,123456789是 G
的句子而 3<数字串 >,<数字 ><整数 >不是句型定义 2.18
文法 G所产生的语言定义为：
L（ G） ={α|S=*=>α且 α∈ Vt*}。
例,L（ G[<整数 >]） ={一切包括前导零的无符号整数 }
定义 2.19
若 L（ G1） = L（ G2），则称 G1,G2是等价的例：设 G1[<整数 >]）：
<整数 >→ <数字串 >
<数字串 >→ <数字串 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
设 G2[<整数 >]）：
<整数 >→ <数字串 >
<数字串 >→ <数字串 > 0| <数字串 > 1| <数字串 > 2| <数字串 > 3| <数字串 > 4| <数字串 > 5| <数字串 > 6| <数字串 > 7|
<数字串 > 8| <数字串 > 9 |0|1|2|3|4|5|6|7|8|9
则 L（ G1） = L（ G2）
由此可以看出，文法描述的语言是该文法一切句子的集合。
从上还可以看出，一个语言是在某特定字母表上按一定的规则构成的符号串集合。显然不符合规则的符号串不能称为语言。
构成语言的三个要点：
1．字母表 也即字符集，它规定了语言中所允许的字符或基本符号
2．目标 这是一个语言最终要达到或处理的目标
3．规则 规则指如何从字母表中的字符或基本符号构成目标文法提供了三个要点。
1．在语言的设计和编译器的编写方面，文法都提供了极大的优点：
2．文法给出了精确的，也于理解的语言语法说明设计得漂亮的文法，把结构加于程序设计语言，这些结构对把源程序翻译成真正的目标代码和错误诊断都是有用的。
3．语言也是逐步完善的，需要补充新的结构和完成附加任务。
如果存在以语法为基础的语言的实现，这些新结构的加入就更方便了。
语言的特征：
1．一种语言需借助于另一种语言来描述
2．语法是以有穷的方式来描述潜在无穷句子集合的手段
3．语法上的正确不能保证语义上的正确
2.1.３ 推导与递归定义 2.20
如果每次推导最左非终结符称最左推导，记为 α=l=>β
定义 2.21
如果每次推导最右非终结符称最右推导，最右推导又称为规范推导，记为 α=r=>β，由最右推导得出的句型称为右句型又称规范句型递归规则与递归文法由于语言通常是无穷的而文法是有限的，用有限的文法定义无穷的语就必须使用递归定义。
递归规则若文法中存在规则
A→ αAβ
这种左部和右部具有相同的非终结符号的规则称为直接递归规则或称递归规则。这种递归称为规则递归。
若 A→ Aα，即为左递归规则；
若 A→ αA，即为右递归规则；
若 A→ αAβ(α,β≠ε），即为自嵌套规则。
递归文法有时文法中不含有直接的递归规则，但通过若干推导仍能得到递归，这种递归称为间接递归或文法递归，含有递归的文法被称为递归文法。
如：
A→ Bα
B→ Aβ
则 A=>Bα=> Aβα
2.1.4 文法的分类形式语言自 1956年乔姆斯基（ Chomsky）进行描述以来，
得到了很大的发展。乔姆斯基从理论上讨论了语言和文法，按照文法规则的不同定义形式进行分类，并且为每一语言构造象自动机一样的识别器。形式语言的理论形成和发展对计算机科学有着深刻的影响，特别是对程序设计语言的设计技术、编译实现都有重大影响。
乔姆斯基把文法分成四种类型，即 0型,1型,2型和 3型文法。
设 G=（ Vn,Vt,P,S）如果它的每个产生式 α→ β是这样一种结构,α∈ （ Vn∪ Vt ） *且至少含有一个非终结符，而 β∈
（ Vn∪ Vt V） *，则 G是个 0型文法。
0型文法也称短语文法。一个非常重要的理论结果是,0型文法的能力相当于图灵机
（ Turing）。或者说；任何 0型语言都是递归可枚举的；反之，
递旧可枚举集必定是一个 0型语言。
设 G=（ Vn,Vt,P,S）为一文法，若 P中的每一个产生式
α→ β除 S→ ε外均满足 |β|≥|α|，则文法 G是 1型或上下文有关文法。
可以证明满足 |β|≥|α|的文法都存在规则均形如 αAβ→ αγβ的等价的文法,α,β不都空，意为非终结符 A在 α,β这样的上下文条件下，允许替换为 γ
设 G= （ Vn,Vt,P,S）,若 P中的每一个产生式 α→ β满足：
α是一非终结符，即,α∈ Vn,β∈ （ Vn∪ Vt ） * 则此文法称为 2
型的或上下文无关文法。
设 G= （ Vn,Vt,P,S）,若 P中的每一个产生式的形式都是
A→ aB或 A→ a，其中 A和 B都是非终结符,a是终结符，则 G是 3
型文法或正规文法。三型文法又分左线性和右线性的。如每一个产生式的形式都是 A→ aB或 A→ a 称为右线性的；如每一个产生式的形式都是 A→ Ba或 A→ a 称为左线性的。
0型文法,1型文法,2型文法,3型文法对应的自动机分别为图灵机、线性界限自动机、下推自动机、有限自动机显然,3型文法即 2型文法,1型文法,0型文法
2型文法即 1型文法,0型文法
1型文法即 0型文法例 1：写出语言 L={aibjck|i,j,k≥1}的文法
S→ aS|aB B→ bB|bC C→ cC|c
例 2：写出语言 L={aibick|i,k≥1}的文法
S→ AC A→ aAb|ab C→ cC|c
例 3：写出语言 L={aibici|i≥1}的文法
S→ aSBC|aBC
CB→ BC aB→ ab bB→ bb bC→ bc cC→ cc
注意：
虽然 3型文法是 0型文法的特例,但 0型文法描述的语言不一定比
3型文法描述的语言丰富
2.2 句型分析所谓句型分析是指给定一个字符串判定是否是文法上定义的句子。在日常生活中语言（无论中文、英文）都是上下文有关。实际上程序设计语言也是上下文有关的。如,GOTO <
标号 > → GOTO无符号整数 ;标识符的前说明后使用问题，但程序设计语言中的大部分规则是可以写成上下文无关文法，上下文无关文法有足够的能力描述现今程序设计语言的语法结构，
比如描述算术表达式，描述各种语句等等。
由于上下文无关文法不必考虑这所处的上下文，计算机实现比较方便，因而在程序设计语言的识别中较多地采用下文无关文法，今后如不特别指出的文法均为上下文无关的文法。
2.2.1 语法树如果把推导的过程用一种直观的图形表示就形成了一棵树，
即语法树．也称推导树或分析树。
例：设 G[S]：
S→ AB A→ aAb|ab B→ cBd|cd
关于句子的推导为：
s=>Ab=>AcBd=>Accdd=>abccdd
其构造语法树如下,
注意树中的概念和文法的关系：
1．结点 表示一个文法符号
2．根 表示识别符号
3．边 表示存在一个推导
4．分支 表示存在这样一条产生式
5．子树 表示若干推导
6．末端结点 表示相应的句型定义 2.22
如果对于某文法的同一句子存在不同的语法树，则称句子的二义性的。包含二义性句了的文法称为二义性文法，否同称该文法为无二义性的定义 2.23
如果对于某语言不存在无二义性文法，则称该语言是二义性的注意：目前人们已经证明，二义性部题是不可判定的。即，不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义 的,
例：设有文法 G[E]：
E→ E+E|E*E|（ E） |i
证明该文法是二义性的由于对于句子 i*i+i有可见，文法 G[E]的句子 i*i+i有两种不同的语法树，故该文法是二义性的注意：文法的二义性和语言的二义性是两个不同的概念。
因为 对于同一语言可能有两个不同的文法 G1和 G2，一个是二义性的，但另一个却不是二义性的。
例,G1[E]:
E→ E+E|E*E|(E)|i
G2[E]:
E→ E+T|T
T→ T*F|F
F→ (E)|i
对于非二义性文法来说，最左（最右）推导是唯一的。
消除二义性如果语言不是二义性的，那么就存在一组非二义性文法规则，
定义该语言，换句话说，有些文法是不能通过改造文法消支其二义性的，也有些文法的二义性是可以通过重写文法而消除二义性。
例,S→ if E then S|if E then S else S|b
对于句型
if E then E then S else S
存在二棵不同的语法树，故该文法是二义性的。
在实际应用中靠近的 then和 else先行匹配，为了识别方便可以消去二义性把该文法改写成：
S→ S1|S2
S1→ if E then S1 else S1|b
S2→ if E then S1|if E then S1 else S2
2.2.2 文法的约定文法虽然规定的语言的形成方法,但文法中有的规则会对分析带来麻烦,有会带来灾难，为此需对文法中的规则加以限制。
有害规则定义 2.23
文法 G中形如 U→ U的规则，称为有害规则。
这种规则没有增加句子的集合，给文法增加了二义性，给今后的分析带来不必要的麻烦，删除这样的规则没有形响到文法定义的语言。
例：设 G[S]：
S→ S|DS|D
D→ 0|1
删除有害规则 S→ S后的新文法
G'[S]：
S→ DS|D
D→ 0|1
显然有 L(G[S])=L(G'[S])，
定义 2.24
文法 G中某一规则，其右部的非终结符为 U，若满足下列条件之一，则称该规则为多余规则。
（ 1）不能从识别符号推导出使用 U的句型,即从除开始符号外不出现在该文法的任何其它的规则的右部,。
（ 2）若在推导中使用该规则，则不能推出终结符号串。
例：设 G[S]：
(1) S → Be
(2) B → Ce
(3) B → Af
(4) A → Ae
(5) A → e
(6) C → Cf
(7) D → f
由于非终结符 D不在规则右部出现，非终结符 C不能推导成终结符号串，故都是多余规则，应删除。（ 6）、（ 7）删除后（ 2）
也不能推导成终结符号串也删除。
故 G‘[S]：
(1) S → Be
(2) B → Af
(3) A → Ae
(4) A → e
当一个上下文无关的文法中不含有害规则和多余规则时，称这个文法是压缩了的文法，在以后各章中介绍的文法不特指都是压缩了的文法。
2.2.2 句型的分析方法对于一个上下文无关文法，语法树就是该文法上的句型的推导过程的几何表示。语法树能将所给句型的结构很直观地显示出来了。利用语法树可直接对句型进行分析。这里所说的句型分析问题，就是对所给定的符号串分析是否是文法定义的句型。句型的分析也就是否能构造出推导过程。进一步说，当给定一个符号串时，试图按照某文法的规则为该符号串构造推导或语法树，以此识别出它是该文法的一个句型；当符号串全部由终结符号组成时，就是识别输入符号串是否是某文法的一个句子。
对于程序设汁语言来说，要识别输入符号串是否是程序设计语言的程序。程序是定义实际上就是程序设计语言的文法的一个句子。句型分析是一个识别输入符号串是否为语法上正确的程序的过程、在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。
由于输入符号串是从左到右的，所以我们介绍的分析算法都称为从左到右的分析算法。 这种分析算法又可分成两大类：
即自顶向下的和自底向上的分析方法。
自顶向下的分析方法自顶向下的分析方法也称为自上而下的分析方法,它是从文法的开始符号出发，反复使用各种产生式，寻找,匹配,于输入符号串的推导至输入符号串。
例,G[S]：
S→ cAd
A→ ab
A→ a
识别输入串 w=cabd是否该文法的句子。
自底向上的分析方法自底向上的分析方法又称自下而上的方法，它是从输入符号用开始，逐步进行,归约,,直至归约到文法的开始符号。
例,设有文法
G[S]：
S→ cAd
A→ ab
A→ a
识别输入串 w=cabd是否该文法的句子。
句型分析的有关问题在自顶向下的分析方法中，需解决的问题是形如
A→ α1|α2|α3|α4···|αk的规则究竟选择那一个候选式。
在自底向上的分析方法中，需解决的问题是如在文法中存在形如 A→ α和 B→ α的规则，并在分析过程中发现形如 α的符号串是把它替换成 A还是 B？
例,设 G[S]:
S→ aBC
B→ ib|b
C→ DE|FG
D→ d
E→ eh
F→ de
G→ t
当分析句子 abdet时,对于 C规则很难确定先用 DE还是 FG
例,G[S]:S→ aAcBe
A→ b
A→ Ab
B→ b
识别输入符号串 abbbcbe
栈 输入符号串
a bbcde
ab bcde
aA bcde
aAb cde
aA cde
aAc de
aAcb e
aAcB e
aAcBe
S
定义 2.25
设 G[S]是一个文法,αβδ是文法 G的一个句型，如果有
S=*=>αAδ且 A=+=>β则称 β是句型 αβδ相对于非终结符 A的短语、特别是，如果有 A→ β则称 β是句型 αβδ相对于规则 A→ β的直接短语（简单短语）
上述定义的意思为某一句型中的子符号串归约后的符号串仍为句型即 S=*=>αAδ=+=>αβδ
定义 2.26
一个句型的最左直接短语称为该句型的句柄。
例：写出 G[<整数 >]:
<整数 >→ <数字串 >
<数字串 >→ <数字串 ><数字 >|<数字 >
<数字 >→ 0|1|2|3|4|5|6|7|8|9
中的句型 <数字串 > <数字 >3的短语、简单短语和句柄短语,3 <数字串 > <数字 > <数字串 > <数字 > 3
简单短语,<数字串 > <数字 > 3
句柄 <数字串 > <数字 >
而 <数字串 >,<数字 > 3不是短语每次归约句柄的归约方式，称为规范归约，归范归约又称最左归约，它是最右推导的逆过程（其分析过程中均为右句型）。
在规范归约中，由于每次归约的是句柄，所在句柄后面不会出现非终结符号，基于这一点，在采用的所谓移入归约法中，
在移入归约过程中，一旦发现句柄即可用规则的左部替换，这种方法犹如,剪句柄,。归约过程实质上也是语法树的构造过程。
下面介绍语法树的特性：
（ 1）对于每棵语法树至少存在一个推导
（ 2）对于每个推导，都有一个相应的语法树，但不同的推导可能有相同的语法树
（ 3）树的每一分支表示一个直接推导，在此推导中，可用这一分支的结点取代这一分支的名字，这样在文法中存在这样的规则，其左部是分支的名字,而其右部是分支结点的符号
（ 4）树的末端结点形成所要推导的句型。
（ 5）设 A是句型 αβδ的某一子树的根，其中 β是形成子树的末端结点的符号串，因此,β是句型 αβδ相对于 A的短语，如果子树是单个分支时，那么就是简单短语定理若 L是由文法 G=（ Vn,Vt,P,S）产生的语言,P中的每一个产生式的形式均为 A→ α，其中 A∈ Vn,α∈ （ Vn∪ Vt） *（ α即可能为 ε），则 L能由这样的一种文法产生，即每一个产生式或者为 A→ β形式，其中 A为一非终结符，即 A∈ Vn,α∈
（ Vn∪ Vt） +，，或者为 S→ ε形式，且 S不出现在任何产生式的右边。
定理如果 G=（ Vn,Vt,P,S）是一个上下文有关文法，则存在另一个上下文有关文法 G1，它所产生的语言与 G产生的相同，其中 G1的开始符号不出现在 G1的任何产生式的右边。又如果 G是一个上下文无关文法，也能找到这样一个上下文无关文法 G1，
如果 G是一个正规文法，则也能找到这样一个正规文法 G1。
例,G[E]:E→ E+T|T
T→ T*F|F
F→ (E)|i
试求出句子 i+i*i+i的短语、
简单短语和句柄故短语为,i+i*i+i i+i*i i i*i i i i
简单 短语为 i i i i
句柄为 i
