编译原理

1.1 考试内容

1.2 简答题（30分）

1.2.1 解释型 VS 编译型 VS 汇编以及各自代表语言

编译型语言和解释型语言的运行机制：
相同点
- 编译型语言和解释型语言前期处理流程上都要经过词法分析、语法分析和语义分析阶段
不同点
- 编译型语言一次性将全部代码翻译成目标程序，解释型语言逐行翻译并执行代码
- 编译型语言：性能高、跨平台性差、开发效率较低，代表语言 C / C++ 、Rust 、Go
- 解释型语言：性能低、跨平台性强、开发效率较高，代表语言 Python、JavaScript、PHP
- 汇编语言：性能高、开发效率低、跨平台性极差，asm

1.2.2 解释器执行步骤

源代码 - > 词法分析 -> Token序列 / 词法错误 -> 语法分析 -> AST / 语法错误 -> 语义分析 -> 经过语义检查的AST / 语义错误 -> 解释执行 -> 结果 / 运行时异常

1.2.3 语义部分

参数传递
- 首先校验函数是否声明，若声明，则获取对应函数节点
- 接着校验获取的节点的参数（形参）与传递的实参的参数数量、参数类型是否一致
- 最后将实参的值拷贝给形参变量，并将形参以形参名+形参值的形式传入本层栈帧的局部变量表中
返回值处理
- 首先查看是无值返回（Back）还是有值返回（Return）
- 无论是哪种返回，都要通过循环不断退栈，到本层函数的栈帧层
- 如果是无值返回，封装空值到自定义异常抛出，由上层捕获并获取返回值
- 如果是有值返回，则计算表达式值，封装表达式值到自定义异常抛出，由上层捕获并获取返回值

1.3 有限状态机应用题（25分）

设计

代码

java

// 模拟状态机
public class ButtonFSM {
    private enum State {IDLE, PRESSED}
    private Timer timer;
    private State currentState = State.IDLE;
    private int count = 0;
    private long pressStartTime;

    // 按下
    public void handlePress() {
        // 有待结算任务时取消，继续统计新的点击序列
        if (timer != null) {
            timer.cancel();
            timer = null;
        }
        pressStartTime = System.currentTimeMillis();
        count++;
        currentState = State.PRESSED;
    }

    // 抬起
    public void handleRelease() {
        long duration = System.currentTimeMillis() - pressStartTime;

        if (duration >= 500 && count == 1) {
            finish("长按");
        } else {
            timer = new Timer();
            timer.schedule(new TimerTask() {
                @Override
                public void run() {
                    finish(count == 1 ? "点击" : count + "连击");
                }
            }, 300);
        }

        currentState = State.IDLE;
    }

    // 结算
    public void finish(String msg) {
        System.out.println("结果为：" + msg);
        count = 0;
    }
}

1.4 ToyPL 编程题（5分）

ToyPL语法请查看：[ToyPL语法](../toypl/1. Toypl.md)

选择排序

int arr[5]
int size[1] // 用数组第0位模拟全局变量 n

// 1. 选择排序 (修改版)
fun selectionSort() {
    int i = 0
    // 使用 size[0] 代替 n
    while(i < size[0] - 1) {
        int minIndex = i
        int j = i + 1
        while(j < size[0]) { // 【可能出空 1】：比较逻辑
            if(arr[j] < arr[minIndex]) { 
                minIndex = j 
            }
            j = j + 1
        }
        // 【可能出空 2】：交换逻辑
        int temp = arr[i] #
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
        i = i + 1
    }
    back
}

插入排序

// 3. 插入排序
fun insertionSort() {
    int i = 1
    while(i < size[0]) {
        int key = arr[i]
        int j = i - 1
        // 【可能出空 3】：循环条件（非 0 为 true）
        while(j >= 0 & arr[j] > key) { 
            arr[j + 1] = arr[j] // 元素右移
            j = j - 1
        }
        // 【可能出空 4】：插入位置
        arr[j + 1] = key 
        i = i + 1
    }
    back
}

快速排序


