实验二语法分析

语法分析

实验二将要求大家实现一个语法分析器 (parser)，提取出一个程序的语义。回忆理论课的所学的上下文无关文法（CFG），是一种能力强大的描述语言的数学模型，能够描述具有递归结构特征的语言，很多编程语言可以用上下文无关文法准确描述或定义。计算机科学中使用 EBNF (Extended Backus–Naur form) 来描述上下文无关文法，本编译原理实验教学要求实现的 SYsU 语言文法（ SysY 语言的变种）使用 EBNF 表示，其中：

符号 [...] 表示方括号内包含的为可选项
符号 {...} 表示花括号内包含的为可重复 0 此或多次的项
双引号括起的，表示的是原字符

SYsU 语言文法

SYsU 语言的文法表示如下，其中 CompUnit 为开始符号：

CompUnit      ::= [CompUnit] (Decl | FuncDef);

Decl          ::= ConstDecl | VarDecl;
ConstDecl     ::= "const" BType ConstDef {"," ConstDef} ";";
BType         ::= "int" | "char" | "long long";
ConstDef      ::= IDENT {"[" ConstExp "]"} "=" ConstInitVal;
ConstInitVal  ::= ConstExp | "{" [ConstInitVal {"," ConstInitVal}] "}";
VarDecl       ::= BType VarDef {"," VarDef} ";";
VarDef        ::= IDENT {"[" ConstExp "]"}
                | IDENT {"[" ConstExp "]"} "=" InitVal;
InitVal       ::= Exp | "{" [InitVal {"," InitVal}] "}";

FuncDef       ::= FuncType IDENT "(" [FuncFParams] ")" Block;
FuncType      ::= "void" | "int";
FuncFParams   ::= FuncFParam {"," FuncFParam};
FuncFParam    ::= BType IDENT ["[" "]" {"[" ConstExp "]"}];

Block         ::= "{" {BlockItem} "}";
BlockItem     ::= Decl | Stmt;
Stmt          ::= LVal "=" Exp ";"
                | [Exp] ";"
                | Block
                | "if" "(" Exp ")" Stmt ["else" Stmt]
                | "while" "(" Exp ")" Stmt
                | "break" ";"
                | "continue" ";"
                | "return" [Exp] ";";
                | "do" "{" Stmt "}" "while" "(" Stmt ")" ";"

Exp           ::= LOrExp;
LVal          ::= IDENT {"[" Exp "]"};
PrimaryExp    ::= "(" Exp ")" | LVal | Number;
Number        ::= INT_CONST;
UnaryExp      ::= PrimaryExp | IDENT "(" [FuncRParams] ")" | UnaryOp UnaryExp;
UnaryOp       ::= "+" | "-" | "!";
FuncRParams   ::= Exp {"," Exp};
MulExp        ::= UnaryExp | MulExp ("*" | "/" | "%") UnaryExp;
AddExp        ::= MulExp | AddExp ("+" | "-") MulExp;
RelExp        ::= AddExp | RelExp ("<" | ">" | "<=" | ">=") AddExp;
EqExp         ::= RelExp | EqExp ("==" | "!=") RelExp;
LAndExp       ::= EqExp | LAndExp "&&" EqExp;
LOrExp        ::= LAndExp | LOrExp "||" LAndExp;
ConstExp      ::= Exp;

其中, 各符号的含义如下:

符号	含义	符号	含义
CompUnit	编译单元	Decl	声明
ConstDecl	常量声明	BType	基本类型
ConstDef	常数定义	ConstInitVal	常量初值
VarDecl	变量声明	VarDef	变量定义
InitVal	变量初值	FuncDef	函数定义
FuncType	函数类型	FuncFParams	函数形参表
FuncFParam	函数形参	Block	语句块
BlockItem	语句块项	Stmt	语句
Exp	表达式	LVal	左值表达式
PrimaryExp	基本表达式	Number	数值
UnaryExp	一元表达式	UnaryOp	单目运算符
FuncRParams	函数实参表	MulExp	乘除模表达式
AddExp	加减表达式	RelExp	关系表达式
EqExp	相等性表达式	LAndExp	逻辑与表达式
LOrExp	逻辑或表达式	ConstExp	常量表达式

需要注意的是:

