文法和语言的基本知识

2.4 语法树 推导和语法树 1. 语法树对句型的推导过程给出一种图形 表示, 这种表示称为语法树，也称推导树 2.4 语法树 例如 设有文法G[E]:构造句型i*i+i的语法树首先给出句型的推导过程 (最左推导) ：EE+T | E–T | T TT*F | T/F | F F(E) | iEE+TT+TT*F+TF*F+Ti*F+T i*i+Ti*i+Fi*i+i2.4 语法树根据推导过程构造句型i*i+i的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+T ii*i+T ii*i+FFi*i+ii2.4 语法树 由例可知，语法树的构造过程是从 文法的开始符号出发，构造一个推导的 过程因为文法的每一个句型 (句子) 都 存在一 个推导，所以文法的每个句型 (句子) 都存在一棵对应的语法树EE+TE+FE+i T+iT*F+i T*i+iF*i+ii*i+i2.4 语法树 对句型i*i+i，还可给出最右推导： EE+TTT*FFiiFi2.4 语法树 这也就是说，一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程, 包括最左(最右)推导。

2.4 语法树 2. 子树语法树的子 树是由某一结点 连同所有分枝组 成的部分EE+TTT*FFiiFi2.4 语法树 3. 简单子树语法树的 简单子树是指 只有单层分枝 的子树即一 步推导)EE+TTT*FFiiFi2.4 语法树 句型的短语、直接短语和句柄的 直观解释是：短语：子树的末端结点形成的符号串是相对于子树根的短语直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语或者：某子树根经过1步推导而获得 的短语句柄：句型中最左直接短语2.4 语法树短语:ni*i+ini*in第一个in第二个in第三个in三个i都是直接短语n第一个i是句柄 注意:i+i不是句型的短语句子 i*i+iEE+TTT*FFiiFi2.4 语法树 前例 对文法G[S]=({S,A,B},{a,b},P,S) 其中P为：可用语法树非常直观地求出句型baSb 的全部短语，直接短语和句柄SABAAa | bB Ba | Sb2.4 语法树分析 首先根据句型baSb的推导过程画出对 应的语法树如下： Sb 为句型的相对于B的短语、直接短语baSb 为句型的相对于S的短语 ba 为句型的相对于A的短语 a 句型的相对于B的短语、直接短语和句柄SABbBBbaBbaSb SABASbbBSbbaSbSABbB Sba由语法树可知2.5.1 文法的二义性从前面的讨论可以看出，对于文法G中 任一句型的推导序列, 我们总能为它构造一棵语法树，现在我们提出一个问题：文法的某个句型是否只对应唯一的一棵 语法树呢？也就是，它是否只有唯一的一 个最左(最右)推导呢？ 2.5.1 文法的二义性 例如 设有文法G[E]：句子 i*i+i 有两个不同的最左推导， 对应两棵不同的语法树。

E  E+E | E*E | (E) | i2.5.1 文法的二义性 最左推导1 EE+EE*E+E i*E+Ei*i+Ei*i+i 最左推导2 EE*Ei*E i*E+Ei*i+E i*i+i EE*EE+EiiiEE+EE*Eiii2.5.1 文法的二义性 如果一个文法存在某个句子对应两 棵不同的语法树，则说这个文法是二义 性的或者说，若一个文法中存在某个句 子，它有两个不同的最左 (最右) 推导， 则这个文法是二义性的 E  E+E | E*E | (E) | i2.5.2 文法二义性的消除 1. 不改变文法中原有的语法规则, 仅加 进一些非形式的语法规定 EE+EE*Eiii2.5.2 文法二义性的消除2. 构造一个等价的无二义性文法即 把排除二义性的规则合并到原有文法中, 改写原有的文法例如，对于上例文法G[E]，将运算符的优先顺序和结合规则：*优先于＋; ＋、*左结合加到原有文法中, 可构造出无二义性文法如下 ：2.5.2 文法二义性的消除则句子i*i+i只有 唯一一棵语法树 ：EE+T | TTT*F | FF(E) | iEE+TTT*FFiiFi2.5.2 文法二义性的消除 例2 定义某程序语言条件语句的文法G为 : 试证明该文法是二义性的并消除之。