// 2. 快速排序 (修改版)
fun quickSort(int low int high) {
    if(low < high) { // (1) 填入递归终止条件
        int pivot = arr[low]
        int i = low
        int j = high
        
        while(i < j) {
        	// 从右向左找小的
            while(i < j & arr[j] >= pivot) { j = j - 1 }
            arr[i] = arr[j]
            // 从左向右找大的
            while(i < j & arr[i] <= pivot) { i = i + 1 }
            arr[j] = arr[i]
        }
        arr[i] = pivot
        
        // 传参依然用空格
        quickSort(low i - 1)  // (2) 填入左侧递归调用
        quickSort(i + 1 high)
    }
    back
}

1.5 词法（20分）

设计
先定义 Token 类型，包括关键字、标识符、数字、运算符、界符和 EOF。然后从左到右扫描源代码，跳过空白字符，按最长匹配原则识别词素，生成 Token 序列供语法分析使用。若遇到非法字符或格式错误，则报告词法错误，并给出行号和列号。

实现

TokenType

java

// Token类型
public enum TokenType {
    // 字面常量
    INT,
    STRING,
    
    // 关键字
    KW,
    PRINT,
    // 标识符
    ID,

    // 界符
    LP,
    RP,

    // 运算符
    ASSIGN,
    PLUS,
    MINUS,
    MUL,
    DIV,

    // 结束符
    EOF
}

Token

java

/**
 * 词法单元，token类
 */
public class Token {

    public final TokenType type;
    public final String value;
    public final int row;
    public final int col;
    // 有参构造、无参构造、getter、setter、toString...
    
}

异常

java

public class MyException extends RuntimeException {
    public MyException(String message) {
        super(message);
    }
}

lexer

java

public class lexer {
    // 结果集
    private List<Token> tokenList;
    // 当前行的内容
    private String currentLine;
    // 当前Token所处行
    private long charRow;
    // 当前Token所处列
    private long charCol;

    // 对源码预处理，分成很多行
    public List<Token> analyzeCode(String code) {
        tokenList = new ArrayList<>();
        if (code == null) {
            tokenList.add(new Token(TokenType.EOF, null, 1, 1));
            return tokenList;
        }
        String[] lines = code.split("\\R", -1);
        for (int i = 0; i < lines.length; i++) {
            currentLine = lines[i];
            charRow = i + 1;
            charCol = 0;
            analyzeLine();
        }
        int eofRow = lines.length == 0 ? 1 : lines.length;
        int eofCol = lines.length == 0 ? 1 : lines[lines.length - 1].length() + 1;
        tokenList.add(new Token(TokenType.EOF, null, eofRow, eofCol));
        return tokenList;
    }

    // 单独处理每一行
    private void analyzeLine() {
        // 逐字符推进
        while (charCol < currentLine.length()) {
            char ch = watchNextChar(charCol);
            // 空白符跳过
            if (Character.isWhitespace(ch)) {
                charCol++;
                continue;
            }
            // 识别Token
            // 1. 数字开头
            if (Character.isDigit(ch)) {
                extractIntToken();
                continue;
            }
            // 2. 字母或下划线开头（标识符） / 关键字
            if (isIdentifierStart(ch)) {
                extractIdentifierToken();
                continue;
            }
            // 3. 双引号开头（字符串常量）
            if (ch == '"') {
                extractStringToken();
                continue;
            }
            // 4. 界符、运算符
            switch (ch) {
                case '(':
                    tokenList.add(new Token(TokenType.LP, "(", charRow, charCol + 1));
                    charCol++;
                    break;
                case ')':
                    tokenList.add(new Token(TokenType.RP, ")", charRow, charCol + 1));
                    charCol++;
                    break;
                case '+':
                    tokenList.add(new Token(TokenType.PLUS, "+", charRow, charCol + 1));
                    charCol++;
                    break;
                case '-':
                    tokenList.add(new Token(TokenType.MINUS, "-", charRow, charCol + 1));
                    charCol++;
                    break;
                case '*':
                    tokenList.add(new Token(TokenType.MUL, "*", charRow, charCol + 1));
                    charCol++;
                    break;
                case '/':
                    tokenList.add(new Token(TokenType.DIV, "/", charRow, charCol + 1));
                    charCol++;
                    break;
                case '=':
                    tokenList.add(new Token(TokenType.ASSIGN, "=", charRow, charCol + 1));
                    charCol++;
                    break;
                default:
                    throw new MyException("Unrecognized character '" + ch + "' at row " + charRow + ", col " + (charCol + 1));
            }
        }
    }

1.6 语法（20分）

设计
语法分析先根据需求设计出语法生成式，根据语法生成式检查 Token 序列是否合法，并构建语法树。采用递归下降法实现语法生成式，发现不符合文法的输入时，报告语法错误并定位到具体位置。
- 语法生成式示例：
```
program -> stmt*
stmt -> decl | assign | printStmt

decl -> KW ID ('=' expr)? ';'
assign -> ID '=' expr ';'
printStmt -> PRINT '(' expr ')' ';'

expr -> term (('+' | '-') term)*
term -> factor (('*' | '/') factor)*
factor -> ID | INT | '(' expr ')'
```

实现

java

import java.util.List;

public class Parser {
    private List<Token> tokens;
    private int index;

