编译原理:LL(1)文法

S_文法

:::tip

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

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

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

S_文法不含$\epsilon$产生式

:::

非终结符的后继符号集

可能在某个句型中,紧跟在A后边的终结符a的集合,记为FOLLOW(A) $\begin{array}{l}\\ FOLLOW(A)=\{a|S\Rightarrow {}^{\ast }\alpha Aa\beta .a\in V_T,\alpha ,\beta \in {(V_T\cup V_N)}^{\ast }\}\end{array}$

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

产生式的可选集

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

$SELECT(A\to a\beta )=\{a\}$ $SELECT(A\to \epsilon )=FOLLOW(A)$

q_文法

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

串首终结符

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

对于 $\forall \alpha \in {(V_T\cup V_N)}^{+}\text{，}FIRST(\alpha )=a|\alpha \Rightarrow \ast a\beta \text{，}a\in V_T\text{，}\beta \in {(V_T\cup V_N)}^{\ast }$；

如果 $\alpha \Rightarrow \ast \epsilon \text{，}\text{那}\text{么}\epsilon \in FIRST(\alpha )$

产生式 A→α 的可选集 SELECT

• 如果 $\epsilon \notin FIRST(\alpha )\text{，}\text{那}\text{么}SELECT(A\to \alpha )=FIRST(\alpha )$
• 如果 $\epsilon \in FIRST(\alpha )\text{，}\text{那}\text{么}SELECT(A\to \alpha )=(FIRST(\alpha )-\epsilon )\cup FOLLOW(A)$

LL(1)文法

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

• 如果$\alpha \text{和}\beta \text{均}\text{不}\text{能}\text{推}\text{导}\text{出}\epsilon$,则 $FIRST(\alpha )\cap FIRST(\beta )=\varnothing$
• $\alpha \text{和}\beta$至多有一个能推导出 $\epsilon$
• 如果 $\beta \Rightarrow {}^{\ast }\epsilon$.则$FIRST(\alpha )\cup FOLLOW(A)=\varnothing$
• 如果 $\alpha \Rightarrow {}^{\ast }\epsilon$.则$FIRST(\beta )\cup FOLLOW(A)=\varnothing$

:::tip

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

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