跳转至

语法分析 Parse

语法给定了一个准确的编程语言的语言规则。

语法分析在编译器中

image-20220516112051963{loading=lazy}

语法分析器有三种:universial,top-down、botton-up,universial 可以分析任何语法,但是实现太复杂,没有太大工程意义;后两者虽然只能处理语法的一个子集,但是运用这个子集也足以分析程序语言的语法。

上下文无关文法

\[ stmt \rightarrow \mathrm{if} \ \mathtt{(}\ expr\ \mathtt{)} \ stmt \ \mathrm{else} \ stmt \]

规则定义

其正规定义如下:

  1. 终结符 Terminal:组成字符串的基本符号
  2. 非终结符 Nonterminal:代表一个字符串集合的语法上的变量
  3. 开始符号 Start symbol:其中一个非终结符,它所代表的字符串集合就是这个语法的语言
  4. 推导 Production:
  5. head (left):一个非终结符。这个推导代表这个非终结符生成的一些字符串
  6. \(\rightarrow\) 符号
  7. body (right):零或多个终结符和非终结符,表示 head 生成字符串的一种方式
\[ \begin{aligned} { expression } & \rightarrow { expression } \mathtt + { term } \\ { expression } & \rightarrow { expression }\mathtt{-} { term } \\ { expression } & \rightarrow { term } \\ { term } & \rightarrow { term } \mathtt* { factor } \\ { term } & \rightarrow { term } \mathtt/ { factor } \\ { term } & \rightarrow { factor } \\ { factor } & \rightarrow { \mathtt{(} expression \mathtt ) } \\ { factor } & \rightarrow \mathrm { id } \end{aligned} \]

我们进行一些约定,上述的语法规则可以简化成下边这样

\[ \begin{array}{ll} E & \rightarrow E+T \mid E-T \mid T \\ T & \rightarrow T * F \mid T / F \mid F \\ F & \rightarrow(E) \mid \text { id } \end{array} \]

其中 \(E\)\(T\)\(F\) 都是非终结符,\(E\)是开始符号,剩下的符号都是非终结符。

推导

推导的正规定义:设非终结符\(A\), 希腊字母\(\alpha\)\(\beta\)\(\gamma\) 代表任意字符串(可空),有推导 \(A \rightarrow \gamma\),那么我们可以写一个推导

\[ \alpha A \beta \Rightarrow \alpha \gamma \beta \]

其中 \(\Rightarrow\) 表示推导一步。如果有 \(\alpha_{1} \Rightarrow \alpha_{2} \Rightarrow \cdots \Rightarrow \alpha_{n}\) 我们说 \(a_1\) 推导出 \(a_n\)。类似闭包,我们用 \(\stackrel{*}{\Rightarrow}\) 表示零步或多步推导,用 \(\stackrel{+}{\Rightarrow}\) 表示一步或多步推导。

如果有 \(S \stackrel{*}{\Rightarrow} \alpha\),其中 \(S\) 是语法 \(G\) 的一个起始符号,那么说 \(\alpha\)\(G\) 的一个句型(sentential form)。

在编译器中常常采用最左推导(leftmost derivation)或最右推导两种方式。

最左推导就是每次替换最左边的非终结符,得到的句型叫最左句型

依然是上边的语法规则,我们考虑以最左推导形式进行语法分析,如下:

\[ E \underset{l m}{\Rightarrow}-E \underset{l m}{\Rightarrow}-(E) \underset{l m}{\Rightarrow}-(E+E) \underset{l m}{\Rightarrow}-(\mathbf{i d}+E) \underset{l m}{\Rightarrow}-(\mathbf{i d}+\mathbf{i d}) \]

语法树

语法树是对推导的图形化表达。还是上边的推导,画成语法树是这个样子:

image-20220516120157578{loading=lazy}

推导过程如下:

image-20220516120220034{loading=lazy}

二义性

对于 \(\mathbf{i d}+\mathbf{i d} * \mathbf{i d}\) 来说,有以下两种可能的推导:

\[ \begin{aligned} E & \Rightarrow E+E \\ & \Rightarrow \quad \mathbf{i d}+E \\ & \Rightarrow \quad \mathbf{i d}+E * E \\ & \Rightarrow \quad \mathbf{i d}+\mathbf{i d} * E \\ & \Rightarrow \quad \mathbf{i d}+\mathbf{i d} * \mathbf{i d} \end{aligned} \]
\[ \begin{aligned} E & \Rightarrow E * E \\ & \Rightarrow \quad E+E * E \\ & \Rightarrow \quad \mathbf{i d}+E * E \\ & \Rightarrow \quad \mathbf{i d}+\mathbf{i d} * E \\ & \Rightarrow \quad \mathbf{i d}+\mathbf{i d} * \mathbf{i d} \end{aligned} \]

