4--改写文法.pptVIP免费

WenshengLiBUPT改写文法--1/12文法的变换文法二义性的消除左递归的消除提取左因子WenshengLiBUPT改写文法--2/12文法二义性的消除映射程序设计语言中IF语句的文法：stmtifexprthenstmt|ifexprthenstmtelsestmt|other句子ifE1thenifE2thenS1elseS2有两棵不同的分析树：stmtifexprthenstmtE1ifexprthenstmtelsestmtE2S1S2stmtifexprthenstmtelsestmtE1ifexprthenstmtS2E2S1WenshengLiBUPT改写文法--3/12最近最后匹配原则else必须匹配离它最近的那个未匹配的then出现在then和else之间的语句必须是“匹配的”。所谓匹配的语句是不包含不匹配语句的if-then-else语句，或是其他任何非条件语句。改写后的文法：stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtifexprthenstmt|ifexprthenmatched_stmtelseunmatched_stmtWenshengLiBUPT改写文法--4/12句子ifE1thenifE2thenS1elseS2的分析树unmatched_stmtifexprthenstmtE1matched_stmtE2otherotherstmtifexprthenmatched_stmtelsematched_stmtS1S2WenshengLiBUPT改写文法--5/12左递归的消除一个文法是左递归的，如果它有非终结符号A，对某个文法符号串，存在推导：消除左递归的方法：简单情况：如果文法G有产生式：AA|可以把A的这两个产生式改写为：AAAA|这两组产生式是等价的由于从A推导出的符号串是相同的，即都是…AA+若存在某个=，则称该文法是有环路的。WenshengLiBUPT改写文法--6/12例：消除表达式文法中的左递归：EE+T|TTT*F|FF(E)|id利用消除直接左递归的方法，可以改写为:ETEE+TE|TFTT*FT|F(E)|idWenshengLiBUPT改写文法--7/12一般情况：假定关于A的全部产生式是：AA1|A2|…|Am|1|2|…|n产生式可以改写为：A1A|2A|…|nAA1A|2A|…|mA|例如有间接左递归文法：SAa|bAAc|Sd|WenshengLiBUPT改写文法--8/12算法：消除左递归输入：无环路、无-产生式的文法G输出：不带有左递归的、与G等价的文法G’方法：（1）把文法G的所有非终结符号按某种顺序排列成A1,A2,…,An（2）fori:=1tondoforj:=1toi-1dobegin把每个形如AiAj的产生式改写为：Ai1|2|…|k；其中Aj1|2|…|k是关于当前Aj的所有产生式消除关于Ai的产生式中的直接左递归end（3）化简第(2)步得到的文...