编译-实验日志

Fyw0o Nothing •

2025-10-01

Compiler

Compiler Lab

Parser

10.20

修改原来的词法分析程序，在Lexer中提供了public Token getNextToken()的接口，方便在实现一遍编译程序时，语法分析程序调用

10.22

编译单元 CompUnit → {Decl} {FuncDef} MainFuncDef

声明 Decl → ConstDecl | VarDecl

常量声明 ConstDecl → ‘const’ BType ConstDef { ‘,’ ConstDef } ‘;’ // i

变量声明 VarDecl → [ ‘static’ ] BType VarDef { ‘,’ VarDef } ‘;’ // i
基本类型 BType → ‘int’
变量定义 VarDef → Ident [ ‘[‘ ConstExp ‘]’ ] | Ident [ ‘[‘ ConstExp ‘]’ ] ‘=’ InitVal // k

函数定义 FuncDef → FuncType Ident ‘(‘ [FuncFParams] ‘)’ Block // j
函数类型 FuncType → ‘void’ | ‘int’

主函数定义 MainFuncDef → ‘int’ ‘main’ ‘(‘ ‘)’ Block // j

识别{Decl}，对于VarDecl，['static'] int，对于Func和MainFunc也都有可能有int。所以：
    如果有const, static一定是；如果是int，那就还要看int ident []，要看是否为'['
识别{FuncDef}，如果有void，一定是；如果是int，那就还要看 int ident ()，是否有'('并且ident不是'main'
识别MainFuncDef，int main，是否有'main'
CompUnit -> {const... | [static] int Ident} {void|int Ident(...) {}} int main (...) {}

不能只看第一个token，还要往下多看几个token，出现问题！

10.23

建立缓冲区解决昨天的问题

10.27

stmt的识别looksLikeAssignStmt()函数，预处理的时候只读几个token的话如果匹配不上回造成死循环

why i write a func named looksLikeAssignStmt?

通过观察stmt的文法，对于大多选项，我们可以通过预读第一个token来进行多路分支判断，如：
check(1, “{“) → Block：最简单，直接解析块语句;
check(1, “if”) → If 语句：预读识别，然后解析条件、语句体和可选的 else;
check(1, “for”) → For 循环：预读识别，解析初值、条件、更新和循环体;
check(1, “break”) → Break 语句：直接识别;
check(1, “continue”) → Continue 语句：直接识别;
check(1, “return”) → Return 语句：直接识别，可选跟表达式;
check(1, “printf”) → Printf 语句：直接识别;
else 分支 → 赋值语句或表达式语句：这里用了更复杂的预读处理
最关键的部分：赋值和表达式，这两种的区分需要更深入的预读，所以有一个专门的方法（其实就是多往后读了几个）
但如果没有找到’]’’=’等会出现无限预读，造成死循环

11.9

创建了AST（抽象语法树）节点类：

public class ASTNode{
    private String name;                    // 节点名称（如 <CompUnit>, <Decl>, 等）
    private String value;                   // 节点值（对于叶子节点，如具体的 token 值）
    private String tokenType;               // token 类型（用于区分终结符）
    private List<ASTNode> children;         // 子节点列表
}

修改parser类返回ASTNode，对每个语法成分创建ASTNode
所以原来直接在递归下降子程序分析的时候打印的语法成分列表现在生成的逻辑变成了后序遍历抽象语法树

11.13

使用预读方法处理STMT时常会出现死循环，更换成回溯的方式：尝试解析，失败时回复状态

保存当前状态（checkpoint, lastLine, errors）
尝试解析赋值语句
├─ 成功 → 返回 true，使用解析结果 ✓
└─ 失败 → 返回 false
失败时恢复状态
├─ 清空多余的 buffer 内容
├─ 恢复 lastConsumedLine
└─ 恢复 errors 列表
按表达式语句重新解析

ps：为了避免这两种方法有一种有bug，仍然保留了预处理的代码，以便实际考试的时候其中一种方法出错

11.14

昨天的回溯由于没有处理buf的consume导致其实写了个假的回溯，今天重新修改了回溯算法：

避免在“尝试失败”时已经消费掉 func 之类的 token，导致伪回溯和死循环。
使用局部索引 i 基于 LA(i) 在当前语句上模拟匹配 LVal ‘=’ Exp ‘;’。
仅在 buf 上前后移动索引，不调用 consume / parseLVal / parseExp，不写文件、不改 AST、不改错误列表。
增强 expectSemicolon() 的同步能力：在缺失 ; 时不仅报错 i，还通过 while 跳过后续 token，直到遇到 ‘;’ / ‘}’ / EOF，再继续解析，避免在错误 token 上原地踏步引发新的死循环。

😭好难啊啊啊啊啊啊啊啊啊～～～～

11.15

放弃了回溯😭，修改了原有的预处理函数，更加包容，“=”识别可能为赋值语句的语法

另外在构建语法树的时候，新增带有行号的节点类构造方法

semantic

11.09

进入编译器的核心阶段之一，为了方便语义分析时的报错与定位，让符号表中的每个符号都会记录其定义所在的准确行号

添加行号支持
- 添加了 private int lineNum; 字段
- 新增构造函数：ASTNode(String name, String value, int lineNum)
- 修改现有构造函数初始化 lineNum = 0
- 添加 getLineNum() 和 setLineNum(int lineNum) 方法
传递Token行号到AST节点：更新了所有创建终结符节点的地方，将 t.getLineNum() 传递给ASTNode构造函数

符号表为了便于维护和后期修改，设计了三层结构：

