版权声明：本文为原创文章，未经博主允许不得用于商业用途。

语法分析

上下文无关文法(CFG)

1.1 基本定义

CFG包含如下四个组成部分：

• 终结符号：组成串的基本符号（词法单元名，id，运算符）
• 非终结符号：表示串的集合的语法符号（如expr，stmt）
• 开始符号：某个被指定的非终结符（如expr）
• 产生式：定义了使用非终结符和终结符狗构造串的方法。
  • 形式：头（左）部$\rightarrow$→体（右）部
  • 头部是一个非终结符，右部是一个符号串

1.2 例子（c语言产生式）

其中$expression$expression表示表达式，$term$term表示术语（保留字，关键字）。

经过简化，此文法可以表示成：，其中’|'为文法描述符，不是文法符号。

1.3 推导

推导可以看作是对产生式的解读，如果产生式$A\rightarrow \gamma$A→γ，则$\alpha A\beta\Rightarrow \alpha \gamma\beta$αAβ⇒αγβ表示“通过一步推导出”。因此推导可以看作是按照产生式规则替换。同理，定义$\overset{*}{\Rightarrow}$⇒∗表示经过零步或多步推导出。

在进行推导时，如果每次都解析最左（右）边的非终结符号，则称为最左（右）推导

• 句型：一个文法可以推导出的所有串的集合
• 句子：不包含非终结符号的句型
• 语言：所有句子的集合

1.4 语法分析树

推导过程可以使用树状结构表示，其中:

• 根结点的标号是文法的开始符号
• 每个叶子结点的标号是非终结符号、终结符号或ε
• 每个内部结点的标号是非终结符号
• 每个内部结点表示某个产生式的一次应用
  • 结点的标号为产生式头，其子结点从左到右是产生式的体

一棵语法分析树可以对应多个推导序列，不过只具有一种最左（右）推导（即前序遍历和后序遍历唯一）。

1.5 上下文无关文法和正则表达式

上下文无关文法比正则表达式的表达能力更强：即CFG可以对两个个体的计数（最多两个个体）而RE（NFA）不能。

例如$\{a^nb^n|n\geq 1\}${anbn∣n≥1}（括号匹配）

• CFG：$S\rightarrow aSb|ab$S→aSb∣ab
• 正则表达式：反证法，若可以表示，若存在一个具有2n个状态的NFA可以表示此语言，则对于$a^{n+1}b^{n+1}$an+1bn+1，必有一个状态$s_0$s0​有一条收到a时指向之前k个状态的边，因此其可以接受$a^{n+k}b^{n+1}$an+kbn+1，不在此语言中。矛盾。

设计文法

消除二义性

对于一些语法，同一个句型可以对应多个语法分析树，如典型的if-else-then语法：

文法1：

$stmt\rightarrow \bold{if}\ expr\ \bold{then}\ stmt\ |\ \bold{if}\ expr\ \bold{then}\ stmt\ \bold{else}\ stmt\ |\ other$stmt→if expr then stmt ∣ if expr then stmt else stmt ∣ other

对于$if\ E_1\ then\ if\ E_2\ then\ S_1\ else\ S_2$if E1​ then if E2​ then S1​ else S2​有两种解读，即$S_2$S2​对应的层次可以是外层if语句，也可以是内层if语句。

可以通过规定else和最近的未匹配then匹配消除二义性，体现在文法层面如下：

文法2：

$stmt\rightarrow matched\_stmt\ |\ open\_stmt$stmt→matched_stmt ∣ open_stmt

$match\_stmt\rightarrow \bold{if}\ expr\ \bold{then}\ matched\_stmt\ \bold{else}\ matched\_stmt\ |\ other$match_stmt→if expr then matched_stmt else matched_stmt ∣ other

$open\_stmt\rightarrow \bold{if}\ expr\ \bold{then}\ stmt\ |\ \bold{if}\ expr\ \bold{then}\ matched\_stmt\ \bold{else}\ open\_stmt$open_stmt→if expr then stmt ∣ if expr then matched_stmt else open_stmt

消除左递归

• 左递归：文法中存在非终结符A使得$A\overset{+}{\Rightarrow}A\alpha$A⇒+Aα
• 立即左递归：文法中存在非终结符A使得$A\rightarrow A\alpha$A→Aα

自顶向下的语法分析无法处理左递归，因为在DFS时可以无限替换下去。

可以通过替换法消除左递归：

• 立即左递归变为立即右递归：
  • 输入：$A\rightarrow A\alpha|\beta$A→Aα∣β
  • 转化为：$A\rightarrow \beta A'$A→βA′，$A'\rightarrow \alpha A'|\epsilon$A′→αA′∣ϵ
• 多步左递归：
  • 算法思路：按照顺序替换产生式，直到立即左递归出现后，消除立即左递归。（相当于求了产生关系的闭包）
  • 

提取左公因子

在CFG分析句型时，每次都通过查看下一个符号选择产生式，因此如果两个产生式具有相同的前缀时，则无法判断应该选择哪一个。

因此需要提取产生是的左公因子(相同前缀)，并且将公因子转化为新的产生式消除相同前缀。

