语法制导的地址代码生成器.docVIP

实验二：语法制导的三地址代码生成器 一 教学重点与实现的关键技术 1.1自顶向下（top—down）分析概述 自顶向下分析法包括：递归子程序法和预测分析法(LL(1))。 自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。其主旨是：对任何输入串，试图用一切可能的办法，从文法开始符号（根）出发，自顶向下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 例：G为：S→xAy A→**|*，输入串：x**y STxAy Tx**y S * * x y A 在子树A通过试探匹配后，才进行下一个符号y的匹配。 实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个子程序可作为一个布尔过程。一旦发现它的某个侯选与输入串相匹配，就用这个侯选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。 这种分析法有许多困难和缺点。 首先，是文法的左递归问题。 其次，回溯会碰到一大堆麻烦事情。 第三，在上述的自顶向下分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能是暂时的。 第四，当最终报告分析不成功时，难于知道输入串中出错的确切位置。 1.2 LL（1）分析法技术 自顶向下分析方法不允许文法含有任何左递归。为构造不带回溯的自顶向下分析算法，首先要消除文法的左递归性，并找出无回溯的充分必要条件。LL（1）分析法主要用于消除左递归和克服回溯的方法。 1.2.1左递归的消除 直接左递归 AT Aα 间接左递归 AT+Aα 左递归的消除方法： 将A→Aα|β替换为A→βA′ 和 A′→α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 例： 间接左递归的消除 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’|ε 消除左递归的一般方法： 用产生式组 A?β1 B|β2 B |…|βn B B?α1 B|α2 B |…|αn B|ε 替换产生式组 A→Aα1|Aα2|…|Aαn|β1|β2|…|βm 其中：B为新变量，相当于A’ 消除左递归的算法： Ⅰ、把文法G的所有非终结符按任一种顺序排列成A1，A2，……，An；按此顺序执行； Ⅱ、FOR i:=1 to n DO Begin FOR j:=1 to i-1 DO 把形如Ai ?Ajγ的规则改写成 Ai?δ1γ│δ2γ│……│δkγ。其中Aj ?δ1│δ2│……│δk 是关于Pj的所有规则； 消除关于Pi规则的直接左递归性 END Ⅲ、化简由（Ⅱ）所得的文法。即去除那些从开始符号出发永远无法到达的非终结符的产生规则，为非终结符编号，再采用代入法将间接左递归变为直接左递归，消除直接左递归。 1.2.2消除回溯、提左因子 欲构造行之有效的自顶向下的分析器，必须消除回溯。为了消除回溯就必须保证：对文法的任何非终结符，当要用它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个侯选去执行任务，并且此侯选的工作结果应是确信无疑的。也就是说，若此侯选获得成功匹配，那么，这种匹配决不会是虚假的；若此侯选无法完成匹配任务，则任何其它侯选也肯定无法完成。 但是，如何把一个文法改造成任何非终结符的所有侯选首符集两两不相交呢？其办法是，提取公共左因子。 例：if语句的原始文法 S→ if E then S |if E then S else S |other 遇到 if 时难以判断用哪一个产生式进行匹配（推导） 存在左因子 if E then S 提取作因子： S→ if E then SS’|other S→ε|else S 左因子提取方法： 将形如 A→αβ1|αβ2|…|αβn |γ1|γ2|… | γm 的规则改写为 A→αA |γ1|γ2|… | γm和 A→β1|β2|…|βn 1.2.3候选式的确定与回溯(Backtracking)