分析 该文法的句子 if b if b A else A 对应下面两棵不同的语法树： Sif b S | if b S else S| A (其它语句）2.5.2 文法二义性的消除 所以该文法是二义的 SifbSbSSifAelseASbSSif AelseAifbSSif b S | if b S else S | A 句子 if b if b A else A2.5.2 文法二义性的消除 消除文法的二义性可采用下面两种方法： 1. 不改变已有规则，仅 加进一非形式的语法规 定：else与前面最接近 的不带else的 if 相对SifbSbSSifAelseA文法G的句子if b if b A else 只对应唯一的一棵语 法树，消除了二义2.5.2 文法二义性的消除 2. 改写文法G为G'S S1 | S2 S1 if b S1 else S1 | AS2 if b S | if b S1 else S2 G':Sif b S | if b S else S| A (其它语句）G :2.5.2 文法二义性的消除这是因为通过分析，得知引起 二义性的原因是: if—else 语句的 if 后可是 if型，因此改写文法时规定: if — else之间只能是if—else语 句或其他语句。

2.5.2 文法二义性的消除 S S1 | S2 S1 if b S1 else S1 | AS2 if b S | if b S1 else S2 ifbSbif AelseASS2S1S1S1对改写后的文法，句子if b if b A else A 只对应唯一的一棵语法 树通常我们只说文法的二义性, 而不 说语言的二义性, 这是因为可能有两个 不同的文法G和G' ，而且其中一个是二 义性的，另一个是无二义性的, 但却有 L(G)=L(G'), 即这两个文法所产生的语言 是相同的2.5.2 文法二义性的消除 应该指出的是文法的二义性和语 言的二义性是两个不同的概念2.5.2 文法二义性的消除 将一个语言说成是二义性的，是 指对它不存在无二义性的文法，这样 的语言称为先天二义性的语言例如L={ ai bj ck | i=j 或 j=k 且 i, j, k≥1} 便是这种语言2.6 文法和语言的分类 著名的语言学家乔姆斯基(Chomsky)将文法和语言分为四大类，即0型、1型 、2型、3型划分的依据是对文法中的规则施加不同的限制 2.6 文法和语言的分类 Ø 0型文法（无限制文法） 若文法G=(VN,VT, P, S)中的每条规则αβ 是这样一种结构： 而且α中至少含一个非终结符, 则称G是0型文法。

α(VN∪VT)+ ,β(VN∪VT)*0型文法描述的语言是 0型语言0型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性语言0型语言由 图灵机识别 2.6 文法和语言的分类 例如，有0型文法G=(VN,VT, P, S) 其中：VN={A,B,S} , VT={0,1} 其描述的 0 型语言为 L0(G[S])={ } P: S  0AB1B  0B  SA | 01A1  SB1A0  S0B2.6 文法和语言的分类 Ø 1型文法（上下文有关文法） 1型文法也称为上下文有关文法， 相应的语言又称为上下文有关语言若文法G=(VN,VT, P, S)中的每一条规则的形式为 αAβ αμβ , 其中： α, β(VN∪VT)* ,AVN ,则称G是1型文法1型文法描述的 语言是1型语言 1型语言由线性 界限自动机识别 μ(VN∪VT)+2.6 文法和语言的分类 例如，有1型文法G=(VN,VT, P, S) 其中：VN={S,A,B} , VT={a,b,c} P: S aSAB | abBBA  BA'BA'  AA' AA'  ABbA  bbbB  bccB  cc 其描述的1型语言为L1(G[S])={anbncn | n≥1} 2.6 文法和语言的分类 Ø 2型文法（上下文无关文法） 2型文法又称上下文无关文法，其产生的语言又称为上下文无关的语言。

若文法G=(VN,VT, P, S)中的每一条规则的形式为 A β , 其中： AVN ,β(VN∪VT)*则称G是2型文法2型文法描述的语 言是2型语言2型语言由下 推自动机识 别例如前面描述算术表达式的文法G[E]:EE+E | E*E | (E) | i2.6 文法和语言的分类 其描述的语言为 L2(G[S])={x | x  {a, b}+ 且x中a和b的个数相同} 例如，有2型文法G=(VN,VT, P, S) 其中：VN={S, A, B} , VT={a, b} P={ S aB | bAA a | aS | bAAB b | bS | aBB }2.6 文法和语言的分类 2.6 文法和语言的分类 Ø 3型文法（正规文法） 右线性文法和左线性文法都称为3型文法若文法G=(VN,VT, P, S)中的每一条规则的形式为A aB 或 A a , 其中： A , BVN, a VT*, 则称G是右线性文法若文法G=(VN,VT, P, S)中的每一条规则的形式为A Ba 或 A a , 其中： A , BVN , a VT*, 则称G是左线性文法。

3型文法描述的语言 是3型语言3型语言由有穷 自动机识别3型文法也称正规文法正规文法产生的语言称为正规语言例如，用左线性正规文法和右线性正规 文法定义标识符 2.6 文法和语言的分类 用I代表标识符; l代表任意一个字母 ; d代表任意一个数字; 则定义标识符的文 法为：左线性文法:P: I→ l | Il | Id右线性文法:P: I→ l | lT T→l | d | lT| dT例如，用左线性正规文法和右线性正规文 法定义无符号整数2.6 文法和语言的分类 用N代表无符号整数; d代表任意一个 数字；则定义的无符号整数文法为：左线性文法:P: N→ Nd | d右线性文法:P: N→ dN | d2.6 文法分类总结0型文法：左部： VN和VT组成(可以由多个VN多个VT组成,但至少一个VN) 右部： VN和VT组成(可以由多个VN多个VT组成)ε1型文法：左部： VN和VT组成(可以由多个VN多个VT组成,且至少一个VN)右部： VN和VT组成(可以由多个VN多个VT组成)左部|<=|右部|2.6 文法分类总结2型文法：左部：只有一个VN 右部：VN和VT组成(可以由多个VN多个VT组成)。

ε3型文法：左部：只有一个VN 右部：最多一个VN ，且在最左或最右ε2.6 文法和语言的分类 由上述四类文法的定义可知, 从0型文 法到3型文法, 是逐渐增加对规则的限制 条件而得到的，因此每一种正规文法都 是上下文无关的文法，每一种上下文无 关的文法都是上下文有关的文法，而每 一种上下文有关的文法都是0型文法, 而 由它们所定义的语言类是依次缩小的， 有 L0  L1  L2  L3 2.7 有关文法的实用限制和变换 文法是用来描述程序设计语言的，在实际应用中需要对文。