1
MiniLang：一个静态类型的命令式语言
2

3
特性：
4
  - 整数和布尔类型
5
  - 变量声明和赋值
6
  - 算术和比较运算
7
  - if/else 条件
8
  - while 循环
9
  - 函数定义和调用
10
  - 返回值
11

12
示例程序：
13
  fn factorial(n: int) -> int {
14
      if n <= 1 {
15
          return 1;
16
      }
17
      return n * factorial(n - 1);
18
  }
19

20
  fn main() -> int {
21
      let result: int = factorial(10);
22
      return result;
23
  }

1
program     → function*
2
function    → "fn" IDENT "(" params? ")" "->" type block
3
params      → param ("," param)*
4
param       → IDENT ":" type
5
type        → "int" | "bool"
6
block       → "{" statement* "}"
7
statement   → let_stmt | assign_stmt | if_stmt | while_stmt | return_stmt | expr_stmt
8
let_stmt    → "let" IDENT ":" type "=" expr ";"
9
assign_stmt → IDENT "=" expr ";"
10
if_stmt     → "if" expr block ("else" block)?
11
while_stmt  → "while" expr block
12
return_stmt → "return" expr? ";"
13
expr        → comparison
14
comparison  → addition (("==" | "!=" | "<" | ">" | "<=" | ">=") addition)?
15
addition    → multiplication (("+" | "-") multiplication)*
16
multiplication → unary (("*" | "/") unary)*
17
unary       → ("!" | "-") unary | call
18
call        → primary ("(" args? ")")?
19
primary     → INT | "true" | "false" | IDENT | "(" expr ")"

1
from enum import Enum, auto
2
from dataclasses import dataclass
3

4
class TokenType(Enum):
5
    # 关键字
6
    FN = auto(); LET = auto(); IF = auto(); ELSE = auto()
7
    WHILE = auto(); RETURN = auto(); TRUE = auto(); FALSE = auto()
8
    INT_TYPE = auto(); BOOL_TYPE = auto()
9
    # 运算符
10
    PLUS = auto(); MINUS = auto(); STAR = auto(); SLASH = auto()
11
    EQ = auto(); NEQ = auto(); LT = auto(); GT = auto()
12
    LTE = auto(); GTE = auto(); ASSIGN = auto(); BANG = auto()
13
    # 分隔符
14
    LPAREN = auto(); RPAREN = auto(); LBRACE = auto(); RBRACE = auto()
15
    COMMA = auto(); SEMICOLON = auto(); COLON = auto(); ARROW = auto()
16
    # 字面量
17
    INT_LIT = auto(); IDENT = auto()
18
    # 特殊
19
    EOF = auto()
20

21
@dataclass
22
class Token:
23
    type: TokenType
24
    value: str
25
    line: int
26
    col: int

1
class Lexer:
2
    KEYWORDS = {
3
        'fn': TokenType.FN, 'let': TokenType.LET,
4
        'if': TokenType.IF, 'else': TokenType.ELSE,
5
        'while': TokenType.WHILE, 'return': TokenType.RETURN,
6
        'true': TokenType.TRUE, 'false': TokenType.FALSE,
7
        'int': TokenType.INT_TYPE, 'bool': TokenType.BOOL_TYPE,
8
    }
9

10
    def __init__(self, source: str):
11
        self.source = source
12
        self.pos = 0
13
        self.line = 1
14
        self.col = 1
15

16
    def tokenize(self) -> list[Token]:
17
        tokens = []
18
        while self.pos < len(self.source):
19
            self.skip_whitespace()
20
            if self.pos >= len(self.source):
21
                break
22

23
            ch = self.source[self.pos]
24

25
            if ch.isdigit():
26
                tokens.append(self.read_number())
27
            elif ch.isalpha() or ch == '_':
28
                tokens.append(self.read_identifier())
29
            elif ch == '-' and self.peek_next() == '>':
