语法分析器实现方案全解

# 文法（已消除左递归）：
# expr   → term (('+' | '-') term)*
# term   → factor (('*' | '/') factor)*
# factor → NUMBER | '(' expr ')'

from dataclasses import dataclass
from typing import Union

@dataclass
class BinOp:
    op: str
    left: Union['BinOp', int]
    right: Union['BinOp', int]

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

    def peek(self):
        return self.tokens[self.pos] if self.pos < len(self.tokens) else None

    def consume(self, expected=None):
        tok = self.peek()
        if expected and tok != expected:
            raise SyntaxError(f"期望 {expected}，但得到 {tok}")
        self.pos += 1
        return tok

    def parse_expr(self):             # expr → term (('+' | '-') term)*
        left = self.parse_term()
        while self.peek() in ('+', '-'):
            op = self.consume()
            left = BinOp(op, left, self.parse_term())
        return left

    def parse_term(self):             # term → factor (('*' | '/') factor)*
        left = self.parse_factor()
        while self.peek() in ('*', '/'):
            op = self.consume()
            left = BinOp(op, left, self.parse_factor())
        return left

    def parse_factor(self):           # factor → NUMBER | '(' expr ')'
        tok = self.peek()
        if isinstance(tok, int):
            return self.consume()
        elif tok == '(':
            self.consume('(')
            node = self.parse_expr()    # 递归调用！
            self.consume(')')
            return node
        raise SyntaxError(f"意外的 token: {tok}")
    

// 文件名：Expr.g4 — 算术表达式文法
grammar Expr;

// Parser 规则（小写开头）
prog   : stat+ ;
stat   : expr NEWLINE
       | ID '=' expr NEWLINE
       | NEWLINE ;
expr   : expr ('*'|'/') expr   // 乘除（高优先级）
       | expr ('+'|'-') expr   // 加减（低优先级）
       | '(' expr ')'
       | INT
       | ID ;

// Lexer 规则（大写开头）
ID      : [a-zA-Z]+ ;
INT     : [0-9]+ ;
NEWLINE : '\r'? '\n' ;
WS      : [ \t]+ -> skip ;
  

# 生成 Python 版解析器
antlr4 -Dlanguage=Python3 -visitor Expr.g4

# 生成 Java 版（默认）
antlr4 -visitor Expr.g4

# 支持语言：Java / Python3 / Go / C# / C++ / Swift / JS / TypeScript...

from antlr4 import *
from ExprLexer import ExprLexer
from ExprParser import ExprParser

class EvalVisitor(ExprVisitor):
    def visitExpr(self, ctx):
        if ctx.INT():
            return int(ctx.INT().getText())
        left  = self.visit(ctx.expr(0))
        op    = ctx.getChild(1).getText()
        right = self.visit(ctx.expr(1))
        return {'+': left+right, '-': left-right,
                '*': left*right, '/': left//right}[op]

input_stream = InputStream("3 + 4 * 2\n")
parser       = ExprParser(CommonTokenStream(ExprLexer(input_stream)))
print(EvalVisitor().visit(parser.prog()))  # → 11

%{
/* C 头文件引用 */
#include <stdio.h>
#include <stdlib.h>
int yylex(void);
void yyerror(const char *);
%}

/* 声明运算符优先级（从低到高）*/
%left '+' '-'
%left '*' '/'
%right UMINUS  /* 一元负号，最高优先级 */

%%

/* 产生式规则 */
input :                        /* 空 */
      | input line ;

line  : '\n'
      | expr '\n'   { printf("= %d\n", $1); } ;

expr  : expr '+' expr    { $$ = $1 + $3; }
      | expr '-' expr    { $$ = $1 - $3; }
      | expr '*' expr    { $$ = $1 * $3; }
      | expr '/' expr    { $$ = $3 ? $1/$3 : (yyerror("除零错误"),0); }
      | '(' expr ')'    { $$ = $2; }
      | '-' expr %prec UMINUS  { $$ = -$2; }
      | NUM             { $$ = $1; } ;
%%

use nom::{branch::alt, bytes::complete::tag,
           character::complete::{digit1, space0},
           combinator::map, sequence::delimited, IResult};

#[derive(Debug)]
enum Expr { Num(i64), Add(Box<Expr>, Box<Expr>) }

// 解析数字
fn parse_num(i: &str) -> IResult<&str, Expr> {
    map(digit1, |s: &str| Expr::Num(s.parse().unwrap()))(i)
}

// 解析加法 "num + num"（组合子无缝拼接）
fn parse_add(i: &str) -> IResult<&str, Expr> {
    let (i, left)  = parse_num(i)?;
    let (i, _)     = delimited(space0, tag("+"), space0)(i)?;
    let (i, right) = parse_num(i)?;
    Ok((i, Expr::Add(Box::new(left), Box::new(right))))
}

// 最终入口：先尝试加法，再尝试纯数字
fn parse_expr(i: &str) -> IResult<&str, Expr> {
    alt((parse_add, parse_num))(i)
}

from lark import Lark, Transformer

grammar = r"""
    expr: expr "+" term  -> add       // 有序选择，无歧义
        | term
    term: term "*" atom  -> mul
        | atom
    atom: NUMBER         -> number
        | "(" expr ")"

    NUMBER: /[0-9]+/
    %ignore /\s+/
"""

class Calc(Transformer):
    def add(self, items): return items[0] + items[1]
    def mul(self, items): return items[0] * items[1]
    def number(self, items): return int(items[0])

parser = Lark(grammar, start='expr', parser='earley')
print(Calc().transform(parser.parse("3 + 4 * 2")))  # → 11