「词法分析器实现」

# 正则表达式运算优先级: 闭包 > 连接 > 选择
# a|bc*  等价于  a | (b (c*))
# 词法规则书写时通常加括号避免歧义
TOKEN_RULES = [
    ("KW_IF",    r"if"),
    ("ID",       r"[a-zA-Z_][a-zA-Z0-9_]*"),
    ("NUM",      r"[0-9]+"),
    ("OP_PLUS",  r"\+"),
    ("OP_MUL",   r"\*"),
    ("WS",       r"[ \t\n]+"),
]

class NFAState:
    def __init__(self):
        self.trans = {}   # 字符 -> [目标状态]
        self.eps = []     # ε 边目标列表
        self.accept = False

class NFASegment:
    def __init__(self, start, end):
        self.start = start
        self.end = end

def thompson_concat(seg1, seg2):
    seg1.end.eps.append(seg2.start)
    return NFASegment(seg1.start, seg2.end)

def thompson_choice(seg1, seg2):
    s, e = NFAState(), NFAState()
    s.eps += [seg1.start, seg2.start]
    seg1.end.eps.append(e)
    seg2.end.eps.append(e)
    return NFASegment(s, e)

def thompson_star(seg):
    s, e = NFAState(), NFAState()
    s.eps += [seg.start, e]
    seg.end.eps += [seg.start, e]
    return NFASegment(s, e)

def epsilon_closure(nfa_states):
    stack = list(nfa_states)
    closure = set(nfa_states)
    while stack:
        s = stack.pop()
        for t in s.eps:
            if t not in closure:
                closure.add(t)
                stack.append(t)
    return frozenset(closure)

def move(nfa_states, ch):
    nxt = set()
    for s in nfa_states:
        nxt.update(s.trans.get(ch, []))
    return nxt

def subset_construction(nfa_start, alphabet):
    dfa_states = {}
    start = epsilon_closure({nfa_start})
    worklist = [start]
    dfa_states[start] = {}
    while worklist:
        cur = worklist.pop()
        for ch in alphabet:
            t = epsilon_closure(move(cur, ch))
            if not t:
                continue
            dfa_states[cur][ch] = t
            if t not in dfa_states:
                dfa_states[t] = {}
                worklist.append(t)
    return dfa_states

def minimize(dfa, accept_states):
    # 初始划分: 接受态 / 非接受态
    partition = [set(accept_states),
                 set(dfa.keys()) - set(accept_states)]
    changed = True
    while changed:
        changed = False
        new_partition = []
        for group in partition:
            # 按每个字符迁移目标所在的组拆分
            buckets = {}
            for s in group:
                key = tuple(partition.index_of(dfa[s][c])
                            for c in ALPHABET)
                buckets.setdefault(key, set()).add(s)
            for bucket in buckets.values():
                new_partition.append(bucket)
                if len(bucket) < len(group):
                    changed = True
        partition = new_partition
    return partition

# 最小化后的词法状态表
# 行是状态, 列是字符, 数字表示迁移目标, -1 表示死状态
LEX_TABLE = [
    [1,  2,  3, -1, -1],   # 状态 0: 起始
    [1, -1, -1, -1, -1],   # 状态 1: 标识符推进
    [-1, 4, -1, -1, -1],   # 状态 2: 数字开头
    [-1, -1, 5, -1, -1],   # 状态 3: 运算符
    [4, -1, -1, -1, -1],   # 状态 4: 数字继续
    [-1, -1, -1, -1, -1],  # 状态 5: 接受
]

def lex(src):
    pos = 0
    tokens = []
    while pos < len(src):
        if src[pos].isspace():
            pos += 1
            continue
        matched = None
        matched_len = 0
        for rule in TOKEN_RULES:
            m = rule.pattern.match(src, pos)
            if m and m.end() - pos > matched_len:
                matched = rule
                matched_len = m.end() - pos
        if matched is None:
            raise LexError(f"unexpected char {src[pos]!r} at {pos}")
        tokens.append((matched.name,
                       src[pos:pos + matched_len]))
        pos += matched_len
    return tokens

class LexError(Exception):
    def __init__(self, msg, line, col):
        self.msg = msg
        self.line = line
        self.col = col
        super().__init__(f"{line}:{col}: {msg}")

def lex_with_recovery(src):
    pos, line, col = 0, 1, 1
    while pos < len(src):
        ch = src[pos]
        try:
            tok, npos = scan_one(src, pos, line, col)
            yield tok
            pos = npos
        except LexError as e:
            print(f"warning: {e}")
            pos += 1            # 跳过非法字符
            col += 1