蒙城做网站的公司,网站建设虚拟,随县网站建设,石家庄网站建设q.479185700棒构造FIRST和FOLLOW的大白话网站
第四章
1
考虑文法 G 1 G_1 G1: S → a ∣ ∧ ∣ ( T ) T → T , S ∣ S S \rightarrow a|\land|(T) \\ T\rightarrow T,S|S S→a∣∧∣(T)T→T,S∣S
先复习左递归如何消除 原书p69页
类似于 P → P a ∣ b P\rightarrow Pa|b P→Pa∣b的…构造FIRST和FOLLOW的大白话网站
第四章
1
考虑文法 G 1 G_1 G1: S → a ∣ ∧ ∣ ( T ) T → T , S ∣ S S \rightarrow a|\land|(T) \\ T\rightarrow T,S|S S→a∣∧∣(T)T→T,S∣S
先复习左递归如何消除 原书p69页
类似于 P → P a ∣ b P\rightarrow Pa|b P→Pa∣b的形式可以改写成 P → b P ′ P\rightarrow bP^{} P→bP′ P ′ → a P ′ ∣ ϵ P^{}\rightarrow aP^{}|\epsilon P′→aP′∣ϵ
提公因子 P → P a 1 ∣ . . . ∣ P a m ∣ b 1 ∣ . . . b n ∣ P\rightarrow Pa_1|...|Pa_m|b_1|...b_n| P→Pa1∣...∣Pam∣b1∣...bn∣ 转换为 P → b 1 P ′ ∣ . . . ∣ b n P ′ ∣ P\rightarrow b_1P^{}|...|b_nP^{}| P→b1P′∣...∣bnP′∣ P ′ → a 1 P ′ ∣ . . . ∣ a m P ′ ∣ ϵ P^{}\rightarrow a_1P^{}|...|a_mP^{}|\epsilon P′→a1P′∣...∣amP′∣ϵ
(1) 消除 G 1 G_1 G1左递归。并对每个非终结符写出不带回溯的递归子程序
1. 消除左递归
分析不难发现左递归只在第二条地推中出现应修改第二条
将b后面塞上一个新非终结符删去原有的左递归部分新非终结符可以递推出 左递归右半部分 新非终结符 S → a ∣ ∧ ∣ ( T ) T → S A A → , S A ∣ ϵ S \rightarrow a|\land|(T) \\ T\rightarrow SA\\ A\rightarrow ,SA|\epsilon S→a∣∧∣(T)T→SAA→,SA∣ϵ
2.递归下降子程序
详见原书 p74
procedure S;
beginif (sym a) or (sym ^)then advancce;else if sym (then beginadvance; Tif sym )then advanceelse errorendelse error;
endprocedure T;
beginS;A
endprocedure A;
beginif sym ,then beginadvance;S;Aendelse error
end根据74页的定义
advance 输入串指示器IP 指向下一个输入符号
sym : IP当前所指的输入符号
error : 出错程序根据原文 (2) 改写后的文法是否为LL(1)的给出预测分析表
知识点
证明文法为LL(1) 预测分析表 M 不含多重定义入口 ⇔ 文法为 L L ( 1 ) 预测分析表M不含多重定义入口 \Leftrightarrow 文法为LL(1) 预测分析表M不含多重定义入口⇔文法为LL(1)
构造分析表M算法
首先需要构造FISRT集
若 X ∈ V T X\in V_T X∈VT则 F I R S T ( X ) { X } FIRST(X) \{X\} FIRST(X){X}若 X ∈ V N ∧ X → a . . . X\in V_N \land X\rightarrow a... X∈VN∧X→a..., 把a放入 F I R S T ( X ) FIRST(X) FIRST(X)中 若 X → ϵ X\rightarrow \epsilon X→ϵ ϵ \epsilon ϵ也放入 F I R S T ( X ) FIRST(X) FIRST(X)中 若 X → Y . . . ∧ Y ∈ V N X\rightarrow Y... \land Y\in V_N X→Y...∧Y∈VN 将 F I R S T ( Y ) − ϵ FIRST(Y) - \epsilon FIRST(Y)−ϵ 的元素加入 F I R S T ( X ) FIRST(X) FIRST(X)中 若 X → Y 1 Y 2 . . . Y k . . . ∧ Y 1 , . . . , Y i − 1 非终结符 ∧ 对于任何 j ( 1 ≤ j ≤ i − 1 ) , F I R S T ( Y j ) 含有 ϵ X\rightarrow Y_1Y_2...Y_k... \land Y_1,...,Y_{i-1}非终结符\land 对于任何j(1\le j \le i - 1), FIRST(Y_j)含有\epsilon X→Y1Y2...Yk...∧Y1,...,Yi−1非终结符∧对于任何j(1≤j≤i−1),FIRST(Yj)含有ϵ, 则把 F I R S T ( Y i ) − ϵ FIRST(Y_i)-\epsilon FIRST(Yi)−ϵ加入 F I R S T ( X ) 中 FIRST(X)中 FIRST(X)中特别的若所有的 F I R S T ( Y j ) 都含有 ϵ , j 1 , 2 , . . . , k FIRST(Y_j)都含有\epsilon, j 1,2,..., k FIRST(Yj)都含有ϵ,j1,2,...,k 把 ϵ \epsilon ϵ 加入 F I R S T ( X ) FIRST(X) FIRST(X)中
省流在生成式右边在最开头的终结符直接计入FIRST 然后开头的终结符除了epsilon也全计入 如果右边整个串可以推导出空串epsilon也计入
然后构造FOLLOW集
对于文法开始符号 S S S放置#到 F O L L O W ( S ) FOLLOW(S) FOLLOW(S) 中 下面这个处理的是first在B后面FIRST 放入 前一个非终结符的FOLLOW 若 A → α B β A\rightarrow \alpha B\beta A→αBβ 把 F I R S T ( β ) − ϵ FIRST(\beta) - \epsilon FIRST(β)−ϵ 放入 F O L L O W ( B ) FOLLOW(B) FOLLOW(B) 后两种本质是同一种将生成式左半部分的FOLLOW 给 末尾的非终结符FOLLOW A → α B A\rightarrow \alpha B A→αB 把 F O L L O W ( A ) FOLLOW(A) FOLLOW(A)放入 F O L L O W ( B ) FOLLOW(B) FOLLOW(B) A → α B β ∧ β ⇒ ϵ A\rightarrow \alpha B\beta \land \beta \Rightarrow\epsilon A→αBβ∧β⇒ϵ (也就是说 ϵ ∈ F I R S T ( β ) \epsilon \in FIRST(\beta) ϵ∈FIRST(β)) 把 F O L L O W ( A ) FOLLOW(A) FOLLOW(A)放入 F O L L O W ( B ) FOLLOW(B) FOLLOW(B)
最后构造M
对文法 G G G 产生式 A → α A\rightarrow \alpha A→α 进行(2)(3)操作终结符 a ∈ F I R S T ( α ) a\in FIRST(\alpha) a∈FIRST(α) 加入 M [ A , a ] M[A, a] M[A,a]中若 ϵ ∈ F I R S T ( α ) \epsilon \in FIRST(\alpha) ϵ∈FIRST(α)则对任何 b ∈ F O L L O W ( A ) b \in FOLLOW(A) b∈FOLLOW(A)把 A → α A\rightarrow \alpha A→α 放入 M [ A , b ] M[A, b] M[A,b]中没有定义则出错 解题过程
① 构造FIRST
首先考虑 S → a ∣ ∧ ∣ ( T ) S \rightarrow a|\land|(T) S→a∣∧∣(T)
不难发现a,^,(都出现在了产生式右端的最左端 所以有 F I R S T ( S ) { a , ∧ , ( } FIRST(S) \{a,\land, (\} FIRST(S){a,∧,(}
考虑 T → S A T\rightarrow SA T→SA
根据构造FOLLOW集的第四种情况需要将 F I R S T ( S ) − ϵ 所有元素放入 F I R S T ( T ) 中 FIRST(S) - \epsilon所有元素放入 FIRST(T)中 FIRST(S)−ϵ所有元素放入FIRST(T)中 F I R S T ( T ) { a , ∧ , ( } FIRST(T) \{a,\land, (\} FIRST(T){a,∧,(}
考虑 A → , S A ∣ ϵ A\rightarrow ,SA|\epsilon A→,SA∣ϵ F I R S T ( A ) { , ϵ } FIRST(A) \{ , \epsilon\} FIRST(A){,ϵ} ② 构造FOLLOW 我们已经有了 F I R S T ( S ) { a , ∧ , ( } FIRST(S) \{a,\land, (\} FIRST(S){a,∧,(} F I R S T ( T ) { a , ∧ , ( } FIRST(T) \{a,\land, (\} FIRST(T){a,∧,(} F I R S T ( A ) { , ϵ } FIRST(A) \{ , \epsilon\} FIRST(A){,ϵ}
首先考虑 S → a ∣ ∧ ∣ ( T ) S \rightarrow a|\land|(T) S→a∣∧∣(T)
根据规则1需要存#进 F O L L O W ( S ) FOLLOW(S) FOLLOW(S)根据规则2需要将 F I R S T ( ) − ϵ FIRST()-\epsilon FIRST()−ϵ的元素放进去 F O L L O W ( T ) FOLLOW(T) FOLLOW(T)
于是第一步我们有 F O L L O W ( S ) { # } F O L L O W ( T ) { ) } FOLLOW(S) \{\#\}\\ FOLLOW(T) \{)\} FOLLOW(S){#}FOLLOW(T){)}
考虑 T → S A T\rightarrow SA T→SA
根据规则3需要将 F O L L O W ( T ) FOLLOW(T) FOLLOW(T)的元素放进去 F O L L O W ( A ) FOLLOW(A) FOLLOW(A)
得到 F O L L O W ( S ) { # } F O L L O W ( T ) { ) } F O L L O W ( A ) { ) } FOLLOW(S) \{\#\}\\ FOLLOW(T) \{)\}\\ FOLLOW(A) \{)\} FOLLOW(S){#}FOLLOW(T){)}FOLLOW(A){)}
考虑 A → , S A ∣ ϵ A\rightarrow ,SA|\epsilon A→,SA∣ϵ
根据规则2需要将 F I R S T ( A ) − ϵ FIRST(A) - \epsilon FIRST(A)−ϵ的元素放进去 F O L L O W ( S ) FOLLOW(S) FOLLOW(S)根据规则4(A可以推导出 ϵ \epsilon ϵ)需要将 F O L L O W ( A ) FOLLOW(A) FOLLOW(A)的元素放进去 F O L L O W ( S ) FOLLOW(S) FOLLOW(S)
得到 F O L L O W ( S ) { , ) , # } F O L L O W ( T ) { ) } F O L L O W ( A ) { ) } FOLLOW(S) \{, ),\#\}\\ FOLLOW(T) \{)\}\\ FOLLOW(A) \{)\} FOLLOW(S){,),#}FOLLOW(T){)}FOLLOW(A){)} ③ 构造M S → a ∣ ∧ ∣ ( T ) T → S A A → , S A ∣ ϵ S \rightarrow a|\land|(T) \\ T\rightarrow SA\\ A\rightarrow ,SA|\epsilon S→a∣∧∣(T)T→SAA→,SA∣ϵ F I R S T ( S ) { a , ∧ , ( } F I R S T ( T ) { a , ∧ , ( } F I R S T ( A ) { , ϵ } F O L L O W ( S ) { , ) , # } F O L L O W ( T ) { ) } F O L L O W ( A ) { ) } FIRST(S) \{a,\land, (\}\quad FIRST(T) \{a,\land, (\} \quad FIRST(A) \{ , \epsilon\} \\ FOLLOW(S) \{, ),\#\}\quad FOLLOW(T) \{)\}\quad FOLLOW(A) \{)\} FIRST(S){a,∧,(}FIRST(T){a,∧,(}FIRST(A){,ϵ}FOLLOW(S){,),#}FOLLOW(T){)}FOLLOW(A){)}
对这三个生成式套用步骤2
首先按照 F I R S T ( S ) FIRST(S) FIRST(S) 我们有 a a a ∧ \land ∧ ( ( ( ) ) ) , , , # \# # S S S S → a S\rightarrow a S→a S → ∧ S\rightarrow \land S→∧ S → ( T ) S\rightarrow (T) S→(T) 然后按照 F I R S T ( T ) FIRST(T) FIRST(T) 我们有 a a a ∧ \land ∧ ( ( ( ) ) ) , , , # \# # S S S S → a S\rightarrow a S→a S → ∧ S\rightarrow \land S→∧ S → ( T ) S\rightarrow (T) S→(T) T T T T → S A T\rightarrow SA T→SA T → S A T\rightarrow SA T→SA T → S A T\rightarrow SA T→SA 根据 F I R S T ( A ) FIRST(A) FIRST(A) a a a ∧ \land ∧ ( ( ( ) ) ) , , , # \# # S S S S → a S\rightarrow a S→a S → ∧ S\rightarrow \land S→∧ S → ( T ) S\rightarrow (T) S→(T) T T T T → S A T\rightarrow SA T→SA T → S A T\rightarrow SA T→SA T → S A T\rightarrow SA T→SA A A A A → ϵ A\rightarrow \epsilon A→ϵ A → , S A A\rightarrow ,SA A→,SA
对这三个生成式套用步骤3发现满足步骤3的只有 A → ϵ A\rightarrow \epsilon A→ϵ A → , S A A\rightarrow ,SA A→,SA这个生成式中 , S A ,SA ,SA无法变成 ϵ \epsilon ϵ ϵ ∈ F I R S T ( A ) \epsilon \in FIRST(A) ϵ∈FIRST(A),对 ∀ b ∈ F O L L O W ( A ) \forall b\in FOLLOW(A) ∀b∈FOLLOW(A)将 A → α A\rightarrow\alpha A→α 放入M[Ab]中
不难发现FOLLOW(A)只有右括号 } 然后重复填入 A → ϵ A\rightarrow \epsilon A→ϵ
最终的M没有多重定义入口 所以满足LL(1) 2
考虑文法G: E → T E ′ E ′ → E ∣ ϵ T → F T ′ T ′ → T ∣ ϵ F → P F ′ F ′ → ∗ F ′ ∣ ϵ P → ( E ) ∣ a ∣ b ∣ ∧ E\rightarrow TE^{}\\E^{}\rightarrow E|\epsilon\\T\rightarrow FT^{}\\ T^{}\rightarrow T|\epsilon\\F\rightarrow PF^{}\\F^{}\rightarrow *F^{}|\epsilon\\P\rightarrow (E)|a|b|\land E→TE′E′→E∣ϵT→FT′T′→T∣ϵF→PF′F′→∗F′∣ϵP→(E)∣a∣b∣∧ (1) 计算文法G非终结符的FIRST和FOLLOW
计算FIRST
① 首先根据规则1 若右边第一个符号是终结符或 ε 则直接将其加入 FIRSTX构造出最初始的FIRST F I R S T ( E ) F I R S T ( E ′ ) { , ϵ } F I R S T ( T ) F I R S T ( T ′ ) { ϵ } F I R S T ( F ) F I R S T ( F ′ ) { ∗ , ϵ } F I R S T ( P ) { ( , a , b , ∧ } FIRST(E)\quad FIRST(E^{}) \{,\epsilon\} \quad FIRST(T) \quad FIRST(T^{}) \{\epsilon\} \\ FIRST(F) \quad FIRST(F^{}) \{*,\epsilon\} \quad FIRST(P) \{ (, a, b, \land \} FIRST(E)FIRST(E′){,ϵ}FIRST(T)FIRST(T′){ϵ}FIRST(F)FIRST(F′){∗,ϵ}FIRST(P){(,a,b,∧}
② 考虑规则2右边第一个符号是非终结符则将其 FIRST 集的的非 ε 元素加入 FIRSTX F I R S T ( E ) { ( , a , b , ∧ } F I R S T ( E ′ ) { , ϵ } F I R S T ( T ) { ( , a , b , ∧ } F I R S T ( T ′ ) { ( , a , b , ∧ , ϵ } F I R S T ( F ) { ( , a , b , ∧ } F I R S T ( F ′ ) { ∗ , ϵ } F I R S T ( P ) { ( , a , b , ∧ } FIRST(E) \{ (, a, b, \land \}\quad FIRST(E^{}) \{,\epsilon\} \quad \\ FIRST(T) \{ (, a, b, \land \} \quad FIRST(T^{}) \{(, a, b, \land, \epsilon\} \\ FIRST(F) \{ (, a, b, \land \} \quad FIRST(F^{}) \{*,\epsilon\} \quad FIRST(P) \{ (, a, b, \land \} FIRST(E){(,a,b,∧}FIRST(E′){,ϵ}FIRST(T){(,a,b,∧}FIRST(T′){(,a,b,∧,ϵ}FIRST(F){(,a,b,∧}FIRST(F′){∗,ϵ}FIRST(P){(,a,b,∧}
再次检查规则123发现无法再使任意一个FIRST集合产生变化故构造FOLLOW集合 FOLLOW集
首先使用规则1 若A-aBb是一条规则则把FIRST(b)中的非ε元素加到FOLLOW(B)中,其中#为终止符默认放在起始符的FOLLOW集合中
$$FOLLOW(E) {#,)}\quad FOLLOW(E^{‘}) {} \quad FOLLOW(T) {} \quad FOLLOW(T^{’}) {} \
FOLLOW(F) {(, a, b, \land} \quad FOLLOW(F^{}) {} \quad FOLLOW§ { * } $$
使用规则2 若A-aB或A-aBb是一条规则且bε,则把FOLLOW(A)加到FOLLOW(B)中; F O L L O W ( E ) { # , ) } F O L L O W ( E ′ ) { # , ) } F O L L O W ( T ) { # , ) , } F O L L O W ( T ′ ) { # , ) , } F O L L O W ( F ) { ( , a , b , ∧ , # , ) , } F O L L O W ( F ′ ) { ( , a , b , ∧ , # , ) , } F O L L O W ( P ) { ( , a , b , ∧ , # , ) , , ∗ } FOLLOW(E) \{\#,)\}\quad FOLLOW(E^{}) \{\#,)\} \quad FOLLOW(T) \{\#,),\} \quad FOLLOW(T^{}) \{\#,),\} \\ FOLLOW(F) \{(, a, b, \land, \#,),\} \quad FOLLOW(F^{}) \{(, a, b, \land, \#,),\} \quad FOLLOW(P) \{ (, a, b, \land, \#,),, * \} FOLLOW(E){#,)}FOLLOW(E′){#,)}FOLLOW(T){#,),}FOLLOW(T′){#,),}FOLLOW(F){(,a,b,∧,#,),}FOLLOW(F′){(,a,b,∧,#,),}FOLLOW(P){(,a,b,∧,#,),,∗} (2) 证明文法为LL(1)
除了直接构造矩阵M看是否有多重入口还可以使用p73的证明
文法无左递归对文法非终结符A产生的候选符集合两两不相交 对于 A → a 1 ∣ . . . ∣ a n F i r s t ( a i ) ∩ F i r s t ( a j ) ∅ 对于A\rightarrow a_1|...|a_n\quad First(a_i)\cap First(a_j) \empty 对于A→a1∣...∣anFirst(ai)∩First(aj)∅文法非终结符A若他候选符集包含 ϵ \epsilon ϵ 则 F I R S T ( A ) ∩ F O L L O W ( A ) ∅ FIRST(A)\cap FOLLOW(A) \empty FIRST(A)∩FOLLOW(A)∅
① 不难发现该文法无左递归
② 有多个候选符的产生式为 第二第四第六第七行
不难发现 注意你要求的是一整个串比如E,就得求FIRST(E)而 E的首字符只有 F I R S T ( E ) { } ∩ F I R S T ( ϵ ) ∅ F I R S T ( T ) { ( , a , b , ∧ } ∩ F I R S T ( ϵ ) ∅ F I R S T ( ∗ F ′ ) { ∗ } ∩ F I R S T ( ϵ ) ∅ F I R S T ( ( E ) ) { ( } , 与 a , b , ∧ 构成的 F I R S T 集两两不相交 FIRST(E) \{\} \cap FIRST(\epsilon) \empty\\ FIRST(T) \{ (, a, b, \land\}\cap FIRST(\epsilon) \empty\\ FIRST(*F^{}) \{*\} \cap FIRST(\epsilon) \empty \\ FIRST((E)) \{ (\},与a,b,\land构成的FIRST集两两不相交 FIRST(E){}∩FIRST(ϵ)∅FIRST(T){(,a,b,∧}∩FIRST(ϵ)∅FIRST(∗F′){∗}∩FIRST(ϵ)∅FIRST((E)){(},与a,b,∧构成的FIRST集两两不相交
③ 产生式含 ϵ \epsilon ϵ的为第二第四第六行。显然 F I R S T ( E ′ ) ∩ F O L L O W ( E ′ ) ∅ F I R S T ( T ′ ) ∩ F O L L O W ( T ′ ) ∅ F I R S T ( F ′ ) ∩ F O L L O W ( F ′ ) ∅ FIRST(E^{}) \cap FOLLOW (E^{}) \empty \\ FIRST(T^{}) \cap FOLLOW (T^{}) \empty \\ FIRST(F^{}) \cap FOLLOW (F^{}) \empty FIRST(E′)∩FOLLOW(E′)∅FIRST(T′)∩FOLLOW(T′)∅FIRST(F′)∩FOLLOW(F′)∅
综上其为LL(1)文法
(3) 构造它的预测分析表
构造M
对文法 G G G 产生式 A → α A\rightarrow \alpha A→α 进行(2)(3)操作终结符 a ∈ F I R S T ( α ) a\in FIRST(\alpha) a∈FIRST(α) 加入 M [ A , a ] M[A, a] M[A,a]中若 ϵ ∈ F I R S T ( α ) \epsilon \in FIRST(\alpha) ϵ∈FIRST(α)则对任何 b ∈ F O L L O W ( A ) b \in FOLLOW(A) b∈FOLLOW(A)把 A → α A\rightarrow \alpha A→α 放入 M [ A , b ] M[A, b] M[A,b]中没有定义则出错
对 E → T E ′ E\rightarrow TE^{} E→TE′ , 我们根据规则2
*ab⋀#E E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′
对 E ′ → E ∣ ϵ E^{}\rightarrow E|\epsilon E′→E∣ϵ , 我们根据规则2
*ab⋀#E E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′E’ E ′ → E E^{}\rightarrow E E′→E
根据规则3
*ab⋀#E E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′E’ E ′ → E E^{}\rightarrow E E′→E E ′ → ϵ E^{}\rightarrow \epsilon E′→ϵ E ′ → ϵ E^{}\rightarrow \epsilon E′→ϵ
最终得到如下分析表
*ab⋀#E E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′ E → T E ′ E\rightarrow TE^{} E→TE′E’ E ′ → E E^{}\rightarrow E E′→E E ′ → ϵ E^{}\rightarrow \epsilon E′→ϵ E ′ → ϵ E^{}\rightarrow \epsilon E′→ϵT T → F T ′ T\rightarrow FT^{} T→FT′ T → F T ′ T\rightarrow FT^{} T→FT′ T → F T ′ T\rightarrow FT^{} T→FT′ T → F T ′ T\rightarrow FT^{} T→FT′T’ T ′ → ϵ T^{}\rightarrow \epsilon T′→ϵ T ′ → T T^{}\rightarrow T T′→T T ′ → ϵ T^{}\rightarrow \epsilon T′→ϵ T ′ → T T^{}\rightarrow T T′→T T ′ → T T^{}\rightarrow T T′→T T ′ → T T^{}\rightarrow T T′→T T ′ → ϵ T^{}\rightarrow \epsilon T′→ϵF F → P F ′ F\rightarrow PF^{} F→PF′ F → P F ′ F\rightarrow PF^{} F→PF′ F → P F ′ F\rightarrow PF^{} F→PF′ F → P F ′ F\rightarrow PF^{} F→PF′F’ F ′ → ϵ F^{}\rightarrow \epsilon F′→ϵ F ′ → ∗ F ′ F^{}\rightarrow *F^{} F′→∗F′ F ′ → ϵ F^{}\rightarrow \epsilon F′→ϵ F ′ → ϵ F^{}\rightarrow \epsilon F′→ϵ F ′ → ϵ F^{}\rightarrow \epsilon F′→ϵ F ′ → ϵ F^{}\rightarrow \epsilon F′→ϵ F ′ → ϵ F^{}\rightarrow \epsilon F′→ϵ F ′ → ϵ F^{}\rightarrow \epsilon F′→ϵP P → ( E ) P\rightarrow (E) P→(E) P → a P\rightarrow a P→a P → b P\rightarrow b P→b P → ∧ P\rightarrow \land P→∧ (4) 构造它的递归下降分析程序
procedure E:
beginif sym ( or sym aor sym Bor sym ^then beginT;E’endelseerror
endprocedure E’:
beginif sym then beginadvance;Eendelse if sym ) and sym #then error
endprocedure T:
beginif sym ( or sym aor sym Bor sym ^then beginF;T’endelseerror
endprocedure T’:
beginif sym ( or sym aor sym Bor sym ^then beginT;endelse if sym *error
endprocedure F:
beginif sym ( or sym aor sym Bor sym ^then beginP;F’endelseerror
endprocedure F’:
beginif sym * then beginadvance;F’end
endprocedure P:
beginif sym aor sym Bor sym ^then advanceelse if sym ( then beginadvance;E;if sym )then advanceelseerrorendelseerror
end3
下面文法中那些是LL(1)文法 一个文法G的预测分析表M不含多重定义入口当且仅当该文法为LL(1)的。
什么时候没有多重入口从M的构造入手
生成时左部如果相同的话他们各自的右部FIRST两两不相交不然会有多重入口其次右边若存在epsilon属于某一个FIRST——并且最多只有一个能生成epsilon串不然根据条件①也是会重复的,需要保证左部的FOLLOW和其余的右部FIRST两两不相交 (要是不会写这个那直接构造M也是可以的但是都能构造M了上面这个其实也应该懂。
(1) S → A B c A → a ∣ ϵ B → b ∣ ϵ S\rightarrow ABc\\ A\rightarrow a|\epsilon\\ B\rightarrow b|\epsilon\\ S→ABcA→a∣ϵB→b∣ϵ
① 不含左递归
② 显然第二第三行的候选终结首符集两两不相交
③ 由于第二第三行推导式右边含 ϵ \epsilon ϵ
先求出相关的FIRST和FOLLOW集合 F I R S T ( S ) { a , b , c } F O L L O W ( S ) { # } F I R S T ( A ) { a , ϵ } F O L L O W ( A ) { b , c } F I R S T ( B ) { b , ϵ } F O L L O W ( B ) { c } FIRST(S) \{a,b,c\} \quad FOLLOW(S) \{\# \}\\ FIRST(A) \{a, \epsilon\}\quad FOLLOW(A) \{b,c\}\\ FIRST(B) \{b, \epsilon\}\quad FOLLOW(B) \{c \}\\ FIRST(S){a,b,c}FOLLOW(S){#}FIRST(A){a,ϵ}FOLLOW(A){b,c}FIRST(B){b,ϵ}FOLLOW(B){c}
不难发现AB对应的FIRST集与FOLLOW集合相交为空集
满足LL(1) (2) S → A b A → a ∣ B ∣ ϵ B → b ∣ ϵ S\rightarrow Ab\\ A\rightarrow a|B|\epsilon\\ B\rightarrow b|\epsilon S→AbA→a∣B∣ϵB→b∣ϵ
① 不含左递归 F I R S T ( S ) { a , b } F O L L O W ( S ) { # } F I R S T ( A ) { a , b , ϵ } F O L L O W ( A ) { b } F I R S T ( B ) { b , ϵ } F O L L O W ( B ) { b } FIRST(S) \{a,b\} \quad FOLLOW(S) \{\# \}\\ FIRST(A) \{a, b,\epsilon\}\quad FOLLOW(A) \{b\}\\ FIRST(B) \{b, \epsilon\}\quad FOLLOW(B) \{ b\}\\ FIRST(S){a,b}FOLLOW(S){#}FIRST(A){a,b,ϵ}FOLLOW(A){b}FIRST(B){b,ϵ}FOLLOW(B){b}
由于A-B参考规则2(因为B后面没字符串了为空船)需要将follow(A)传递给follow(B)
② 对于第二行导出式子有 F I R S T ( B ) ∩ F I R S T ( ϵ ) { ϵ } FIRST(B)\cap FIRST(\epsilon) \{\epsilon\} FIRST(B)∩FIRST(ϵ){ϵ}
不符合LL(1) (3) S → A B B A A → a ∣ ϵ B → b ∣ ϵ S\rightarrow ABBA\\ A\rightarrow a|\epsilon\\ B\rightarrow b|\epsilon S→ABBAA→a∣ϵB→b∣ϵ
① 不含左递归 F I R S T ( S ) { a , b , ϵ } F O L L O W ( S ) { # } F I R S T ( A ) { a , ϵ } F O L L O W ( A ) { b , # } F I R S T ( B ) { a , b , ϵ } F O L L O W ( B ) { a , b , # } FIRST(S) \{a,b,\epsilon\} \quad FOLLOW(S) \{\# \}\\ FIRST(A) \{a,\epsilon\}\quad FOLLOW(A) \{b,\#\}\\ FIRST(B) \{a, b,\epsilon\}\quad FOLLOW(B) \{a, b, \#\}\\ FIRST(S){a,b,ϵ}FOLLOW(S){#}FIRST(A){a,ϵ}FOLLOW(A){b,#}FIRST(B){a,b,ϵ}FOLLOW(B){a,b,#}
② 对于第二行和第三行他们的候选终结首符集两两不相交
③ F I R S T ( B ) ∩ F O L L O W ( B ) { a , b } ≠ ∅ FIRST(B)\cap FOLLOW(B) \{a,b\} \neq \empty FIRST(B)∩FOLLOW(B){a,b}∅
不满足LL(1) (4) S → a S e ∣ B B → b B e ∣ C C → c C e ∣ d S\rightarrow aSe|B\\ B\rightarrow bBe|C\\ C\rightarrow cCe|d S→aSe∣BB→bBe∣CC→cCe∣d
① 不含左递归 F I R S T ( S ) { a , b , c , d } F O L L O W ( S ) { e , # } F I R S T ( B ) { b , c , d } F O L L O W ( B ) { e , # } F I R S T ( C ) { c , d } F O L L O W ( C ) { e , # } FIRST(S) \{a,b,c,d\} \quad FOLLOW(S) \{e,\#\}\\ FIRST(B) \{b,c,d\}\quad FOLLOW(B) \{e,\#\}\\ FIRST(C) \{c,d\}\quad FOLLOW(C) \{e,\#\}\\ FIRST(S){a,b,c,d}FOLLOW(S){e,#}FIRST(B){b,c,d}FOLLOW(B){e,#}FIRST(C){c,d}FOLLOW(C){e,#}
不难发现均满足条件②和条件③
符合LL(1)文法 4
对下面的文法 E x p r → − E x p r E x p r → ( E x p r ) ∣ V a r E x p r T a i l E x p r T a i l → − E x p r ∣ ϵ V a r → i d V a r T a i l V a r T a i l → ( E x p r ) ∣ ϵ Expr\rightarrow -Expr\\ Expr \rightarrow (Expr)| Var\ ExprTail\\ ExprTail \rightarrow -Expr|\epsilon\\ Var\rightarrow id\ VarTail\\ VarTail \rightarrow (Expr)|\epsilon Expr→−ExprExpr→(Expr)∣Var ExprTailExprTail→−Expr∣ϵVar→id VarTailVarTail→(Expr)∣ϵ
构造LL(1)分析表
重命名一下太花里胡哨了 E → − E E → ( E ) ∣ V D D → − E ∣ ϵ V → i d C C → ( E ) ∣ ϵ E\rightarrow -E\\ E \rightarrow (E)|\ VD\\ D \rightarrow -E|\epsilon\\ V\rightarrow id\ C\\ C \rightarrow (E)|\epsilon E→−EE→(E)∣ VDD→−E∣ϵV→id CC→(E)∣ϵ
构造FIRST和FOLLOW F I R S T ( E ) { − , ( , i d } F O L L O W ( E ) { # , ) } F I R S T ( V ) { i d } F O L L O W ( V ) { − , # , ) } F I R S T ( D ) { − , ϵ } F O L L O W ( D ) { # , ) } F I R S T ( C ) { ( , ϵ } F O L L O W ( C ) { − , # , ) } FIRST(E) \{-,(,id\} \quad FOLLOW(E) \{\# ,)\}\\ FIRST(V) \{id\} \quad FOLLOW(V) \{-,\# ,)\}\\ FIRST(D) \{-,\epsilon\} \quad FOLLOW(D) \{\# ,)\}\\ FIRST(C) \{(,\epsilon\} \quad FOLLOW(C) \{-,\# ,)\}\\ FIRST(E){−,(,id}FOLLOW(E){#,)}FIRST(V){id}FOLLOW(V){−,#,)}FIRST(D){−,ϵ}FOLLOW(D){#,)}FIRST(C){(,ϵ}FOLLOW(C){−,#,)}
-id()#E E → − E E\rightarrow -E E→−E E → V D E\rightarrow VD E→VD E → ( E ) E\rightarrow (E) E→(E)D D → − E D\rightarrow -E D→−E D → ϵ D\rightarrow \epsilon D→ϵ D → ϵ D\rightarrow \epsilon D→ϵV V → i d C V\rightarrow id\ C V→id CC C → ϵ C\rightarrow \epsilon C→ϵ C → ( E ) C\rightarrow (E) C→(E) C → ϵ C\rightarrow \epsilon C→ϵ C → ϵ C\rightarrow \epsilon C→ϵ
给出句子 id--id((id))的分析过程
分析栈输入产生式#Eid–id((id)) ##DVid–id((id)) #E→VD#DCidid–id((id)) #V→idC#DC–id((id)) ##D–id((id)) #C→ε#E-–id((id)) #D→-E#E-id((id)) ##E--id((id)) #E→-E#Eid((id)) ##DVid((id)) #E→VD#DCidid((id)) #V→idC#DC((id)) ##D)E(((id)) #C→(E)#D)E(id)) ##D))E((id)) #E→(E)#D))Eid)) ##D))DVid)) #E→VD#D))DCidid)) #V→idC#D))DC)) ##D))D)) #C→ϵ#D)))) #D→ϵ#D)) ##D###D→ϵ
ps:麻了这作业花了我六七个小时
