# Compiler24

**Repository Path**: li-zhengyang2023/compiler24

## Basic Information

- **Project Name**: Compiler24
- **Description**: compiler 2024 SysY
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-12-07
- **Last Updated**: 2024-12-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 编译器架构

## 词法分析

### 词法分析类
Lexer 单例模式语法分析器

### 符号类
Token 单个符号

TokenType 枚举类型，符号种类

TokenList 符号列表，处理一次语法分析获得的所有符号

### 错误类
Error 单个错误

ErrorList 错误列表，处理一次语法分析的错误

（为了与后续错误输出部分统一，所以这里是列表；输出只需要输出一个错误即可；Lexer也只会存入一个错误）

### 结果输出

对于正确结果，输出
```
{符号名称 类别码}
```
到文件lexer.txt中

对于错误结果，输出
```
错误行号 类别码
```

## 语法分析

### 语法修改

为了方便处理，对其中的左递归文法进行改写；

为了不改变原来的语法的结构，在输出时加入一个标签代表语法成分自身
```
乘除模表达式 MulExp → UnaryExp { <MulExp> ('*' | '/' | '%') UnaryExp }
加减表达式 AddExp → MulExp { <AddExp> ('+' | '−') MulExp }
关系表达式 AddExp → AddExp { <AddExp> ('<' | '>' | '<=' | '>=') AddExp }
相等性表达式 EqExp → RelExp { <EqExp> ('==' | '!=') RelExp }
逻辑与表达式 LAndExp → EqExp { <LAndExp> '&&' EqExp }
逻辑或表达式 LOrExp → LAndExp { <LOrExp> LOrExp '||' LAndExp }
```

此外，计算文法中各语法成分的首字符集，在编程时可以参考

这里只给出常用字符集，全部字符集见附录
```
Decl {CONSTTK, INTTK, CHARTK}
InitVal {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}

FuncDef {VOIDTK, INTTK, CHARTK}
FuncFParams, FuncFParam {INTTK, CHARTK}

Block {RBRACE}
BlockItem {CONSTTK, INTTK, CHARTK, IDENFR, LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT, RBRACE, SEMICN, IFTK, FORTK, BREAKTK, CONTINUETK, PRINTFTK}
Stmt {IDENFR, LPARENT, INTCON, CHRCON, PLUS, MINU, NOT, RBRACE, SEMICN, IFTK, FORTK, BREAKTK, CONTINUETK, PRINTFTK, RETURNTK}
ForStmt {IDENFR}

Exp, Cond {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
LVal {IDENFR}
PrimaryExp {LPARENT, IDENFR, INTCON, CHRCON}
UnaryExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
UnaryOp {PLUS, MINU, NOT}
```

### 语法分析器设计
#### 基础数据结构
1. CompUnit 整个编译单元的语法树结构
2. TokenHandler 负责存放语法分析过程中的错误，并且负责提供符号表

#### 语法成分类设计
语法分析过程中，所有语法成分可以归为4类。针对每一类，设计语法成分类并将其放入1个包中，方便管理

总共有4个包：

1. decl 数据定义 Decl, Def, InitVal
2. expr 表达式 Exp, Cond, LVal, PrimaryExp, UnaryExp, FuncRParams, MulExp, AddExp, RelExp, EqExp, LAndExp, LOrExp
3. function 函数定义 FuncDef, FuncFParam, FuncFParams
4. stmt 语句 Block, Stmt, ForStmt

类分析过程：
1. 为了避免类定义过多不好管理，对于Decl, BType, BlockItem这些不显示的类，就不进行定义
2. 此外，NumberExp, CharacterExp, UnaryOp, FuncType这些只有终结符节点的语法成分，就不进行定义，只需要在输出时另起一行，并且在后面加上标签即可
3. MainFuncDef, 由于和FuncDef很近似，就不定义，只需要在FuncDef中加入属性Token mainToken和一个布尔值表示是否为main函数即可
4. ConstExp也可在Exp中加入布尔值判断是否为const，并且加入一个属性constToken即可
5. 同样的，将VarDecl和ConstDecl合并为Decl，将VarDef和ConstDef合并为Def，将VarInitVal和ConstInitVal合并为InitVal

#### 分析器类设计
1. 针对不同种类的语法成分，分别构建分析器，提供方法分析其中任意一种语法成分，并且返回对应的结果
2. DeclParser, ExpParser, FuncParser和StmtParser（它们之间都可以相互调用，所以方法都是public的）
3. 此外，创建类Parser提供对于CompUnit语法成分的获取方法。Parser调用DeclParser和FuncParser的对应方法

#### 附加注意
针对错误输出，需要按照行号输出；所以，在输出错误前，需要先合并词法分析与文法分析的错误表，并且按照行号对错误进行排序。

此外，对于词法分析的错误，需要改正并且输出（出现的错误是|或者&符号错误）

词法分析可能出现的错误
```
逻辑与表达式 LAndExp → EqExp | LAndExp '&&' EqExp // a
逻辑或表达式 LOrExp → LAndExp | LOrExp '||' LAndExp // a
```

### 语义分析
#### 架构设计
符号表相关的包是frontend.symbol

SymbolType 定义符号类型

