LL(1)文法 - 好文

文章目录

* 预测分析法的工作过程 <https://blog.csdn.net/hjc256/article/details/87949500#_1>
* S_文法（简单的确定性文法） <https://blog.csdn.net/hjc256/article/details/87949500#S__5>
* 什么时候使用$\epsilon$产生式？
<https://blog.csdn.net/hjc256/article/details/87949500#epsilon_14>
* 非终结符的后继符号集 <https://blog.csdn.net/hjc256/article/details/87949500#_42>
* 产生式的可选集 <https://blog.csdn.net/hjc256/article/details/87949500#_61>
* q_文法 <https://blog.csdn.net/hjc256/article/details/87949500#q__68>
* 串首终结符集 <https://blog.csdn.net/hjc256/article/details/87949500#_74>
* LL(1)文法 <https://blog.csdn.net/hjc256/article/details/87949500#LL1_84>

<>预测分析法的工作过程

从文法开始符号触发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。

<>S_文法（简单的确定性文法）

特点：

* 每个产生式的右部都以终结符开始。
* 同一非终结符的各个候选式的首终结符都不同。
* S_文法不包含ϵ\epsilonϵ产生式
<>什么时候使用ϵ\epsilonϵ产生式？

如果当前某非终结符A与当前输入符a不匹配时，若存在A→ϵA \rightarrow{\epsilon}A→ϵ，可通过检查a是否可以出现在A
的后面，来决定是否使用产生式A→ϵA \rightarrow{\epsilon}A→ϵ。（若文法中无A→ϵA \rightarrow{\epsilon}A→ϵ
，则应报错）。

例：

文法：

* S→aBCS\rightarrow{aBC}S→aBC
* B→bCB \rightarrow{bC}B→bC
* B→dBB\rightarrow{dB}B→dB
* B→ϵB \rightarrow{\epsilon}B→ϵ
* C→cC\rightarrow{c}C→c
* C→aC \rightarrow{a}C→a
* D→eD \rightarrow{e}D→e
输入：

a d a

推导：

aBC⇒adBC⇒adC⇒adaaBC \Rightarrow{adBC \Rightarrow{adC \Rightarrow{ada}}}aBC⇒adBC
⇒adC⇒ada

可以看到在第三步推导中，B转成了空串。而上述文字的意思就是，由于此时输入的字符是a，而B没有候选式能够匹配，因此检查a能否出现在B的后面。换句话说，看看B
后面的C能不能匹配a。如果可以匹配则可以使用B的ϵ\epsilonϵ产生式，没有则报错。

<>非终结符的后继符号集

可能在某个句型中紧跟在A后边的终结符a的集合，即为FOLLOW(A)，FOLLOW(A)={a∣⇒∗αAaβ,a∈VT,a,β∈(VT∪VN)∗}
FOLLOW(A) = \{a | \Rightarrow^*{\alpha A a \beta}, a \in V_T, a,\beta \in (V_T
\cup V_N)^*\}FOLLOW(A)={a∣⇒∗αAaβ,a∈VT,a,β∈(VT∪VN)∗}

注：如果A是某个句型的最右符号，则将结束符$添加到FOLLOW(A)中。

例：

* S→aBCS\rightarrow{aBC}S→aBC
* B→bCB \rightarrow{bC}B→bC
* B→dBB\rightarrow{dB}B→dB
* B→ϵB \rightarrow{\epsilon}B→ϵ
* C→cC\rightarrow{c}C→c
* C→aC \rightarrow{a}C→a
那么FOLLOW(B)={a,c}FOLLOW(B)= \{a, c\}FOLLOW(B)={a,c}。

换句话说，当输入为b或d时，选择产生式2或3。而当输入为a或c时，选择产生式4。

<>产生式的可选集

产生式A→βA \rightarrow{\beta}A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT(A→β)
SELECT(A \rightarrow{\beta})SELECT(A→β)。也就是说，当遇到可选集中的字符输入时，可以选用可选集对应的产生式。

