实验 1 词法与语法分析器

在本实验中，你将通过编写文法描述文件，使用 ANTLR v4 生成词法和语法分析器，并编写一个在 parse tree 上遍历生成 abstract syntax tree (AST) 的 visitor 来实现一个 C1 语言分析器。

• C1 语言说明
• 实验内容与提交要求
  • Lab1-1. C1的词法分析
    • 主要任务
    • 重点与难点
    • 提交说明
  • Lab1-2. C1的语法分析
    • 主要任务
    • 回答问题
    • 提交说明
  • Lab1-3. 生成 AST 的 C1 解析器
    • 主要任务
    • 重点与难点
    • 回答问题
    • 提交说明
• ANTLR v4 的使用
  • 文法描述文件.g4的编写
    • 词法分析(Lexer)
    • 语法分析(Parser)
  • 对ANTLR生成的代码进行编程
    • Parse Tree的结构
• Design Pattern
  • Visitor Pattern
  • 结合Lab1-3理解Visitor Pattern
• 实验代码的编译和运行以及可视化
  • Lab1-1和Lab1-2的文法文件的测试以及可视化
  • Lab1-3的编译和运行

C1 语言说明

C1 是本课程实验要实现的一个 C 语言子集。它没有完善的类型系统，只有int、float和元素为 int 或 float 类型的一维数组，并附带 const 描述符；它的函数定义没有参数和返回值。C1语言的文法采用 EBNF (Extended Backus-Naur Form) 表示如下：

CompUnit    → [ CompUnit ] ( Decl | FuncDef ) 
Decl        → ConstDecl 
            | VarDecl
ConstDecl   → 'const' BType ConstDef { ',' ConstDef } ';'
BType       → 'int' | 'float'
ConstDef    → Ident '=' Exp
            | Ident '[' [ Exp ] ']' '=' '{' Exp { ',' Exp } '}'
VarDecl     → BType VarDef { ',' VarDef } ';'
VarDef      → Ident 
            | Ident '[' Exp ']' 
            | Ident '=' Exp
            | Ident '[' [ Exp ] ']' '=' '{' Exp { ',' Exp } '}'
FuncDef     → void Ident '(' ')' Block
Block       → '{' { BlockItem } '}'
BlockItem   → Decl 
            | Stmt
Stmt        → LVal '=' Exp ';'
            | Ident '(' ')' ';' 
            | Block 
            | 'if' '( Cond ')' Stmt [ 'else' Stmt ] 
            | 'while' '(' Cond ')' Stmt 
            | ';'
LVal        → Ident
            | Ident '[' Exp ']'
Cond        → Exp RelOp Exp
RelOp       → '==' | '!=' | '<' | '>' | '<=' | '>='
Exp         → Exp BinOp Exp
            | UnaryOp Exp 
            | '(' Exp ')' 
            | LVal 
            | Number
Number      → FloatConst
            | IntConst
BinOp       → '+' | '−' | '*' | '/' | '%'
UnaryOp     → '+' | '−'

EBNF 中的符号含义

• [...]: 内包含的为可选项
• {...}: 内包含的为可重复0次至无数次的项

文法之外，需要补充说明的内容有：

• C1 语言中运算符的优先级及结合性与 C 语言一致
• C1 语言中标识符Ident规范为 C 语言标识符规范子集，参考 ISO/IEC 9899 第51页关于标识符的定义。规范中，将非终结符 identifier 产生式修改为 identifier-nondigit: nondigit，不考虑universal-character-name、other implementation-defined characters等
• C1 语言中注释规范与 C 语言一致，参考 ISO/IEC 9899 第66页关于注释的定义, 其中

// \
this is a two-line comment.

/\
/ this is also a two-line comment actually.

• C1 语言中数值常量可以是整型数IntConst，也可以是浮点数FloatConst。整型数参考 ISO/IEC 9899 第54页关于整型常量的定义，在此基础上忽略所有后缀；浮点数参考 ISO/IEC 9899 第57页关于浮点常量的定义，在此基础上上忽略16进制浮点表示和所有后缀。

实验内容与提交要求

在本课程实验中，你将通过编写文法描述文件和相关的处理代码，使用 ANTLR v4，最终为C1 语言实现一个能输出抽象语法树的 C1 解析器。为便于过程控制与管理，课程实验拆分成三步，分三次提交：

• lab1-1：构造 C1 的词法分析器
• lab1-2：构造 C1 的语法分析器
• lab1-3：构造能生成 AST 的 C1 解析器

你需要对所提供的课程实验软件包中的部分文件进行修改和完善，补充更多的测试例子，撰写和提交介绍课程实验的分析、设计和测试方面的报告。你需要事先阅读本页其他小节的内容，它们将能在一定程度上给你的课程实验提供帮助和指引。如果有疑问请及时提出，我们会公开回答有必要回答的问题。

