S_文法
💡
S_文法(简单的确定性文法)
每个产生式的右部都以终结符开始
同一非终结符的各个候选式的首终结符都不同
S_文法不含ε产生式
非终结符的后继符号集
可能在某个句型中,紧跟在A后边的终结符a的集合,记为FOLLOW(A)
FOLLOW(A)={a∣S⇒∗αAaβ.a∈VT,α,β∈(VT∪VN)∗}
ℹ️
如果A是某个句型的最右符号,则将结束符"$"添加到FOLLOW(A)中
产生式的可选集
产生式A→β 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为SELECT(A→β)
SELECT(A→aβ)={a}
SELECT(A→ε)=FOLLOW(A)
q_文法
- 每个产生式的右部或为 ε ,或以终结符开始
- 具有相同左部的产生式有不相交的可选集
串首终结符
串首第一个符号,并且是终结符,简称首终结符
给定一个文法符号 α ,α的串首终结符集FIRST(α)
被定义为可以从α推导出的所有串首终结符构成的集合.如果α⇒∗ε
那么varepsilon也在FIRST(α)中
对于 ∀α∈(VT∪VN)+,FIRST(α)=a∣α⇒∗aβ,a∈VT,β∈(VT∪VN)∗;
如果 α⇒∗ε,那么ε∈FIRST(α)
产生式 A→α 的可选集 SELECT
- 如果 ε∈/FIRST(α),那么SELECT(A→α)=FIRST(α)
- 如果 ε∈FIRST(α),那么SELECT(A→α)=(FIRST(α)−ε)∪FOLLOW(A)
LL(1)文法
文法G是LL(1)的,当且仅当G的任意两个具有相同左部的产生式A→α∣β 满足下面的条件
- 如果α和β均不能推导出ε,则 FIRST(α)∩FIRST(β)=∅
- α和β至多有一个能推导出 ε
- 如果 β⇒∗ε.则FIRST(α)∪FOLLOW(A)=∅
- 如果 α⇒∗ε.则FIRST(β)∪FOLLOW(A)=∅
- 第一个L表示从左向右扫描输入
- 第二个L表示产生最左推导
- 1表示在每一步中只需要向前看一个输入符号来决定语法分析动作