30
                tokens.append(self.make_token(TokenType.ARROW, '->'))
31
            elif ch in '+-*/=!<>':
32
                tokens.append(self.read_operator())
33
            elif ch in '(){}:,;':
34
                tokens.append(self.read_punctuation())
35
            else:
36
                raise SyntaxError(f"Unexpected character '{ch}' at {self.line}:{self.col}")
37

38
        tokens.append(Token(TokenType.EOF, '', self.line, self.col))
39
        return tokens
40

41
    def read_number(self) -> Token:
42
        start = self.pos
43
        while self.pos < len(self.source) and self.source[self.pos].isdigit():
44
            self.advance()
45
        return Token(TokenType.INT_LIT, self.source[start:self.pos], self.line, self.col)
46

47
    def read_identifier(self) -> Token:
48
        start = self.pos
49
        while self.pos < len(self.source) and (self.source[self.pos].isalnum() or self.source[self.pos] == '_'):
50
            self.advance()
51
        word = self.source[start:self.pos]
52
        token_type = self.KEYWORDS.get(word, TokenType.IDENT)
53
        return Token(token_type, word, self.line, self.col)

1
from dataclasses import dataclass
2
from typing import Optional
3

4
@dataclass
5
class Expr: pass
6

7
@dataclass
8
class IntLit(Expr):
9
    value: int
10

11
@dataclass
12
class BoolLit(Expr):
13
    value: bool
14

15
@dataclass
16
class VarRef(Expr):
17
    name: str
18

19
@dataclass
20
class BinaryOp(Expr):
21
    op: str; left: Expr; right: Expr
22

23
@dataclass
24
class UnaryOp(Expr):
25
    op: str; operand: Expr
26

27
@dataclass
28
class CallExpr(Expr):
29
    name: str; args: list[Expr]
30

31
@dataclass
32
class Stmt: pass
33

34
@dataclass
35
class LetStmt(Stmt):
36
    name: str; type_name: str; init: Expr
37

38
@dataclass
39
class AssignStmt(Stmt):
40
    name: str; value: Expr
41

42
@dataclass
43
class IfStmt(Stmt):
44
    condition: Expr; then_block: list[Stmt]; else_block: Optional[list[Stmt]]
45

46
@dataclass
47
class WhileStmt(Stmt):
48
    condition: Expr; body: list[Stmt]
49

50
@dataclass
51
class ReturnStmt(Stmt):
52
    value: Optional[Expr]
53

54
@dataclass
55
class ExprStmt(Stmt):
56
    expr: Expr
57

58
@dataclass
59
class Function:
60
    name: str; params: list[tuple[str, str]]; return_type: str; body: list[Stmt]
61

62
@dataclass
63
class Program:
64
    functions: list[Function]

1
class Parser:
2
    def __init__(self, tokens: list[Token]):
3
        self.tokens = tokens
4
        self.pos = 0
5

6
    def parse(self) -> Program:
7
        functions = []
8
        while not self.at_end():
9
            functions.append(self.parse_function())
10
        return Program(functions)
11

12
    def parse_function(self) -> Function:
13
        self.expect(TokenType.FN)
14
        name = self.expect(TokenType.IDENT).value
15
        self.expect(TokenType.LPAREN)
16
        params = self.parse_params()
17
        self.expect(TokenType.RPAREN)
18
        self.expect(TokenType.ARROW)
19
        return_type = self.parse_type()
20
        body = self.parse_block()
21
        return Function(name, params, return_type, body)
22

23
    def parse_expr(self) -> Expr:
24
        return self.parse_comparison()
25

26
    def parse_comparison(self) -> Expr:
27
        left = self.parse_addition()
28
        while self.match(TokenType.EQ, TokenType.NEQ, TokenType.LT,
29
                        TokenType.GT, TokenType.LTE, TokenType.GTE):
30
            op = self.previous().value