* SELECT(A→aβ)=aSELECT(A \rightarrow{a \beta}) = {a}SELECT(A→aβ)=a
* SELECT(A→ϵ)SELECT(A \rightarrow{\epsilon})SELECT(A→ϵ) = FOLLOW(A)FOLLOW(A)FO
LLOW(A)
<>q_文法

* 每个产生式的右部或为ϵ\epsilonϵ，或以终结符开始
* 具有相同左部的产生式有不相交的可选集。
* q_文法不含右部以非终结符打头的产生式。
<>串首终结符集

* 串首终结符：串的第一个符号，并且是终结符。简称首终结符。
* 给定一个文法符号串α\alphaα，α\alphaα的串首终结符集FIRST(α)FIRST(\alpha)FIRST(α)被定义为可以从α\alpha
α推导出的所有串首终结符构成的集合。如果α⇒∗ϵ\alpha \Rightarrow^*{\epsilon}α⇒∗ϵ，那么ϵ\epsilonϵ也在FIRST(α
)FIRST(\alpha)FIRST(α)中
* 对于∀α∈(VT∪VN)+\forall\alpha \in(V_T \cup V_N)^+∀α∈(VT∪VN)+，FIRST(α)=a∣α⇒∗aβ
,a∈VT,β∈(VT∪VN)FIRST(\alpha)={a | \alpha \Rightarrow^*{a\beta},a \in V_T, \beta
\in (V_T \cup V_N)}FIRST(α)=a∣α⇒∗aβ,a∈VT,β∈(VT∪VN)
* 如果α⇒∗ϵ\alpha \Rightarrow^*{\epsilon}α⇒∗ϵ，那么ϵ∈FIRST(α)\epsilon \in
FIRST(\alpha)ϵ∈FIRST(α)。（α\alphaα中的每一个符号都是非终结符，且每一个非终结符都能推导出空串）
* 产生式A→αA \rightarrow{\alpha}A→α的可选集SELECTSELECTSELECT
* 如果ϵ∉FIRST(α)\epsilon \notin FIRST(\alpha)ϵ∈/FIRST(α)，那么SELECT(A→α)=FIRST(α)
SELECT(A \rightarrow{\alpha}) = FIRST(\alpha)SELECT(A→α)=FIRST(α)
* 如果ϵ∈FIRST(α)\epsilon \in FIRST(\alpha)ϵ∈FIRST(α)，那么SELECT(A→α)=(FIRST(α)−{ϵ}
)∪FOLLOW(A)SELECT(A \rightarrow{\alpha}) = (FIRST(\alpha) - \{\epsilon\}) \cup
FOLLOW(A)SELECT(A→α)=(FIRST(α)−{ϵ})∪FOLLOW(A)
<>LL(1)文法

文法G是LL(1)LL(1)LL(1)的，当且仅当G的任意两个具有相同左部的产生式A→α∣βA \rightarrow{\alpha | \beta}A→α∣
β满足下面的条件：

* 不存在终结符a使得α\alphaα和β\betaβ都能推导出以a开头的串。
* α\alphaα和β\betaβ至多有一个能推导出ϵ\epsilonϵ
* 如果β⇒∗ϵ\beta \Rightarrow^*{\epsilon}β⇒∗ϵ，则FIRST(α)∩FOLLOW(A)=ΦFIRST(\alpha)
\cap FOLLOW(A) = \PhiFIRST(α)∩FOLLOW(A)=Φ
* 如果α⇒∗ϵ\alpha \Rightarrow^*{\epsilon}α⇒∗ϵ，则FIRST(β)∩FOLLOW(A)=ΦFIRST(\beta)
\cap FOLLOW(A) = \PhiFIRST(β)∩FOLLOW(A)=Φ
因为如果β⇒∗ϵ\beta \Rightarrow^*{\epsilon}β⇒∗ϵ，那么SELECT(β)SELECT(\beta)SELECT(β)就包含了
FOLLOW(A)FOLLOW(A)FOLLOW(A)，所以FIRST(α)FIRST(\alpha)FIRST(α)就不能包含FOLLOW(A)
FOLLOW(A)FOLLOW(A)中元素。不然两个的SELECTSELECTSELECT集将会相交。

* 同一非终结符的各个产生式的可选集互不相交

热门工具换一换