Lab1-1. C1 的词法分析

Lab1-1 主要任务

• 根据 C1 语言 的词法描述，修改并完善 C1 的词法描述文件c1recognizer/grammar/C1Lexer.g4
• 利用 ANTLR v4 节介绍的antlr4和grun工具正确构造你的词法分析器
• 编写若干个正确的和错误的C1程序（侧重在词法是否有错误）作为测试用例，测试你的C1 词法分析器
  • 测试程序置于c1recognizer/test/test_cases/lexer目录下
  • 正确测试用例文件名前缀为pt_
  • 错误测试用例文件名前缀为ft_
• 在c1recognizer/doc目录下增加markdown文件描述实验遇到的问题、分析与设计，文件名前缀为lab1-1

Lab1-1 重点与难点

• 特别注意行尾的处理，正确地处理 CRLF 和 LF 两种换行
• 你需要仔细编写单行注释和多行注释的词法规则，并构造各种测试例子进行测试
• 你需要仔细考虑数值的多种形式，编写能表达这些形式的词法规则，并构造各种测试例子进行测试

Lab1-1 提交说明

你需要参照实验软件包 c1recognizer的目录结构来组织你本次实验的提交文件，目录结构如下。助教会借助脚本实现实验的半自动检查，请一定严格按照本节要求组织项目目录和文件，否则会影响本次实验成绩。

- <your repo>
  | c1recognizer         复制自公共仓库的 c1recognizer 项目，请勿遗漏内容。
    | cmake/
>>  | grammar/           修改其中的 C1Lexer.g4
    | include/c1recognizer/ 
    | src/
>>  | test/test_cases/   增加你的测试程序
>>  | doc/               增加文档描述实验中遇到的问题、分析和设计，文件名前缀为lab1-1
    | 其他已有的文件

Lab1-2. C1 的语法分析

Lab1-2 主要任务

• 根据 C1语言 的 EBNF 描述，修改并完善课程实验软件包中 C1 的语法描述文件c1recognizer/grammar/C1Parser.g4
• 利用 ANTLR v4 节介绍的antlr4和grun工具正确构造你的分析器
• 编写若干个正确的和错误的C1程序作为测试用例，来测试你的C1 语法分析器
  • 测试输入应置于test/test_cases/parser目录下
  • 正确测试用例文件名前缀为pt_
  • 错误测试用例文件名前缀为ft_

• 在lab1-answer/目录下增加回答lab1-2的问题1--问题3的解答，文件名前缀为lab1-2，以及可能的被引用图像文件

• 在c1recognizer/doc目录下增加markdown文件描述实验遇到的问题、分析与设计，文件名前缀为lab1-2

Lab1-2 回答问题

问题1. 分析和总结 ANTLR 对左递归文法的处理方法

• ANTLR 容许哪些类型的左递归？
• ANTLR 对所支持的左递归如何处理？例如，对下面两种情况分别会怎样解析？

  Exp : Exp '*' Exp | Exp '+' Exp | IntConst;
  Exp : Exp '+' Exp | Exp '*' Exp | IntConst;
  

• ANTLR 能为上面哪一种情况构造出符号'*'的优先级比'+'高的表达式解析器？这是基于ANTLR 采用的什么样的二义性消除规则？
• 如果将下面的第1行改写成第2行，那么生成的解析器源码有什么样的变化？请理解和说明 '# Mult' 的作用和意义。
  • Exp : Exp '*' Exp | Exp '+' Exp | IntConst;
  • Exp : Exp '*' Exp # Mult | Exp '+' Exp # Add | IntConst # Int ;
• 给出ANTLR 不支持的左递归文法的例子并尝试分析原因。

问题2. 阅读 LL(*) 分析方法 [PLDI 2011]，并回答以下问题

• 简述LL(*)分析方法的核心逻辑，它与传统的LL分析区别在哪里？
• 证明下面的文法为LL-regular文法，并按照文章的LL(*) parser构造算法绘制该文法的ATN和Lookahead DFA。在算法执行过程中会出现哪些问题？解释问题产生的原因。假设ATNLR允许的最大递归深度$m=1$。

S → Ac | Ad
A → aA | b

问题3. 阅读Adaptive LL(*)分析方法[OOPSLA 2014]，并回答以下问题

• 简述ALL(*)分析方法的核心逻辑，试比较它与LL(*)分析方法的区别。
• 给定如下文法，描述输入"xba"的ALL(*)分析过程并给出最终构造的lookahead DFA。

  S → xB | yC
  B → Aa
  C → Aba
  A → b | ε
  

关于上述三个问题的解答格式要求：

• 解答建议以 markdown 文件来组织，其他可选的形式是 latex，主文件命名为 `lab1-2`
• 解答过程中涉及数学符号表达时，如果用 markdown，则必须使用markdown支持的latex语法进行描述
• 解答文件统一放到<your repo>/lab1-answer/lab1-2.md文件中；如有必要可以在该文件中添加图像引用，并将所引图像置于<your repo>/lab1-answer目录下，请确保引用路径正确

