S_文法

预测分析法的工作过程

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

S_文法(简单的确定性文法,Korenjak & Hopcroft,1966)

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

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

S_文法不含ε产生式

例:

可以紧跟 B后面出现的终结符:c、a

什么时候使用ε产生式?

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

非终结符的后继符号集

非终结符A的后继符号集:可能在某个句型中紧跟在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_文法:

  • 每个产生式的右部或为ε ,或以终结符开始
  • 具有相同左部的产生式有不相交的可选集

q_文法不含右部以非终结符打头的产生式

串首终结符集

串首终结符:串首第一个符号,并且是终结符。简称首终结符。

给定一个文法符号串α, α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。如果α => ε,那么ε也在FIRST(α)中

  • 对于 ∀α∈(VT∪V N)+, FIRST(α)={ a | α => aβ,a∈ VT,β∈(V T∪ V N)};

  • 如果 α =>* ε,那么 ε∈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) =Φ;

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

可以为LL(1)文法构造预测分析器

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

最后修改日期:2020年6月2日

留言

撰写回覆或留言