编译原理期末速成二
编译原理期末速成(二)
LL(1) 文法:求 First、Follow 集,预测分析表
定义
依次表示表示自左向右扫描、最左推导、每次(只需)向右读取一个字符
-
文法不含左递归
公式形如 $ p \rightarrow p \alpha |\beta $ 消除左递归
- p → β p ′ p \rightarrow \beta p^{'} p→βp′
- p ′ → α p ′ ∣ ϵ p^{'} \rightarrow \alpha p^{'} | \epsilon p′→αp′∣ϵ
-
非终结符产生式的候选字符集两两不相交
-
非终结符
$A \rightarrow \alpha_1 | \alpha_2 ……|\epsilon $
有 F i r s t ( A ) ∩ F o l l o w ( A ) = ∅ First(A) \cap Follow(A) = \bf \emptyset First(A)∩Follow(A)=∅
求 First 和 Follow
E → E + T ∣ T E \rightarrow E+T |T E→E+T∣T
T → T ∗ F ∣ F T \rightarrow T*F | F T→T∗F∣F
F → ( E ) ∣ i F \rightarrow (E)|i F→(E)∣i
消除左递归
-
对于 E E E
(1) E → T E ′ E \rightarrow TE^{'} E→TE′
(2) E ′ → + T E ′ ∣ ϵ E^{'} \rightarrow +TE^{'} | \epsilon E′→+TE′∣ϵ
-
对于 T T T
(3) T → F T ′ T \rightarrow FT^{'} T→FT′
(4) T ′ → ∗ F T ′ ∣ ϵ T^{'} \rightarrow *F T^{'} | \epsilon T′→∗FT′∣ϵ
(5) F → ( E ) ∣ i F \rightarrow (E) | i F→(E)∣i
求解
四项基本原则
- 直接推 ( → \rightarrow →)
- 最前 || 最后
- F → P Q F \rightarrow PQ F→PQ (进入)
- 紧挨着 (右侧紧挨着的)
F i r s t First First 遵循123, F o l l w Follw Follw 遵循 234
First
待求:
- F i r s t ( E ) First(E) First(E)
- F i r s t ( E ′ ) First(E^{'}) First(E′)
- F i r s t ( T ) First(T) First(T)
- F i r s t ( T ′ ) First(T^{'}) First(T′)
- F i r s t ( F ) First(F) First(F)
对于 1 中的 E,依次有非终结符序列 E → T → F E \rightarrow T \rightarrow F E→T→F, F F F 能直接推的包括 ( , i ) (,i) (,i), 从而有 F i r s t ( F ) = { ( , i } = F i r s t ( T ) = F i r s t ( E ) First(F) = \{(,i\} = First(T) = First(E) First(F)={(,i}=First(T)=First(E)
对于 2 中的 E ′ E^{'} E′,有 F i r s t ( E ′ ) = { + , ϵ } First(E^{'}) = \{+,\epsilon\} First(E′)={+,ϵ}
对于 4 中的 T ′ T^{'} T′,有 F i r s t ( T ′ ) = { ∗ , ϵ } First(T^{'}) = \{*,\epsilon\} First(T′)={∗,ϵ}
综上所述:
- F i r s t ( E ) = { ( , i } First(E) = \{(,i\} First(E)={(,i}
- F i r s t ( E ′ ) = { + , ϵ } First(E^{'}) = \{+,\epsilon \} First(E′)={+,ϵ}
- F i r s t ( T ) = { ( , i ) } First(T) = \{(,i)\} First(T)={(,i)}
- F i r s t ( T ′ ) = { ∗ , ϵ } First(T^{'}) = \{*,\epsilon\} First(T′)={∗,ϵ}
- F i r s t ( F ) = { ( , i ) } First(F) = \{(,i)\} First(F)={(,i)}
Follow
待求:
- F o l l o w ( E ) Follow (E) Follow(E)
- F o l l o w ( E ′ ) Follow(E^{'}) Follow(E′)
- F o l l o w ( T ) Follow(T) Follow(T)
- F o l l o w ( T ′ ) Follow(T^{'}) Follow(T′)
- F o l l o w ( F ) Follow(F) Follow(F)
对于 E E E,(右侧)挨着的有 ( ( (,对于开始符号必定有 # \# #,从而有 F o l l o w ( E ) = { ) , # } Follow (E) = \{),\#\} Follow(E)={),#}
根据产生式 (1) E → T E ′ E \rightarrow TE^{'} E→TE′、规则 3 ,知 F o l l o w ( E ) Follow (E) Follow(E) “进入” F o l l o w ( T ) Follow (T) Follow(T) 和 F o l l o w ( E ′ ) Follow (E^{'}) Follow(E′),从而有 F o l l o w ( E ′ ) = { ) . # Follow (E^{'}) = \{).\# Follow(E′)={).#, F o l l o w ( T ) = { ) , # Follow(T) = \{),\# Follow(T)={),#
注意此时均未完待续(没有右侧大括号)
检查 F o l l o w ( E ′ ) Follow (E^{'}) Follow(E′),右侧无元素(紧挨着)、没有 E ′ → E^{'} \rightarrow E′→,则确定 F o l l o w ( E ′ ) = { ) . # Follow (E^{'}) = \{).\# Follow(E′)={).#
检查 F o l l o w ( T ) Follow (T) Follow(T),对于产生式 (2) E ′ → + T E ′ ∣ ϵ E^{'} \rightarrow +TE^{'} | \epsilon E′→+TE′∣ϵ ,有 E ′ E{'} E′ 紧挨着,则将 F i r s t ( E ′ ) First(E^{'}) First(E′) 中的非 ϵ \epsilon ϵ 元素加入 F o l l o w ( T ) Follow(T) Follow(T)
综上所述:
- F o l l o w ( E ) = { ) , # } Follow(E) = \{),\#\} Follow(E)={),#}
- F o l l o w ( E ′ ) = { ) , # , Follow(E^{'}) = \{),\#, Follow(E′)={),#,
- F o l l o w ( T ) = { ) , # , + } Follow(T) = \{),\#,+\} Follow(T)={),#,+}
- F o l l o w ( T ′ ) = { ) , # , + Follow(T^{'}) = \{),\#,+ Follow(T′)={),#,+
- F o l l o w ( F ) = { ) , # , + , ∗ } Follow(F) = \{),\#,+,*\} Follow(F)={),#,+,∗}
此时 123 已完成
由 (3) T → T ′ F T \rightarrow T^{'}F T→T′F 、规则 3 可知
-
F o l l o w ( T ′ ) = F o l l o w ( T ) + s o m e t h i n g = { ) , # , + Follow(T^{'}) = Follow(T) + something = \{),\#,+ Follow(T′)=Follow(T)+something={),#,+
T ′ T^{'} T′ 无 4 ,则此处 s o m e t h i n g = ∅ something = \empty something=∅, F o l l o w ( T ′ ) = { ) , # , + } Follow(T^{'}) = \{),\#,+\} Follow(T′)={),#,+}
-
F o l l o w ( F ) = F o l l o w ( T ) + s o m e t h i n g = { ) , # , + Follow(F^{}) = Follow(T) + something = \{),\#,+ Follow(F)=Follow(T)+something={),#,+
根据文法(3),规则 4 ,将 ∗ * ∗ 加入
对于同一非终结符、且含空的First和Follow,二者是否有交集
# \# #, ϵ \epsilon ϵ 视作不同
F i r s t ( E ′ ) ∩ F o l l o w ( E ′ ) = ∅ First(E^{'}) \cap Follow(E^{'}) = \empty First(E′)∩Follow(E′)=∅
F i r s t ( T ′ ) ∩ F o l l o w ( T ′ ) = ∅ First(T^{'}) \cap Follow(T^{'}) = \empty First(T′)∩Follow(T′)=∅
预测分析表
参考 First 的部分
列为非终结符、行为终结符
i | + | * | ( | ) | # | |
---|---|---|---|---|---|---|
E E^{} E | ||||||
E ′ E^{'} E′ | ||||||
T T T | ||||||
T ′ T^{'} T′ | ||||||
F F F |
对于所有非终结符, F i r s t First First 的字符填上(产生式)
对于 F i r s t ( E ) First(E) First(E),即终结符 ( , i (,i (,i,使用产生式 (1)
i | + | * | ( | ) | # | |
---|---|---|---|---|---|---|
E E^{} E | E → T E ′ E \rightarrow TE^{'} E→TE′ | E → T E ′ E \rightarrow TE^{'} E→TE′ | ||||
E ′ E^{'} E′ | ||||||
T T T | ||||||
T ′ T^{'} T′ | ||||||
F F F |
对于 F i r s t ( E ′ ) First(E^{'}) First(E′),即终结符 + , ϵ +,\epsilon +,ϵ,使用仅有产生式 (2)
注意含 ϵ \epsilon ϵ 的部分的处理,也就是对于“或”的处理
i | + | * | ( | ) | # | |
---|---|---|---|---|---|---|
E E^{} E | E → T E ′ E \rightarrow TE^{'} E→TE′ | E → T E ′ E \rightarrow TE^{'} E→TE′ | ||||
E ′ E^{'} E′ | $E^{‘} \rightarrow +TE^{’} $ | E ′ → ϵ E^{'} \rightarrow\epsilon E′→ϵ | ||||
T T T | ||||||
T ′ T^{'} T′ | ||||||
F F F |
对于 F i r s t ( T ) First(T) First(T),即终结符 ( , i (,i (,i,使用产生式 (3)
i | + | * | ( | ) | # | |
---|---|---|---|---|---|---|
E E^{} E | E → T E ′ E \rightarrow TE^{'} E→TE′ | E → T E ′ E \rightarrow TE^{'} E→TE′ | ||||
E ′ E^{'} E′ | $E^{‘} \rightarrow +TE^{’} $ | E ′ → ϵ E^{'} \rightarrow\epsilon E′→ϵ | ||||
T T T | T → F T ′ T \rightarrow FT^{'} T→FT′ | T → F T ′ T \rightarrow FT^{'} T→FT′ | ||||
T ′ T^{'} T′ | ||||||
F F F |
对于 F i r s t ( T ′ ) First(T^{'}) First(T′),即终结符 ∗ , ϵ *,\epsilon ∗,ϵ,使用产生式 (4)
i | + | * | ( | ) | # | |
---|---|---|---|---|---|---|
E E^{} E | E → T E ′ E \rightarrow TE^{'} E→TE′ | E → T E ′ E \rightarrow TE^{'} E→TE′ | ||||
E ′ E^{'} E′ | $E^{‘} \rightarrow +TE^{’} $ | E ′ → ϵ E^{'} \rightarrow\epsilon E′→ϵ | ||||
T T T | T → F T ′ T \rightarrow FT^{'} T→FT′ | T → F T ′ T \rightarrow FT^{'} T→FT′ | ||||
T ′ T^{'} T′ | $T^{‘} \rightarrow *F T^{’} $ | T ′ → ϵ T^{'} \rightarrow \epsilon T′→ϵ | ||||
F F F |
对于 F i r s t ( F ) First(F^{}) First(F),即终结符 ( , i (,i (,i,使用产生式 (5)
i | + | * | ( | ) | # | |
---|---|---|---|---|---|---|
E E^{} E | E → T E ′ E \rightarrow TE^{'} E→TE′ | E → T E ′ E \rightarrow TE^{'} E→TE′ | ||||
E ′ E^{'} E′ | $E^{‘} \rightarrow +TE^{’} $ | E ′ → ϵ E^{'} \rightarrow\epsilon E′→ϵ | ||||
T T T | T → F T ′ T \rightarrow FT^{'} T→FT′ | T → F T ′ T \rightarrow FT^{'} T→FT′ | ||||
T ′ T^{'} T′ | $T^{‘} \rightarrow *F T^{’} $ | T ′ → ϵ T^{'} \rightarrow \epsilon T′→ϵ | ||||
F F F | F → i F \rightarrow i F→i | F → ( E ) F \rightarrow (E) F→(E) |
参考 Follow 的部分
对于新引进的非终结符(此处是 T ′ T^{'} T′ 和 E ′ E^{'} E′), F o l l o w Follow Follow 集也要补上
用 $ \rightarrow \epsilon$ 补充
i | + | * | ( | ) | # | |
---|---|---|---|---|---|---|
E E^{} E | E → T E ′ E \rightarrow TE^{'} E→TE′ | E → T E ′ E \rightarrow TE^{'} E→TE′ | ||||
E ′ E^{'} E′ | $E^{‘} \rightarrow +TE^{’} $ | E ′ → ϵ E^{'} \rightarrow \epsilon E′→ϵ | E ′ → ϵ E^{'} \rightarrow\epsilon E′→ϵ | |||
T T T | T → F T ′ T \rightarrow FT^{'} T→FT′ | T → F T ′ T \rightarrow FT^{'} T→FT′ | ||||
T ′ T^{'} T′ | $ T^{'} \rightarrow \epsilon$ | $T^{‘} \rightarrow *F T^{’} $ | $ T^{'} \rightarrow \epsilon$ | T ′ → ϵ T^{'} \rightarrow \epsilon T′→ϵ | ||
F F F | F → i F \rightarrow i F→i | F → ( E ) F \rightarrow (E) F→(E) |
根据预测分析表写推导
每一步包括对三个部分的处理
-
对分析栈
-
入栈
- 如果是步骤1,则将 # \# # 和开始符依次入栈
- 如果非步骤1,则将上一步推导公式的结果(右侧部分)入栈
此处注意入栈的顺序,如推导式 E → T E ′ E \rightarrow TE^{'} E→TE′,其入栈的顺序为 先 E ′ E^{'} E′ 后 T T T
-
寻找产生式
将分析栈栈顶元素取出,与剩余串串首元素对比
- 栈顶元素 == 剩余串串首元素,
- 栈顶元素 != 剩余串串首元素,则在预测分析表中寻找对应产生式
-
-
对剩余串
若上一步骤完成了“匹配”,将串首元素移除
-
推导式
- 匹配,记作 分析站栈顶元素 → 剩余串串首元素 分析站栈顶元素 \rightarrow 剩余串串首元素 分析站栈顶元素→剩余串串首元素
- 不匹配,写出对应的产生式
如此循环到 分析站顶元素 = 剩余串串首元素 = # 分析站顶元素 = 剩余串串首元素 = \# 分析站顶元素=剩余串串首元素=# ,匹配结束,句子被正确的接收
仍旧以上述文法为基础,以产生式 i + i ∗ i # i+ i*i\# i+i∗i# 为例
步骤 | 分析栈 | 剩余串 | 推导公式 |
---|---|---|---|
1 | # E \#E #E | i + i ∗ i # i+i*i\# i+i∗i# | E → T E ′ E \rightarrow TE^{'} E→TE′ |
- 将 # \# # 和开始符入栈
- 取出栈顶元素 E E E,与串首元素 i i i 对比,寻找推导式
步骤 | 分析栈 | 剩余串 | 推导公式 |
---|---|---|---|
1 | # E \#E #E | i + i ∗ i # i+i*i\# i+i∗i# | E → T E ′ E \rightarrow TE^{'} E→TE′ |
2 | # E T \# ET #ET | i + i ∗ i # i+i*i\# i+i∗i# | T → F T ′ T \rightarrow FT^{'} T→FT′ |
- 将上一步推导式右侧入栈
- 取出栈顶元素 T T T,与串首元素 i i i 对比,寻找推导式
步骤 | 分析栈 | 剩余串 | 推导公式 |
---|---|---|---|
1 | # E \#E #E | i + i ∗ i # i+i*i\# i+i∗i# | E → T E ′ E \rightarrow TE^{'} E→TE′ |
2 | # E ′ T \# E^{'}T #E′T | i + i ∗ i # i+i*i\# i+i∗i# | T → F T ′ T \rightarrow FT^{'} T→FT′ |
3 | # E ′ T ′ F \#E^{'}T^{'}F #E′T′F | i + i ∗ i # i+i*i\# i+i∗i# | F → i F \rightarrow i F→i |
- 将上一步推导式右侧入栈
- 取出栈顶元素 F F F,与串首元素 i i i 对比,寻找推导式
步骤 | 分析栈 | 剩余串 | 推导公式 |
---|---|---|---|
1 | # E \#E #E | i + i ∗ i # i+i*i\# i+i∗i# | E → T E ′ E \rightarrow TE^{'} E→TE′ |
2 | # E ′ T \# E^{'}T #E′T | i + i ∗ i # i+i*i\# i+i∗i# | T → F T ′ T \rightarrow FT^{'} T→FT′ |
3 | # E ′ T ′ F \#E^{'}T^{'}F #E′T′F | i + i ∗ i # i+i*i\# i+i∗i# | F → i F \rightarrow i F→i |
4 | # E ′ T ′ i \#E^{'}T^{'}i #E′T′i | i + i ∗ i # i+i*i\# i+i∗i# | i i i 匹配 |
- 将上一步推导式右侧入栈
- 取出栈顶元素 i i i,与串首元素 i i i 对比,寻找推导式
- 完成匹配
步骤 | 分析栈 | 剩余串 | 推导公式 |
---|---|---|---|
1 | # E \#E #E | i + i ∗ i # i+i*i\# i+i∗i# | E → T E ′ E \rightarrow TE^{'} E→TE′ |
2 | # E ′ T \# E^{'}T #E′T | i + i ∗ i # i+i*i\# i+i∗i# | T → F T ′ T \rightarrow FT^{'} T→FT′ |
3 | # E ′ T ′ F \#E^{'}T^{'}F #E′T′F | i + i ∗ i # i+i*i\# i+i∗i# | F → i F \rightarrow i F→i |
4 | # E ′ T ′ i \#E^{'}T^{'}i #E′T′i | i + i ∗ i # i+i*i\# i+i∗i# | i i i 匹配 |
5 | # E ′ T ′ \#E^{'}T^{'} #E′T′ | + i ∗ i # +i*i\# +i∗i# | $ T^{'} \rightarrow \epsilon$ |
- 上一步没有推导式,没有符号入栈
- 上一步完成了匹配,剩余串栈顶元素删除
- 取出栈顶元素 T ′ T^{'} T′,与串首元素 i i i 对比,寻找推导式
步骤 | 分析栈 | 剩余串 | 推导公式 |
---|---|---|---|
1 | # E \#E #E | i + i ∗ i # i+i*i\# i+i∗i# | E → T E ′ E \rightarrow TE^{'} E→TE′ |
2 | # E ′ T \# E^{'}T #E′T | i + i ∗ i # i+i*i\# i+i∗i# | T → F T ′ T \rightarrow FT^{'} T→FT′ |
3 | # E ′ T ′ F \#E^{'}T^{'}F #E′T′F | i + i ∗ i # i+i*i\# i+i∗i# | F → i F \rightarrow i F→i |
4 | # E ′ T ′ i \#E^{'}T^{'}i #E′T′i | i + i ∗ i # i+i*i\# i+i∗i# | i i i 匹配 |
5 | # E ′ T ′ \#E^{'}T^{'} #E′T′ | + i ∗ i # +i*i\# +i∗i# | $ T^{'} \rightarrow \epsilon$ |
6 | # E ′ \#E^{'} #E′ | + i ∗ i # +i*i\# +i∗i# | $E^{‘} \rightarrow +TE^{’} $ |
- 上一步推导式右侧为空,没有符号入栈
- 取出栈顶元素 $ E^{'}$,与串首元素 i i i 对比,寻找推导式
步骤 | 分析栈 | 剩余串 | 推导公式 |
---|---|---|---|
1 | # E \#E #E | i + i ∗ i # i+i*i\# i+i∗i# | E → T E ′ E \rightarrow TE^{'} E→TE′ |
2 | # E ′ T \# E^{'}T #E′T | i + i ∗ i # i+i*i\# i+i∗i# | T → F T ′ T \rightarrow FT^{'} T→FT′ |
3 | # E ′ T ′ F \#E^{'}T^{'}F #E′T′F | i + i ∗ i # i+i*i\# i+i∗i# | F → i F \rightarrow i F→i |
4 | # E ′ T ′ i \#E^{'}T^{'}i #E′T′i | i + i ∗ i # i+i*i\# i+i∗i# | i i i 匹配 |
5 | # E ′ T ′ \#E^{'}T^{'} #E′T′ | + i ∗ i # +i*i\# +i∗i# | $ T^{'} \rightarrow \epsilon$ |
6 | # E ′ \#E^{'} #E′ | + i ∗ i # +i*i\# +i∗i# | $E^{‘} \rightarrow +TE^{’} $ |
7 | # E ′ T + \#E^{'}T+ #E′T+ | + i ∗ i # +i*i\# +i∗i# | + + + 匹配 |
- 将上一步推导式右侧入栈
- 取出栈顶元素 i i i,与串首元素 i i i 对比,寻找推导式
- 完成匹配
编辑不易,后续内容省略,此推导共 17 17 17 步,最终能接受
自底向上的语法分析
定义
L:从左到右扫描输入串
R:构造最右推导的逆过程
- 记住已移进和规约的内容
- 根据产生式推测下一个符号
F i r s t V T FirstVT FirstVT 和 L a s t V T LastVT LastVT 的构建规则
F i r s t V T FirstVT FirstVT 规则
- 有 P → a + s o m e t h i n g P \rightarrow a + something P→a+something,或 P → Q a + s o m e t h i n g P \rightarrow Qa + something P→Qa+something,有 a ∈ F i r s t V T ( P ) a \in FirstVT(P) a∈FirstVT(P)
- 有 P → Q + s o m e t h i n g P \rightarrow Q + something P→Q+something,则 F i r s t V T ( Q ) ∈ F i r s t V T ( P ) FirstVT(Q) \in FirstVT(P) FirstVT(Q)∈FirstVT(P)
L a s t V T LastVT LastVT 规则
- 有 P → s o m e t h i n g + a P \rightarrow something + a P→something+a,或 P → s o m e t h i n g + a Q P \rightarrow something + aQ P→something+aQ,有 a ∈ L a s t V T ( P ) a \in LastVT(P) a∈LastVT(P)
- 有 P → s o m e t h i n g + Q P \rightarrow something +Q P→something+Q,则 L a s t V T ( Q ) ∈ L a s t V T ( P ) LastVT(Q) \in LastVT(P) LastVT(Q)∈LastVT(P)
例子
有如下文法
E → E + T ∣ T E \rightarrow E+T |T E→E+T∣T
T → T ∗ F ∣ F T \rightarrow T*F | F T→T∗F∣F
F → ( E ) ∣ i F \rightarrow (E)|i F→(E)∣i
求解 F i r s t V t FirstVt FirstVt
根据规则1,有
F i r s t V T ( E ) = { + FirstVT(E) = \{+ FirstVT(E)={+
F i r s t V T ( T ) = { ∗ FirstVT(T) = \{* FirstVT(T)={∗
F i r s t V T ( F ) = { ( , i ) FirstVT(F) = \{(,i) FirstVT(F)={(,i)
根据规则2,有
F i r s t V T ( E ) = { + } + F i r s t V T { T } = { + , ∗ , ( , i } FirstVT(E) = \{+\} + FirstVT\{T\} = \{+,*,(,i\} FirstVT(E)={+}+FirstVT{T}={+,∗,(,i}
$FirstVT(T) = {}+ FirstVT(F) = {,(,i} $
F i r s t V T ( F ) = { ( , i ) FirstVT(F) = \{(,i) FirstVT(F)={(,i)
求解 L a s t V t LastVt LastVt
根据规则1,有
L a s t V t ( E ) = { + LastVt(E) = \{+ LastVt(E)={+
L a s t V T ( T ) = { ∗ LastVT(T) = \{* LastVT(T)={∗
L a s t V T ( F ) = { ) , i LastVT(F) = \{),i LastVT(F)={),i
根据规则2,有
L a s t V t ( E ) = { + , ) , i , ∗ } LastVt(E) = \{+,),i,*\} LastVt(E)={+,),i,∗}
L a s t V T ( T ) = { ∗ , i , ) } LastVT(T) = \{*,i,)\} LastVT(T)={∗,i,)}
L a s t V T ( F ) = { ) , i } LastVT(F) = \{),i\} LastVT(F)={),i}
优先关系表的构建
构建规则
- A → s o m e t h i n g + a b A \rightarrow something + ab A→something+ab 或 A → s o m e t h i n g + a B b A \rightarrow something + aBb A→something+aBb,则有 a = b a = b a=b
- A → s o m e t h i n g + a B + s o m e t h i n g A \rightarrow something + aB+something A→something+aB+something,则对于 ∀ b ∈ F i r s t V T ( B ) \forall b \in FirstVT(B) ∀b∈FirstVT(B),有 a < b a < b a<b
- A → s o m e t h i n g + B a + s o m e t h i n g A \rightarrow something + Ba+something A→something+Ba+something,则对于 ∀ b ∈ L a s t V T ( B ) \forall b \in LastVT(B) ∀b∈LastVT(B),有 a > b a > b a>b
写表规则
- 终结符 + + + 非终结符,横向写
- 非终结符 + + + 终结符,纵向写
例子
有如下文法
E → E + T ∣ T E \rightarrow E+T |T E→E+T∣T
T → T ∗ F ∣ F T \rightarrow T*F | F T→T∗F∣F
F → ( E ) ∣ i F \rightarrow (E)|i F→(E)∣i
列出表格
等号的准确写法是 = = = 的两横中间一个实心圆点
对于 + + +
- ∀ a ∈ L a s t V T ( E ) , a ⋗ + \forall a \in LastVT(E),a \gtrdot + ∀a∈LastVT(E),a⋗+
- ∀ b ∈ F i r s t V T ( T ) , + ⋖ b \forall b \in FirstVT(T),+ \lessdot b ∀b∈FirstVT(T),+⋖b
+ | * | ( | ) | i | # \# # | |
---|---|---|---|---|---|---|
+ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ||
* | ⋗ \gtrdot ⋗ | |||||
( | ||||||
) | ⋗ \gtrdot ⋗ | |||||
i | ⋗ \gtrdot ⋗ | |||||
# \# # |
对于 ∗ * ∗
- ∀ a ∈ L a s t V T ( T ) , a ⋗ ∗ \forall a \in LastVT(T),a \gtrdot * ∀a∈LastVT(T),a⋗∗
- ∀ b ∈ F i r s t V T ( F ) , ∗ ⋖ b \forall b \in FirstVT(F),* \lessdot b ∀b∈FirstVT(F),∗⋖b
+ | * | ( | ) | i | # \# # | |
---|---|---|---|---|---|---|
+ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ||
* | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ||
( | ||||||
) | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ||||
i | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ||||
# \# # |
对于 ( ( (
- ∀ b ∈ F i r s t V T ( E ) , ∗ ⋖ b \forall b \in FirstVT(E),* \lessdot b ∀b∈FirstVT(E),∗⋖b
- ( = ) ( = ) (=)
+ | * | ( | ) | i | # \# # | |
---|---|---|---|---|---|---|
+ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ||
* | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ||
( | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | = = = | ⋖ \lessdot ⋖ | |
) | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ||||
i | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ||||
# \# # |
对于 ) ) )
- ∀ a ∈ L a s t V T ( E ) , a ⋗ ) \forall a \in LastVT(E),a \gtrdot ) ∀a∈LastVT(E),a⋗)
+ | * | ( | ) | i | # \# # | |
---|---|---|---|---|---|---|
+ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | |
* | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | |
( | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | = = = | ⋖ \lessdot ⋖ | |
) | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | |||
i | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | |||
# \# # |
对于 i i i
无对应
对于 # \# #
纵向填 ⋗ \gtrdot ⋗,横向填 ⋖ \lessdot ⋖,自身与自身相等
+ | * | ( | ) | i | # \# # | |
---|---|---|---|---|---|---|
+ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋗ \gtrdot ⋗ |
* | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋖ \lessdot ⋖ | ⋗ \gtrdot ⋗ | |
( | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | = = = | ⋖ \lessdot ⋖ | ⋗ \gtrdot ⋗ |
) | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | |||
i | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ⋗ \gtrdot ⋗ | ||
# \# # | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | ⋖ \lessdot ⋖ | = = = |
LR 分析法
项目
规则
将 . . . 或者 △ \triangle △ 依次放在每个产生式中,即求得所有的项目
. . . 前的部分表示已经识别, . . . 后表示尚未识别(“希望”出现)
- . . . 在最右侧的称作“归约项目”
- . . . 右侧有终结符称作“移进项目”
- . . . 右侧有非终结符称作“待约项目”
例子
有文法 G [ S ] G[S] G[S]
S → A S \rightarrow A S→A
A → a A b A \rightarrow aAb A→aAb
A → c A \rightarrow c A→c
则有项目
S → . A S \rightarrow .A S→.A
S → A . S \rightarrow A. S→A.
A → . a A b A \rightarrow .aAb A→.aAb
A → a . A b A \rightarrow a.Ab A→a.Ab
A → a A . b A \rightarrow aA.b A→aA.b
A → a A b . A \rightarrow aAb. A→aAb.
A
→
.
c
A \rightarrow .c
A→.c
A
→
c
.
A \rightarrow c.
A→c.
文法的拓广
即对现有文法加一个开头(一般记作 开始符 号 ′ 开始符号^{'} 开始符号′ ,并展开)
对文法
S → A S ∣ ϵ S \rightarrow AS|\epsilon S→AS∣ϵ
A → a A ∣ b A \rightarrow aA|b A→aA∣b
可以拓广为
S ′ → S S^{'} \rightarrow S S′→S
S → A S S \rightarrow AS S→AS
S → ϵ S \rightarrow \epsilon S→ϵ
A → a A A \rightarrow aA A→aA
A → b A\rightarrow b A→b
状态描述集
状态内容 Basic(S) 和 CLOSURE(S)
B A S I C ( S i ) BASIC(S_i) BASIC(Si)
有已知的状态集 S k S_k Sk ,有 S k S_k Sk 关于 X X X 的后继状态 S i S_i Si
则对于先前的状态 A → a Δ X β A\rightarrow a \Delta X \beta A→aΔXβ,移动三角符号位置,有 B A S I C ( S i ) = { A → α X Δ β } BASIC(S_i) = \{A \rightarrow \alpha X\Delta\beta\} BASIC(Si)={A→αXΔβ}
C L O S U R E ( S i ) CLOSURE(S_i) CLOSURE(Si)
- 包括了 B A S I C ( S i ) BASIC(S_i) BASIC(Si)
- 对于 A → α Δ Y β A \rightarrow \alpha \Delta Y\beta A→αΔYβ (待规约项目),任何 Y → . γ Y \rightarrow .\gamma Y→.γ 都属于 C L O S U R E ( S i ) CLOSURE(S_i) CLOSURE(Si)
根据预测分析表写推导
查表规则
S i S_i Si 表示移进, r i r_i ri 表示规约
- 移进:使用状态栈顶元素和输入串串首元素,确定下一个状态
- 规约:
- 根据 r i r_i ri,确定使用第 i i i 号规约式进行规约
- 根据
i
i
i 号规约式右侧
- 确定规约长度 j j j
- 将状态栈和符号栈的上 j j j 个元素出栈
- 根据 i i i 号规约式左侧
- 将其放入符号栈
- 将其与当前状态栈栈顶元素比对,确定下一个状态并将其移入状态栈
有分析表
ACTION | GOTO | |||||
---|---|---|---|---|---|---|
a | b | , | # | L | E | |
S 0 S_0 S0 | S 3 S_3 S3 | S 4 S_4 S4 | ||||
S 1 S_1 S1 | A C C ACC ACC | |||||
S 2 S_2 S2 | S 5 S_5 S5 | r 2 r_2 r2 | ||||
S 3 S_3 S3 | r 3 r_3 r3 | $ r_3$ | ||||
S 4 S_4 S4 | r 4 r_4 r4 | r 4 r_4 r4 | ||||
S 5 S_5 S5 | S 3 S_3 S3 | S 4 S_4 S4 | 6 | 2 | ||
S 6 S_6 S6 | r 1 r_1 r1 |
S i S_i Si 表示移进, r i r_i ri 表示按照第 i i i 个产生式进行规约
以 a , b , a # a,b,a\# a,b,a# 为例
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# |
初始状态, S 0 S_0 S0 和 # \# #入栈
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# | |
2 | S 0 S 3 S_0S_3 S0S3 | # a \#a #a | , b , a # ,b,a\# ,b,a# |
栈顶元素 S 0 S_0 S0 与串头元素 a a a 查表知转移到状态 S 3 S_3 S3, a a a 进入符号栈
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# | |
2 | S 0 S 3 S_0S_3 S0S3 | # a \#a #a | , b , a # ,b,a\# ,b,a# | |
3 | S 0 S 2 S_0S_2 S0S2 | # E \#E #E | E → a E \rightarrow a E→a | , b , a # ,b,a\# ,b,a# |
栈顶元素 S 3 S_3 S3 与串头元素 , , , 查表知转移到状态 r 3 r_3 r3
r 3 r_3 r3 对应规约式 E → a E \rightarrow a E→a
规约长度为 1 1 1,状态栈、符号栈各弹出一个元素
将归约到的符号入符号栈
状态栈符号根据现有栈顶元素 S 0 S_0 S0 和规约到的 E E E 查表知
转移到状态 S 2 S_2 S2
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# | |
2 | S 0 S 3 S_0S_3 S0S3 | # a \#a #a | , b , a # ,b,a\# ,b,a# | |
3 | S 0 S 2 S_0S_2 S0S2 | # E \#E #E | E → a E \rightarrow a E→a | , b , a # ,b,a\# ,b,a# |
4 | S 0 S 2 S 5 S_0S_2S_5 S0S2S5 | # E , \#E, #E, | b , a # b,a\# b,a# |
栈顶元素 S 2 S_2 S2 与串头元素 , , , 查表知转移到状态 S 5 S_5 S5, , , , 进入符号栈
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# | |
2 | S 0 S 3 S_0S_3 S0S3 | # a \#a #a | , b , a # ,b,a\# ,b,a# | |
3 | S 0 S 2 S_0S_2 S0S2 | # E \#E #E | E → a E \rightarrow a E→a | , b , a # ,b,a\# ,b,a# |
4 | S 0 S 2 S 5 S_0S_2S_5 S0S2S5 | # E , \#E, #E, | b , a # b,a\# b,a# | |
5 | S 0 S 2 S 5 S 4 S_0S_2S_5S_4 S0S2S5S4 | # E , b \#E,b #E,b | , a # ,a\# ,a# |
栈顶元素 S 5 S_5 S5 与串头元素 b b b 查表知转移到状态 S 4 S_4 S4, b b b 进入符号栈
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# | |
2 | S 0 S 3 S_0S_3 S0S3 | # a \#a #a | , b , a # ,b,a\# ,b,a# | |
3 | S 0 S 2 S_0S_2 S0S2 | # E \#E #E | E → a E \rightarrow a E→a | , b , a # ,b,a\# ,b,a# |
4 | S 0 S 2 S 5 S_0S_2S_5 S0S2S5 | # E , \#E, #E, | b , a # b,a\# b,a# | |
5 | S 0 S 2 S 5 S 4 S_0S_2S_5S_4 S0S2S5S4 | # E , b \#E,b #E,b | , a # ,a\# ,a# | |
6 | S 0 S 2 S 5 S 2 S_0S_2S_5S_2 S0S2S5S2 | # E , E \#E,E #E,E | E → b E \rightarrow b E→b | , a # ,a\# ,a# |
栈顶元素 S 4 S_4 S4 与串头元素 , , , 查表知转移到状态 r 4 r_4 r4
对应产生式 E → b E \rightarrow b E→b
状态栈与符号栈顶各移除一个元素
E E E 进入符号栈, S 5 S_5 S5 与 E E E 查表得到 S 2 S_2 S2
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# | |
2 | S 0 S 3 S_0S_3 S0S3 | # a \#a #a | , b , a # ,b,a\# ,b,a# | |
3 | S 0 S 2 S_0S_2 S0S2 | # E \#E #E | E → a E \rightarrow a E→a | , b , a # ,b,a\# ,b,a# |
4 | S 0 S 2 S 5 S_0S_2S_5 S0S2S5 | # E , \#E, #E, | b , a # b,a\# b,a# | |
5 | S 0 S 2 S 5 S 4 S_0S_2S_5S_4 S0S2S5S4 | # E , b \#E,b #E,b | , a # ,a\# ,a# | |
6 | S 0 S 2 S 5 S 2 S_0S_2S_5S_2 S0S2S5S2 | # E , E \#E,E #E,E | E → b E \rightarrow b E→b | , a # ,a\# ,a# |
7 | S 0 S 2 S 5 S 2 S 5 S_0S_2S_5S_2S_5 S0S2S5S2S5 | # E , E , \#E,E, #E,E, | a # a\# a# |
序号 | 状态栈 | 符号栈 | 产生式 | 输入串 |
---|---|---|---|---|
1 | S 0 S_0 S0 | # \# # | a , b , a # a,b,a\# a,b,a# | |
2 | S 0 S 3 S_0S_3 S0S3 | # a \#a #a | , b , a # ,b,a\# ,b,a# | |
3 | S 0 S 2 S_0S_2 S0S2 | # E \#E #E | E → a E \rightarrow a E→a | , b , a # ,b,a\# ,b,a# |
4 | S 0 S 2 S 5 S_0S_2S_5 S0S2S5 | # E , \#E, #E, | b , a # b,a\# b,a# | |
5 | S 0 S 2 S 5 S 4 S_0S_2S_5S_4 S0S2S5S4 | # E , b \#E,b #E,b | , a # ,a\# ,a# | |
6 | S 0 S 2 S 5 S 2 S_0S_2S_5S_2 S0S2S5S2 | # E , E \#E,E #E,E | E → b E \rightarrow b E→b | , a # ,a\# ,a# |
7 | S 0 S 2 S 5 S 2 S 5 S_0S_2S_5S_2S_5 S0S2S5S2S5 | # E , E , \#E,E, #E,E, | a # a\# a# | |
8 | S 0 S 2 S 5 S 2 S 5 S 3 S_0S_2S_5S_2S_5S_3 S0S2S5S2S5S3 | # E , E , a \#E,E,a #E,E,a | # \# # |
读到
acc
结束,读到空则出错
原文地址:https://blog.csdn.net/qq_44458671/article/details/135466250
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!