# 文法分析

本框架的文法分析器由 [Jacc](http://web.cecs.pdx.edu/~mpj/jacc/) 生成。 Jacc 是一个类似于 [yacc](http://dinosaur.compilertools.net/yacc/index.html) 的工具，同样基于 LALR(1) 分析。 只不过，它能生成 Java 源码。

## Jacc 中的优先级与结合性

`Decaf.jacc` 文件包含了所有 Decaf 的文法。 Jacc 文法描述形式如同 BNF，遗憾的是，它**不支持** EBNF 中诸如 `?`/`+`/`*` 等符号。 因此，遇到这样的文法时，我们不得不手动将其转换为普通的 BNF。 转换方式不难想到，你可以参考我们已经定义出来的文法，并与语言标准中给出 EBNF 进行比对。

在 `Decaf.jacc` 文件的导言区，我们用如下格式的一张“表”定义出了 Decaf 语言操作符的优先级和结合性：

```
%left OR
%left AND
%nonassoc EQUAL NOT_EQUAL
%nonassoc LESS_EQUAL GREATER_EQUAL '<' '>'
%left  '+' '-'
%left  '*' '/' '%'
%nonassoc UMINUS '!'
%nonassoc '[' '.'
%nonassoc ')' EMPTY
%nonassoc ELSE
```

不难猜测出，结合性由 `%left` 等命令指定，而优先级按照声明的顺序**由低到高**。 更多细节请查阅[用户手册](http://web.cecs.pdx.edu/~mpj/jacc/jacc.pdf)。

## 左递归

Jacc 采用 LR 分析，因此左递归并不会引起冲突。你可以在书写文法时自由使用左递归。

## 语义动作——构造 AST

与 JFlex 类似，在 Jacc 中定义文法时，我们可以在每个产生式（右部）后面跟上一个用大括号括起来的 Java 代码片段。 这个代码片段被称为“语义动作”，即当用这个产生式进行规约以后，我们要做的事情。 在本框架中，语义动作就是将该产生式左部非终结符对应的那个 AST 结点构造出来，并存储到*语义值*中。 如果语法分析成功，那么最终我们会用到开始符号对应的那个产生式进行规约，规约时的语义动作就是把 AST 的根结点构造出来：

```
TopLevel :  ClassList
            {
                tree = new TopLevel($1.classList, $1.pos);
            }
            ;
```

这里的 `tree` 是语法分析阶段我们期望的输出。

每个语法符号（终结符和非终结符）都会对应着一个语义值，其定义参见 `SemValue.java`。 需要特别指出的是，在 LR 分析过程中，我们常用一个语义值**栈**来维护当前状态下各个语法符号对应的语义值。 这就无形中要求所有语义值都得是**同一**（或者它们有公共的上界，homogeneous）类型。 但是我们的 AST 分为好多种 (heterogenous) 类型，比如语句、表达式等等。 一种可行的方法是栈里面全部存所有 AST 结点的基类 `TreeNode`，这样无论你是啥结点都可以表示。 但问题在于，当你需要读取一个特定的类型，如表达式的时候，就得不得把这个 `TreeNode` 对象向下转型为 `Expr`。这个方法十分丑陋。 作为惯例，Jacc 工具要求用户设计出来一个 `SemValue` 类，把要用到的那些具体的类型全部作为这个类的成员：

```java
class SemValue {
    final Kind kind;

    // For parser
    Tree.ClassDef clazz;
    List<Tree.ClassDef> classList;

    Tree.Field field;
    List<Tree.Field> fieldList;

    List<Tree.LocalVarDef> varList;

    Tree.TypeLit type;

    Tree.Stmt stmt;
    List<Tree.Stmt> stmtList;
    Tree.Block block;

    Tree.Expr expr;
    List<Tree.Expr> exprList;
    Tree.LValue lValue;

    Tree.Id id;

    /* ... */
}
```

这样就不用强转了，只需直接访问指定的成员即可，如 `.stmt`, `.expr` 等。用 C++ 的话说，`SemValue` 就是个 *union*。

以下列 if 语句为例：

```
Stmt :  IF '(' Expr ')' Stmt ElseClause
        {
            $$ = svStmt(new If($3.expr, $5.stmt, Optional.ofNullable($6.stmt), $1.pos));
        }
```

产生式左部 `Stmt` 所对应的语义值用 `$$` 表示，而产生式右部的符号按照从左往右的顺序依次用 `$1`, `$2`, ... 表示。 在语法树中，一个 if 语句用类 `If` 表示，它的构造函数签名如下：

```java
public If(Expr cond, Stmt trueBranch, Optional<Stmt> falseBranch, Pos pos)
```

我们通过 `$3.expr` 访问到括号中的表达式，`$5.stmt` 访问到第一个语句，`$6.stmt` 访问到第二个语句（如果没有，则是 null）。 最后，我们需要设置该 AST 结点的位置——`IF` 那个单词对应的位置。

此外，`AbstractParser` 类提供了一组用于构造特定类型语义值的函数，如这里的 `svStmt` 函数输入一个 `Stmt` 结点， 返回一个 `kind` 是语句的 `SemValue`。请在开始实验前阅读并了解所提供的接口，便于在开发时使用。

由于 IDE 一般不会支持像 `.jacc` 这种“小众”格式的源码，为了方便你写出符合 Java 语法的语义动作代码， 你可以先在 `SemValue.java` 提供的 `UserAction` 函数里面实现，然后再粘贴到 `.jacc` 文件中。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://decaf-lang.gitbook.io/decaf-book/java-kuang-jia-fen-jie-duan-zhi-dao/pa1a-yu-fa-fen-xi-qi-de-zi-dong-gou-zao/parser.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.