上一节:
下一节:

  编译器设计 - 语法分析

  • 简述

    语法分析或解析是编译器的第二阶段。在本章中，我们将学习构建解析器时使用的基本概念。
    我们已经看到词法分析器可以借助正则表达式和模式规则来识别标记。但是由于正则表达式的限制，词法分析器无法检查给定句子的语法。正则表达式无法检查平衡标记，例如括号。因此，这个阶段使用上下文无关文法（CFG），它被下推自动机识别。
    另一方面，CFG 是正则语法的超集，如下图所示：
    CFG 与正则文法的关系
    这意味着每个正则语法也是上下文无关的，但存在一些问题，这些问题超出了正则语法的范围。CFG 是描述编程语言语法的有用工具。

  • 上下文无关语法

    在本节中，我们将首先了解上下文无关语法的定义，并介绍解析技术中使用的术语。
    上下文无关文法有四个组成部分：
    • 一套non-terminals（五）。非终结符是表示字符串集的句法变量。非终结符定义了有助于定义语法生成的语言的字符串集。
    • 一组令牌，称为terminal symbols(Σ)。终端是构成字符串的基本符号。
    • 一套productions(P)。文法的产生式指定终结符和非终结符可以组合形成字符串的方式。每个生产包括一个non-terminal称为产生式的左侧，箭头和一系列标记和/或on- terminals，称为产生式的右侧。
    • 其中一个非终结符被指定为开始符号（S）；从哪里开始生产。
    对于该非终结符，这些字符串是通过将一个非终结符（最初是开始符号）重复替换为一个产生式的右侧而从开始符号派生的。

    例子

    我们以回文语言的问题为例，它不能用正则表达式来描述。也就是说，L = { w | w = w R } 不是常规语言。但可以用CFG来描述，如下图： 
    
G = ( V, Σ, P, S )
    在哪里： 
    
V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S = { Q }
    该语法描述回文语言，如：1001、11100111、00100、1010101、11111等。

  • 语法分析器

    语法分析器或解析器以令牌流的形式从词法分析器获取输入。解析器根据生产规则分析源代码（令牌流）以检测代码中的任何错误。这个阶段的输出是parse tree.
    语法分析器
    这样，解析器完成了两个任务，即解析代码、查找错误和生成解析树作为阶段的输出。
    即使程序中存在一些错误，解析器也应该解析整个代码。解析器使用错误恢复策略，我们将在本章后面学习。

  • 推导

    推导基本上是一系列生产规则，以获取输入字符串。在解析期间，我们对某些句子形式的输入做出两个决定：
    • 决定要替换的非终端。
    • 决定生产规则，根据该规则，非终端将被替换。
    要决定用生产规则替换哪个非终端，我们可以有两种选择。

    最左推导

    如果从左到右扫描并替换输入的句子形式，则称为最左派生。由最左派生的句型称为左句型。

    最右推导

    如果我们从右到左扫描并用产生式规则替换输入，则称为最右派生。从最右派生的句子形式称为右句形式。
    Example
    制作规则： 
    
E → E + E
E → E * E
E → id
    输入字符串：id + id * id
    最左边的推导是： 
    
E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id
    请注意，最左侧的非终结符总是首先被处理。
    最右边的推导是： 
    
E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id

  • 解析树

    解析树是推导的图形描述。查看字符串是如何从开始符号派生的很方便。推导的开始符号成为解析树的根。让我们通过上一个主题的示例来了解这一点。
    我们取 a + b * c 的最左推导
    最左边的推导是： 
    
E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id
    步骤1：
    E → E * E 解析树构造
    第2步：
    E → E + E * E 解析树构造
    第 3 步：
    E → id + E * E 解析树构造
    第4步：
    E → id + id * E 解析树构造
    第 5 步：
    E → id + id * id 解析树构造
    在解析树中：
    • 所有叶节点都是终端。
    • 所有内部节点都是非终端。
    • 中序遍历给出原始输入字符串。
    解析树描述了运算符的关联性和优先级。首先遍历最深的子树，因此该子树中的运算符优先于父节点中的运算符。

  • 歧义

    如果一个文法 G 对于至少一个字符串有不止一棵解析树（左推导或右推导），则称它是不明确的。
    Example 
    
E → E + E
E → E – E
E → id
    对于字符串id + id - id，上面的语法生成两个解析树：
    解析树构造
    歧义文法生成的语言称为inherently ambiguous. 语法中的歧义不利于编译器的构造。没有任何方法可以自动检测和消除歧义，但可以通过重写整个语法而不产生歧义，或者通过设置和遵循关联性和优先约束来消除歧义。

  • 关联性

    如果一个操作数两边都有操作符，那么操作符取这个操作数的那一侧是由这些操作符的结合性决定的。如果运算是左结合的，则操作数将由左运算符获取，或者如果运算是右结合的，则右运算符将获取操作数。
    Example
    诸如加法、乘法、减法和除法之类的运算是左结合的。如果表达式包含： 
    
id op id op id
    它将被评估为： 
    
(id op id) op id
    例如，(id + id) + id
    像 Exponentiation 这样的运算是右结合的，即同一表达式中的求值顺序为： 
    
