实验二：语法制导的三地址代码生成器
一 教学重点与实现的关键技术
1.1 自顶向下（top—down）分析概述
自顶向下分析法包括：递归子程序法和预测分析法(LL(1))。
自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。其
主旨是：对任何输入串，试图用一切可能的办法，从文法开始符号（根）出发，自顶向下地为
输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试
探过程，是反复使用不同产生式谋求匹配输入串的过程。
例：G 为：S→xAy A→**|*，输入串：x**y
SÞxAy
Þx**y
在子树 A 通过试探匹配后，才进行下一个符号 y 的匹配。
实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序 。
每个子程序可作为一个布尔过程。一旦发现它的某个侯选与输入串相匹配，就用这个侯选去扩
展语法树，并返回“真”值；否则，保持原来的语法树和 IP 值不变，并返回“假”值。
这种分析法有许多困难和缺点。
首先，是文法的左递归问题。
其次，回溯会碰到一大堆麻烦事情。
第三，在上述的自顶向下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功
可能是暂时的。
第四，当最终报告分析不成功时，难于知道输入串中出错的确切位置。
1.2 LL（1）分析法技术
自顶向下分析方法不允许文法含有任何左递归。为构造不带回溯的自顶向下分析算法，首
先要消除文法的左递归性，并找出无回溯的充分必要条件。LL（1）分析法主要用于消除左递
归和克服回溯的方法。
1.2.1 左递归的消除
直接左递归 AÞ Aα
间接左递归 AÞ+Aα
左递归的消除方法：
将 A→Aα|β 替换为 A→βA′ 和 A′→αA′｜ε
例：表达式文法直接左递归的消除
例： 间接左递归的消除
S→Ac|c A→Bb|b B→Sa|a
将 B 的定义代入 A 产生式得：A→Sab|ab|b
将 A 的定义代入 S 产生式得: S→Sabc|abc|bc|c
消除直接左递归： S→abcS’|bcS’|cS’
S’→abcS’|ε
删除“多余的”产生式：A→Sab|ab|b 和 B→Sa|a
结果： S→abcS’|bcS’|cS’
S’→abcS’|ε
消除左递归的一般方法：
*
*
S
x
y
A
E→ T E’
E’→ + T E’|ε
T→ F T’
T’→* F T’｜ε
F→ ( E )｜id
E → E + T｜T
T → T * F｜F
F → ( E )｜id