    public void init(List<Token> tokens) {
        this.tokens = tokens;
        this.index = 0;
    }

    public void parse() {
        while (!check(TokenType.EOF)) {
            parseStatement();
        }
    }

    private void parseStatement() {
        if (check(TokenType.KW)) {
            parseDeclaration();
            return;
        }

        if (check(TokenType.PRINT)) {
            parsePrint();
            return;
        }

        if (check(TokenType.ID) && lookAhead(1).getType() == TokenType.ASSIGN) {
            parseAssignment();
            return;
        }

        throw error(current(), "Invalid statement");
    }

    private void parseDeclaration() {
        consume(TokenType.KW, "Expected type keyword");
        consume(TokenType.ID, "Expected identifier");

        if (match(TokenType.ASSIGN)) {
            parseExpr();
        }

        consume(TokenType.SEMICOLON, "Expected ';' after declaration");
    }

    private void parseAssignment() {
        consume(TokenType.ID, "Expected identifier");
        consume(TokenType.ASSIGN, "Expected '='");
        parseExpr();
        consume(TokenType.SEMICOLON, "Expected ';' after assignment");
    }

    private void parsePrint() {
        consume(TokenType.PRINT, "Expected print");
        consume(TokenType.LP, "Expected '(' after print");
        parseExpr();
        consume(TokenType.RP, "Expected ')'");
        consume(TokenType.SEMICOLON, "Expected ';' after print");
    }

    private void parseExpr() {
        parseTerm();
        while (check(TokenType.PLUS) || check(TokenType.MINUS)) {
            consumeCurrent();
            parseTerm();
        }
    }

    private void parseTerm() {
        parseFactor();
        while (check(TokenType.MUL) || check(TokenType.DIV)) {
            consumeCurrent();
            parseFactor();
        }
    }

    private void parseFactor() {
        if (match(TokenType.INT)) {
            return;
        }

        if (match(TokenType.ID)) {
            return;
        }

        if (match(TokenType.LP)) {
            parseExpr();
            consume(TokenType.RP, "Expected ')'");
            return;
        }

        throw error(current(), "Expected factor");
    }

    private boolean match(TokenType type) {
        if (check(type)) {
            index++;
            return true;
        }
        return false;
    }

    private void consume(TokenType type, String message) {
        if (!check(type)) {
            throw error(current(), message);
        }
        index++;
    }

    private Token consumeCurrent() {
        return tokens.get(index++);
    }

    private boolean check(TokenType type) {
        return current().getType() == type;
    }

    private Token current() {
        return tokens.get(index);
    }

    private Token lookAhead(int offset) {
        int pos = index + offset;
        if (pos >= tokens.size()) {
            return tokens.get(tokens.size() - 1);
        }
        return tokens.get(pos);
    }

    private RuntimeException error(Token token, String message) {
        return new RuntimeException(
            "Syntax error at row " + token.getRow() + ", col " + token.getCol() + ": " + message
        );
    }
}

编译原理 ​

1.1 考试内容 ​

1.2 简答题（30分） ​

1.2.1 解释型 VS 编译型 VS 汇编 以及各自代表语言 ​

1.2.2 解释器执行步骤 ​

1.2.3 语义部分 ​

1.3 有限状态机应用题（25分） ​

1.4 ToyPL 编程题（5分） ​

1.5 词法（20分） ​

1.6 语法（20分） ​

编译原理

1.1 考试内容

1.2 简答题（30分）

1.2.1 解释型 VS 编译型 VS 汇编以及各自代表语言

1.2.2 解释器执行步骤

1.2.3 语义部分

1.3 有限状态机应用题（25分）

1.4 ToyPL 编程题（5分）

1.5 词法（20分）

1.6 语法（20分）