• 原语法：$A\rightarrow \alpha \beta_1|\alpha\beta_2$A→αβ1​∣αβ2​
• 提取左公因子后：$A\rightarrow \alpha A',A'\rightarrow \beta_1|\beta_2$A→αA′,A′→β1​∣β2​

自顶向下的语法分析

自顶向下语法分析按照先根次序深度优先的创建节点（对应最左推导）建立语法分析树，一次读入一个字符，知道完成整个输入串的解析。

此算法类似贪心算法，显然当遇到一个错误时，不一定是语法错误，也可能是之前的产生式选择错误，因此可以通过回溯改良算法。

FIRST和FOLLOW

通常在选择产生式时使用FIRST和FOLLOW两个函数。

• $FIRST(\alpha)$FIRST(α)定义为可以从$\alpha$α推导出的首符号的集合。
  • 若$\alpha$α为终结符，则加入$\alpha$α
  • 若$\alpha$α为非终结符，且$\alpha \rightarrow \beta_1\beta_2...\beta_k$α→β1​β2​...βk​
    • 若$\theta\in FIRST(\beta_i),\epsilon\in FIRST(\beta_1),FIRST(\beta_2),...,FIRST(\beta_{i-1})$θ∈FIRST(βi​),ϵ∈FIRST(β1​),FIRST(β2​),...,FIRST(βi−1​)，加入$\theta$θ
    • 若$\epsilon\in FIRST(\beta_1),FIRST(\beta_2),...,FIRST(\beta_{k})$ϵ∈FIRST(β1​),FIRST(β2​),...,FIRST(βk​)，加入$\epsilon$ϵ
  • 若$\alpha$α为非终结符，且$\alpha \rightarrow \epsilon$α→ϵ，加入$\epsilon$ϵ
• $FIRST(\alpha_1\alpha_2...\alpha_n)$FIRST(α1​α2​...αn​)计算如下：
  • 加入$FIRST(\alpha_1)$FIRST(α1​)中所有非$\epsilon$ϵ符号
  • 若$\epsilon\notin FIRST(\alpha_i),\epsilon\in FIRST(\alpha_1),FIRST(\alpha_2),...,FIRST(\alpha_{i-1})$ϵ∈/​FIRST(αi​),ϵ∈FIRST(α1​),FIRST(α2​),...,FIRST(αi−1​)，加入$FIRST(\beta_i)$FIRST(βi​)
  • 若$\epsilon\in FIRST(\alpha_1),FIRST(\alpha_2),...,FIRST(\alpha_{n})$ϵ∈FIRST(α1​),FIRST(α2​),...,FIRST(αn​)，加入$\epsilon$ϵ
• $FOLLOW(\alpha)$FOLLOW(α)定义了可以跟随在$\alpha$α右边的终结符号集合
  • 例如：$S\rightarrow a\alpha b\beta$S→aαbβ，则终结符b在$FOLLOW(\alpha)$FOLLOW(α)中
  • 计算：将右端结束标记$加入FOLLOW(B)中，保证非空
    • 存在$S\rightarrow \alpha B\beta$S→αBβ，则将$FIRST(\beta)$FIRST(β)中的非$\epsilon$ϵ符号加入
    • 存在$A\rightarrow \alpha B\ or\ A\rightarrow \alpha B\beta,\epsilon\in FIRST(\beta)$A→αB or A→αBβ,ϵ∈FIRST(β)，则将$FOLLOW(A)$FOLLOW(A)中所有符号加入

LL(1)文法

LL(1)文法中的LL和1分别代表从左向右扫描输入字符、最左推导、每一步只需向前看一个输入字符。

对于任意一个产生式$A\rightarrow \alpha |\beta$A→α∣β，满足如下两个条件：

• $FIRST(\alpha)\cap FIRST(\beta)=\Phi$FIRST(α)∩FIRST(β)=Φ
• 若$\epsilon\in FIRST(\beta),FIRST(\alpha)\cap FOLLOW(A)=\Phi$ϵ∈FIRST(β),FIRST(α)∩FOLLOW(A)=Φ，反之亦然

对于满足上述条件的LL(1)文法，可以构造出不需要回溯的递归下降语法分析器。

预测分析表

为了避免重复计算，为语言构造预测分析表M，其中行表示非终结符号，列表示输入符号（终结符号），每个单元记录非终结符是否可以通过产生式推导出终结符。

构造算法：

• 对于文法G中的每个产生式$A\rightarrow\alpha$A→α
  • 对于$FIRST(\alpha)$FIRST(α)中的每个终结符号a，将$A\rightarrow \alpha$A→α写入$M[A,a]$M[A,a]单元中
  • 如果$\epsilon\in First(\alpha)$ϵ∈First(α)，对于$FOLLOW(A)$FOLLOW(A)中的每个终结符号b，将$A\rightarrow \alpha$A→α写入$M[A,b]$M[A,b]单元中
• 算法执行后，在空白单元格填入error

由于LL(1)语法不存在二义性，因此在执行递归算法时对于每个输入符号可以根据M唯一的选择产生式。

特别的，如果出现冲突，则说明G不满足LL(1)的条件，即具有二义性。

非递归预测分析

由于LL(1)文法时最左推导的，因此每次分析时只需记住尚未分析的产生式右侧部分即可。

可以通过一个栈实现预测分析。具体过程如下：