这种语法是有二义性(ambiguous)的,对应到表达式求值上,就是 (a+b)*ca+(b*c) 的算符优先级问题。

语法的完备性证明

证明完备性分两部分:证明语法 \(G\) 生成的每一个字符串都在语言 \(L\) 中,同时证明语言 \(L\) 中的字符串都能被 \(G\) 生成。

可以使用数学归纳法。

编写语法

消除二义性

首先我们拿 if-else 配对为例,下面语法会产生 dangling-else 这种常见的错误:

\[ \begin{array}{rcl} \text { stmt } & \rightarrow & \text { if expr then stmt } \\ & \mid & \text { if expr then stmt else stmt } \\ & \mid & \text { other } \end{array} \]

有如下 hack:

\[ \text { if } E_{1} \text { then } S_{1} \text { else if } E_{2} \text { then } S_{2} \text { else } S_{3} \]

这种二义性语法本身造成的,需要通过改写语法消除二义性。

如下是没有二义性的文法,每一个 else 与最近的一个 if 配对。

消除左递归

当一个语法中存在如 \(A \stackrel{+}{\Rightarrow} A\alpha\) 的语法时,我们说这个语法是左递归的。

如果我们有形如 \(A \rightarrow A\alpha \mid \beta\) 的语法,我们可以如下改写:

\[ \begin{gathered} A \rightarrow \beta A^{\prime} \\ A^{\prime} \rightarrow \alpha A^{\prime} \mid \epsilon \end{gathered} \]

上边例子是直接左递归,麻烦的是间接左递归。间接左递归可以用如下的算法消除。

image-20220516130227501{loading=lazy}

其实就是一个将间接左递归展开为直接左递归,再手动消除直接左递归的过程。

左因子

左因子指一个非终结符的推导的两个或多个候选式中的公共前缀,如:

\[ \begin{array}{rcl} \text { stmt } & \rightarrow & \text { if expr then stmt else } s t m t \\ &\mid & \text { if expr then stmt } \end{array} \]

if expr就是一个左因子。

消除左因子的方法是提取左因子。假设有 \(A\) 的两个推导 \(A \rightarrow \alpha \beta_{1} \mid \alpha \beta_{2}\),有左因子 \(\alpha\),提取左因子如下:

\[ \begin{aligned} &A \rightarrow \alpha A^{\prime} \\ &A^{\prime} \rightarrow \beta_{1} \mid \beta_2 \end{aligned} \]

自顶向下分析

递归下降分析

递归下降分析是最简单的一种自顶向下分析方法,但当一个非终结符有两种或以上推导时,需要进行试错与回溯。

image-20220522093046680{loading=lazy}

前瞻语法 Lookahead Grammar

FIRST 和 FOLLOW

\(\mathrm{FIRST}(\alpha)\),其中 \(\alpha\) 是任意语法符号,定义为从 \(\alpha\) 推导出的所有字符串中可能的首字符的集合。

\(\mathrm{FOLLOW}(A)\) 定义为在某句型中直接出现在终结符 \(A\) 之后的所有字符的集合,即 \(S \stackrel{*}{\Rightarrow} \alpha Aa\beta\)

\(\mathrm{FIRST}(X)\) 以如下算法计算:

  1. \(X\) 是终结符,\(\mathrm{FIRST}(X) = X\)
  2. \(X\) 是非终结符且有推导 \(X \rightarrow Y_1Y_2\ldots Y_k\)\(k\ge1\),若对于某个 \(i\)\(\epsilon \in \cap_{s=1}^{i-1}(\mathrm{FIRST(Y_s)})\)\(a \in \mathrm{FIRST}(Y_i)\),将 \(a\) 加入 \(\mathrm{FIRST}(X)\)
  3. 如果有推导 \(X \rightarrow \epsilon\),将 \(\epsilon\) 加入 \(\mathrm{FIRST(X)}\)

\(\mathrm{FOLLOW(A)}\) 以如下算法计算:

  1. 从开始符号 \(S\) 开始,将 \(\$\) 加入 \(\mathrm{FOLLOW(S)}\)
  2. 若有推导 \(A \rightarrow \alpha B \beta\),将 \(\mathrm{FIRST}(\beta)\) 中除 \(\epsilon\) 外的所有元素加入 \(\mathrm{FOLLOW}(B)\)
  3. 若有推导 \(A \rightarrow \alpha B\)\(A \rightarrow \alpha B \beta\),其中 \(\epsilon \in \mathrm{FIRST}(\beta)\),将 \(\mathrm{FOLLOW}(A)\) 中所有元素加入 \(\mathrm{FOLLOW}(B)\)