Exp: SYsU 中表达式的类型均为 int 、long long 、char 、float型. 当 Exp 出现在表示条件判断的位置时 (例如 if 和 while), 表达式值为 0 时为假, 非 0 时为真.
~~ConstExp: 其中使用的 IDENT 必须是常量.~~

Clang 的语法分析

以下面这段 C 代码 tmp.sysu.c 为例：

$ cat tmp.sysu.c
int a;
int main() { 
    return 0; 
}

在命令行下输入：

( 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 tmp.sysu.c |
  clang -cc1 -ast-dump=json )

将输出：

{
  "id": "0x1095388",
  "kind": "TranslationUnitDecl",
  "loc": {},
  "range": {
    "begin": {},
    "end": {}
  },
  "inner": [
    {"commet": "原先第十行到第一百五十三行为内置类型，此处省略"},
    {
      "id": "0x10fadd0",
      "kind": "VarDecl",
      "loc": {
        "offset": 141,
        "file": "<stdin>",
        "line": 8,
        "presumedFile": "tmp.sysu.c",
        "presumedLine": 1,
        "col": 5,
        "tokLen": 1
      },
      "range": {
        "begin": {
          "offset": 137,
          "col": 1,
          "tokLen": 3
        },
        "end": {
          "offset": 141,
          "col": 5,
          "tokLen": 1
        }
      },
      "name": "a",
      "mangledName": "a",
      "type": {
        "qualType": "int"
      }
    },
    {
      "id": "0x10faed0",
      "kind": "FunctionDecl",
      "loc": {
        "offset": 148,
        "line": 9,
        "presumedLine": 2,
        "col": 5,
        "tokLen": 4
      },
      "range": {
        "begin": {
          "offset": 144,
          "col": 1,
          "tokLen": 3
        },
        "end": {
          "offset": 171,
          "line": 11,
          "presumedLine": 4,
          "col": 1,
          "tokLen": 1
        }
      },
      "name": "main",
      "mangledName": "main",
      "type": {
        "qualType": "int ()"
      },
      "inner": [
        {
          "id": "0x10fafa0",
          "kind": "CompoundStmt",
          "range": {
            "begin": {
              "offset": 155,
              "line": 9,
              "presumedLine": 2,
              "col": 12,
              "tokLen": 1
            },
            "end": {
              "offset": 171,
              "line": 11,
              "presumedLine": 4,
              "col": 1,
              "tokLen": 1
            }
          },
          "inner": [
            {
              "id": "0x10faf90",
              "kind": "ReturnStmt",
              "range": {
                "begin": {
                  "offset": 161,
                  "line": 10,
                  "presumedLine": 3,
                  "col": 5,
                  "tokLen": 6
                },
                "end": {
                  "offset": 168,
                  "col": 12,
                  "tokLen": 1
                }
              },
              "inner": [
                {
                  "id": "0x10faf70",
                  "kind": "IntegerLiteral",
                  "range": {
                    "begin": {
                      "offset": 168,
                      "col": 12,
                      "tokLen": 1
                    },
                    "end": {
                      "offset": 168,
                      "col": 12,
                      "tokLen": 1
                    }
                  },
                  "type": {
                    "qualType": "int"
                  },
                  "valueCategory": "prvalue",
                  "value": "0"
                }
              ]
            }
          ]
        }
      ]
    }
  ]

可以发现，clang -cc1 -ast-dump=json 输出一个 Json 格式的抽象语法树 (AST)，考虑到 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 tmp.sysu.c |   clang -cc1 -ast-dump)

输出：

TranslationUnitDecl 0x899358 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 原先的第 2 行到第 15 行为内置内容，忽略
|-VarDecl 0x8feda0 <tmp.sysu.c:1:1, col:5> col:5 a 'int'
`-FunctionDecl 0x8feea0 <line:2:1, line:4:1> line:2:5 main 'int ()'
  `-CompoundStmt 0x8fef70 <col:12, line:4:1>
    `-ReturnStmt 0x8fef60 <line:3:5, col:12>
      `-IntegerLiteral 0x8fef40 <col:12> 'int' 0

将上面信息对应的语法树画出来：

flowchart TD;
0x899358 --> 0x8feda0
0x899358 --> 0x8feea0
0x8feea0 --> 0x8fef70
0x8fef70 --> 0x8fef60
0x8fef60 --> 0x8fef40