Symbol是符号，包括ConstInt， IntFunc等种类；对于函数符号，还定义了函数的参数签名和返回值

SymbolTable是某一作用域的符号表，其存放了外层作用域的指针，在处理符号时会生成前向树
#### 错误处理
b **当前作用域**内重复定义的名字
```
ConstDef → Ident [ '[' ConstExp ']' ] '=' ConstInitVal
VarDef → Ident [ '[' ConstExp ']' ] | Ident [ '[' ConstExp ']' ] '=' InitVal 
FuncDef → FuncType Ident '(' [FuncFParams] ')' Block
FuncFParam → BType Ident ['[' ']'] 
```
c 未定义的名字
```
LVal → Ident ['[' Exp ']']
```
d 函数参数个数不匹配/e 参数数量不匹配
```
UnaryExp → Ident '(' [FuncRParams] ')'
```
f void函数有返回值/g 非void函数无返回
```
Stmt -> 'return' [Exp] ';' // f
FuncDef → FuncType Ident '(' [FuncFParams] ')' Block // g
MainFuncDef → 'int' 'main' '(' ')' Block // g
```
h LVal是常量

l printf参数个数不匹配

m break和continue不在for循环中

## 附录
### 文法
```
编译单元 CompUnit → {Decl} {FuncDef} MainFuncDef 

声明 Decl → ConstDecl | VarDecl 
常量声明 ConstDecl → 'const' BType ConstDef { ',' ConstDef } ';' // i
基本类型 BType → 'int' | 'char' 
常量定义 ConstDef → Ident [ '[' ConstExp ']' ] '=' ConstInitVal // k
常量初值 ConstInitVal → ConstExp | '{' [ ConstExp { ',' ConstExp } ] '}' | StringConst
变量声明 VarDecl → BType VarDef { ',' VarDef } ';' // i
变量定义 VarDef → Ident [ '[' ConstExp ']' ] | Ident [ '[' ConstExp ']' ] '=' InitVal // k
变量初值 InitVal → Exp | '{' [ Exp { ',' Exp } ] '}' | StringConst 

函数定义 FuncDef → FuncType Ident '(' [FuncFParams] ')' Block // j
主函数定义 MainFuncDef → 'int' 'main' '(' ')' Block // j
函数类型 FuncType → 'void' | 'int' | 'char'
函数形参表 FuncFParams → FuncFParam { ',' FuncFParam } 
函数形参 FuncFParam → BType Ident ['[' ']'] // k

语句块 Block → '{' { BlockItem } '}' 
语句块项 BlockItem → Decl | Stmt 
语句 Stmt → LVal '=' Exp ';' // i
| [Exp] ';' // i
| Block
| 'if' '(' Cond ')' Stmt [ 'else' Stmt ] // j
| 'for' '(' [ForStmt] ';' [Cond] ';' [ForStmt] ')' Stmt 
| 'break' ';' | 'continue' ';' // i
| 'return' [Exp] ';' // i
| LVal '=' 'getint''('')'';' // i j
| LVal '=' 'getchar''('')'';' // i j
| 'printf''('StringConst {','Exp}')'';' // i j
语句 ForStmt → LVal '=' Exp 

表达式 Exp → AddExp 
条件表达式 Cond → LOrExp 
左值表达式 LVal → Ident ['[' Exp ']'] // k
基本表达式 PrimaryExp → '(' Exp ')' | LVal | Number | Character// j
数值 Number → IntConst
字符 Character → CharConst
一元表达式 UnaryExp → PrimaryExp | Ident '(' [FuncRParams] ')' | UnaryOp UnaryExp // j
单目运算符 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 → AddExp 注：使用的 Ident 必须是常量
```

### 首字符集
```
Decl {CONSTTK, INTTK, CHARTK}
ConstDecl {CONSTTK}
ConstDef {IDENFR}
ConstInitVal {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
VarDecl {INTTK, CHARTK}
VarDef {IDENFR}
InitVal {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
BType {INTTK, CHARTK}

FuncDef {VOIDTK, INTTK, CHARTK}
MainFuncDef {INTTK}
FuncType {VOIDTK, INTTK, CHARTK}
FuncFParams {INTTK, CHARTK}
FuncFParam {INTTK, CHARTK}

Block {RBRACE}
BlockItem {CONSTTK, INTTK, CHARTK, IDENFR, LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT, RBRACE, SEMICN, IFTK, FORTK, BREAKTK, CONTINUETK, PRINTFTK}
Stmt {IDENFR, LPARENT, INTCON, CHRCON, PLUS, MINU, NOT, RBRACE, SEMICN, IFTK, FORTK, BREAKTK, CONTINUETK, PRINTFTK, RETURNTK}
ForStmt {IDENFR}

Exp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
Cond {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
LVal {IDENFR}
PrimaryExp {LPARENT, IDENFR, INTCON, CHRCON}
Number {INTCON}
Character {CHRCON}
UnaryExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
UnaryOp {PLUS, MINU, NOT}
FuncRParams {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
MulExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
AddExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
RelExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
EqExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
LAndExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
LOrExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
ConstExp {LPARENT, IDENFR, INTCON, CHRCON, PLUS, MINU, NOT}
```