我的大学

外观

上下文无关语法

约 1276 字大约 4 分钟

2025-01-09

上下文无关语法

这一节解析器，主要讨论了如何描述并识别编程语言的语法结构。解析器负责将词法分析器生成的标记流转换为抽象语法树（AST），以便后续的语义分析和代码生成。

解析是编译器前端的第二个阶段。解析器与由扫描器分词后的程序协同工作；它看到的是标注了其语法类别的单词流（类似于它们的词性）。解析器为程序推导出一个句法结构，将单词适配到源编程语言的语法规则模型中。如果解析器确定输入流是一个有效的程序，它会构建程序的具体模型，即中间表示，供编译器的其余部分使用。如果解析器发现错误，它会向用户报告问题及其位置。

首先来探讨一下为什么扫描器中描述的正则表达式不能继续在解析器中使用。

  • 正则表达式只能描述有限的语法结构，能表示给定结构的固定次数的重复或者没有指定次数的重复
  • 不能用于描述配对或嵌套的结构
    • 例如，正则表达式不能描述 (n)n,n≥0(^n )^n ,n \geq 0 语句的语法结构,因为有限自动机无法记录访问他同一状态的次数。

因此在解析器中，我们引入了上下文无关语法，来描述编程语言的语法结构。

上下文无关语法G由一个四元组来进行定义(T,NT,P,S)。

  • T是终结符的有限集合。语言L(G)中的终端符号集，或称为单词。终端符号对应于扫描器返回的语法类别。
  • NT是非终结符的有限集合。它们是为在G的产生式中提供抽象和结构而引入的语法变量。
  • P是产生式的有限集合。P中的每条规则具有形式 NT→(T∪NT)+NT → (T ∪ NT)^+；也就是说，它用一个或多个语法符号的字符串替换单一的非终端符号。
  • S是开始符号。

上下文无关的的意思在文法推导的每一步

αAβ→αγβ\alpha A\beta \to \alpha \gamma \beta

符号串γ\gamma仅根据AA的产生式推导，而无需依赖AA的上下文α,β\alpha,\beta。

提示

上下文语法英文是Context-Free Grammar，简称CFG。注意与后面的CFG,Control Flow Graph区分，控制流图区分。

那么回到上面的例子，如何用一个上下文无关(CFG)语法来描述 (n)n,n≥0(^n )^n ,n \geq 0:

S→(S)∣εS\to (S)|\varepsilon

最左推导和最右推导

最左推导和最右推导很简单，我们用一个例子来进行说明假设有如下的文法规则：

  • S→ABS \to A B
  • A→aA \to a
  • B→bCB \to b C
  • C→cC \to c
  1. 最左推导就是始终把最左边的非终结符替换掉。
  • 推导过程：
    • S→ABS \to A B （最左非终结符A）
    • →aB\to a B （最左非终结符B）
    • →abC\to a b C （最左非终结符C）
    • →abc\to a b c （推导完成）
  1. 最右推导就是始终把最右边的非终结符替换掉。
  • 推导过程：
    • S→ABS \to A B （最右非终结符B）
    • →AbC\to A b C （最右非终结符C）
    • →Abc\to A b c （最右非终结符A）
    • →abc\to a b c （推导完成）

文法的二义性

文法的二义性是指一个句子可以通过多种不同的方式推导出来，从而产生多个不同的语法树。这种二义性会导致编译器无法确定程序的正确语法结构。

产生二义性的主要原因包括：

  1. 存在多个产生式可以推导同一个非终结符
  2. 产生式的顺序安排不当
  3. 缺少明确的优先级和结合性规则

以if-else语句为例，考虑以下文法：

Stmt→i f Expr then Stmt∣i f Expr then Stmt else  Stmt∣Other\begin{array} {c c l} {{{{S t m t}}}} & {{{\to}}} & {{{{\textnormal{i f}} \ E x p r \ \mathrm{t h e n} \ \mathrm{S t m t}}}} \\ {{{}}} & {{{|}}} & {{{{\textnormal{i f}} \ E x p r \ \mathrm{t h e n} \ \mathrm{S t m t} \ \mathrm{e l s e} \ \ \mathrm{S t m t}}}} \\ {{{}}} & {{{|}}} & {{{{O t h e r}}}} \\ \end{array}

对于句子 ifExprithenifExpr2thenOther1elseOther2if Expri then if Expr2 then Other1 else Other2，则会存在两棵语法推导树。 cycle_constructioncycle_construction

这个语法出现二义性的原因是，每个 elseelse 与最近的 thenthen 匹配。 我们可以进行一下修改，就避免产生了二义性：

1Stmt→if Expr then Stmt2∣if Expr then WihElse else Stmt3∣Other4WithElse→if Expr then WithElse else WithElse5∣Other\begin{array} {l l l l} {{{1}}} & {{{S t m t}}} & {{{\to}}} & {{{\mathrm{i f ~ E x p r ~ t h e n ~ S t m t}}}} \\ {{{2}}} & {{}} & {{{|}}} & {{{\mathrm{i f ~ E x p r ~ t h e n ~ W i h E l s e ~ e l s e ~ S t m t}}}} \\ {{{3}}} & {{}} & {{{|}}} & {{{O t h e r}}} \\ {{{4}}} & {{{W i t h E l s e}}} & {{{\to}}} & {{\mathrm{i f ~ E x p r ~ t h e n ~ W i t h E l s e ~ e l s e ~ W i t h E l s e}}} \\ {{{5}}} & {{}} & {{|}} & {{O t h e r}} \\ \end{array}

更新日志

2025/1/9 08:04
查看所有更新日志
  • 2b275-更新自顶向下解析器于