《《编译原理》课程简介 (22).pdf》由会员分享，可在线阅读，更多相关《《编译原理》课程简介 (22).pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理 C O M P I L A T I O N P RIN C IP LE 第四章 语法分析-自上而下分析4.3.1 消除左递归和回溯 4.3 消除左递归和回溯一、左递归的消除n使用自顶向下的任何一种算法必须消除左递归和提取公共左因子。v1、直接左递归的消除p若文法中有形如PP的产生式，则称直接左递归，如AAb|a。设 P VN ，有PP|，若，不以P开头（否则不可能消除左递归）。则改写为：P P P P|可消除左递归4.3 消除左递归和回溯n例：SSabc|Sab|ab 消除直接左递归得：SabS SabcS|abS|n一般地，若PP 1|P 2|.|P m|1|.|n i ，j不以P
2、开头，则可改写为：P 1 P|2P|.|n P P 1 P|2P|.|m P|从而消除直接左递归。4.3 消除左递归和回溯v2、完全消除左递归 分析SQc|cQRb|bRSa|a虽不含直接左递归，但所以含有左递归。SQcRbcSabc如果文法G不含回路（P P），也不含产生式，则下列算法可消除左递归（完全）把G的非终结符按任意顺序排列成P1,Pnfor i:=1 to n do for j:=1 to i-1 do 把形如 Pi P j 的规则改写成 P i 1|.|k,其中 P i 1|.|k ；消除关于Pi的直接左递归化简由得到的文法（取消无用非终结符产生式）4.3 消除左递归和回溯上述文
3、法例排序：S,Q,R循环：i=1时，处理SQc|c，消除直接左递归，不变 i=2时，处理QRb|b，j=1，把有关Q的产生式中以S开头的候选式替换（无），所以不变 i=3时，处理RSa|a，j=1，把以S开头的候选式替换，得RQca|ca|a4.3 消除左递归和回溯j=2，把以Q开头的候选式替换，得：RRbca|bca|ca|a消除R的直接左递归，得：R bcaR|caR|aR RbcaR|整理：得：S Qc|c Q Rb|b R bcaR|caR|aR RbcaR|4.3 消除左递归和回溯二、提取左因子、消除回溯v1、FIRST()通常关于条件语句的产生式例n语句if 条件 then 语句
4、else 语句n|if 条件 then 语句n 就是这样一种情形n设文法G是不含左递归的文法，对其任何非终结的候选式定义：FIRST()=a|a,aVT,(VT U VN)*若 ，则规定FRIST()*4.3 消除左递归和回溯v2、应用n如果一个文法G的非终结符A的多个候选式之首符集两两不相交，那么在自上而下分析时便可消除回溯。n设A 1|2|.|n，而FIRST(1),FIRST(n)两两不相交，那么当分析时要A去匹配某输入串时，便可根据此输入串的输入符号a,准确地选用候选式i。4.3 消除左递归和回溯文法SaSb|c，输入串为aacbb时：例4.3 消除左递归和回溯v3、公共左因子的提取n 把文法改造为每个非终结符的所有候选式两两不相交的方法是提取公共左因子。A 1|2|.|n|1|2|.|mA A|1|.|m A 1|2|.|n n 可改造为：|编译原理谢 谢Thanks