31
            right = self.parse_addition()
32
            left = BinaryOp(op, left, right)
33
        return left
34

35
    def parse_addition(self) -> Expr:
36
        left = self.parse_multiplication()
37
        while self.match(TokenType.PLUS, TokenType.MINUS):
38
            op = self.previous().value
39
            right = self.parse_multiplication()
40
            left = BinaryOp(op, left, right)
41
        return left
42

43
    def parse_multiplication(self) -> Expr:
44
        left = self.parse_unary()
45
        while self.match(TokenType.STAR, TokenType.SLASH):
46
            op = self.previous().value
47
            right = self.parse_unary()
48
            left = BinaryOp(op, left, right)
49
        return left
50

51
    def parse_primary(self) -> Expr:
52
        if self.match(TokenType.INT_LIT):
53
            return IntLit(int(self.previous().value))
54
        if self.match(TokenType.TRUE):
55
            return BoolLit(True)
56
        if self.match(TokenType.FALSE):
57
            return BoolLit(False)
58
        if self.match(TokenType.IDENT):
59
            name = self.previous().value
60
            if self.match(TokenType.LPAREN):
61
                args = self.parse_args()
62
                self.expect(TokenType.RPAREN)
63
                return CallExpr(name, args)
64
            return VarRef(name)
65
        if self.match(TokenType.LPAREN):
66
            expr = self.parse_expr()
67
            self.expect(TokenType.RPAREN)
68
            return expr
69
        raise SyntaxError(f"Unexpected token: {self.peek()}")

1
class TypeChecker:
2
    def __init__(self):
3
        self.scopes: list[dict[str, str]] = [{}]  # 符号表栈
4
        self.functions: dict[str, Function] = {}
5

6
    def check_program(self, program: Program):
7
        for func in program.functions:
8
            self.functions[func.name] = func
9
        for func in program.functions:
10
            self.check_function(func)
11

12
    def check_function(self, func: Function):
13
        self.enter_scope()
14
        for name, type_name in func.params:
15
            self.declare(name, type_name)
16
        for stmt in func.body:
17
            self.check_stmt(stmt, func.return_type)
18
        self.exit_scope()
19

20
    def check_expr(self, expr: Expr) -> str:
21
        if isinstance(expr, IntLit): return 'int'
22
        if isinstance(expr, BoolLit): return 'bool'
23
        if isinstance(expr, VarRef):
24
            return self.lookup(expr.name)
25
        if isinstance(expr, BinaryOp):
26
            left_type = self.check_expr(expr.left)
27
            right_type = self.check_expr(expr.right)
28
            if left_type != right_type:
29
                raise TypeError(f"Type mismatch: {left_type} vs {right_type}")
30
            if expr.op in ('+', '-', '*', '/'):
31
                if left_type != 'int':
32
                    raise TypeError(f"Arithmetic on non-int: {left_type}")
33
                return 'int'
34
            if expr.op in ('==', '!=', '<', '>', '<=', '>='):
35
                return 'bool'
36
        if isinstance(expr, CallExpr):
37
            func = self.functions.get(expr.name)
38
            if not func:
39
                raise NameError(f"Undefined function: {expr.name}")
40
            if len(expr.args) != len(func.params):
41
                raise TypeError(f"Wrong number of arguments for {expr.name}")
42
            for (arg, (pname, ptype)) in zip(expr.args, func.params):
43
                arg_type = self.check_expr(arg)
44
                if arg_type != ptype:
45
                    raise TypeError(f"Argument type mismatch: expected {ptype}, got {arg_type}")
46
            return func.return_type
47
        raise ValueError(f"Unknown expression type: {type(expr)}")

1
@dataclass
2
class IRInstr:
3
    op: str          # 操作码
4
    dest: str = ''   # 目标变量
5
    arg1: str = ''   # 操作数1
6
    arg2: str = ''   # 操作数2
