• Compiler Design Video Tutorials

编译器设计 - 语法分析

上一页
下一页

语法分析或解析是编译器的第二阶段。本章我们将学习构建解析器中使用的基本概念。

我们已经看到，词法分析器可以借助正则表达式和模式规则来识别标记。但是，由于正则表达式的局限性，词法分析器无法检查给定句子的语法。正则表达式无法检查平衡标记，例如括号。因此，此阶段使用上下文无关文法 (CFG)，它由下推自动机识别。

另一方面，CFG 是正则文法的超集，如下图所示

Relation of CFG and Regular Grammar

这意味着每个正则文法也是上下文无关的，但存在一些问题超出了正则文法的范围。CFG 是描述编程语言语法的有用工具。

上下文无关文法

在本节中，我们将首先了解上下文无关文法的定义，并介绍在解析技术中使用的术语。

上下文无关文法有四个组成部分

  • 一组非终结符 (V)。非终结符是表示字符串集的语法变量。非终结符定义有助于定义由文法生成的语言的字符串集。

  • 一组标记，称为终结符 (Σ)。终结符是从中形成字符串的基本符号。

  • 一组产生式 (P)。文法的产生式指定了如何组合终结符和非终结符以形成字符串。每个产生式由一个称为产生式左边的非终结符、一个箭头和一个标记和/或非终结符序列组成，称为产生式的右边。

  • 其中一个非终结符被指定为起始符号 (S)；从这里开始产生式。

通过重复用该非终结符的产生式右边替换一个非终结符（最初是起始符号），从起始符号导出字符串。

示例

我们以回文语言问题为例，它无法用正则表达式来描述。也就是说，L = { w | w = wR } 不是正则语言。但它可以用 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 等。

语法分析器

语法分析器或解析器以标记流的形式接收来自词法分析器的输入。解析器根据产生式规则分析源代码（标记流），以检测代码中的任何错误。此阶段的输出是语法树。

Syntax Analyzer

这样，解析器完成了两个任务，即解析代码，查找错误并生成语法树作为该阶段的输出。

即使程序中存在一些错误，也希望解析器解析整个代码。解析器使用错误恢复策略，我们将在本章后面学习。

推导

推导基本上是一系列产生式规则，用于获取输入字符串。在解析过程中，我们对输入的一些句子式进行两个决定

  • 决定要替换哪个非终结符。
  • 决定用哪个产生式规则来替换非终结符。

为了决定用哪个产生式规则替换哪个非终结符，我们可以有两个选择。

最左推导

如果从左到右扫描和替换输入的句子式，则称为最左推导。通过最左推导导出的句子式称为左句子式。

最右推导

如果我们从右到左用产生式规则扫描和替换输入，则称为最右推导。从最右推导导出的句子式称为右句子式。

示例

产生式规则

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 * EParse Tree Construction

步骤 2

E → E + E * EParse Tree Construction

步骤 3

E → id + E * EParse Tree Construction

步骤 4

E → id + id * EParse Tree Construction

步骤 5

E → id + id * idParse Tree Construction

在语法树中

  • 所有叶子节点都是终结符。
  • 所有内部节点都是非终结符。
  • 中序遍历给出原始输入字符串。

语法树描述了运算符的结合性和优先级。最深的子树首先被遍历，因此该子树中的运算符优先于父节点中的运算符。

二义性

如果文法 G 对至少一个字符串具有多个语法树（左推导或右推导），则称该文法为二义性的。

示例

E → E + E
E → E – E
E → id

对于字符串 id + id – id，上述文法生成两棵语法树

Parse Tree Construction

由二义性文法生成的语言被称为固有二义性。文法中的二义性对于编译器构造不利。没有方法可以自动检测和消除二义性，但可以通过重写整个文法而不含二义性，或者通过设置和遵循结合性和优先级约束来消除二义性。

结合性

如果一个操作数两侧都有运算符，则运算符获取此操作数的哪一侧由这些运算符的结合性决定。如果运算为左结合性，则操作数将被左运算符获取；如果运算为右结合性，则右运算符将获取操作数。

示例

加法、乘法、减法和除法等运算符是左结合的。如果表达式包含

id op id op id

它将被计算为

(id op id) op id

例如，(id + id) + id

指数运算等运算符是右结合的，即同一表达式中的计算顺序将为

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”本身作为最左边的符号，则该文法成为左递归。左递归文法被认为是自顶向下解析器的一个问题情况。自顶向下解析器从起始符号开始解析，起始符号本身是非终结符。因此，当解析器在其推导中遇到相同的非终结符时，它很难判断何时停止解析左非终结符，并且它会进入无限循环。

示例

(1) A => Aα | β

(2) S => Aα | β 
    A => Sd

(1) 是直接左递归的示例，其中 A 是任何非终结符，α 表示非终结符的字符串。

(2) 是间接左递归的示例。

Left Recursion

自顶向下解析器将首先解析 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

示例

产生式集

S => Aα | β 
A => Sd

应用上述算法后，应该变成

S => Aα | β 
A => Aαd | βd

然后，使用第一种技术消除直接左递归。

A  => βdA'
A' => αdA' | ε

现在没有产生式具有直接或间接左递归。

左因子化

如果多个文法产生式规则具有共同的前缀字符串，则自顶向下解析器无法选择应该使用哪个产生式来解析手中的字符串。

示例

如果自顶向下解析器遇到类似这样的产生式

A ⟹ αβ | α𝜸 | …

那么它无法确定要遵循哪个产生式来解析字符串，因为这两个产生式都是从相同的终结符（或非终结符）开始的。为了消除这种混淆，我们使用一种称为左因子化的技术。

左因子化转换文法使其对自顶向下解析器有用。在这种技术中，我们为每个公共前缀创建一个产生式，其余的推导由新的产生式添加。

示例

上述产生式可以写成

A => αA'
A'=> β | 𝜸 | …

现在解析器每个前缀只有一个产生式，这使得决策更容易。

FIRST 集和 FOLLOW 集

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

FIRST 集

此集合用于确定非终结符在首位推导出的终结符是什么。例如：

α → t β

α在首位推导出t（终结符）。因此，t ∈ FIRST(α)。

计算First集合的算法

查看FIRST(α)集合的定义

  • 如果α是终结符，则FIRST(α) = { α }。
  • 如果α是非终结符且α → ℇ是一个产生式，则FIRST(α) = { ℇ }。
  • 如果α是非终结符且α → 𝜸1 𝜸2 𝜸3 … 𝜸n，并且任何FIRST(𝜸)包含t，则t在FIRST(α)中。

First集合可以看作

Follow集合

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

计算Follow集合的算法

  • 如果α是开始符号，则FOLLOW(α) = $

  • 如果α是非终结符，并且有产生式α → AB，则FIRST(B)（除了ℇ）在FOLLOW(A)中。

  • 如果α是非终结符，并且有产生式α → AB，其中B≠ℇ，则FOLLOW(A)在FOLLOW(α)中。

Follow集合可以看作：FOLLOW(α) = { t | S *αt*}

语法分析器的局限性

语法分析器以标记的形式从词法分析器接收输入。词法分析器负责语法分析器提供的标记的有效性。语法分析器有以下缺点：

  • 它无法确定标记是否有效；
  • 它无法确定标记是否在使用前已声明；
  • 它无法确定标记是否在使用前已初始化；
  • 它无法确定对标记类型执行的操作是否有效。

这些任务由语义分析器完成，我们将在语义分析中学习。

打印页面
上一页
下一页
广告