\(\mathrm{LL}(1)\) 语法

第一个 \(\mathrm L\)自左向右扫描输入字符串,第二个 \(\mathrm L\) 代表最左推导

\(\mathrm{LL}(1)\) 以表驱动的方式进行推导,表 \(M\) 中的每一项 \(M[A, a]\) 代表当前看到了非终结符 \(A\),扫描到的下一个非终结符是 \(a\) 时应该执行的推导。

表的构造算法如下:

输入:语法 \(G\)

输出:Parsing Table \(M\)

方法:对于语法中每个推导 \(A \rightarrow \alpha\),执行下列操作

  1. 对于 \(\mathrm{FIRST}(\alpha)\) 中的每一个终结符 \(a\),将 \(A\rightarrow \alpha\) 加入\(M[A, a]\)
  2. \(\mathrm{FIRST}(\alpha)\) 中含有 \(\epsilon\),对 \(\mathrm{FOLLOW}(\alpha)\) 中所有非终结符 \(b\),将 \(A\rightarrow\alpha\) 加入 \(M[A, b]\)
  3. \(\mathrm{FIRST}(\alpha)\) 中含有 \(\epsilon\),对 \(\mathrm{FOLLOW}(\alpha)\) 中含有 \(\$\),把 \(A\rightarrow\alpha\) 加入 \(M[A, \$]\)

最后,\(M[A, a]\) 中的空项置为 \(\mathbf{error}\)

对每一个 \(\mathrm{LL}(1)\) 文法,parsing table 的每一项必须是唯一的推导或错误。如果不唯一,说明不是 \(\mathrm{LL}(1)\) 文法。

非递归前瞻分析

程序需要显式维护一个栈,栈顶是当前正在处理的非终结符。

image-20220522094411427{loading=lazy}

image-20220522094328776{loading=lazy}

一次推导的过程如下

image-20220522094452822{loading=lazy}

自底向上分析

规约分析

自底向上分析可以看做是规约分析,也就是说,从输入字符串开始,将一个与某个推导的 body 相同的子串,规约为这个推导的 head。如下的字符串

\[ \mathbf{i d} * \mathbf{i d}, \quad F * \mathbf{i d}, \quad T * \mathbf{i d}, \quad T * F, T, E \]

对应了推导

\[ E \Rightarrow T \Rightarrow T * F \Rightarrow T * \mathbf{i d} \Rightarrow F * \mathbf{i d} \Rightarrow \mathbf{i d} * \mathbf{i d} \]

移位归约分析

流程:

  1. 首先,自左向右扫描输入字符串,将每个字符压栈。若栈顶构成某个推导 \(A \rightarrow \beta\) 的结果 \(\beta\),则将 \(\beta\) 中全部符号出栈,\(A\) 进栈。
  2. 直到栈中剩下起始符号,输入已空,接受。

image-20220522095419043{loading=lazy}

对语法的要求是无二义性,不能出现同时有两个 handle 的情况。

image-20220522095737762{loading=lazy}

LR 分析

LR 分析器通过维护状态来确定在分析的那个阶段,进而决定下一步是移位或是规约。

例如,推导 \(A\rightarrow XYZ\) 可以产生如下四个状态

\[ \begin{aligned} A&\rightarrow \cdot X Y Z \\ A& \rightarrow X \cdot Y Z \\ A& \rightarrow X Y \cdot Z \\ A& \rightarrow X Y Z \cdot \end{aligned} \]

每一个 \(\cdot\) 表示所处于推导中的位置,每一个状态代表一个项目

\(A \rightarrow \epsilon\) 只有一个状态:\(A \rightarrow \cdot\)

文法的 \(\mathrm{LR}(0)\) 项目分为四种:

  • 规约项目:\(A \rightarrow \alpha \cdot\)
  • 接受项目:\(S \rightarrow \alpha \cdot\)(特殊的规约项目)
  • 移进项目:\(A\rightarrow \alpha \cdot a \beta\)
  • 待约项目:\(A \rightarrow \alpha \cdot B \beta\)

为了计算语法的标准 \(\mathrm{LR}(0)\) 集,我们介绍一种增强语法\(\mathrm{CLOSURE}\)\(\mathrm{GOTO}\) 函数。

设原语法为 \(G\)\(G\) 中起始符号为 \(S\),则增强语法 \(G'\) 中,起始符号为 \(S'\) 且有推导 \(S' \rightarrow S\)

引入增强的起始状态的目的是,当完成推导 \(S' \rightarrow S\) 并输入串扫描完毕时,接受。

\(\mathrm{LR}(0)\) 分析

\(\mathrm L\) 代表从左到右扫描输入字符串,\(R\) 代表执行最右推导。

有四种 Action (行为)

  • shift:读入下一个输入符号并将其移入栈
  • reduce:当栈顶符号形成句柄时进行规约,用产生式左侧的非终结符替换栈顶的句柄。
  • accept:当栈顶只有 \(\$\) 和开始符号,输入串也只有 \(\$\) 时,分析成功,是一种特殊的规约。
  • error:发现一个语法错误,调用错误处理程序。

\(\mathrm{CLOSURE}\)

如果 \(I\) 是语法 \(G\) 的一个项目集,那么 \(\mathrm{CLOSURE}(I)\) 可以由以下两条方法计算:

  1. 初始,把 \(I\) 中所有元素加入 \(\mathrm{CLOSURE}(I)\)
  2. 如果 \(A \rightarrow \alpha \cdot B \beta\)\(\mathrm{CLOSURE}(I)\) 中,并且 \(B \rightarrow \gamma\) 是一个推导,那么将 \(B \rightarrow\cdot \gamma\) 加入 \(\mathrm{CLOSURE}(I)\) 中。重复该步骤,直到没有新的 item 能被加入 \(\mathrm{CLOSURE}(I)\) 中。

\(\mathrm{GOTO}\)

\(I\) 是一个项目集\(X\) 是一个语法符号,\(\mathrm{GOTO}(I,X)\)\(I\)\([A\rightarrow \alpha X \cdot \beta]\) 中所有元素的闭包。

\(\mathrm{GOTO}(I,X)\) 用于定义自动机中的转移。

image-20220522104133303{loading=lazy}

自动机构造方法

  1. 构造表达式文法的规范 \(\mathrm{LR}(0)\) 项目集族

  2. 若文法 \(G\)\(\mathrm{LR}(0)\) 自动机不存在下述情况

  3. 既含移进项目又含规约项目

  4. 含有多个规约项目

则称 \(G\) 是一个 \(\mathrm{LR}(0)\) 文法

  1. \(I_k\) 为当前状态(的项集族)

  2. 规约项目:若 \(A \rightarrow \alpha\cdot \in I_k\),则对所有终结符 \(a\)(或 \(\$\)),\(\mathrm{ACTION}[k, a] = \mathrm{reduce}(A \rightarrow \alpha)\)

  3. 接受项目:若 \(S' \rightarrow S \in I_k\),则 \(\mathrm{ACTION}[k, a] = \mathrm{success()}\)
  4. 移进项目:若 \(A \rightarrow \alpha \cdot a \beta\),且 \(\mathrm{GOTO}(I_k, a) = I_j\),则 \(\mathrm{ACTION}[k, a] = \mathrm{shift}(s_j)\)
  5. 待约项目:若 \(A \rightarrow \alpha \cdot B \beta\),且 \(\mathrm{GOTO}(I_k, B) = I_j\),则 \(\mathrm{GOTO}[k, B] = j\)
  6. 分析表中空白位置为出错标志

Problem & Solution

\(\mathrm{LR}(0)\) 文法没有实用价值。(为什么?)

构造 \(\mathrm{SLR}(1)\) 分析表

\(I_k\) 为当前状态(的项集族)

  1. 规约项目:若 \(A \rightarrow \alpha\cdot \in I_k\),则对==所有\(a \in \mathrm{FOLLOW}(A)\)==,\(\mathrm{ACTION}[k, a] = \mathrm{reduce}(A \rightarrow \alpha)\)
  2. 接受项目:若 \(S' \rightarrow S \in I_k\),则 \(\mathrm{ACTION}[k, a] = \mathrm{success()}\)
  3. 移进项目:若 \(A \rightarrow \alpha \cdot a \beta\),且 \(\mathrm{GOTO}(I_k, a) = I_j\),则 \(\mathrm{ACTION}[k, a] = \mathrm{shift}(s_j)\)
  4. 待约项目:若 \(A \rightarrow \alpha \cdot B \beta\),且 \(\mathrm{GOTO}(I_k, B) = I_j\),则 \(\mathrm{GOTO}[k, B] = j\)
  5. 分析表中空白位置为出错标志

Chapter4_7_14{loading=lazy}

image-20220522115418179{loading=lazy}

image-20220522115424556{loading=lazy}

Problems & Solutions

  • \(\mathrm{FOLLOW}(A)\) 是指所有可能推导出的句型中,可以跟随在 \(A\) 后边的符号集
  • \(\mathrm{LR}\) 分析法的规约应该仅对右句型中跟随在 \(A\) 后的终结符有效。否则,规约之后得到的符号串可能不是右句型。

更强大的 LR 分析器过于复杂,就不再介绍了。