20. 编译原理基础

# 简单词法分析器：识别标识符、数字、运算符、关键字
import re

TOKEN_RE = [
    ("NUMBER",  r"\d+"),
    ("ID",      r"[A-Za-z_]\w*"),
    ("OP",      r"[+\-*/=<>!]"),
    ("WS",      r"\s+"),
]

KEYWORDS = {"if", "else", "while", "return"}

def lex(code):
    tokens = []
    pos = 0
    while pos < len(code):
        for kind, pattern in TOKEN_RE:
            m = re.match(pattern, code[pos:])
            if m:
                text = m.group()
                if kind == "ID" and text in KEYWORDS:
                    kind = "KEYWORD"
                if kind != "WS":            # 跳过空白
                    tokens.append((kind, text))
                pos += len(text)
                break
        else:
            raise SyntaxError(f"无法识别: {code[pos:]}")
    tokens.append(("EOF", ""))
    return tokens

print(lex("x = 42 + y"))   # [('ID','x'),('OP','='),('NUMBER','42'),('OP','+'),('ID','y')]

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos]

    def consume(self, expect=None):
        tok = self.tokens[self.pos]
        if expect and tok[1] != expect:
            raise SyntaxError(f"期望 {expect}, 实际 {tok}")
        self.pos += 1
        return tok

    def parse_expr(self):
        node = self.parse_term()
        while self.peek()[1] in ("+", "-"):
            op = self.consume()[1]
            rhs = self.parse_term()
            node = (op, node, rhs)          # 左结合：((a+b)-c)
        return node

    def parse_term(self):
        node = self.parse_factor()
        while self.peek()[1] in ("*", "/"):
            op = self.consume()[1]
            rhs = self.parse_factor()
            node = (op, node, rhs)
        return node

    def parse_factor(self):
        kind, val = self.consume()
        if kind == "NUMBER":
            return ("num", int(val))
        if val == "(":
            inner = self.parse_expr()
            self.consume(")")
            return inner
        raise SyntaxError("非法因子")

# tokens = lex("3 + 4 * (2 - 1)")
# ast = Parser(tokens).parse_expr()   → ('+', ('num',3), ('*',('num',4), ('-',('num',2),('num',1))))

# LL(1) 预测分析表驱动的核心循环（伪代码）
def predictive_parse(table, start_symbol, tokens):
    stack = [start_symbol]
    a = next_token(tokens)
    while stack:
        X = stack.pop()
        if X.is_terminal():
            if X == a:
                a = next_token(tokens)
            else:
                raise SyntaxError("终结符不匹配")
        else:
            production = table[X][a]       # 由前瞻符号查表决定产生式
            stack.push(reversed(production))  # 右端逆序入栈

// 表达式 3 + 4 * (2 - 1) 的 AST
{
  "type": "BinaryExpr",
  "op": "+",
  "left": { "type": "Number", "value": 3 },
  "right": {
    "type": "BinaryExpr",
    "op": "*",
    "left": { "type": "Number", "value": 4 },
    "right": {
      "type": "BinaryExpr",
      "op": "-",
      "left": { "type": "Number", "value": 2 },
      "right": { "type": "Number", "value": 1 }
    }
  }
}

# AST 求值：递归遍历节点
def evaluate(node):
    kind = node[0]
    if kind == "num":
        return node[1]
    op, left, right = node
    l, r = evaluate(left), evaluate(right)
    if op == "+": return l + r
    if op == "-": return l - r
    if op == "*": return l * r
    if op == "/": return l // r

# 窥孔优化示例：合并相邻指令（模式匹配滑动窗口）
def peephole(ir):
    optimized = []
    for insn in ir:
        # 模式 1: x = y; z = x  →  z = y
        # 模式 2: if x == 0 goto L; goto L2 → if x == 0 goto L; L2: ...
        optimized.append(insn)
    return optimized