1
# 一个简单的算术表达式文法
2
# E → E + T | E - T | T
3
# T → T * F | T / F | F
4
# F → ( E ) | NUMBER | IDENT
5

6
# 用 Python 表示文法
7
grammar = {
8
    'E': [['E', '+', 'T'], ['E', '-', 'T'], ['T']],
9
    'T': [['T', '*', 'F'], ['T', '/', 'F'], ['F']],
10
    'F': [['(', 'E', ')'], ['NUMBER'], ['IDENT']],
11
}

1
# 歧义文法：E → E + E | E * E | NUMBER
2
# 输入：3 + 4 * 5
3

4
# 推导 1：(3 + 4) * 5 = 35
5
# 推导 2：3 + (4 * 5) = 23  ← 数学上正确

1
# 左递归（适合左结合运算符）
2
E → E + T | T
3

4
# 右递归（适合右结合运算符，如赋值）
5
E → T + E | T
6

7
# 左递归的问题：递归下降分析器会无限递归！
8
# 解决：消除左递归
9
# E → T E'
10
# E' → + T E' | ε

1
# 消除左递归的算法
2
def eliminate_left_recursion(grammar):
3
    """消除文法的直接左递归"""
4
    new_grammar = {}
5
    for A in grammar:
6
        # 分离左递归和非左递归产生式
7
        left_rec = [prod for prod in grammar[A] if prod[0] == A]
8
        non_left_rec = [prod for prod in grammar[A] if prod[0] != A]
9

10
        if left_rec:
11
            # 创建新的非终结符 A'
12
            A_prime = A + "'"
13
            new_grammar[A] = [prod + [A_prime] for prod in non_left_rec]
14
            new_grammar[A_prime] = [prod[1:] + [A_prime] for prod in left_rec] + [['ε']]
15
        else:
16
            new_grammar[A] = grammar[A]
17

18
    return new_grammar

1
from dataclasses import dataclass
2
from typing import Union
3

4
# AST 节点定义
5
@dataclass
6
class NumberLit:
7
    value: int
8

9
@dataclass
10
class Identifier:
11
    name: str
12

13
@dataclass
14
class BinaryOp:
15
    op: str
16
    left: 'Expr'
17
    right: 'Expr'
18

19
# 其他节点类型遵循相同模式（UnaryOp、CallExpr、VarDecl、ReturnStmt、Block、FuncDecl 等）
20

21
Expr = Union[NumberLit, Identifier, BinaryOp]
22

23
class Parser:
24
    def __init__(self, tokens):
25
        self.tokens = tokens
26
        self.pos = 0
27

28
    def _peek(self):
29
        if self.pos < len(self.tokens):
30
            return self.tokens[self.pos]
31
        return Token(TokenType.EOF, '', 0, 0)
32

33
    def _advance(self):
34
        token = self._peek()
35
        self.pos += 1
36
        return token
37

38
    def _expect(self, token_type):
39
        token = self._advance()
40
        if token.type != token_type:
41
            raise SyntaxError(
42
                f"Expected {token_type}, got {token.type} "
43
                f"'{token.value}' at {token.line}:{token.col}"
44
            )
45
        return token
46

47
    def _match(self, *token_types):
48
        if self._peek().type in token_types:
49
            return self._advance()
50
        return None
51

52
    # 表达式解析（算符优先）
53
    def parse_expr(self) -> Expr:
54
        return self._parse_comparison()
55

56
    def _parse_comparison(self) -> Expr:
57
        left = self._parse_addition()
58
        while self._peek().type in (TokenType.LT, TokenType.GT,
59
                                     TokenType.EQ, TokenType.NEQ):
60
            op = self._advance().value
61
            right = self._parse_addition()
62
            left = BinaryOp(op, left, right)
63
        return left
64

65
    def _parse_addition(self) -> Expr:
66
        left = self._parse_multiplication()
67
        while self._peek().type in (TokenType.PLUS, TokenType.MINUS):
68
            op = self._advance().value
69
            right = self._parse_multiplication()
70
            left = BinaryOp(op, left, right)
71
        return left
72

73
    def _parse_multiplication(self) -> Expr:
74
        left = self._parse_unary()
75
        while self._peek().type in (TokenType.STAR, TokenType.SLASH):
76
            op = self._advance().value
77
            right = self._parse_unary()
78
            left = BinaryOp(op, left, right)
79
        return left
80

81
    def _parse_unary(self) -> Expr:
82
        if self._peek().type == TokenType.MINUS:
83
            self._advance()
84
            operand = self._parse_unary()
85
            return UnaryOp('-', operand)
86
        return self._parse_primary()
87

88
    def _parse_primary(self) -> Expr:
89
        token = self._peek()
90
        if token.type == TokenType.INTEGER:
91
            self._advance()
92
            return NumberLit(int(token.value))
93
        elif token.type == TokenType.IDENTIFIER:
94
            self._advance()
95
            if self._peek().type == TokenType.LPAREN:
96
                return self._parse_call(token.value)