7
    label: str = ''  # 标签（跳转目标）
8

9
class IRGenerator:
10
    def __init__(self):
11
        self.temp_count = 0
12
        self.label_count = 0
13
        self.instructions: list[IRInstr] = []
14

15
    def new_temp(self) -> str:
16
        self.temp_count += 1
17
        return f"t{self.temp_count}"
18

19
    def new_label(self) -> str:
20
        self.label_count += 1
21
        return f"L{self.label_count}"
22

23
    def gen_function(self, func: Function) -> list[IRInstr]:
24
        self.instructions = []
25
        self.emit('func', label=func.name)
26
        for name, _ in func.params:
27
            self.emit('param', dest=name)
28
        for stmt in func.body:
29
            self.gen_stmt(stmt)
30
        self.emit('endfunc')
31
        return self.instructions
32

33
    def gen_expr(self, expr: Expr) -> str:
34
        if isinstance(expr, IntLit):
35
            return str(expr.value)
36
        if isinstance(expr, VarRef):
37
            return expr.name
38
        if isinstance(expr, BinaryOp):
39
            left = self.gen_expr(expr.left)
40
            right = self.gen_expr(expr.right)
41
            dest = self.new_temp()
42
            self.emit(expr.op, dest=dest, arg1=left, arg2=right)
43
            return dest
44
        if isinstance(expr, CallExpr):
45
            args = [self.gen_expr(a) for a in expr.args]
46
            for arg in args:
47
                self.emit('push', arg1=arg)
48
            dest = self.new_temp()
49
            self.emit('call', dest=dest, arg1=expr.name, arg2=str(len(args)))
50
            return dest
51
        raise ValueError(f"Unknown expr: {type(expr)}")

1
class ConstantFolder:
2
    def optimize(self, instructions: list[IRInstr]) -> list[IRInstr]:
3
        constants: dict[str, int] = {}
4
        result = []
5

6
        for instr in instructions:
7
            if instr.op == 'assign' and instr.arg1.isdigit():
8
                constants[instr.dest] = int(instr.arg1)
9
                result.append(instr)
10
            elif instr.op in ('+', '-', '*', '/'):
11
                left_val = constants.get(instr.arg1)
12
                right_val = constants.get(instr.arg2)
13
                if left_val is not None and right_val is not None:
14
                    # 编译期计算
15
                    folded = self.eval_op(instr.op, left_val, right_val)
16
                    constants[instr.dest] = folded
17
                    result.append(IRInstr('assign', dest=instr.dest, arg1=str(folded)))
18
                else:
19
                    result.append(instr)
20
            else:
21
                result.append(instr)
22
        return result
23

24
    def eval_op(self, op: str, a: int, b: int) -> int:
25
        if op == '+': return a + b
26
        if op == '-': return a - b
27
        if op == '*': return a * b
28
        if op == '/': return a // b
29
        raise ValueError(f"Unknown op: {op}")

1
class DeadCodeEliminator:
2
    def optimize(self, instructions: list[IRInstr]) -> list[IRInstr]:
3
        used: set[str] = set()
4
        # 第一遍：收集使用的变量
5
        for instr in instructions:
6
            if instr.arg1 and not instr.arg1.isdigit():
7
                used.add(instr.arg1)
8
            if instr.arg2 and not instr.arg2.isdigit():
9
                used.add(instr.arg2)
10
        # 第二遍：删除未使用的赋值
11
        result = []
12
        for instr in instructions:
13
            if instr.op in ('assign', '+', '-', '*', '/', '/') and instr.dest not in used:
14
                continue  # 死代码，跳过
15
            result.append(instr)
16
        return result

1
class StackCodeGenerator:
2
    def generate(self, instructions: list[IRInstr]) -> list[str]:
3
        code = []
4
        for instr in instructions:
5
            if instr.op == 'func':
6
                code.append(f"FUNC {instr.label}")
7
            elif instr.op == 'endfunc':