0x899358["
	TranslationUnitDecl
"]
0x8feda0["
	VarDecl
	a 'int'
"]
0x8feea0["
	FunctionDecl
	main 'int ()'
"]
0x8fef70["
	CompoundStmt
"]
0x8fef60["
	ReturnStmt
"]
0x8fef40["
	IntegerLiteral
	'int' 0
"]

容易看出，lexer 实验输出的 token 构成了这棵树的叶节点。根据相应的语法规则，从叶节点出发，逐步向上构造，直至根节点 TranslationUnitDecl 的出现，一棵语法分析树望眼欲穿。

另外，实验中生成的 json 格式文件，也可以在这里转换成更易读的 yaml 格式。

实验要求

在本语法分析实验中，你被希望完成一个语法分析器 sysu-parser，接受来自 sysu-lexer 的输入，产生与 clang -cc1 -ast-dump=json 相当的输出。预期的代码行数为 1000 行，预期的完成时间为 24 小时～ 72 小时。

parser/parser.y下提供了一个基于 bison + llvm::json 实现的模板，接受词法分析器的输出，你可以基于此继续实现完整的逻辑，也可以使用其他的工具实现，如 antlr4，但不得使用其提供的 C 语言模板；也不得使用任何封装好的库直接获得 ast，如 libclang。

* 基于 Bison + `llvm::json` 实现

Bison 介绍

Bison是一个通用语法分析器生成器，它使用 LALR(1)、IELR(2) 或规范LR(1) 语法表，将带注释的上下文无关文法（CFG) 转换为确定性 LR 或广义LR（GLR）语法分析器。总之，是一个能够帮助我们生成语法分析器的工具。

Bison 的使用

基本用法是：

编写一个 xxx.y 文件
通过 Bison 将 xxx.y 文件转换成 C 代码源文件
然后编译 C 代码源文件生成可执行程序，即得到语法分析器

如何编写 .y 文件

以parser/parser.y 为例，它提供了一个基于 Bison + llvm::json 实现的模板，它的部分代码如下：

%{
#include "parser.hh"
#include <llvm/Support/JSON.h>
#include <llvm/Support/MemoryBuffer.h>
#include <llvm/Support/raw_ostream.h>
#define yyerror(x)                                                             \
  do {                                                                         \
    llvm::errs() << (x);                                                       \
  } while (0)
...
auto yylex() {
...
  return YYEOF;
}
int main() {
  yyparse();
  llvm::outs() << stak.back() << "\n";
} 
%}

%token T_NUMERIC_CONSTANT
%token T_IDENTIFIER
%token T_INT
%token T_RETURN
%token T_SEMI
%token T_L_PAREN
%token T_R_PAREN
%token T_L_BRACE
%token T_R_BRACE
%start CompUnit
    
%%
CompUnit: CompUnit CompUnitItem {
  auto inner = stak.back();
  stak.pop_back();
  stak.back().getAsObject()->get("inner")->getAsArray()->push_back(inner);
}
...
Stmt: T_RETURN T_NUMERIC_CONSTANT T_SEMI {
  auto inner = stak.back();
  stak.back() = llvm::json::Object{{"kind", "ReturnStmt"},
                                   {"inner", llvm::json::Array{inner}}};
}
%%

程序由 4 段组成，和 flex 类似，分别是：

%{
P1: Prologue，序言段：函数和变量的宏定义和声明。
%}

P2: Bison declarations，Bison 声明段：终结符号和非终结符号、指定优先级等的声明。

%%
P3：Grammar rules，语法规则段：定义规则以及规则对应的后续动作
%%

P4: Epilogue，尾段：该部分的代码将被原样复制到 bison 生成的文件末尾

其中，语法规则段（Grammar rules section）由语法规则 (rule) 和动作(action，包括 C 代码)组成。语法规则基本就是 BNF，规则中目标或非终结符放在左边，后跟一个冒号，然后是产生式的右边，之后的 { } 内为该语法规则对应的动作，例如 parser/parser.y 的 101-105 行：

Stmt: T_RETURN T_NUMERIC_CONSTANT T_SEMI {
  auto inner = stak.back();
  stak.back() = llvm::json::Object{{"kind", "ReturnStmt"},
                                   {"inner", llvm::json::Array{inner}}};
}

Stmt 是非终结符号，T_RETURN T_NUMERIC_CONSTANT T_SEMI 为产生式的右边，简单实现了此条 EBNF 文法： Stmt ::= "return" Exp ";" 。后面的 {} 内为此条规则对应的动作代码，含义为：创建了一个 ReturnStmt 的 json 节点，并加入到 stak 栈里。

Bison 更加详细的学习参考 GNU Bison - The Yacc-compatible Parser Generator ，其中 https://www.gnu.org/software/bison/manual/bison.html#RPN-Calc 提供了一个用 Bison 实现计算器的例子。

模板生成 `sysu-parser`

只修改 parser.y 情况下，不需要修改 parser/CMakeLists.txt 。

下面演示目前模板生成的 sysu-parser，在命令行下输入

# 进入到 SYsU-lang 目录，路径可能需要根据自己的实际情况调整
cd SYsU-lang

# 编译安装
# `${CMAKE_C_COMPILER}` 仅用于编译 `.sysu.c`
# 非 SYsU 语言的代码都将直接/间接使用 `${CMAKE_CXX_COMPILER}` 编译（后缀为 `.cc`）
rm -rf ~/sysu
cmake -G Ninja \
  -DCMAKE_C_COMPILER=clang \
  -DCMAKE_CXX_COMPILER=clang++ \
  -DCMAKE_INSTALL_PREFIX=~/sysu \
  -DCMAKE_MODULE_PATH=$(llvm-config --cmakedir) \
  -DCPACK_SOURCE_IGNORE_FILES=".git/;tester/third_party/" \
  -B ~/sysu/build
cmake --build ~/sysu/build
cmake --build ~/sysu/build -t install

然后进入 ~/sysu/bin 目录：

$ cd ~/sysu/bin && ls
sysu-compiler  sysu-generator  sysu-lexer  sysu-linker  sysu-optimizer  sysu-parser  sysu-preprocessor  sysu-translator

sysu-parser 即为模板生成的语法分析器，它具备初步的语法分析功能，但是功能不完整，需要自行补全。

一个例子演示如何使用 sysu-parser:

# 进入到 SYsU-lang 目录，路径可能需要根据自己的实际情况调整
$ cd SYsU-lang

# 目前仅支持从标准输入读入，使用了 '|' 管道，parser 接收来自 lexer 的输入
$ ~/sysu/bin/sysu-preprocessor tmp.sysu.c | ~/sysu/bin/sysu-lexer | ~/sysu/bin/sysu-parser 
{"inner":[{"kind":"VarDecl","name":"a"},{"inner":[{"inner":[{"inner":[{"kind":"IntegerLiteral","value":"0"}],"kind":"ReturnStmt"}],"kind":"CompoundStmt"}],"kind":"FunctionDecl","name":"main"}],"kind":"TranslationUnitDecl"}

可以看到模板的 sysu-parser 产生了和 Clang 一致的语法分析结果。

你可以修改 parser/parser.y 来完善语法分析器的功能。

Hints

1. 循序渐进文法分析

考虑到 SYsU 文法的复杂，建议不是必须按下面文法顺序循序渐进实现语法分析：

一元表达式

Stmt        ::= "return" Exp ";";

Exp         ::= UnaryExp;
PrimaryExp  ::= "(" Exp ")" | Number;
Number      ::= INT_CONST;
UnaryExp    ::= PrimaryExp | UnaryOp UnaryExp;
UnaryOp     ::= "+" | "-" | "!";

算术表达式

Exp         ::= AddExp;
MulExp      ::= UnaryExp | MulExp ("*" | "/" | "%") UnaryExp;
AddExp      ::= MulExp | AddExp ("+" | "-") MulExp;

逻辑表达式

Exp         ::= LOrExp;
RelExp      ::= AddExp | RelExp ("<" | ">" | "<=" | ">=") AddExp;
EqExp       ::= RelExp | EqExp ("==" | "!=") RelExp;
LAndExp     ::= EqExp | LAndExp "&&" EqExp;
LOrExp      ::= LAndExp | LOrExp "||" LAndExp;

常量

Decl          ::= ConstDecl;
ConstDecl     ::= "const" BType ConstDef {"," ConstDef} ";";
BType         ::= "int" | "char" | "long long";
ConstDef      ::= IDENT "=" ConstInitVal;
ConstInitVal  ::= ConstExp;

Block         ::= "{" {BlockItem} "}";
BlockItem     ::= Decl | Stmt;

LVal          ::= IDENT;
PrimaryExp    ::= "(" Exp ")" | LVal | Number;

ConstExp      ::= Exp;

变量和赋值

Decl          ::= ConstDecl | VarDecl;
ConstDecl     ::= ...;
BType         ::= ...;
ConstDef      ::= ...;
ConstInitVal  ::= ...;
VarDecl       ::= BType VarDef {"," VarDef} ";";
VarDef        ::= IDENT | IDENT "=" InitVal;
InitVal       ::= Exp;

...

Block         ::= ...;
BlockItem     ::= ...;
Stmt          ::= LVal "=" Exp ";"
                | "return" Exp ";";

语句块和作用域

Stmt ::= LVal "=" Exp ";"
       | [Exp] ";"
       | Block
       | "return" [Exp] ";";

if 语句

Stmt ::= ...
       | ...
       | ...
       | "if" "(" Exp ")" Stmt ["else" Stmt]
       | ...;

while 语句

Stmt ::= ...
       | ...
       | "while" "(" Exp ")" Stmt
       | "do" "{" Stmt "}" "while" "(" Stmt ")" ";"
       | "break" ";"
       | "continue" ";"
       ...;

函数和全局变量

CompUnit    ::= [CompUnit] FuncDef;

FuncDef     ::= FuncType IDENT "(" [FuncFParams] ")" Block;
FuncType    ::= "void" | "int";
FuncFParams ::= FuncFParam {"," FuncFParam};
FuncFParam  ::= BType IDENT;

UnaryExp    ::= ...
              | IDENT "(" [FuncRParams] ")"
              | ...;
FuncRParams ::= Exp {"," Exp};

数组

ConstDef      ::= IDENT {"[" ConstExp "]"} "=" ConstInitVal;
ConstInitVal  ::= ConstExp | "{" [ConstInitVal {"," ConstInitVal}] "}";
VarDef        ::= IDENT {"[" ConstExp "]"}
                | IDENT {"[" ConstExp "]"} "=" InitVal;
InitVal       ::= Exp | "{" [InitVal {"," InitVal}] "}";

LVal          ::= IDENT {"[" Exp "]"};
FuncFParam ::= BType IDENT ["[" "]" {"[" ConstExp "]"}];

2. Clang AST

Clang 的 AST 结点包含的东西较多，但实验中只需要关注特定结点信息。

以过 parser-1 测试为例，只需要关注 "kind"、"name"、"value" 、"inner" 这些键值。

"kind": 指明一个结点是什么类型，比如 "kind" : "ReturnStmt" 表明这是一个 return xxxx 的结点
"name": 指明一个结点的名字是什么，一般是函数的名字、变量的名字
"innner": 包含所有的子节点信息，默认是数组
"value": 指明结点的值，一般是常量的值

...

你可能会感兴趣的

GNU Bison - The Yacc-compatible Parser Generator
FindBISON — CMake 3.18.6 Documentation
JSON 在线可视化
Introduction to the Clang AST
llvm::json
- 该文件同样位于 debian:11 中 llvm-dev 包的 </usr/include/llvm/Support/JSON.h>。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

实验二语法分析

语法分析

SYsU 语言文法

Clang 的语法分析

实验要求

* 基于 Bison + `llvm::json` 实现

Bison 介绍

Bison 的使用

如何编写 .y 文件

模板生成 `sysu-parser`

Hints

1. 循序渐进文法分析

一元表达式

算术表达式

逻辑表达式

常量

变量和赋值

语句块和作用域

if 语句

while 语句

函数和全局变量

数组

2. Clang AST

你可能会感兴趣的

Clone this wiki locally

实验二语法分析

语法分析

SYsU 语言文法

Clang 的语法分析

实验要求

* 基于 Bison + llvm::json 实现

Bison 介绍

Bison 的使用

如何编写 .y 文件

模板生成 sysu-parser

Hints

1. 循序渐进文法分析

一元表达式

算术表达式

逻辑表达式

常量

变量和赋值

语句块和作用域

if 语句

while 语句

函数和全局变量

数组

2. Clang AST

你可能会感兴趣的

Clone this wiki locally

* 基于 Bison + `llvm::json` 实现

模板生成 `sysu-parser`