[工学]编译原理第4章.pptVIP

例4.6 对于文法G(E) E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 构造每个非终结符的FIRST和FOLLOW集合： 回顾：LL(1)分析法 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯 一般而言，假定P关于的全部产生式 P→P?1 | P?2 | … | P?m | ?1 | ?2|…|?n 其中，每个?都不等于?，每个?都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成： P→?1P? | ?2P? | … | ?nP? P?→?1P? | ?2P? |… | ?mP? | ? 消除左递归的算法: 1. 把文法G的所有非终结符按任一种顺序排列成P1，P2，…，Pn；按此顺序执行； 2. FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如Pi→Pj?的规则改写成 Pi→?1?|?2?|…|?k? ; (其中Pj→?1|?2|…|?k是关于Pj的所有规则) 消除关于Pi规则的直接左递归性 END 3. 化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。 回顾：LL(1)分析法 构造不带回溯的自上而下分析算法 要消除文法的左递归性 克服回溯 消除回溯、提左因子 为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。 A→? 1 | ? 2 | … | ? n 令G是一个不含左递归的文法，对G的所有非终结符的每个候选?定义它的终结首符集FIRST(?)为： 提取公共左因子: 假定关于A的规则是 A→?? 1 | ?? 2 | …| ?? n | ? 1 | ? 2 | … | ?m (其中，每个? 不以?开头) 那么，可以把这些规则改写成 A→?A? | ? 1 | ? 2 | … | ? m A?→? 1 | ? 2 | … | ? n 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。 FOLLOW定义 假定S是文法G的开始符号，对于G的任何非终结符A，我们定义 对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为 A→? 1 | ? 2 | … | ? n 1. 若a?FIRST(? i)，则指派? i执行匹配任务； 2. 若a不属于任何一个候选首符集，则： (1) 若?属于某个FIRST(?i )且 a?FOLLOW(A)， 则让A与?自动匹配。 (2) 否则，a的出现是一种语法错误。 例:文法G(E): E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。 例:文法G(E): E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i 对应的递归下降子程序为: PROCEDURE F； IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGIN ADVANCE; E； IF SYM=‘)’ THEN ADVANCE ELSE ERROR END ELSE ERROR; 例如，通常的“实数”可定义为： decimal→[sign]integer.{digit}[exponent] exponent→E[sign]integer integer→digit{digit} sign→ + | - 用扩充的巴科斯范式来描述语法，直观易懂，便于表示左递归消去和因子提取。 例4.5 文法 E→T | E+T T→F | T*F F→i | (E) 可表示成 E→T{+T} T→F{*F} F→i | (E) (4.6) E→T{+T} T→F{*F} F→i | (E)