Lab1-2 提交说明

你需要在 Lab1-1 的基础上修改并组织你本次实验的提交文件，目录结构如下。助教会借助脚本实现实验的半自动检查，请一定严格按照本节要求组织项目目录和文件，否则会影响本次实验成绩。

- <your repo>
  | lab1-answer
    | lab1-2.*           回答lab1-2的问题1--问题3
    | 其他被引用图像文件
  | c1recognizer         复制自公共仓库的 c1recognizer 项目。请勿遗漏内容。
    | cmake/
>>  | grammar/           修改其中的 C1Parser.g4
    | include/c1recognizer/ 
    | src/
>>  | test/test_cases/   补充你的测试程序
>>  | doc/               增加文档描述实验中遇到的问题、分析和设计,文件名前缀为lab1-2.
    | 其他已有的文件

Lab1-3. 生成 AST 的 C1 解析器

Lab1-3 主要任务

• 分析课程实验软件包中 c1recognizer 项目结构的内容，将分析结果记录在<your repo>/c1recognizer/doc/lab1-3.md文件中，分析内容至少需要包括以下几项内容：

  • 对项目编译流程的理解，主要是对 CMakeLists.txt 文件内容的理解；
  • 对项目中的文件组织及结构的理解，说明各个文件的主要用途；
  • 项目依赖的外部组件有哪些，这些组件的用途是什么；
  • 项目由哪些主要的功能模块组成，描述模块间的交互关系

• 阅读 Lab1-3的编译和运行 一节了解项目的编译和运行方法，编译你的项目并在<your repo>/c1recognizer/doc/lab1-3.md 文件中记录编译过程中遇到的问题与解决方案。

• 阅读 对ANTLR生成的代码进行编程 和 Design Pattern，以理解 Visitor Pattern及其在 ANTLR 生成的解析器中的应用特点，并学习构建AST，在<your repo>/c1recognizer/doc/lab1-3.md 中总结这些接口与你在lab1-2中所写文法之间的关系。

  • 为了从Parse Tree生成 AST，相关的数据结构位于syntax_tree.h。你需要在 syntax_tree_builder.cpp中补充代码，以实现对AST的构建。在syntax_tree_builder.cpp已提供的初始代码中，你需要对其中形如visitSomeContext的函数补充相应的实现代码。请确保你理解了以下内容，再开展实际的代码工作：

    • 函数 antlrcpp::Any syntax_tree_builder::visitExp(C1Parser::ExpContext *ctx)的实现 ，注意理解C1Parser::ExpContext、result的含义、与文法的对应关系、使用的编程接口及其含义，查阅 antlrcpp::Any、访问者模式相关的源码
    • 函数ptr<syntax_tree_node> syntax_tree_builder::operator()(antlr4::tree::ParseTree *ctx)的实现，注意理解其中的result、result.as

    在理解之后，分析C1的Parse Tree结构，实现通过访问Parse Tree来构建AST。

• 修改并完善以下文件，使得项目编译后生成的c1r_test可执行程序能够解析输入的c1文件，并输出其AST结构。请确保你最终的提交中没有修改除下面四个文件外的任何项目文件，在提交前通过git status检查提交涉及的文件将会是一个很好的方法。修改recognizer.cpp中解析的起始符号为compilationUnit，完善syntax_tree_builder.cpp中的空白方法，如有必要可以调整C1Lexer.g4和C1Parser.g4。在<your repo>/c1recognizer/doc/lab1-3.md文件中，给出实现与调式过程中你所遇到的问题与解决方案。

  • <your repo>/c1recognizer/grammer/C1Lexer.g4
  • <your rpeo>/c1recognizer/grammer/C1Parser.g4
  • <your repo>/c1recognizer/src/recognizer.cpp
  • <your repo>/c1recognizer/scr/syntax_tree_builder.cpp

• 使用Lab1-2中你编写的测试用例对c1r_test程序进行测试，确保在你的测试用例下生成的AST是正确的，使用仓库中名为c1r_ref_ubuntu或c1r_ref_mac的二进制文件（指令集架构均x86-64）作为参考.

• 最后的检查将通过严格比较参考的二进制文件输出和你的输出来进行评测。

Lab1-3 重点与难点

在本次实验中，你可以阅读 对ANTLR生成的代码进行编程 和 Design Pattern 来起步，你需要：

• 理解项目结构与编译流程；
• 学习使用ANTLR ParseTree (分析树)的编程接口；
• 学习使用访问者模式来构建AST；
• 结合源码深入理解ANTLR的分析原理。

Lab1-3 回答问题

阅读ANTLR生成的解析器源码和ANTLR运行时源码，并结合lab1-2中对ALL(*)的理解回答以下问题。答案记录在<your repo>/lab1-answer/lab1-3.md文件中。

