文档介绍：二工大温敬和
2008年1月25日
第4章自上而下的语法分析
1
带回溯的自上而下分析法概述
直接左递归的消除
不带回溯的自上而下分析法的基本原理
提取左因子
first集和follow集
递归下降分析法
预测分析法
从文法的开始符号出发进行推导,最终推出确定的输入串(由单词种别构成的源程序)。
2
带回溯的自上而下分析法概述
从根结点出发,试图用一切可能的办法,自上而下地为输入串建立一棵语法树。或者说,为输入串寻找一个最左推导。
㈠分析过程概述
例已知文法G:
S→xAy
A→**|*
和输入串α=x*y。
①初始时,指示器P指向α的第一个符号x。
②从S推导,因最左子结和输入串第1个符号相匹配,故P指向下一符号*。
③因第二个子结是非终结符A,从A采用第一个候选进行推导。从A推导出的左子结和指示器P所指的符号一致,故P指向下一个符号y。
④因A的第二个子结*和指示器P所指的符号不一致,这意味着A的第一个候选不适用于构造α的语法树,应该回溯。将A的子树注销,P恢复进入A时的值。
⑤用A的第二个候选进行推导,因子树A的子结和指示器P所指的符号*一致,则P指向下一个符号y。
⑥因S的第三个子结和指示器P所指的符号一致,故α是一个句子。
3
显然上述分析过程本质上是一个试探过程,是反复使用不同产生式谋求匹配输入串的过程。
㈡问题和困难
①对于左递归文法定义的语言,不能采用自上而下的语法分析法。
②存在虚假匹配,回溯不可避免。
③编译程序的语法分析和语义分析通常是同时进行的。由于回溯,编译程序所做的一大堆语义分析工作必须推倒重来。
④当选用所有的不同候选组合,都不能为输入串建立一棵语法树,那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子,而无法告知输入串错在何处。
⑤带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法,因此效率很低,这种分析法几乎没有实用价值。
总上所述,必须消除分析过程中的回溯,只有不带回溯的分析方法才是实际可使用的。
4
直接左递归的消除
程序设计语言文法的左递归性通常是由左递归规则直接引起的,由规则推导所产生的间接左递归的情况较少见。
㈠实例引入
例:已知左递归文法G:S→Sa|b,构造文法G的等价文法G',G'不含左递归。
解:文法G'如下所示
S→bS'
S'→aS'|ε
∵SSaSaa…ban 或 Sb
∴L(G)={ ban∣n≥0}
∵SbS'baS'…ban 或 SbS'b
∴L(G')={ ban∣n≥0}
∵L(G)= L(G')
∴文法G和G'等价,而文法G'不含左递归。
5
㈡直接左递归消除方法
假定关于非终结符P的规则为
P→Pα|β
其中,β不以P开头。可以把关于P的规则变换为如下形式:
P→βP'
P'→αP'|ε
由于二者推导出的句型均为βαn(n≥0),故上述变换是等价的。
例文法G:
E→E+T|T
T→T*F|F
F→(E)|i|x|y
经消除直接左递归后变成
E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→(E)|i|x|y
6
㈢直接左递归消除一般规则及等价性证明
设非终结符P的产生式如下
P→Pα1|Pα2|…|Pαm|β1|β2|…|βn
其中,βi(1≤i≤n)不以P开头。可将P的规则改成如下等价形式,即可消除左递归。
P→β1P'|β2P'|…|βnP'
P'→α1P'|α2 P'|…|αm P' |ε
证:
P→Pα1| Pα2|…| Pαm|β1|β2|…|βn
等价于
P→P(α1|α2|…|αm)|(β1|β2|…|βn)
令α=α1|α2|…|αm、β=β1|β2|…|βn,则上式为:
P→Pα|β。
消除直接左递归后变成
P→βP'
P'→αP'|ε
7
证:
P→Pα1| Pα2|…| Pαm|β1|β2|…|βn
等价于
P→P(α1|α2|…|αm)|(β1|β2|…|βn)
令α=α1|α2|…|αm、β=β1|β2|…|βn,则上式为:
P→Pα|β。
消除直接左递归后变成
P→βP'
P'→αP'|ε
用α1|α2|…|αm替代α,用β1|β2|…|βn替代β,则有
P→(β1|β2|…|βn)P'
P'→(α1|α2|…|αm)P' |ε
等价于
P→β1P'|β2P'|…|βnP'
P'→α1P'|α2 P'|…|αm P' |ε
8
不带回溯的自上而下分析法的基本原理
设文法G有产生式:A→α1|α2|…|αn
㈠带回溯的自上而下的分析法