上次課程內(nèi)容回顧(參考版)
2024-07-29 00:56本頁(yè)面
【正文】 因此，實(shí)際編譯器中使用更多的是一類 LL(1)文法的真超集，即 LR(1)文法。 根據(jù)推論 ，有左遞歸和左因子的文法不是 LL(1)文法。)是 LL(1)的，因?yàn)槿齻€(gè)條件均滿足。 事實(shí)上：任何直接左遞歸必有公共左因子?！?FT39。) T →FT39?！?TE39。 ■ E →TE39。 ■ 36 LL(1)文法（續(xù) 2） 對(duì)所有 A→α ： 2. 對(duì) FIRST(α) 的每個(gè)終結(jié)符 a，加入 α 到 M[A， a]； 3. 若 ε∈FIRST(α) ，則 FOLLOW(A)每個(gè)終結(jié)符 b(包括 )， 加入 α 到 M[A， b]； 證明： 1. 若條件 1不滿足 ，即存在終結(jié)符 a， α 和 β 同時(shí)推導(dǎo)出以a開始的串，則根據(jù)算法 2， M[A， a]中有多重定義 A→α 和 A→β ； 2. 若條件 2不滿足 ， 即 α 和 β 均可推出 ε 串 ， 則根據(jù)算法 3， 任何屬于 FOLLOW（ A） 的終結(jié)符 b(包括 )，M[A， b]中有多重定義 A→α 和 A→β ； 3. 若條件 3不滿足 ，即存在終結(jié)符 b，它既在 FOLLOW(A)中，又在 FIRST(α) 中，則算法 2把條目 A→α 加入到M[A， b]中，而步驟 3又把條目 A→β 加入到 M[A， b]中，即 M[A， b] 中有多重定義 A→α 和 A→β 。 ■ 判定 LL(1)文法的方法： ； 。由此分析表所組成的分析器被稱為 LL(1)分析器 ，它所分析的語(yǔ)言被稱為 LL(1)語(yǔ)言 。)= {, e} FOLLOW(C) = {t} a iCtSS39。 C 預(yù)測(cè)分析表 ： FIRST與 FOLLOW集合： FIRST(C) = FIRST(S39。|a S39。 mod FT39。 *FT39。 FT39。 TE39。 TE39。L TE39。L E。 T T39。} 2. 對(duì) FIRST(α) 的每個(gè)終結(jié)符 a，加入 α 到 M[A， a]； 3. 若 ε∈FIRST(α) ，則FOLLOW(A)每個(gè)終結(jié)符 b(包括 )， 加入 α 到 M[A， b]； 從文法構(gòu)造分析表 id num + * / mod ( ) 。)= {+ 。)= {) 。) = {* / mod ε} FIRST(E39。 2. 若當(dāng)前棧頂為 A， 當(dāng)前輸入為 b且 b∈FOLLOW(A) ， 則 規(guī)則 3表示下一步動(dòng)作是展開 A→ε ， 即棧頂彈出 A， 繼續(xù)分析 A之后的部分，因?yàn)?b∈FOLLOW(A) ， 所以彈出 A后下一次正好匹配A的后繼 b。} 32 構(gòu)造預(yù)測(cè)分析表（續(xù) 4） 算法 構(gòu)造預(yù)測(cè)分析表 輸入 文法 G 輸出 分析表 M 方法 應(yīng)用下述規(guī)則 1. 對(duì)文法的每個(gè)產(chǎn)生式 A→α ， 執(zhí)行 2和 3； 2. 對(duì) FIRST(α) 的每個(gè)終結(jié)符 a， 加入 α 到 M[A， a]； 3. 若 ε∈FIRST(α) ， 則 FOLLOW(A)每個(gè)終結(jié)符 b（ 包括 ） ，加入 α 到 M[A， b]； 4. M中其它沒有定義的條目均是 error。) = {+ 。} FOLLOW(T) = {+ 。} FOLLOW(E39。) = {* / mod ε} FIRST(T) = FIRST(F) = {( id num} FIRST(E39。|mod FT39?！?FT39。|ε T →FT39?！?TE39。L|ε E →TE39。 ■ 31 構(gòu)造預(yù)測(cè)分析表（續(xù) 3） 例 計(jì)算非終結(jié)符的 FIRST 與 FOLLOW。|ε F →(E)|id|num 30 構(gòu)造預(yù)測(cè)分析表（續(xù) 2） 算法 計(jì)算所有非終結(jié)符的 FOLLOW集合 輸入 文法 G 輸出 G中所有非終結(jié)符的 FOLLOW集合 方法 應(yīng)用下述規(guī)則 : 步驟 3的理解： 若 S =*δAa a緊跟 A之后 則 =*δαBa a也緊跟 B之后 因?yàn)? ε∈FIRST(β) 使得 B成為 A產(chǎn)生式右部最右的文法符號(hào) 即 對(duì)任何 a∈FOLLOW(A) ，均有 a∈FOLLOW(B) 1. 加入 到 FOLLOW(S)， 其中 S是開始符號(hào) ， 是輸入結(jié)束標(biāo)記 2. 若有產(chǎn)生式 A→αBβ ， 則除 ε 外 ， FIRST(β) 的全體加入到 FOLLOW(B)。|/FT39。 T39。| TE39。 E39。)={ (， id, num } L →E 。)=FIRST(FT39。 那么對(duì)所有 j(0≤j≤k) ， 若 a∈FIRST(Yj+ 1)且 ε∈FIRST(Yj), 則加入 a到 FIRST(X)。|ε F →(E)|id|num 定義 文法符號(hào)序列 α 的 FIRST集合為 : FIRST(α) ={a|α= *a...， a∈T} ， 若 α= *ε ， 則 ε∈FIRST(α) 。|/FT39。 T39。| TE39。 E39。 } L →E 。 而 A的 FOLLOW集合，就是從開始符號(hào)可以導(dǎo)出的所有含A的文法符號(hào)序列中緊跟 A之后的終結(jié)符。 定義 非終結(jié)符 A的 FOLLOW集合如下 : FOLLOW（ A） = { a |S=*...Aa...， a∈T} ， 若 A是某句型的最右符號(hào)，則 ∈FOLLOW （ A）。), next(ip) 。 。) (E39。 ?！? L。 pop(T39。T39。 pop(id), next(ip) id L。T39。 pop(F), push(id) (F→id) L。T39。 pop(*), next(ip) * L。T39。) L。) (T39。 pop(T39。T39。 pop(id), next(ip) id L。T39。 pop(F), push(id) (F→id) L。T39。) L。 pop(T), push(FT39。E39。T+ +id*id。) L。) (E39。 pop(E39。E39。) (T39。 +id*id。E39。id id+id*id。E39。F id+id*id。E39。) (T→FT39。T id+id*id。) L。 pop(E), push(TE39。L) L。 pop(L), push(E。 ε ε F id num (E) 4 用預(yù)測(cè)分析器分析句子 id+id*id。 /FT39。 T39。 FT39。 TE39。 E39。 TE39。L E。 L E。 分析成功 end loop。 end if。展開產(chǎn)生式 else error(2)。 else if M[x, a] = X→Y 1Y2...Yk then pop(X)。 匹配終結(jié)符 else error(1)。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1