• 了解并总结以下三个函数的作用、接口和主要处理流程；
  • enterRecursionRule
  • unrollRecursionContexts
  • adaptivePredict
• 描述ANTLR的错误处理机制；
• 对比分析SLL、LL、以及ALL(*)的异同，例如文法二义、试探回溯等。

Lab1-3 提交说明

你需要在 Lab1-2 的基础上修改并组织你本次实验的提交文件，目录结构如下。助教会借助脚本实现实验的半自动检查，请一定严格按照本节要求组织项目目录和文件，否则会影响本次实验成绩。

- <your repo>
  | lab1-answer
    | lab1-2.*
>>  | lab1-3.md          回答Lab1-3的问题
  | c1recognizer         复制自公共仓库的 c1recognizer 项目，请勿遗漏内容。
    | cmake/
    | grammar/           
    | include/c1recognizer/ 
>>  | src/                 修改完善recognizer.cpp和syntax_tree_builder.cpp
>>  | test/test_cases/   如果有更多的测试程序，可以在其中补充
>>  | doc/               描述实验中遇到的问题、分析和设计,增加lab1-3.md记录主要任务一节要求的内容
    | 其他已有的文件

ANTLR v4 的使用

ANTLR v4 是一个基于 LL(*) 分析方法 [PLDI 2011] 、Adaptive LL(*)分析[OOPSLA 2014]的自上而下分析的LL解析器的生成工具（Parser Generator）。它接收一个或多个.g4格式的文法描述文件作为输入，然后分析它们并为之生成一套解析器的源程序。生成的解析器依赖于 ANTLR v4 的运行时库，能够执行指定的文法分析过程，并可以通过 ANTLR v4 运行时提供的接口和数据格式来调用与访问。

ANTLR v4 所提倡的思想在于，使用文法描述文件描述语言本身，而不必描述具体实现细节。也就是说，文法描述文件应当只是对语言本身文法的一个规范描述，它不应包括其实现逻辑（虽然 ANTLR 具备在文法描述文件中附加程序代码的功能，但并不提倡使用该功能；这一功能是从 ANTLR v3 遗留下来的）；直到根据输入生成 parse tree 后，才通过用 ANTLR 工作语言编写的 Visitor 遍历parse tree 并生成抽象语法树 AST。**

文法描述文件的编写

在这里安利 Visual Studio Code的antlr4插件 ！这在一定程度上可以通过自动的检查来避免一些低级错误的产生。

g4格式文件的作用是描述语言的文法。其中能够定义终结符和非终结符，终结符代表词法记号，非终结符代表语法结构。

ANTLR v4 允许在单个文法描述文件中描述语言的词法和语法，但是本实验会将词法描述和语法描述分离成多个文件。分离的原因主要是为了便于分步进行课程实验、调试和提交，也有助于理解和评分。

在用于本课程实验的初始代码中，给出了全部需要完成的终结符和非终结符，但是只填入了能够完成简单的整数加、减、乘、除、取余表达式解析的文法描述。你需要在本实验中将它完善至能够解析完整的 C1 语言。

词法分析 Lexer

词法分析的文法文件（未完成,等待修改/增加内容）位于课程实验软件包的c1recognizer/grammar/C1Lexer.g4。它的初始内容如下：

lexer grammar C1Lexer;

tokens {
    Comma,
    SemiColon,
    Assign,
    LeftBracket,
    RightBracket,
    LeftBrace,
    RightBrace,
    LeftParen,
    RightParen,
    If,
    Else,
    While,
    Const,
    Equal,
    NonEqual,
    Less,
    Greater,
    LessEqual,
    GreaterEqual,
    Plus,
    Minus,
    Multiply,
    Divide,
    Modulo,

    Int,
    Float,
    Void,

    Identifier,
    IntConst,
    FloatConst
}

LeftParen: '(';
RightParen: ')';

Plus: '+' ;
Minus: '-' ;
Multiply: '*' ;
Divide: '/' ;
Modulo: '%' ;

WhiteSpace: [ \t\r\n]+ -> skip;

文法类型和分析器名

在 ANTLR v4 的文法文件格式中，首先应注明文法类型和分析器名：lexer grammar C1Lexer;表示该文法文件描述了一个词法分析器，其名称为 C1Lexer。

记号声明

tokens{...} 中声明所有token名，以逗号分隔。这里已经列出了你会用到的所有 token。需要注意的是：

• 在 ANTLR 语法文件中，token 名需以大写字母开头;
• 空白符等不包含在其中。

你可以看到，在文件最后一行出现的 WhiteSpace 并不在这里出现。这是因为它们所代表的文本将被忽略（通过命令 -> skip 来表达，后面会有详细解释），不会出现在词法分析器 C1Lexer 输出的 token 流（ANTLR v4 运行时库中的TokenStream）中。

文法规则——词法规则

接下来则是文法规则。在 lexer grammar 中，这里出现的规则必须是对词法单元的描述，即对 token 的定义。每条规则由大写字母开头的 token 名开始，后跟一个冒号，然后是对该 token 构成规则的描述。一个 token 可以由多种模式匹配到，各个模式之间以 | 分隔，规则以 ; 结束。

规则的表示

规则的表述与正则表达式大致相同。例如，你可以看到 'blabla' 表示相应的字面文本，[0-9] 表示相应的单字符可能值，+ 作为后缀修饰符表示一次或多次出现相应的文本；此外，还有 ? 作为后缀修饰符表示被修饰文本的可选出现，而 (somerule)* 等价于 ((somerule)+)?。这些都与正则表达式的表示相同。但是需要注意其中的区别也是存在的：在课程实验中主要涉及的区别在于，正则表达式中使用 [^a-z] 表示一个非小写字母的字符，而在 ANTLR 中使用记号 ~[a-z]，其中 ~ 为一个前缀修饰符，用于匹配一个不在此修饰符后描述的字符范围内的字符；这里的“范围”可能不仅由[] 内的规则指定，还可能是单字符的字面值，例如 ~'a'表示一个非a的字符。

本次实验中匹配注释是最困难的部分。你可能会用到一些后缀标识符，如*?，它代表 non-greedy many，也就是说，在此处匹配尽可能少的内容使得整条规则得以匹配。其它的简单后缀标识符，包括+和?，都有它们的 non-greedy 版本，即+?和??，它们的含义也类似。

命令

每一条规则结尾处可附加一条命令，跟随在 -> 之后。本次实验中仅会用到命令 skip，它表示此条规则匹配到的 token 会被忽略，不计入 TokenStream中。

其他

此外，ANTLR 允许在词法规则中附加操作代码，也允许词法规则中出现嵌套和递归，同时还有匹配模式(mode)的切换和模式栈机制的存在。如果你想了解更多关于 ANTLR Lexer 规则的信息，请参考 Lexer Rules。

语法分析 Parser

语法分析的语法文件（未完成）位于c1recognizer/src/grammar/C1Parser.g4。它的初始内容如下：

parser grammar C1Parser;
options { tokenVocab = C1Lexer; }

compilationUnit: ;
decl: ;
constdecl: ;
constdef: ;
vardecl: ;
vardef: ;
funcdef: ;
block: ;
stmt: ;
lval: ;
cond: ;
exp:
    (Plus | Minus) exp
    | exp (Multiply | Divide | Modulo) exp
    | exp (Plus | Minus) exp
    | LeftParen exp RightParen
    | number
;
number: ;

这里的语法文件类型为parser grammar，名称为C1Parser。options { tokenVocab = C1Lexer; }表示从C1Lexer引入 token 字典，这里不需要更改。

非终结符名称需要以小写字母开头；每条规则由非终结符名称开始，冒号后跟随多条可选规则，用|分隔。规则可以出现左递归，但出现左递归的标识符必须存在非左递归的匹配规则；各种后缀标识符（? * + ?? *? +?）含义与 Lexer 阶段相同，不再赘述。

出现左递归的情形下，运算符优先级按从上到下依次降低。默认的结合性为左结合，我们的 C1 语言中不涉及双目以上右结合的运算，因此你暂时无须理会结合性的问题。

如果你想了解更多关于 ANTLR Parser 规则的信息，请参考 Parser Rules。可以看到，我们的语法分析文件中没有任何代码段，这贯彻了 ANTLR v4 的设计思想。下一小节中会介绍如何使用分析结果。

对ANTLR生成的代码进行编程

在代码中使用 ANTLR 生成的程序是较为麻烦的一件事。但我们已经构建好了一套基于 CMake 的自动构建过程（后面 会进行介绍），并准备好了基本的程序，你只需要了解 Parse Tree 的结构，再基于 访问者模式 编写你希望对Parse Tree所做的处理等相关代码即可。

Parse Tree的结构

以 C1Parser.g4 生成的C1Parser.h为例，我们这里截取部分代码：

namespace c1_recognizer {


class  C1Parser : public antlr4::Parser {
public:
  enum {
    Comma = 1, SemiColon = 2, Assign = 3, LeftBracket = 4, RightBracket = 5, 
    LeftBrace = 6, RightBrace = 7, LeftParen = 8, RightParen = 9, If = 10, 
    Else = 11, While = 12, Const = 13, Equal = 14, NonEqual = 15, Less = 16, 
    Greater = 17, LessEqual = 18, GreaterEqual = 19, Plus = 20, Minus = 21, 
    Multiply = 22, Divide = 23, Modulo = 24, Int = 25, Float = 26, Void = 27, 
    Identifier = 28, FloatConst = 29, IntConst = 30, LineComment = 31, BlockComment = 32, 
    WhiteSpace = 33
  };