8
                code.append("ENDFUNC")
9
            elif instr.op == 'param':
10
                code.append(f"LOAD_PARAM {instr.dest}")
11
            elif instr.op == 'assign':
12
                code.append(f"PUSH {instr.arg1}")
13
                code.append(f"STORE {instr.dest}")
14
            elif instr.op in ('+', '-', '*', '/'):
15
                code.append(f"LOAD {instr.arg1}")
16
                code.append(f"LOAD {instr.arg2}")
17
                code.append(f"OP {instr.op}")
18
                code.append(f"STORE {instr.dest}")
19
            elif instr.op == 'call':
20
                code.append(f"CALL {instr.arg1} {instr.arg2}")
21
                code.append(f"STORE {instr.dest}")
22
            elif instr.op == 'return':
23
                if instr.arg1:
24
                    code.append(f"LOAD {instr.arg1}")
25
                code.append("RET")
26
        return code

1
class Interpreter:
2
    def __init__(self):
3
        self.stack: list[int] = []
4
        self.variables: dict[str, int] = {}
5
        self.functions: dict[str, list[str]] = {}
6

7
    def run(self, code: list[str]) -> int:
8
        # 加载函数
9
        self.load_functions(code)
10
        # 调用 main
11
        return self.call_function('main', [])
12

13
    def call_function(self, name: str, args: list[int]) -> int:
14
        func_code = self.functions[name]
15
        local_vars = {}
16
        # 绑定参数
17
        for i, instr in enumerate(func_code):
18
            if instr.startswith('LOAD_PARAM'):
19
                var_name = instr.split()[1]
20
                local_vars[var_name] = args.pop(0)
21

22
        # 执行
23
        ip = 0
24
        while ip < len(func_code):
25
            instr = func_code[ip]
26
            parts = instr.split()
27
            op = parts[0]
28

29
            if op == 'PUSH':
30
                self.stack.append(int(parts[1]))
31
            elif op == 'LOAD':
32
                self.stack.append(local_vars.get(parts[1], self.variables.get(parts[1], 0)))
33
            elif op == 'STORE':
34
                local_vars[parts[1]] = self.stack.pop()
35
            elif op == 'OP':
36
                b, a = self.stack.pop(), self.stack.pop()
37
                if parts[1] == '+': self.stack.append(a + b)
38
                elif parts[1] == '-': self.stack.append(a - b)
39
                elif parts[1] == '*': self.stack.append(a * b)
40
                elif parts[1] == '/': self.stack.append(a // b)
41
            elif op == 'RET':
42
                return self.stack.pop() if self.stack else 0
43
            elif op == 'CALL':
44
                result = self.call_function(parts[1], [self.stack.pop() for _ in range(int(parts[2]))][::-1])
45
                self.stack.append(result)
46
            ip += 1
47
        return 0

1
def test_factorial():
2
    source = """
3
    fn factorial(n: int) -> int {
4
        if n <= 1 {
5
            return 1;
6
        }
7
        return n * factorial(n - 1);
8
    }
9
    fn main() -> int {
10
        return factorial(10);
11
    }
12
    """
13

14
    # 1. 词法分析
15
    tokens = Lexer(source).tokenize()
16

17
    # 2. 语法分析
18
    ast = Parser(tokens).parse()
19

20
    # 3. 语义分析
21
    TypeChecker().check_program(ast)
22

23
    # 4. IR 生成
24
    ir = IRGenerator().gen_program(ast)
25

26
    # 5. 优化
27
    ir = ConstantFolder().optimize(ir)
28
    ir = DeadCodeEliminator().optimize(ir)
29

30
    # 6. 代码生成
31
    code = StackCodeGenerator().generate(ir)
32

33
    # 7. 执行
34
    result = Interpreter().run(code)
35

36
    assert result == 3628800  # 10!
37
    print(f"factorial(10) = {result}")