在本次语法分析实验中，你被希望完成一个文法分析器，产生类似于 clang -cc1 -dump-tokens 2>&1、clang -cc1 -ast-dump=json 的输出。预期的代码行数为 1000 行，预期的完成时间为 24 小时 ～ 72 小时。
注意，以下 log 省略了无关内容。
$ ( export PATH=$HOME/sysu/bin:$PATH \
CPATH=$HOME/sysu/include:$CPATH \
LIBRARY_PATH=$HOME/sysu/lib:$LIBRARY_PATH \
LD_LIBRARY_PATH=$HOME/sysu/lib:$LD_LIBRARY_PATH &&
clang -E tester/functional/000_main.sysu.c |
clang -cc1 -dump-tokens 2>&1 )
int 'int' [StartOfLine] Loc=<tester/functional/000_main.sysu.c:1:1>
identifier 'main' [LeadingSpace] Loc=<tester/functional/000_main.sysu.c:1:5>
l_paren '(' Loc=<tester/functional/000_main.sysu.c:1:9>
r_paren ')' Loc=<tester/functional/000_main.sysu.c:1:10>
l_brace '{' Loc=<tester/functional/000_main.sysu.c:1:11>
return 'return' [StartOfLine] [LeadingSpace] Loc=<tester/functional/000_main.sysu.c:2:5>
numeric_constant '3' [LeadingSpace] Loc=<tester/functional/000_main.sysu.c:2:12>
semi ';' Loc=<tester/functional/000_main.sysu.c:2:13>
r_brace '}' [StartOfLine] Loc=<tester/functional/000_main.sysu.c:3:1>
eof '' Loc=<tester/functional/000_main.sysu.c:3:2>
$ ( export PATH=$HOME/sysu/bin:$PATH \
CPATH=$HOME/sysu/include:$CPATH \
LIBRARY_PATH=$HOME/sysu/lib:$LIBRARY_PATH \
LD_LIBRARY_PATH=$HOME/sysu/lib:$LD_LIBRARY_PATH &&
clang -E tester/functional/000_main.sysu.c |
clang -cc1 -ast-dump=json )
{
"id": "0x1c9b558",
"kind": "TranslationUnitDecl",
"loc": {},
"range": {
"begin": {},
"end": {}
},
"inner": [
{ "commet": "原先第十行到第一百五十三行为内置类型，此处省略" },
{
"id": "0x1cdad18",
"kind": "FunctionDecl",
"loc": {
"offset": 135,
"file": "<stdin>",
"line": 8,
"presumedLine": 1,
"col": 5,
"tokLen": 4
},
"range": {
"begin": {
"offset": 131,
"col": 1,
"tokLen": 3
},
"end": {
"offset": 157,
"line": 10,
"presumedLine": 3,
"col": 1,
"tokLen": 1
}
},
"name": "main",
"mangledName": "main",
"type": {
"qualType": "int ()"
},
"inner": [
{
"id": "0x1cdae30",
"kind": "CompoundStmt",
"range": {
"begin": {
"offset": 141,
"line": 8,
"presumedLine": 1,
"col": 11,
"tokLen": 1
},
"end": {
"offset": 157,
"line": 10,
"presumedLine": 3,
"col": 1,
"tokLen": 1
}
},
"inner": [
{
"id": "0x1cdae20",
"kind": "ReturnStmt",
"range": {
"begin": {
"offset": 147,
"line": 9,
"presumedLine": 2,
"col": 5,
"tokLen": 6
},
"end": {
"offset": 154,
"col": 12,
"tokLen": 1
}
},
"inner": [
{
"id": "0x1cdae00",
"kind": "IntegerLiteral",
"range": {
"begin": {
"offset": 154,
"col": 12,
"tokLen": 1
},
"end": {
"offset": 154,
"col": 12,
"tokLen": 1
}
},
"type": {
"qualType": "int"
},
"valueCategory": "rvalue",
"value": "3"
}
]
}
]
}
]
}
]
}
可以发现，clang -cc1 -ast-dump=json 输出一个 json 格式的语法分析树。我们要求你的输出不包含图上忽略的内置类型，也不需要为每个节点生成单独的 id。
本目录下提供了一个基于 antlr4 + llvm::json 实现的模板，接受词法分析器的输出，你可以基于此继续实现完整的逻辑，也可以使用其他的工具实现，如 bison，但不得使用任何封装好的库直接获得 ast，如 libclang。C.g4 语法文件来自于 antlr/grammars-v4 社区（感谢！），如有需要可自行修改。
考虑到 json 格式不方便肉眼调试，你可以像这样，输出更加符合人眼阅读方式的语法树，辅助调试。
$ ( export PATH=$HOME/sysu/bin:$PATH \
CPATH=$HOME/sysu/include:$CPATH \
LIBRARY_PATH=$HOME/sysu/lib:$LIBRARY_PATH \
LD_LIBRARY_PATH=$HOME/sysu/lib:$LD_LIBRARY_PATH &&
clang -E tester/functional/027_if2.sysu.c |
clang -cc1 -ast-dump )
TranslationUnitDecl 0x23d4568 <<invalid sloc>> <invalid sloc>
|-TypedefDecl # 原先第二行到第十五行为内置类型，此处省略
|-VarDecl 0x2413d00 <tester/functional/027_if2.sysu.c:1:1, col:5> col:5 used a 'int'
`-FunctionDecl 0x2413e08 <line:2:1, line:10:1> line:2:5 main 'int ()'
`-CompoundStmt 0x2414038 <col:11, line:10:1>
|-BinaryOperator 0x2413ee8 <line:3:2, col:6> 'int' '='
| |-DeclRefExpr 0x2413ea8 <col:2> 'int' lvalue Var 0x2413d00 'a' 'int'
| `-IntegerLiteral 0x2413ec8 <col:6> 'int' 10
`-IfStmt 0x2414010 <line:4:2, line:9:2> has_else
|-BinaryOperator 0x2413f60 <line:4:6, col:8> 'int' '>'
| |-ImplicitCastExpr 0x2413f48 <col:6> 'int' <LValueToRValue>
| | `-DeclRefExpr 0x2413f08 <col:6> 'int' lvalue Var 0x2413d00 'a' 'int'
| `-IntegerLiteral 0x2413f28 <col:8> 'int' 0
|-CompoundStmt 0x2413fb0 <col:11, line:6:2>
| `-ReturnStmt 0x2413fa0 <line:5:3, col:10>
| `-IntegerLiteral 0x2413f80 <col:10> 'int' 1
`-CompoundStmt 0x2413ff8 <line:7:6, line:9:2>
`-ReturnStmt 0x2413fe8 <line:8:3, col:10>
`-IntegerLiteral 0x2413fc8 <col:10> 'int' 0
将上图对应的树画出来，可得到下图（源码参见这里）。
flowchart TD;
0x23d4568-->0x2413d00
0x23d4568-->0x2413e08
0x2413e08-->0x2414038
0x2414038-->0x2413ee8
0x2414038-->0x2414010
0x2413ee8-->0x2413ea8
0x2413ee8-->0x2413ec8
0x2414010-->0x2413f60
0x2414010-->0x2413fb0
0x2414010-->0x2413ff8
0x2413f60-->0x2413f48
0x2413f60-->0x2413f28
0x2413f48-->0x2413f08
0x2413fb0-->0x2413fa0
0x2413fa0-->0x2413f80
0x2413ff8-->0x2413fe8
0x2413fe8-->0x2413fc8
0x23d4568["
TranslationUnitDecl
"]
0x2413d00["
VarDecl
used a 'int'
"]
0x2413e08["
FunctionDecl
main 'int ()'
"]
0x2414038["
CompoundStmt
"]
0x2413ee8["
BinaryOperator
'int' '='
"]
0x2413ea8["
DeclRefExpr
'int' lvalue
"]
0x2413ec8["
IntegerLiteral
'int' 10
"]
0x2414010["
IfStmt
has_else
"]
0x2413f60["
BinaryOperator
'int' '>'
"]
0x2413f48["
ImplicitCastExpr
'int' <LValueToRValue>
"]
0x2413f08["
DeclRefExpr
'int' lvalue
"]
0x2413f28["
IntegerLiteral
'int' 0
"]
0x2413fb0["
CompoundStmt
"]
0x2413fa0["
ReturnStmt
"]
0x2413f80["
IntegerLiteral
'int' 1
"]
0x2413ff8["
CompoundStmt
"]
0x2413fe8["
ReturnStmt
"]
0x2413fc8["
IntegerLiteral
'int' 0
"]
容易看出，lexer 实验输出的 token 构成了这棵树的叶节点。我们要做的就是，根据叶节点，写出语法规则，逐步自底向上地构造出根节点 TranslationUnitDecl 所在的完整子树。
另外，实验中生成的 json 格式文件，也可以在这里转换成更易读的 yaml 格式。
llvm::json？llvm::json，可以让同学们提前上手 LLVM 库的使用，平滑下一个实验的难度。TL;DR: Vistor 更符合任务需求，但是 Listener 仍然更加趁手。
Visitor 有更强的可定制性，但是需要自行实现每个节点到子节点的访问规则；Listener 则适合更轻量的任务，例如只提取某些语法规则的上下文。在本实验中，按道理每个节点都需要被访问，因此 Vistor 更符合任务需求，Listener 的优势没有那么大。然而，根据助教的使用经验，Listener 仍然是一个更常用且好用的选择。
本实验的评分分为两部分：基础部分和挑战部分。
如有疑问，参照 clang -cc1 -dump-tokens 2>&1、clang -cc1 -ast-dump=json。你需要提交一份实验报告，简要记录你的实验过程、遇到的难点以及解决的方法，并在报告中附上自动评测的结果。
本次实验的评测项目为 grammar-[0-7]。grammar-0，grammar-4 仅用于证明模板（代码与评测脚本）可以正确工作，不计入成绩；其他三个评测项依次检查：
sysu-grammar 是否提取出正确的 token。sysu-grammar 是否提取出正确的 token location。sysu-grammar 是否识别其他无关字符。sysu-grammar 是否提取出正确的 "kind"、"name"、"value" 键值，不含 "InitListExpr"。sysu-grammar 是否提取出正确的 "type" 键值及是否构造正确的 "InitListExpr" 生成树。sysu-grammar 是否提取出其它非 "id" 以外的键值。评测脚本忽略空白符，可以查看评测脚本以了解检查算法，但不得修改评测逻辑而投机取巧。你也可以像这样调用评测脚本，单独执行其中某一个评测项。
( export PATH=$HOME/sysu/bin:$PATH \
CPATH=$HOME/sysu/include:$CPATH \
LIBRARY_PATH=$HOME/sysu/lib:$LIBRARY_PATH \
LD_LIBRARY_PATH=$HOME/sysu/lib:$LD_LIBRARY_PATH &&
sysu-compiler --unittest=grammar-1 "**/*.sysu.c" )
此外，107_long_code2.sysu.c 这个算例在测试时直接使用 clang 导出的语法树大小为 8.9G，助教这里直接给出了压缩后的语法树。由于该算例语法树层级过多，评测时允许超时跳过。但你被鼓励去解决这一问题。
根据同学们的反馈下调了实验难度，只需通过 grammar-[0-5] 即可通过本次实验，grammar-6、grammar-7 列为本次实验的挑战选项。
本节给出一些挑战方向供参考。
sysu-tidy，如
const int 作为数组大小（符合 SysY 语法和 CPP 语法但不符合 C 语法！）-Wdangling-else）-Wunused-value）-Wempty-body）-Wtautological-compare）sysu-format：面向 SYsU 的代码格式化工具sysu-refactor：面向 SYsU 的代码重构工具
while (Cond) Simt 替换为 if (Cond) do Simt while (Cond)antlr4-runtime/antlr4-runtime.h