id op (id op id)
    比如id^(id^id)

  • 优先级

    如果两个不同的运算符共享一个共同的操作数，则运算符的优先级决定了哪个将采用该操作数。即2+3*4可以有两种不同的解析树，一种对应(2+3)*4，另一种对应2+(3*4)。通过设置运算符之间的优先级，可以轻松解决此问题。与前面的示例一样，在数学上 *（乘法）优先于 +（加法），因此表达式 2+3*4 将始终被解释为： 
    
2 + (3 * 4)
    这些方法减少了语言或其语法出现歧义的机会。

  • 左递归

    如果一个文法有任何非终结符“A”，其推导包含“A”本身作为最左边的符号，则该文法变为左递归。左递归语法被认为是自上而下解析器的一个有问题的情况。自上而下的解析器从 Start 符号开始解析，它本身是非终端的。因此，当解析器在其推导中遇到相同的非终结符时，它很难判断何时停止解析左侧的非终结符并进入无限循环。
    Example: 
    
(1) A => Aα | β
(2) S => Aα | β 
    A => Sd
    (1) 是立即左递归的示例，其中 A 是任何非终结符，α 表示一串非终结符。
    (2) 是间接左递归的一个例子。
    左递归
    自上而下的解析器将首先解析 A，然后将产生一个由 A 本身组成的字符串，并且解析器可能会永远进入循环。

    去除左递归

    删除左递归的一种方法是使用以下技术：
    生产 
    
A => Aα | β
    转换为以下产生式 
    
A => βA'
A'=> αA' | ε
    这不会影响从语法派生的字符串，但会删除立即左递归。
    第二种方法是使用以下算法，该算法应该消除所有直接和间接的左递归。 
    
START
Arrange non-terminals in some order like A1, A2, A3,…, An
   for each i from 1 to n
      {
      for each j from 1 to i-1
         {
         replace each production of form Ai ⟹Aj?
         with Ai ⟹ δ1?  | δ2? | δ3? |…| ? 
         where Aj ⟹ δ1 | δ2|…| δn  are current Aj productions
         }
      }
   eliminate immediate left-recursion
   
END
    Example
    生产集 
    
S => Aα | β 
A => Sd
    应用上述算法后，应该变成 
    
S => Aα | β 
A => Aαd | βd
    然后，使用第一种技术删除立即左递归。 
    
A  => βdA'
A' => αdA' | ε
    现在没有一个产品具有直接或间接的左递归。

  • 左保理

    如果不止一个语法产生式规则有一个公共前缀字符串，那么自上而下的解析器就不能选择它应该使用哪个产生式来解析手头的字符串。
    Example
    如果自上而下的解析器遇到像 
    
A ⟹ αβ | α? | …
    然后它无法确定要遵循哪个产生式来解析字符串，因为两个产生式都从同一个终端（或非终端）开始。为了消除这种混淆，我们使用了一种称为左分解的技术。
    左分解转换语法以使其对自上而下的解析器有用。在这种技术中，我们为每个公共前缀制作一个产生式，其余的派生由新产生式添加。
    Example
    上面的产生式可以写成 
    
A => αA'
A'=> β | ? | …
    现在解析器每个前缀只有一个产生式，这使得决策更容易。

  • 第一套和跟随套

    解析器表构造的一个重要部分是创建 first 和 follow 集合。这些集合可以提供推导中任何终端的实际位置。这样做是为了创建解析表，其中决定用一些产生式规则替换 T[A, t] = α。

    第一套

    创建这个集合是为了知道非终结符在第一个位置派生出什么终结符。例如， 
    
α → t β
    也就是说，α 在第一个位置导出 t（终端）。所以，t ∈ FIRST(α)。

    计算第一组的算法

    看一下 FIRST(α) 集合的定义：
    • 如果 α 是终结符，则 FIRST(α) = { α }。
    • 如果 α 是非终结符且 α → l 是产生式，则 FIRST(α) = { l }。
    • 如果 α 是非终结符且 α → ?1 ?2 ?3 ... ?n 且任何 FIRST(?) 包含 t，则 t 在 FIRST(α) 中。
    第一组可以看成：

    跟随集

    同样，我们计算产生式规则中紧跟非终结符 α 的终结符。我们不考虑非终结符可以生成什么，而是我们看到在生成非终结符之后的下一个终结符符号是什么。

    计算跟随集的算法：

    • 如果 α 是开始符号，则 FOLLOW() = $
    • 如果 α 是非终结符并且具有产生式 α → AB，则 FIRST(B) 位于 FOLLOW(A) 中，但 ℇ 除外。
    • 如果 α 是一个非终结符并且有一个产生式 α → AB，其中 B ℇ，那么 FOLLOW(A) 在 FOLLOW(α) 中。
    跟随集可以看作：FOLLOW(α) = { t | S *αt*}

  • 语法分析器的限制

    语法分析器以标记的形式从词法分析器接收输入。词法分析器负责语法分析器提供的令牌的有效性。语法分析器有以下缺点 -
    • 它无法确定令牌是否有效，
    • 它无法确定令牌在使用之前是否已声明，
    • 它无法确定令牌在使用之前是否已初始化，
    • 它无法确定对令牌类型执行的操作是否有效。
    这些任务由语义分析器完成，我们将在语义分析中进行研究。
上一节:
下一节: