c实现消除文法左递归

编译原理实验报告 实验名称 消除文法的左递归 实验时间 2010.11.1 院系 计算机科学与技术 班级 2008 学号 JB****** 姓名 潘亚飞 1 .试验目的 输入：任意的上下文无关文法。 输出：消除了左递归的等价文法。 2 .实验原理 1．直接左递归的消除 消除产生式中的直接左递归是比较容易的。例如假设非终结符P 的规则为 P→Pα / β 其中，β 是不以 P 开头的符号串。那么，我们可以把 P 的规则改写为如下的非直接左递归形式： P→βP’ P’→αP’ / ε 这两条规则和原来的规则是等价的，即两种形式从 P 推出的符号串是相同的。 设有简单表达式文法G[E]： E→E+T/ T T→T*F/ F F→（E）/ I 经消除直接左递归后得到如下文法： E→TE’ E’ →+TE’/ ε T→FT’ T’ →*FT’/ ε F→（E）/ I 考虑更一般的情况，假定关于非终结符P 的规则为 P→Pα1 / Pα2 /…/ Pαn / β1 / β2 /…/βm 其中，αi（I＝1，2，…，n）都不为ε，而每个 βj（j＝1，2，…，m）都不以P 开头，将上述规则改写为如下形式即可消除P 的直接左递归： P→β1 P’ / β2 P’ /…/βm P’ P’ →α1P’ / α2 P’ /…/ αn P’ /ε 2．间接左递归的消除 直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。有些文法虽然表面上不存在左递归，但却隐藏着左递归。例如，设有文法G[S]： S→Qc/ c Q→Rb/ b R→Sa/ a 虽不具有左递归，但 S、Q、R 都是左递归的，因为经过若干次推导有 SQcRbcSabc QRbSabQcab RSaQcaRbca 就显现出其左递归性了，这就是间接左递归文法。 消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。 如果一个文法不含有回路，即形如PP 的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。 消除左递归算法： （1） 把文法G 的所有非终结符按任一顺序排列，例如，A1，A2，…，An。 （2） for （i＝1；i<=n；i++） for （j＝1；j<=i－1；j++） { 把形如Ai→Ajγ 的产生式改写成 Ai→δ1γ /δ2γ /…/δkγ 其中 Aj→δ1 /δ2 /…/δk是关于的Aj全部规则； 消除Ai规则中的直接左递归； } （3） 化简由（2）所得到的文...