4.1. Jison¶

本节主题包括：

1. 解析器生成器

2. Jison 解析器生成器

一个 词法分析器 是一个程序，它接受作为输入一个在 源语言 （即您正在编译或解释的编程语言）中的程序，并确定源程序在语法上是否正确。如果正确，词法分析器返回一个信号表明它是正确的（例如，源程序的语法树）。否则，词法分析器返回一个或多个语法错误。

解析通常是编译或解释程序时首先完成的一个子任务。

Jison 是由 Zach Carter 开发的解析器生成器。它可以在 https://gerhobbelt.github.io/jison/ 下载或在线使用。详细描述 Jison 超出了本课程编程语言的范畴。然而，我们确实希望提供一个概述，说明如何使用它，因为它将被纳入本课程后期开发的解释器中。Jison 的描述可以在 https://gerhobbelt.github.io/jison/docs/ 找到。

作为使用 Jison 的一个示例，我们在前一章节中给出的语法 第三个示例文法 将以如下形式提供给 Jison:

/*
  描述：解析简单的算术表达式
*/

// 语法的词法部分 // ==============================

%lex %% \s+                   /* 没有返回值语句，因此跳过空白字符 */ [A-Z]                 return "VAR"    /* 变量是一个单独的英文大写字母 */ "*"                   return "TIMES" "/"                   return "DIV" "-"                   return "MINUS" "+"                   return "PLUS" "("                   return "LPAREN" ")"                   return "RPAREN" <<EOF>>               return "EOF" .                     return "INVALID"

/lex

%start 程序

// 语法规则中的短语结构部分 // =======================================

%%

程序
    : 表达式 "EOF"
      { 返回 "该程序是有效的"; } /* 由成功解析返回 */
    ;
表达式
    : 项 | 表达式 "PLUS" 项 | 表达式 "MINUS" 项 ;
项
    : 因子 | 项 "TIMES" 因子 | 项 "DIV" 因子 ;
因子
    : "VAR" | "LPAREN" 表达式 "RPAREN"
  ;

您的讲师将提供有关如何在您的安装中使用时 Jison 的具体说明。 然而，它非常容易在线尝试。 只需执行以下操作：

• 前往 https://gerhobbelt.github.io/jison/try/ 。在那里，你会发现 Jison 提供了一个文本区域，您可以将文法粘贴进去。

• 将上述出现的 Jison 文法粘贴到此文本区域中，替换掉已经存在的默认文法。然后单击 Generate Parser 按钮，这将相应地在 Jison 服务器上生成您的解析器。

• 然后在 Test Your Parser 区域输入 第三个示例文法 的有效表达式，并单击 Parse 按钮。如果您的表达式确实有效，您应该看到生成的消息 "The program is valid"。为什么？因为 program 是该文法 Jison 版本中的顶级开始符号，并且在上述 Jison 规范中，这是我们在成功解析时应该返回的字符串（由于文法中的行 return "The program is valid"）。如果您输入的表达式无效，您将看到由 Jison 生成的详细错误消息。

本节练习问题集包含两个涉及简单 Jison 语法的练习问题。在开始这些问题之前，你需要了解一种用于表达词法结构的 Jison 约定。在上面的示例文法中，该约定体现在以下规范中:

[A-Z]                 返回"VAR"    /* 一个变量是一个大写字母 */

符号 [A-Z] 告诉 Jison 变量必须由 "A" 到 "Z" 之间的一个大写字母组成。如果我们也希望允许使用小写字母，则应给出以下规范:

[A-Z]|[a-z]           return "VAR"    /* 一个变量是一个大写字母或小写字母 */

注意垂直线，它表示“或”。

如果我们想要指定一个变量是单个大写字母后跟单个数字，我们可以使用如下语法:

[A-Z][0-9]            return "VAR"    /* 一个变量是一个大写字母后跟一个数字 */

此处，缺少垂直线表示这两个字符必须按顺序出现，而不是单独出现其中一个。

包含竖线、方括号、双引号字符串等（以及我们将在此处不讨论的其他符号）且在 Jison 语法的 lexical 部分位于"return"关键字之前的表达式被称为 正则表达式。

下面的第一个问题将帮助你理解 Jison 文件所表示的语法。注意，该问题是随机生成的。你必须 连续三次正确解决它 才能获取与之相关的学分。

4.2. 更多练习 Jison¶

该问题将为您提供更多练习，以理解在 Jison 文件格式中定义的语法。