97
            return Identifier(token.value)
98
        elif token.type == TokenType.LPAREN:
99
            self._advance()  # (
100
            expr = self.parse_expr()
101
            self._expect(TokenType.RPAREN)  # )
102
            return expr
103
        else:
104
            raise SyntaxError(
105
                f"Unexpected token {token.type} '{token.value}' "
106
                f"at {token.line}:{token.col}"
107
            )
108

109
    def _parse_call(self, func_name: str) -> CallExpr:
110
        self._expect(TokenType.LPAREN)
111
        args = []
112
        if self._peek().type != TokenType.RPAREN:
113
            args.append(self.parse_expr())
114
            while self._match(TokenType.COMMA):
115
                args.append(self.parse_expr())
116
        self._expect(TokenType.RPAREN)
117
        return CallExpr(func_name, args)

1
# LL(1) 预测分析表
2
# 文法：
3
# E  → T E'
4
# E' → + T E' | ε
5
# T  → F T'
6
# T' → * F T' | ε
7
# F  → ( E ) | NUMBER
8

9
predict_table = {
10
    ('E', '('):  ['T', "E'"],
11
    ('E', 'NUMBER'): ['T', "E'"],
12
    ("E'", '+'): ['+', 'T', "E'"],
13
    ("E'", ')'): ['ε'],
14
    ("E'", '$'): ['ε'],
15
    ('T', '('):  ['F', "T'"],
16
    ('T', 'NUMBER'): ['F', "T'"],
17
    ("T'", '*'): ['*', 'F', "T'"],
18
    ("T'", '+'): ['ε'],
19
    ("T'", ')'): ['ε'],
20
    ("T'", '$'): ['ε'],
21
    ('F', '('):  ['(', 'E', ')'],
22
    ('F', 'NUMBER'): ['NUMBER'],
23
}

1
# 简化的 LR 分析器
2
def lr_parse(tokens, action_table, goto_table):
3
    stack = [0]  # 状态栈
4
    pos = 0
5

6
    while True:
7
        state = stack[-1]
8
        token = tokens[pos]
9

10
        action = action_table.get((state, token.type))
11

12
        if action is None:
13
            raise SyntaxError(f"Syntax error at {token}")
14

15
        if action[0] == 'shift':
16
            stack.append(token)
17
            stack.append(action[1])  # 新状态
18
            pos += 1
19

20
        elif action[0] == 'reduce':
21
            prod_len = action[2]  # 产生式右部长度
22
            non_terminal = action[1]  # 产生式左部
23
            # 弹出 2*prod_len 个元素
24
            for _ in range(2 * prod_len):
25
                stack.pop()
26
            state = stack[-1]
27
            stack.append(non_terminal)
28
            stack.append(goto_table[(state, non_terminal)])
29

30
        elif action[0] == 'accept':
31
            return "Parse successful!"

1
# 运算符优先级表
2
precedence = {
3
    ('+', '+'): '>', ('+', '-'): '>', ('+', '*'): '<', ('+', '/'): '<',
4
    ('-', '+'): '>', ('-', '-'): '>', ('-', '*'): '<', ('-', '/'): '<',
5
    ('*', '+'): '>', ('*', '-'): '>', ('*', '*'): '>', ('*', '/'): '>',
6
    ('/', '+'): '>', ('/', '-'): '>', ('/', '*'): '>', ('/', '/'): '>',
7
    # '$' 是结束标记
8
    ('$', '+'): '<', ('$', '*'): '<', ('+', '$'): '>', ('*', '$'): '>',
9
}
10

11
# '<' : 栈顶运算符优先级低，移进
12
# '>' : 栈顶运算符优先级高，归约
13
# '=' : 优先级相同（用于括号匹配）

1
class PrattParser:
2
    def __init__(self, tokens):
3
        self.tokens = tokens
4
        self.pos = 0
5

6
    # 绑定力度表：值越大优先级越高
7
    PREFIX_BP = {
8
        '-': 7, '!': 7,
9
    }
10

11
    INFIX_BP = {
12
        '=': (2, 1),   # 右结合：左绑定力 2，右绑定力 1
13
        '+': (5, 6),   # 左结合：左绑定力 5，右绑定力 6
14
        '-': (5, 6),
15
        '*': (7, 8),
16
        '/': (7, 8),
17
    }
18

19
    def parse_expr(self, min_bp=0):
20
        # 前缀操作
21
        left = self.parse_prefix()
22

23
        # 中缀操作
24
        while True:
25
            op = self._peek().value
26
            if op not in self.INFIX_BP:
27
                break
28
            (left_bp, right_bp) = self.INFIX_BP[op]
29
            if left_bp < min_bp:
30
                break
31
            self._advance()
32
            right = self.parse_expr(right_bp)
33
            left = BinaryOp(op, left, right)
34

35
        return left
36

37
    def parse_prefix(self):
38
        token = self._advance()
39
        if token.type == TokenType.INTEGER:
40
            return NumberLit(int(token.value))
41
        elif token.type == TokenType.IDENTIFIER:
