图41试探分析法
11 S x A y S x A y S x A y a b a (a) (b) (c) 图4.1 试探分析法
递归下降分析法的两个障碍 公共的左因子:a P→aβ1aβ21….aβ 导致必须回溯到上次试探的现场。 左递归文法:P→Pa|B 导致无限的最左推导,使匹配陷入困境。 12
12 递归下降分析法的两个障碍 •公共的左因子： α P→α β 1 | α β 2 | … | α β n 导致必须回溯到上次试探的现场 。 •左递归文法： P→ P α | β 导致无限的最左推导，使匹配陷入困境
、提取左因子 生式 P→aβ1uβ21-..|a阝 有公共的左因子a。引进新的非终符P’, P→aP|6 β1|β2|….|Bn (4.2) 则它与(4.1)是等价的,而β1,β2,…,Bn没有公 共左因子。其中8是不以为前缀的候选式。当然 所花的代价是增加了一个非终结符,增加了一个 产生式。 13
13 二、提取左因子 产生式 P→α β 1 | α β 2 | … | α β n (4.1) 有公共的左因子α 。引进新的非终符P’ ， 令： P→α P’ | P’→ β 1 | β 2 | … | β n (4.2) 则它与(4.1)是等价的，而β 1， β 2， … ，β n没有公 共左因子。其中是不以α为前缀的候选式。当然 所花的代价是增加了一个非终结符，增加了一个 产生式
「例4.2例4.的文法提取左因子后为 S->XA A->aa A->b| 14
14 [例4.2] 例4.1的文法提取左因子后为： S->xAy A->aA’ A’->b |
三、消除左递归 产生式 A→>Aa|B 其中β不以A为前缀。这是直接左递归形式,它产生的符号串为 结构。引进非终结符A,令 A→>BA A→,c'|E 它同样产生βo形符号串,所以与(43)等价,但是它不是左递归的。 更一般些对 A→>Ax1|Aa2|… AamB|B2|…B 的等价文法为 A→B1A|B2A|…BnA A→>a1Aa2A'|…|am4'|E 15
15 三、消除左递归 产生式 其中b不以A为前缀。这是直接左递归形式，它产生的符号串为ba* 结构。引进非终结符A’ ，令 它同样产生ba*形符号串，所以与(4.3)等价，但是它不是左递归的。 更一般些对 的等价文法为 AAa| b a b A A | A A A Aa Aa Aam b b bn | | | | | | | 1 2 1 2 a a a b b b | | | | | | | 1 2 1 2 A A A A A A A A m n