编译原理实验课程教案.doc

安 徽 大 学 江 淮 学 院 实 验 课 程 教 案 课 程 名 称 编译原理 课 程 属 性 专业基础 开 课 学 年 开 课 学 期 年 级 专 业 主 讲 教 师 课程所属院系部 课程所属系(教研室) 实验一 名称 Chomsky文法类型判断（Recognizing the type of the Chomsky grammar） 一、、实验实验1型2型3型；即L0 L1 L2 L3 四、仪器 微机 五、实验步骤（包括操作方法、数据处理） 六、注意事项 ⑴ 文法的输入应简便。 ⑵ 指明是哪一类Chomsky 文法，并给出相应的四元组形式：G=（VN，VT，P，S）。 说明：简单起见， 可以不考虑0型文法类。 七、思考题 3型文法和DFA、NFA、正规式的关系如何？ 实验 二 名称 消除文法的左递归（Removing the left recursion of the grammar） 一、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都是左递归的，因为经过若干次推导有 SQcRbcSabc QRbSabQcab RSaQcaRbca 就显现出其左递归性了，这就是间接左递归文法。 消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。 如果一个文法不含有回路，即形如PP的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。 消除左递归算法： 把文法G的所有非终结符按任一顺序排列，例如，A1，A2，…，An。 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规则中的直接左递归； } 化简由（2）所得到的文法，即去掉多余的规则。 利用此算法可以将上述文法进行改写，来消除左递归。 首先，令非终结符的排序为R、Q、S。对于R，不存在直接左递归。把R代入到Q中的相关规则中，则Q的规则变为Q→Sab/ ab/ b。 代换后的Q不含有直接左递归，将其代入S，S的规则变为S→Sabc/ abc/ bc/ c。 此时，S存在直接左递归。在消除了S的直接左递归后，得到整个文法为： S→abcS’/ bcS/ cS S’ →abcS/ ε Q→Sab/ ab/ b R→Sa/ a 可以看到从文法开始符号S出发，永远无法达到Q和R，所以关于Q和R的规则是多余的，将其删除并化简，最后得到文法G[S]为： S→abcS/ bcS’/ cS S →abcS/ ε 当然如果对文法非终结符排序的不同，最后得到的文法在形式上可