  enum {
    RuleCompilationUnit = 0, RuleDecl = 1, RuleConstdecl = 2, RuleConstdef = 3, 
    RuleVardecl = 4, RuleVardef = 5, RuleFuncdef = 6, RuleBlock = 7, RuleStmt = 8, 
    RuleLval = 9, RuleCond = 10, RuleExp = 11, RuleNumber = 12
  };

  C1Parser(antlr4::TokenStream *input);
  ~C1Parser();

  ...

  class ExpContext; 

  ...

  class  ExpContext : public antlr4::ParserRuleContext {
  public:
    ExpContext(antlr4::ParserRuleContext *parent, size_t invokingState);
    virtual size_t getRuleIndex() const override;
    std::vector<ExpContext *> exp();
    ExpContext* exp(size_t i);
    antlr4::tree::TerminalNode *Plus();
    antlr4::tree::TerminalNode *Minus();
    antlr4::tree::TerminalNode *LeftParen();
    antlr4::tree::TerminalNode *RightParen();
    LvalContext *lval();
    NumberContext *number();
    antlr4::tree::TerminalNode *Multiply();
    antlr4::tree::TerminalNode *Divide();
    antlr4::tree::TerminalNode *Modulo();

    virtual void enterRule(antlr4::tree::ParseTreeListener *listener) override;
    virtual void exitRule(antlr4::tree::ParseTreeListener *listener) override;

    virtual antlrcpp::Any accept(antlr4::tree::ParseTreeVisitor *visitor) override;

  };

  ExpContext* exp();
};

}  // namespace c1_recognizer

上述代码中，ExpContext是 Parse Tree 中代表exp非终结符的节点；其它命名中包含Context的类也是类似的。在ExpContext的成员中，std::vector<ExpContext *> exp();和ExpContext* exp(size_t i);返回的是该节点的子结构中代表exp非终结符的节点，前者返回全部，后者返回第i个。生成这些接口的原因在于，exp 的产生式规则中的右部(right hand side, RHS)可能存在多个exp非终结符，作为当前节点的子结构；如果最多只有一个exp子结构，生成的接口会形如ExpContext* exp();，返回唯一一个这样的孩子节点；如果不存在exp子结构，则会返回nullptr，即 C 语言中的NULL。

ExpContext中的其它诸如antlr4::tree::TerminalNode *Plus();的接口，返回的是相应名称的终结符节点，若不存在，返回的是nullptr。如果你需要从一个TerminalNode指针p获取其匹配的原文文本，你应使用p->getSymbol()->getText()。这在分析处理Identifier和Number时会有用。

ExpContext中的虚方法 void enterRule(antlr4::tree::ParseTreeListener *listener ) 和void exitRule(antlr4::tree::ParseTreeListener *listener ) 分别表示在进入和退出该 exp 语法结构时调用参数 listener 提供的实现来进行相应的处理；而虚方法 antlrcpp::Any accept(antlr4::tree::ParseTreeVisitor *visitor) 则表示调用参数 visitor 提供的实现来访问该 exp 结构。

Design Pattern

Design Pattern(设计模式) 是软件开发人员在软件开发过程中面临的一般问题的解决方案，是一套被反复使用、经过分类的、代码设计经验的总结。使用设计模式的目的是为了代码可重用性、让代码更容易被他人理解、保证代码可靠性。 介绍Design Pattern的著名书籍是 Design Patterns - Elements of Reusable Object-Oriented Software（中文译名：设计模式 - 可复用的面向对象软件元素，不过该书并不太容易理解）。你可以阅读网上的教程来理解，为开展本实验，你需要学习Factory Pattern以及下面的Visitor Pattern。

Visitor Pattern

Visitor Pattern(访问者模式)是为了解决稳定的数据结构和易变的操作耦合问题而产生的一种设计模式。解决方法就是在被访问的类里面加一个对外提供接待访问者的接口，其关键在于在数据基础类里面有一个方法接受访问者，将自身引用传入访问者。这里举一个应用实例来帮助理解访问者模式：您在朋友家做客，您是访问者；朋友接受您的访问，您通过朋友的描述，然后对朋友的描述做出一个判断，这就是访问者模式。

有关 Visitor Pattern 的含义、模式和特点可参见中文维基百科和英文维基百科，其中 C++ 的示例值得一看。Lab1软件包中定义的Syntax Tree的访问者类 syntax_tree_visitor 即以此示例为原型来构架。在Lab1-3中，你需要实现和使用访问者类 syntax_tree_builder，在 Parse Tree 上遍历，来构建Syntax Tree，即AST。

结合Lab1-3理解Visitor Pattern

