目录

一、句型的分析

1、规范推导和规范归约

2、短语、简单短语和句柄

3、语法树

4、通过树来寻找短语、简单短语、句柄

二、文法的二义性

1、文法二义性的定义

2、文法二义性的消除

（1）定义规定或规则

（2）改写文法

三、例题

1、语言L={ambn ,m>=1,n>=1},试写出文法。

2、语言L={anbncm ,m>=1,n>=1},试写出文法。

3、语言L={anbbn ,n>=1},试写出文法。

4、语言L={anbmcmdn ,m>=1,n>=1},试写出文法。

5、语言L={ambn ,n>=m>=1},试写出文法。

最左（右）推导：在任一步推导v=>w中，都是对符号串v的最左(右）非终结符号进行替换,称最左（右）推导。

规范推导：即最右推导。

规范句型：由规范推导所得的句型。

规范归约：规范推导的逆过程，称规范归约或最左归约。

例:

G[] →| | →a|b|...|z|A|...|Z →0|1|2|...|9

规范推导 => =>y => y =>4y =>4y =>a4y

规范归约 a4y bBB =>baB=>baSb           且B=>Sb (2) S=>AB =>ASb =>bBSb=>baSb        且B=>a (3) S=>AB =+>baSb                               且A=+>ba

Sb是相对于B、句型baSb的短语且为简单短语， a是相对于B、句型baSb的短语且为简单短语， ba是相对A、句型baSb的短语 句柄为a。

语法树：一个句型或句子推导过程的图示法表示，形成一棵语法树。

根：开始符号。

子树：某一非终结符号 (子树的根)及其下面的分支。

叶：树的末端结点。

语法树的全部末端结点（自左向右）形成当前句型。

例:

G[S]： S→AB A→Aa|bB B→a|Sb

最左推导         S=>AB =>bBB =>baB =>baSb

说明：

设文法G=(Vn,Vt,P,S),对G的任何句型都能构造与之关联的、满足下列条件的一课语法树。

短语：子树的末端结点形成的符号串。

简单子树：只有一层分支的子树。

简单短语：简单子树的末端结点形成的符号串。

例：

          句型baSb的语法树

共有三颗子树，

三个短语:ba ,a, Sb，baSb 简单短语: a, Sb 句柄: a

 1、如何找短语？

从树根S开始，找S的末端结点是：baSb（也就是句型本身）

然后往下找A的末端结点是：ba

                  B的末端结点是：Sb

再往下只有B有末端结点是：a

2、如何找简单短语？

先找到简单子树即只有一层分支的子树；

然后简单子树的末端结点形成的符号串即简单短语。

3、如何找句柄？

找左边的简单短语

结论：

 说明：

例:

证明文法G[S]：S→aSb|Sb|b为二义性文法。

证明：对于句子abbb存在两个不同的最左推导 最左推导1： S=>aSb=>aSbb=>abbb 最左推导2： S=>Sb=>aSbb=>abbb 因此，句子abbb是二义性的，由于文法存在二义性的句子，所以文法G[S]是二义性的。

例：

G1[E]:E→E+E|E*E|(E)|i

规定：四则运算法则，成无二义性文法。

G[S]: S →if B then S else S|if B then S

规定：else跟与它最近尚未匹配的then匹配，成无二义性文法

例：

G1[E]:E→E+E|E*E|(E)|i

二义性文法，无优先关系信息，不能直接使用。

G2[E]: E→E+T|T T→T*F|F F→(E)|i

无二义性文法，含四则运算信息，语法分析时使用。

G[S]： S→AB A→Aa|a B→bB|b 或G[S]： S→AB A→aA|a B→bB|b

G[S]： S→AB A→aAb|ab B→cB|c

G[S]： S→aAb A→aAb|b

或G[S]： S→aSb|A A→abb

G[S]： S→aSd|aAd A→bAc|bc

解： 改写为等价语言 L={ambmbk ,m>=1,k>=0}

G1[S]:S→AB A→aAb|ab B→bB|ε

G2[S]: S→aAb A→aAb|Ab|ε

或改写为等价语言 L={ambkbm ,m>=1,k>=0}

G3[S]: S→aSb|aAb A→bA|ε