42
            return Identifier(token.value)
43
        elif token.value in self.PREFIX_BP:
44
            bp = self.PREFIX_BP[token.value]
45
            operand = self.parse_expr(bp)
46
            return UnaryOp(token.value, operand)
47
        elif token.type == TokenType.LPAREN:
48
            expr = self.parse_expr(0)
49
            self._expect(TokenType.RPAREN)
50
            return expr
51
        else:
52
            raise SyntaxError(f"Unexpected token: {token}")

1
class ASTVisitor:
2
    """AST 访问者基类"""
3

4
    def visit(self, node):
5
        method_name = f'visit_{type(node).__name__}'
6
        method = getattr(self, method_name, self.generic_visit)
7
        return method(node)
8

9
    def generic_visit(self, node):
10
        raise NotImplementedError(
11
            f"No visit_{type(node).__name__} method"
12
        )
13

14
class PrettyPrinter(ASTVisitor):
15
    """AST 美化打印"""
16

17
    def visit_BinaryOp(self, node):
18
        left = self.visit(node.left)
19
        right = self.visit(node.right)
20
        return f"({left} {node.op} {right})"
21

22
    def visit_NumberLit(self, node):
23
        return str(node.value)
24

25
    def visit_Identifier(self, node):
26
        return node.name
27

28
    def visit_UnaryOp(self, node):
29
        operand = self.visit(node.operand)
30
        return f"({node.op}{operand})"
31

32
    def visit_VarDecl(self, node):
33
        init = f" = {self.visit(node.init)}" if node.init else ""
34
        return f"{node.type_name} {node.name}{init};"
35

36
# 使用
37
ast = VarDecl("int", "x", BinaryOp("+", NumberLit(3), NumberLit(4)))
38
printer = PrettyPrinter()
39
print(printer.visit(ast))  # int x = (3 + 4);

1
class ParserWithErrorRecovery(Parser):
2
    # 同步 Token 集合
3
    SYNC_TOKENS = {TokenType.SEMI, TokenType.RBRACE, TokenType.EOF}
4

5
    def _synchronize(self):
6
        """跳过 Token 直到遇到同步点"""
7
        while self._peek().type not in self.SYNC_TOKENS:
8
            self._advance()
9
        # 跳过同步 Token 本身
10
        if self._peek().type == TokenType.SEMI:
11
            self._advance()
12

13
    def parse_stmt(self):
14
        try:
15
            return super().parse_stmt()
16
        except SyntaxError as e:
17
            self.errors.append(e)
18
            self._synchronize()
19
            return None  # 返回空节点

1
# 安装 ANTLR
2
pip install antlr4-python3-runtime
3

4
# 创建语法文件
5
cat > Expr.g4 << 'EOF'
6
grammar Expr;
7

8
expr: expr ('*' | '/') expr
9
    | expr ('+' | '-') expr
10
    | NUMBER
11
    | IDENT
12
    | '(' expr ')'
13
    ;
14

15
NUMBER: [0-9]+;
16
IDENT:  [a-zA-Z_][a-zA-Z0-9_]*;
17
WS:     [ \t\r\n]+ -> skip;
18
EOF
19

20
# 生成 Python 解析器
21
antlr4 -Dlanguage=Python3 Expr.g4

1
# 使用上面的 Parser 类
2
from lexer import Lexer, TokenType
3

4
source = "int x = 3 + 4 * 5;"
5
lexer = Lexer(source)
6
tokens = lexer.tokenize()
7

8
parser = Parser(tokens)
9
ast = parser.parse_var_decl()
10
print(ast)  # VarDecl(type_name='int', name='x', init=BinaryOp(op='+', ...))

1
# 查看 Clang 的 AST 输出
2
cat > test.c << 'EOF'
3
int add(int a, int b) {
4
    return a + b;
5
}
6
EOF
7

8
clang -ast-dump test.c 2>/dev/null

1
import graphviz
2

3
def visualize_ast(node, dot=None, counter=[0]):
4
    if dot is None:
5
        dot = graphviz.Digraph()
6
        dot.attr(rankdir='TB')
7

8
    node_id = f"n{counter[0]}"
9
    counter[0] += 1
10

11
    if isinstance(node, BinaryOp):
12
        dot.node(node_id, f"BinaryOp\\n{node.op}")
13
        left_id = visualize_ast(node.left, dot, counter)
14
        right_id = visualize_ast(node.right, dot, counter)
15
        dot.edge(node_id, left_id)
16
        dot.edge(node_id, right_id)
17
    elif isinstance(node, NumberLit):
18
        dot.node(node_id, f"NumberLit\\n{node.value}")
19
    elif isinstance(node, Identifier):
20
        dot.node(node_id, f"Identifier\\n{node.name}")
21

22
    return node_id
23

24
# 使用
25
ast = BinaryOp('+', BinaryOp('*', NumberLit(4), NumberLit(5)), NumberLit(3))
26
dot = visualize_ast(ast)
27
dot.render('ast', format='png', cleanup=True)