下面以C1中exp（表达式）为例来解释 Visitor Pattern。在syntax_tree_builder.cpp中的visitExp( ) 给出了分析Parse Tree 中的表达式节点 C1Parser::ExpContext，构建对应的AST 的实现。下面代码给出了当表达式是 number 时，会调用 visit(number) 来分析 number 语法结构并为之构造 AST 节点。

// syntax_tree_builder.cpp
antlrcpp::Any syntax_tree_builder::visitExp(C1Parser::ExpContext *ctx)
{
  ...
    if (auto number = ctx->number())
        return visit(number); // <-这里
  ...
}

这里，类 syntax_tree_builder 是 ANTLR v4 根据 C1Parser.g4 自动生成的 C1ParserBaseVisitor 类的子类。 C1ParserBaseVisitor 是ANTLR v4 为类 C1ParserVisitor 提供的一个空的实现，用户可以从它派生自己的访问者类，来根据需要实现其中的部分或全部方法。C1Parser::ExpContext 的代码片段见上面。为便于查看，下面列出C1Parser::ExpContext中的部分代码：

  class  ExpContext : public antlr4::ParserRuleContext {
  public:
    ExpContext(antlr4::ParserRuleContext *parent, size_t invokingState);
    virtual size_t getRuleIndex() const override;
    std::vector<ExpContext *> exp();
    ExpContext* exp(size_t i);
  ...
    NumberContext *number();
  ...
    virtual void enterRule(antlr4::tree::ParseTreeListener *listener) override;
    virtual void exitRule(antlr4::tree::ParseTreeListener *listener) override;
    virtual antlrcpp::Any accept(antlr4::tree::ParseTreeVisitor *visitor) override;
  };

在ANTLR v4 生成的C1Parser.cpp 中有C1Parser::ExpContext 的enterRule()、exitRule()和accept()方法的如下实现：

// C1Parser.cpp
void C1Parser::ExpContext::enterRule(tree::ParseTreeListener *listener) {
  auto parserListener = dynamic_cast<C1ParserListener *>(listener);
  if (parserListener != nullptr)
    parserListener->enterExp(this);
}

void C1Parser::ExpContext::exitRule(tree::ParseTreeListener *listener) {
  auto parserListener = dynamic_cast<C1ParserListener *>(listener);
  if (parserListener != nullptr)
    parserListener->exitExp(this);
}

antlrcpp::Any C1Parser::ExpContext::accept(tree::ParseTreeVisitor *visitor) {
  if (auto parserVisitor = dynamic_cast<C1ParserVisitor*>(visitor))
    return parserVisitor->visitNumber(this); // <-这里
  else
    return visitor->visitChildren(this);
}

以accept( )的实现为例，其参数类型 tree::ParseTreeVisitor 的定义位于 ANTLR v4 为 C1Parser 分析器提供的运行时库代码中，一般位于build/externals/antlr4cpp/src/antlr4cpp/runtime/Cpp/目录下的ParseTreeVisitor.h中。 ANTLR v4 在上述目录下，还提供了AbstractParseTreeVisitor.h，为类ParseTreeVisitor提供了一个缺省的实现类 AbstractParseTreeVisitor。

从ExpContext::accept() 的实现中可以看到，它主要是根据exp的文法构成，调用访问者对象提供的visitXXX( ) 去访问其子结构 XXX 。而AbstractParseTreeVisitor 实现类中的 antlrcpp::Any visit(ParseTree *tree)（代码如下）又会调用 accept( ) 方法来应用访问者AbstractParseTreeVisitor 处理当前的ParseTree 结构。

// AbstractParseTreeVisitor.h
namespace antlr4 {
namespace tree {

