前面我们提到过可以用一张图表示一个句型的推导，这种表示称为语法分析树，
或简称为语法树。语法树有助于理解一个句子语法结构的层次。语法树通常表示成一棵倒立的树，根在上，枝叶在下。语法树的根结由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生出下一代新结，候选式中自左至右的每个符号对应一个新结，并用这些符号标记其相应的新结。每个新结和其父结间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。例如，对于文法(2.1)，关于(i*i+i)的推导(2.2)的语法树如图2.2所示。
E(根) （ E ） E + E E * E i i i 图2.2 语法树
这就是说，一棵语法树表示了一个句型种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。这样的一棵语法树是这些不同推导过程的共性抽象，是它们的代表。
如果我们坚持使用最左(最右)推导，那么，一棵语法树就完全等价于一个最左(最右)推导，这种等价性包括树的步步成长和推导的步步展开之间的完全一致性。但是，一个句型是否只对应唯一的一棵语法树呢?也就是，它是否只有唯一的一个最左(最右)推导呢?不尽然。 3.1.3 形式语言鸟瞰
前面乔姆斯基把文法分成四种类型，即0型，1型，2型，和3型。0型强于1
型，1型强于2型，2型强于3型。这几类文法的差别在于对产生式施加不同的限制。
0型文法：也称短语文法，其能力相当于图灵机。任何0型语言都是递归可枚举
的，反之，递归可枚举集必定是一个0型语言。
1型文法：也称上下文有关文法，对非终结符进行替换时务必联系上下文，并且
一般不允许替换成空串。
2型文法：也称上下文无关文法
3型文法：也称右线性文法，这类文法等价于正规式，所以也称正规文法。只有
下面两种形式的产生式：A→Ba 或A→a。 3.2.1文法等价的概念：
若L(G1)=L(G2),则称文法G1和G2是等价的
例如：下列两个文法是等价的
G1[A]: A 0R A 01 R A1 G2[A]：S 0S1 S 01 因为L(G1)=L(G2)={0n1n|n ≥1}
13
定义：对文法进行变换，使变换后的文法满足某种要求并于原文法等价，这种变换成
为文法的等价变换。 3.2.2、增广文法 定义：设文法G[S]={VN,VT,P,S}，构造文法G‘[S‘]=(VN∪{S‘},VT,P‘,S‘),其中，P‘={A
α|A α ∈P}∪{S‘ S},显然L(G)= L(G‘)，称G‘为文法G的增广文法。 例：[Z]:Z →abZA|a A→b
经等价变换后可得到增广文法G[A?]: Z‘ →Z
Z →abZA|a A→b
3.2.3、提取左因子 定义：若文法中有产生式P→δβ1|δβ2|…|δβn,则称该文发含有左因子δ。其中
P ∈VN ，β1，β2… βn ∈ (VN∪ VT)*。 例：文法[S]: S →iEtS|iEtSeS|a E →b 提取左因子该文法变为： G[S]: S →iEtSS‘|a S‘ →eS|ε E →b 3.2.4、消除左递归
定义：若文法中存在推导：P ?+ Pα,则称该文法含有左递归。若存在产生式P ? P
α,则称该文法含有直