S_文法

💡

S_文法(简单的确定性文法)

每个产生式的右部都以终结符开始

同一非终结符的各个候选式的首终结符都不同

S_文法不含ε\varepsilon产生式

非终结符的后继符号集

可能在某个句型中,紧跟在A后边的终结符a的集合,记为FOLLOW(A)
FOLLOW(A)={aSαAaβ.aVT,α,β(VTVN)}\\FOLLOW(A) = \{a| S \Rightarrow {}^*\alpha Aa \beta.a \in V_T,\alpha , \beta \in (V_T \cup V_N )^* \}

ℹ️

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

产生式的可选集

产生式AβA \rarr \beta 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为SELECT(Aβ)SELECT(A \rarr \beta)

SELECT(Aaβ)={a}SELECT(A \rarr a\beta ) = \{ a \}
SELECT(Aε)=FOLLOW(A)SELECT(A \rarr \varepsilon ) = FOLLOW(A)

q_文法

  • 每个产生式的右部或为 ε\varepsilon ,或以终结符开始
  • 具有相同左部的产生式有不相交的可选集
    • q_文法不含右部以非终结符打头的产生式

串首终结符

串首第一个符号,并且是终结符,简称首终结符
给定一个文法符号 α\alpha ,α\alpha 的串首终结符集FIRST(α)FIRST(\alpha)
被定义为可以从α\alpha 推导出的所有串首终结符构成的集合.如果αε\alpha \Rightarrow {}^* \varepsilon
那么varepsilonvarepsilon也在FIRST(α)FIRST(\alpha)

对于 α(VTVN)+FIRST(α)=aαaβaVTβ(VTVN)∀α∈(V_T∪V_N)^+,FIRST(α)= {a | α ⇒* aβ,a ∈ V_T,β∈(V_T∪V_N)^*}

如果 αε,那么εFIRST(α)α ⇒* ε,那么 ε∈FIRST(α)

产生式 A→α 的可选集 SELECT

  • 如果 εFIRST(α),那么SELECT(Aα)=FIRST(α)ε∉FIRST(α),那么 SELECT(A→α)= FIRST(α)
  • 如果 εFIRST(α),那么SELECT(Aα)=(FIRST(α)ε)FOLLOW(A)ε∈FIRST(α),那么 SELECT(A→α)= (FIRST(α)-{ε})∪FOLLOW(A)

LL(1)文法

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

  • 如果αβ均不能推导出ε\alpha 和 \beta 均不能推导出 \varepsilon ,则 FIRST(α)FIRST(β)=FIRST(\alpha) \cap FIRST(\beta) = \emptyset
  • αβ \alpha 和 \beta 至多有一个能推导出 ε\varepsilon
  • 如果 βε\beta \Rightarrow {}^* \varepsilon .则FIRST(α)FOLLOW(A)=FIRST(\alpha)\cup FOLLOW(A) = \emptyset
  • 如果 αε\alpha \Rightarrow {}^* \varepsilon .则FIRST(β)FOLLOW(A)=FIRST(\beta)\cup FOLLOW(A) = \emptyset

💡

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

  • 第一个L表示从左向右扫描输入
  • 第二个L表示产生最左推导
  • 1表示在每一步中只需要向前看一个输入符号来决定语法分析动作