SymbolType enum
class Symbol: name, type, scopeId, lineNum, isArray, arraySize, …

Scope:

public class Scope {
    private int scopeId;                              // 作用域序号
    private Scope parent;                             // 父作用域
    private List<Scope> children;                     // 子作用域
    private Map<String, Symbol> symbols;              // 该作用域中的符号
    private List<Symbol> orderedSymbols;              // 按声明顺序排列的符号
}

初步确定了维护符号表的思路，在维护符号表时需要注意的几个点：

全局域->函数->语句块这些跳转与作用域有关

所以处理函数定义和语句块的时候，需要处理作用域：

private void analyzeFuncDef(ASTNode node) {
    // 第一步：提取函数信息
    String funcName = null;
    SymbolType funcType = null;  // 从FuncType子节点确定
    int lineNum = 0;
    
    // 第二步：将函数本身加入当前作用域
    Symbol funcSymbol = new Symbol(funcName, funcType, currentScope.getScopeId(), lineNum);
    currentScope.addSymbol(funcSymbol);
    
    // 第三步：创建函数内部作用域
    enterScope();
    
    // 第四步：处理函数参数（加入函数作用域）
    analyzeFuncFParams(...);
    
    // 第五步：处理函数体
    analyzeBlock(...);
    
    // 第六步：退出函数作用域
    exitScope();
}

/**
* 分析语句块
*/
private void analyzeBlock(ASTNode node, boolean createNewScope) {
    if (createNewScope) {
        enterScope();
    }
    
    for (ASTNode child : node.getChildren()) {
        if (child.getName().equals("ConstDecl") || child.getName().equals("VarDecl")) {
            analyzeDecl(child);
        } else if (child.getName().equals("Stmt")) {
            analyzeStmt(child);
        }
    }
    
    if (createNewScope) {
        exitScope();
    }
}

对于作用域的管理

/**
* 进入新作用域
*/
private void enterScope() {
    Scope newScope = new Scope(++scopeCounter, currentScope);
    currentScope = newScope;
}

/**
* 退出当前作用域
*/
private void exitScope() {
    if (currentScope.getParent() != null) {
        currentScope = currentScope.getParent();
    }
}

11.14

修改了Symbol类，修改如下

public class Symbol {
    private String name;           // 符号名称
    private SymbolType type;       // 符号类型
    private int scopeId;           // 作用域序号
    private int lineNum;           // 定义所在行号
    private boolean isArray;       // 是否为数组
    private Integer arraySize;     // 数组大小（如果是数组）
    private List<ParamType> params; // 函数参数列表（仅用于函数）
    private boolean isBuiltin;     // 是否为内置函数（如 getint, putint 等）
}

增加了错误处理，其中错误处理检测策略

1. 错误 b - 名字重定义

1
2
3

检测时机：声明 ConstDef、VarDef、FuncDef、FuncFParam
方法：在当前作用域查找同名符号
注意：只检查同一层级作用域，允许内层覆盖外层

2. 错误 c - 未定义的名字

1
2
3

检测时机：LVal 使用、函数调用
方法：从当前作用域递归向上查找
特殊处理：内置函数（getint）预先注册到全局作用域

3. 错误 d/e - 函数参数不匹配

检测时机：UnaryExp 的函数调用
参数个数：比较实参与形参数量
参数类型：逐个比较实参与形参类型
  - int 对应 INT
  - int[] 对应 INT_ARRAY

4. 错误 f - void函数有return值

1
2
3

检测时机：分析 return 语句
方法：检查 currentFuncType 是否为 VOID_FUNC
判断依据：return 后是否有 Exp 子节点

5. 错误 g - int函数缺少return

1
2
3

检测时机：FuncDef/MainFuncDef 的 Block 结束
方法：检查 Block 最后一个语句是否为 return
注意：只检查末尾，不考虑控制流分析

6. 错误 h - 修改常量

1
2
3

检测时机：赋值语句（Stmt、ForStmt）
方法：查找 LVal 对应符号，检查是否为 CONST_INT 或 CONST_INT_ARRAY
行号：LVal 的第一个 Ident 行号

7. 错误 l - printf格式不匹配

1
2
3

检测时机：printf 语句
方法：统计 StringConst 中 %d 的个数与实参个数比较
特殊处理：忽略 %%、\n 等转义序列

8. 错误 m - 非循环块中使用break/continue

检测时机：break/continue 语句
方法：维护 loopDepth 计数器
  - 进入 for 循环时 ++
  - 退出 for 循环时 --
  - break/continue 时检查 loopDepth > 0

一些值得注意的实现细节

1. 行号获取策略

终结符节点：创建时从 Token 获取行号
错误报告：使用节点的行号或最后消费的token行号
特殊情况：
  - 错误 i/j/k：使用前一个符号的行号
  - 错误 g：使用函数右大括号的行号

2. 作用域管理

全局作用域：程序启动时创建（scopeId = 1）
函数作用域：进入函数时创建新作用域
  - 函数参数属于函数内部作用域
语句块作用域：每个 Block 创建新作用域
作用域序号：按进入顺序递增编号

3. 内置函数处理

预定义函数：getint
处理方式：
  - 初始化时注册到全局作用域
  - 标记为 isBuiltin = true
  - 符号表输出时自动过滤

4. AST节点行号传递

所有终结符节点创建时必须包含行号：
new ASTNode(name, value, lineNum)

错误处理占位符也需要行号：
expectSemicolon() -> 使用 lastConsumedLine
expectRParen() -> 使用 lastConsumedLine
expectRBrack() -> 使用 lastConsumedLine