编译器是将高级编程语言翻译为机器可执行代码的核心系统软件。一个典型的编译器分为前端和后端：前端负责词法分析、语法分析和语义分析，将源代码转换为中间表示；后端负责代码优化和目标代码生成。本文将用Java实现一个简化版编译器前端，能够解析算术表达式并计算结果，涵盖词法分析器的正则匹配、递归下降语法分析器的文法推导，以及抽象语法树（AST）的构建与求值。
编译器前端架构
编译器前端通常包含三个阶段：
- 词法分析（Lexical Analysis）：将源代码字符流切分为有意义的词法单元（Token），如标识符、关键字、运算符、常量等
- 语法分析（Syntax Analysis）：根据文法规则将Token序列组织成语法树，检查语法正确性
- 语义分析（Semantic Analysis）：检查类型一致性、变量声明等语义规则
本文实现一个表达式编译器，支持加减乘除、括号优先级和变量赋值。
Java实现
import java.util.*;
import java.util.regex.*;
/**
* 简化版编译器前端实现
* 支持算术表达式词法分析、递归下降语法解析与AST求值
*/
public class ExpressionCompiler {
// ==================== 词法分析器 ====================
/**
* 词法单元类型
*/
enum TokenType {
NUMBER, // 数字常量
IDENTIFIER, // 标识符（变量名）
PLUS, // +
MINUS, // -
MULTIPLY, // *
DIVIDE, // /
ASSIGN, // =
LPAREN, // (
RPAREN, // )
SEMICOLON, // ;
EOF // 文件结束
}
/**
* 词法单元
*/
static class Token {
TokenType type;
String value;
int position;
Token(TokenType type, String value, int position) {
this.type = type;
this.value = value;
this.position = position;
}
public String toString() {
return String.format("Token(%s, '%s', pos=%d)", type, value, position);
}
}
/**
* 词法分析器：将输入字符串转换为Token列表
*/
static class Lexer {
private String input;
private int pos;
// 正则表达式匹配各类型Token
private static final Pattern NUMBER_PATTERN = Pattern.compile("^[0-9]+(\\.[0-9]+)?");
private static final Pattern IDENTIFIER_PATTERN = Pattern.compile("^[a-zA-Z_][a-zA-Z0-9_]*");
public Lexer(String input) {
this.input = input;
this.pos = 0;
}
public List<Token> tokenize() {
List<Token> tokens = new ArrayList<>();
while (pos < input.length()) {
char ch = input.charAt(pos);
// 跳过空白字符
if (Character.isWhitespace(ch)) {
pos++;
continue;
}
// 匹配数字
Matcher numMatcher = NUMBER_PATTERN.matcher(input.substring(pos));
if (numMatcher.find()) {
String num = numMatcher.group();
tokens.add(new Token(TokenType.NUMBER, num, pos));
pos += num.length();
continue;
}
// 匹配标识符
Matcher idMatcher = IDENTIFIER_PATTERN.matcher(input.substring(pos));
if (idMatcher.find()) {
String id = idMatcher.group();
tokens.add(new Token(TokenType.IDENTIFIER, id, pos));
pos += id.length();
continue;
}
// 匹配单字符Token
switch (ch) {
case '+': tokens.add(new Token(TokenType.PLUS, "+", pos)); pos++; break;
case '-': tokens.add(new Token(TokenType.MINUS, "-", pos)); pos++; break;
case '*': tokens.add(new Token(TokenType.MULTIPLY, "*", pos)); pos++; break;
case '/': tokens.add(new Token(TokenType.DIVIDE, "/", pos)); pos++; break;
case '=': tokens.add(new Token(TokenType.ASSIGN, "=", pos)); pos++; break;
case '(': tokens.add(new Token(TokenType.LPAREN, "(", pos)); pos++; break;
case ')': tokens.add(new Token(TokenType.RPAREN, ")", pos)); pos++; break;
case ';': tokens.add(new Token(TokenType.SEMICOLON, ";", pos)); pos++; break;
default:
throw new RuntimeException("未知字符 '" + ch + "' 在位置 " + pos);
}
}
tokens.add(new Token(TokenType.EOF, "", pos));
return tokens;
}
}
// ==================== 语法分析与AST ====================
/**
* AST节点基类
*/
abstract static class ASTNode {
abstract double evaluate(Map<String, Double> variables);
}
static class NumberNode extends ASTNode {
double value;
NumberNode(double value) { this.value = value; }
double evaluate(Map<String, Double> variables) { return value; }
}
static class VariableNode extends ASTNode {
String name;
VariableNode(String name) { this.name = name; }
double evaluate(Map<String, Double> variables) {
if (!variables.containsKey(name)) {
throw new RuntimeException("未定义的变量: " + name);
}
return variables.get(name);
}
}
static class BinaryOpNode extends ASTNode {
ASTNode left, right;
TokenType op;
BinaryOpNode(ASTNode left, TokenType op, ASTNode right) {
this.left = left; this.op = op; this.right = right;
}
double evaluate(Map<String, Double> variables) {
double l = left.evaluate(variables);
double r = right.evaluate(variables);
switch (op) {
case PLUS: return l + r;
case MINUS: return l - r;
case MULTIPLY: return l * r;
case DIVIDE:
if (r == 0) throw new RuntimeException("除零错误");
return l / r;
default: throw new RuntimeException("未知运算符: " + op);
}
}
}
static class AssignmentNode extends ASTNode {
String varName;
ASTNode expr;
AssignmentNode(String varName, ASTNode expr) {
this.varName = varName; this.expr = expr;
}
double evaluate(Map<String, Double> variables) {
double value = expr.evaluate(variables);
variables.put(varName, value);
return value;
}
}
/**
* 递归下降语法分析器
* 文法规则：
* program -> statement* EOF
* statement -> assignment | expr
* assignment -> IDENTIFIER '=' expr
* expr -> term (('+' | '-') term)*
* term -> factor (('*' | '/') factor)*
* factor -> NUMBER | IDENTIFIER | '(' expr ')'
*/
static class Parser {
private List<Token> tokens;
private int pos;
public Parser(List<Token> tokens) {
this.tokens = tokens;
this.pos = 0;
}
private Token current() { return tokens.get(pos); }
private Token advance() { return tokens.get(pos++); }
private boolean match(TokenType... types) {
for (TokenType t : types) {
if (current().type == t) { pos++; return true; }
}
return false;
}
private Token expect(TokenType type) {
if (current().type != type) {
throw new RuntimeException("期望 " + type + " 但在位置 " + current().position + " 得到 " + current().type);
}
return advance();
}
public List<ASTNode> parse() {
List<ASTNode> statements = new ArrayList<>();
while (current().type != TokenType.EOF) {
statements.add(parseStatement());
if (current().type == TokenType.SEMICOLON) advance();
}
return statements;
}
private ASTNode parseStatement() {
// 尝试解析赋值语句：identifier = expr
if (current().type == TokenType.IDENTIFIER && peek().type == TokenType.ASSIGN) {
String name = advance().value;
advance(); // 消费 '='
ASTNode expr = parseExpr();
return new AssignmentNode(name, expr);
}
return parseExpr();
}
private Token peek() {
return pos + 1 < tokens.size() ? tokens.get(pos + 1) : tokens.get(tokens.size() - 1);
}
private ASTNode parseExpr() {
ASTNode node = parseTerm();
while (match(TokenType.PLUS, TokenType.MINUS)) {
TokenType op = tokens.get(pos - 1).type;
ASTNode right = parseTerm();
node = new BinaryOpNode(node, op, right);
}
return node;
}
private ASTNode parseTerm() {
ASTNode node = parseFactor();
while (match(TokenType.MULTIPLY, TokenType.DIVIDE)) {
TokenType op = tokens.get(pos - 1).type;
ASTNode right = parseFactor();
node = new BinaryOpNode(node, op, right);
}
return node;
}
private ASTNode parseFactor() {
Token token = current();
if (match(TokenType.NUMBER)) {
return new NumberNode(Double.parseDouble(token.value));
}
if (match(TokenType.IDENTIFIER)) {
return new VariableNode(token.value);
}
if (match(TokenType.LPAREN)) {
ASTNode node = parseExpr();
expect(TokenType.RPAREN);
return node;
}
throw new RuntimeException("意外的Token: " + token);
}
}
// ==================== 执行器 ====================
/**
* 执行AST并返回结果
*/
public static double execute(String code) {
// 1. 词法分析
Lexer lexer = new Lexer(code);
List<Token> tokens = lexer.tokenize();
System.out.println("词法分析结果: " + tokens);
// 2. 语法分析
Parser parser = new Parser(tokens);
List<ASTNode> ast = parser.parse();
// 3. 语义分析与求值
Map<String, Double> variables = new HashMap<>();
double result = 0;
for (ASTNode node : ast) {
result = node.evaluate(variables);
}
System.out.println("变量状态: " + variables);
return result;
}
public static void main(String[] args) {
// 测试表达式解析与求值
String[] testCases = {
"3 + 4 * 2",
"(1 + 2) * (3 + 4)",
"10 / 2 + 3 * 4",
"a = 5; a * 2 + 3",
"x = 10; y = 20; x + y * 2"
};
for (String code : testCases) {
System.out.println("\n输入: " + code);
try {
double result = execute(code);
System.out.println("结果: " + result);
} catch (Exception e) {
System.out.println("错误: " + e.getMessage());
}
}
}
}
文法与递归下降解析
本文使用的表达式文法是一种典型的上下文无关文法（CFG），采用EBNF（扩展巴科斯范式）描述：
expr = term { ("+" | "-") term }
term = factor { ("*" | "/") factor }
factor = number | identifier | "(" expr ")"
递归下降分析器为每个非终结符编写一个对应的解析函数，函数之间通过递归调用来处理嵌套结构。这种实现方式直观易懂，且天然支持运算符优先级：乘法/除法在term层解析，加法/减法在expr层解析，括号在factor层解析，因此 * 和 / 天然具有比 + 和 - 更高的优先级。
复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 词法分析 | $O(n)$ | $O(n)$（Token列表） |
| 语法分析 | $O(n)$ | $O(h)$（递归栈深度） |
| AST求值 | $O(n)$ | $O(h)$ |
其中 $n$ 为输入字符串长度，$h$ 为AST树高。整个编译器前端的时间复杂度为线性 $O(n)$，效率极高。
扩展方向
本文实现的表达式编译器可扩展为完整编译器：增加条件语句（if/else）、循环语句（while/for）、函数定义与调用、类型系统（int/double/bool）、以及中间代码生成（三地址码或LLVM IR）。理解递归下降解析的核心思想后，学习更复杂的LR/LALR分析器（如Yacc/Bison）或现代编译器框架（如ANTLR）将变得更加容易。
