2 语法分析-语法树、文法等价变化

第三章：语法分析

语法树

二义性文法

文法等价变换

内容介绍语法树文法的二义性文法等价变换 继续为自顶向下的语法分析方法做准备！语言树的定义中文主谓宾名词短语动词短语名词短语动词形容词名词名词是我的名字李雷语言树的定义语法树：设G是给定的语法，称满足下列条件的树为G的一棵语法树：1.树的每个节点都标有G的一个语法符号，且根节点标有初始符S。2.如果一个非叶节点A按从左到右顺序有n个儿子节点B1、B2、…、Bn，则:A

B1B2…Bn一定是G的一个产生式.根节点开始符非叶子节点非终极符叶子节点（非）终极符与上节课的概念间关系！1.1语言树的定义例子：有文法E

E+TE

TT

T

*FT

FF(E)|iEE+TTFiF(E)语法树句型语法树反映了句型的推导！（不体现推导的先后顺序）语法树的作用作用主要有两点：语法树反映出我们推导的过程，每一步节点的生长过程都可以对应到我们的一步推导。语法树反应出串的语法结构。语法树和语法概念的关系子树：某语法树T中的某一节点A和它所有分支组成的树T'，则称T'是T的一颗子树。简单子树：某一节点A与其子节点（单层节点）组成的树。从严格意义上来说，A应该有且仅有一层子节点（只有一层的子树）。子树的叶子节点短语简单子树的叶子节点简单短语最左边简单子树句柄语法树和语法概念的关系结论语法树的所有叶节点对应语法符号从左到右连接起来组成的符号串是一个句型。语法树的子树所有叶节点对应语法符号从左到右连接起来组成的符号串是一个短语。简单子树所有叶节点对应语法符号从左到右连接起来组成的符号串是一个简单短语。最左简单子树叶节点对应语法符号从左到右连接起来组成的符号串是句柄。例：已知文法G: ET|E+T TF|T*F F(E)|i问：(T+i)*i+F是否为G的一个句型，若是请列出该句型的所有短语、简单短语和句柄。语法树和语法概念的关系EE+TTT*FiF(E)E+TTiFF例：文法G: ET|E+T TF|T*F F(E)|i(T+i)*i+F推导过程如下：E

E+T

T+T

T*F+T

F*F+T

(E)*F+T(E+T)*F+T(T+T)*F+T(T+F)*F+T(T+i)*F+T(T+i)*i+T(T+i)*i+F左线性推导关于句型(T+i)*i+F的短语、简单短语和句柄：短语有8个：1.(T+i)*i+F2.(T+i)*i3.(T+i)4.T+i5.T6.第一个i7.第二个i8.F简单短语有4个：T,第一个i,第二个i,F句柄：TEE+TTT*FiF(E)E+TTiFF可见：基于语法树找短语、简单短语、句柄很容易！！

对一个文法G，如果至少存在一个句子，有两棵（或两棵以上）不同的语法树，则称该句子是二义性的.包含有二义性句子的文法称为二义性文法，否则，该文法是无二义性的.文法的二义性EE+EE*EiiiEE*EE+EiiiG（E）：Ei|E+E|E*E|(E)

句型i+i*i(i+i)*ii+(i*i)例1:有问题么？例2:<Stm>→if<Exp>then<Stm>else<Stm> <Stm>→if<Exp>then<Stm> <Stm>→......假设有条件语句：ife1thenife2thens1elses2则可有下图所示的两棵不同的语法分析树：

if语句的二义性<Stm><Stm><Stm><Stm>elsethenifthenif<Exp><Exp>e1e2S1S2ife1thenife2thens1elses2ififthen<Stm><Stm><Stm><Stm>elsethen<Exp><Exp>e1e2s1s2ife1thenife2thens1elses2编译器无法处理！！！如何消除二义性？方法一：文法变换文法的二义性Ei|E+E|E*E|(E)

ET|E+T TF|T*F F(E)|i加入优先级加入左结合如何消除二义性？

文法的二义性

<stm>→<matched_stm>|<open_stm><matched_stm>→if<Exp>then<matched_stm>else<matched_stm>|other<open_stm>→if<Exp>then<stm>|

if<Exp>then<matched_stm>else<open_stm>If和else中间的语句不能缺省

<Stm>→if<Exp>then<Stm>else<Stm> <Stm>→if<Exp>then<Stm> <Stm>→......如何消除二义性？

方法二：添加语义规则文法的二义性Ei|E+E|E*E|(E)

规定优先级规定左结合If语句规定else跟最近未匹配的if配对

通过添加规则将错误的理解删除即可2.2文法二义性的判定和利用文法二义性的判断目前，不存在一个一般性的方法来判断一个现有文法是否为二义性文法。文法二义性的判定和利用常用的经验性判断:S

SS|a可以推导出SSS串，必有二义性

S

S+S可以推导出S+S+S，必有二义性G[S]:SSandSSSorSSnotS……串：SandSandSSorSorSSandSorS……文法二义性的判定和利用文法二义性的利用 对二义性文法进行修改，消除其二义性会导致文法的复杂程度和符号数目迅速升高。可以利用二义性文法状态少，分析快的特点，使用二义性文法，对具体问题加入语义规则，约束其二义性即可。3.文法等价变化提取公共前缀消除直接左递归自顶向下（最左推导的方式）不允许有左递归的出现！AaB;AaC......想要推导ab这个串选哪条规则？？？公共前缀:A的不同产生式的右部具有相同的前缀.这种情形不满足自顶向下的语法分析条件.可用提取左因子的方法消除产生式的公共前缀.假定关于Ａ的规则是：A

1|

2|…|

n|

1|

2|…|γm(其中每个

不以

开头)则将这些规则写成：A

A’|

1|γ2|…|γmA’

1|

2|…|

n经过反复提取左因子，就能够使每个非终极符的不同产生式的右部具有不同的前缀.

提取公共前缀

提取公共前缀例子：A

aB|aC|aDB

bB|bD|cDd提取公共前缀A

aA'A'

B|C|DB

bB'|cB'

B|DDd

消除直接左递归对于简单情形A

A

|

即有A

αα…α则转化A

A'A'

A'|

对于一般情形

A

A

1|A

2|…|A

m|

1|

2|…|

n

则转化A

(

1|

2|…|

n)A'A'

(

1|

2|…|

m)A'|

消除直接左递归例子E

E+T|TT

T

*F|FF(E)|iA

A

|

E

E+T|T

=+T

=TE

TE'E'

+TE'|

E

TE'E'

+TE'|

T

FT'T'

*FT'|

F(E)|i消除左递归（选学）E

+E

ETF排序：E（1），T（2），F（3）；规定：要求推导的序列，右边不能大于左边，此时FE则为不合法的规则；去掉不合法的规则（不断用右部替换左部）；最终，不合法的规则会变成直接左递归，消除。例题构造一个文法G，使L(G)={anbmck|m=n+k,n≥1,m>1,k≥1}G[S]:S

AB

A

aAb|ab

B

bBc|bc利用该性质anbmck=anbnb