  class ANTLR4CPP_PUBLIC AbstractParseTreeVisitor : public ParseTreeVisitor {
  public:
    virtual antlrcpp::Any visit(ParseTree *tree) override {
      return tree->accept(this); // <-这里
    }
  ...
  }

综上，node ->accept(visitor) 和 visitor->visitXXX(node) 表明了树和对树进行访问处理的访问者之间的关系, 其中node 是tree中的节点，XXX 是 node的子结构。利用这样的访问者模式，用户可以定义不同的tree结构，为tree中不同类别的node分别实现一个accept(visitor)方法；而对tree的访问处理，则可以根据不同需求定义不同的visitor类，在其中为类XXX的node实现相应的visitXXX(node)方法。

实验代码的编译和运行以及可视化

Lab1-1和Lab1-2的文法文件的测试以及可视化

ANTLR v4 具备独立测试语法文件、将分析图和分析结果可视化的功能。为可视化分析图，推荐使用 Visual Studio Code 作为编辑器，安装 ANTLR 插件。在一个.g4文件的编辑窗口中右键，你会看到几个选项，点击即可。

为测试语法文件并可视化分析结果，你首先需要按照 Environment 页面中的要求配置好 ANTLR v4 的工作环境。在此前提下，按如下步骤完成测试（在src/grammar目录中）：

# Compile grammar to Java source code
antlr4 *.g4
# Compile Java source code
javac *.java
# Testing lexer
grun C1Lexer tokens -tokens ../test/test_cases/simple.c1
# Testing lexer + parser, GUI version parse tree
grun C1 compilationUnit -gui ../test/test_cases/simple.c1
# Testing lexer + parser, console printed version parse tree
grun C1 compilationUnit -tree ../test/test_cases/simple.c1

这里simple.c1是预置的简易测试文件。由于我们最初提供的代码中仅包含了exp的分析，你需要将compilationUnit更换为exp，并用你自己建立的表达式输入样例取代../test/test_cases/simple.c1作为输入文件，才能正确查看结果。当然，这里的测试文件你可以任意选择，确认好文件位置就好。

grun 的命令中你也可以不指定输入文件，采用标准输入流作为输入文本。这时候你需要键入一个 EOF 标志来结束输入：在 Linux 等环境中是 Ctrl-D。

参考的输出如下:

>> grun C1Lexer tokens -tokens ../test/test_cases/simple.c1
[@0,0:2='int',<'int'>,1:0]
[@1,4:4='i',<Identifier>,1:4]
[@2,6:6='=',<'='>,1:6]
[@3,8:8='0',<IntConst>,1:8]
[@4,9:9=';',<';'>,1:9]
[@5,12:15='void',<'void'>,2:0]
[@6,17:20='main',<Identifier>,2:5]
[@7,21:21='(',<'('>,2:9]
[@8,22:22=')',<')'>,2:10]
[@9,25:25='{',<'{'>,3:0]
[@10,32:32='i',<Identifier>,4:4]
[@11,34:34='=',<'='>,4:6]
[@12,36:36='1',<IntConst>,4:8]
[@13,37:37=';',<';'>,4:9]
[@14,40:40='}',<'}'>,5:0]
[@15,43:42='<EOF>',<EOF>,6:0]
>> 
>> grun C1 compilationUnit -tree ../test/test_cases/simple.c1
(compilationUnit (decl (vardecl (btype int) (vardef i = (exp (number 0))) ;)) (funcdef void main ( ) (block { (stmt (lval i) = (exp (number 1)) ;) })) <EOF>)
>>

Lab1-3的编译和运行

如果你希望为编译过程指定 C++ 编译器，请修改环境变量 CXX 为你希望使用的编译器。CMake 会自动处理。

编译过程分两步：

1. 使用 CMake 创建 Makefile

   # 在c1recognizer目录下
   mkdir build
   cd build
   cmake -DCMAKE_BUILD_TYPE=Debug -DANTLR4CPP_JAR_LOCATION=<path-to-antlr>/antlr-4.7.1-complete.jar ..
   make
   cmake ..

我们用-DCMAKE_BUILD_TYPE=Debug得到debug版本,以方便你通过gdb等进行调试.

如此，你便在build目录下创建了用于编译实验代码的 Makefile。注意，请不要使用build以外的文件夹名，否则会污染 Git 仓库。

第一次make 操作会下载外部依赖并对其进行编译，时间会较长，请安心等待。这里不能并行编译，原因在于 CMake 对于外部库的依赖解析有一些问题。本次make操作必定会失败，这是由于 antlr4cpp 的 CMake 脚本的实现方式错误导致的。这里采取的workaround是make操作完成后重新运行 CMake，即可生成正确的 Makefile。

1. 进行编译

   make -j
   

   编译后，build目录下会出现可执行程序c1r_test。这一程序的功能是根据命令行参数中的文件名，读取其内容作为源代码输入，经过你的 C1Lexer、C1Parser、syntax_tree_builder，在标准输出中以 JSON 格式序列化输出 AST。它已经基本实现好了对表达式结构的解析，你可以在build目录下使用如下指令进行测试。

   ./c1r_test ../test/test_cases/exp_example.c1
   

上述build目录主要用于存放编译过程中的中间文件，整个build目录都是不需要提交远程仓库的，所以请各位同学一定要执行以下命令将build目录加入git追踪的忽略列表中，避免提交无用文件。

cd /path/to/your/repo; echo "build/*" >> .gitignore

关于构建系统的解释

本次实验的代码采用了 CMake 作为构建系统，项目的编译行为在 CMakeLists.txt 中指定。该文件引用ExternalAntlr4Cpp.cmake将 ANTLR 的语法文件的代码生成集成进构建过程中；另外还使用ExternalProject_Add宏引用rapidjson库完成c1r_test中AST 的序列化输出。

然后，CMakeLists.txt添加了两个编译目标c1recognizer库和c1r_test可执行程序项目，并配置了安装步骤。安装步骤的存在是为了支持下一阶段的实验；我们将可以直接引用安装好的c1recognizer，这也是 CMake 推荐的项目依赖方式。

对于cmake,可以参考官方教程和CMake入门实战进行进一步的了解.