1. 简介
词法分析（Lexical analysis），也称为词法扫描（lexing）或扫描（scanning），是编译过程的第一个阶段。 它将字符序列转换为称为token（标记）的有意义单元，这些token是后续语法分析和语义分析的构建块。
本教程将探讨词法分析的基础知识，并用Java构建一个简单的算术词法分析器。一个设计良好的词法分析器通过将原始输入结构化为明确定义的token，能显著提升编译器的效率和可维护性。
2. 什么是词法分析器？
词法分析器（lexer）读取字符流，并将其组织称为词素（lexeme）的单元。
词素是匹配token模式的原始字符序列。将词素值与附加数据结合就形成了token——一个分类元素，如关键字、运算符或字面量。换句话说，token是词素的结构化表示，包含类型和可选属性值。
例如，表达式"1 + 2"中的词素是"1"、"+"和"2"。词法分析器将其分类并生成以下token：NUMBER(1)、OPERATOR(+)和NUMBER(2)。
下面我们将构建一个简单的算术词法分析器来演示这种方法。
3. 构建算术词法分析器
首先，需要定义词法分析器的范围。
词法分析器应能识别整数和算术运算符：+、–、*和/。Grammar枚举包含所有支持的符号，并提供字符分类的实用方法：
private enum Grammar {
ADDITION('+'),
SUBTRACTION('-'),
MULTIPLICATION('*'),
DIVISION('/');
private final char symbol;
Grammar(char symbol) {
this.symbol = symbol;
}
public static boolean isOperator(char character) {
return Arrays.stream(Grammar.values())
.anyMatch(grammar -> grammar.symbol == character);
}
public static boolean isDigit(char character) {
return Character.isDigit(character);
}
public static boolean isWhitespace(char character) {
return Character.isWhitespace(character);
}
public static boolean isValidSymbol(char character) {
return isOperator(character) || isWhitespace(character) || isDigit(character);
}
}
接下来，将输入字符串包装到简单的Expression工具类中。它允许词法分析器逐个迭代表达式中的字符。此外，hasNext()方法检查表达式中是否还有待处理的字符：
public class Expression {
private final String value;
private int index = 0;
public Expression(String value) {
this.value = value != null ? value : "";
}
public Optional<Character> next() {
if (index >= value.length()) {
return Optional.empty();
}
return Optional.of(value.charAt(index++));
}
public boolean hasNext() {
return index < value.length();
}
// 标准getter
}
最后，创建Token类。我们可以创建单个Token类，或选择抽象基类和两个具体实现（一个用于数字，一个用于运算符）。尽管我们的词法分析器相对简单，但后者提供了更清晰的结构，且在未来需要支持多种token类型时更易于扩展。
它还提供了灵活性，可以添加特定于token的方法来处理每种类型特有的行为，例如将值转换为不同格式或计算运算符优先级：
public abstract class Token {
private final String value;
private final TokenType type;
protected Token(TokenType type, String value) {
this.type = type;
this.value = value;
}
public TokenType getType() {
return type;
}
public String getValue() {
return value;
}
}
public class TokenNumber extends Token {
protected TokenNumber(String value) {
super(TokenType.NUMBER, value);
}
public int getValueAsInt() {
return Integer.parseInt(getValue());
}
}
public class TokenOperator extends Token {
protected TokenOperator(String value) {
super(TokenType.OPERATOR, value);
}
}
至此，我们可以创建词法分析的主类了。
4. Lexer类
首先构建tokenize()方法，它处理输入表达式并生成token列表。该方法需要从输入中逐个字符读取，直到能识别出下一个词素并为其生成token。
为简化，我们不允许输入字符串以运算符开头，即有效表达式的第一个字符必须是数字。换句话说，所有运算符都将被视为右结合。
构建词法分析器有多种方法，下面探讨几种。
4.1. 有限状态机（FSM）词法分析器
可以使用状态机构建词法分析器。 创建State枚举来跟踪词法分析的当前状态：
private enum State {
INITIAL,
NUMBER,
OPERATOR,
INVALID
}
INITIAL是起始状态。此时词法分析器期望数字、运算符或空白字符。如果是空白字符，则继续处理下一个字符。如果遇到数字，状态将切换到NUMBER，表示正在处理单个或多个数字组成的数字。
同样，OPERATOR状态表示正在处理运算符。此外，必须添加检查以确保表达式不以OPERATOR开头。最后一个状态处理无效字符或与有效token模式不匹配的意外符号：
public List<Token> tokenize(Expression expression) {
State state = State.INITIAL;
StringBuilder currentToken = new StringBuilder();
ArrayList<Token> tokens = new ArrayList<>();
while (expression.hasNext()) {
final Character currentChar = getValidNextCharacter(expression);
switch (state) {
case INITIAL:
if (Grammar.isWhitespace(currentChar)) {
break;
} else if (Grammar.isDigit(currentChar)) {
state = State.NUMBER;
currentToken.append(currentChar);
} else if (Grammar.isOperator(currentChar) && !tokens.isEmpty()) { // 确保表达式不以OPERATOR开头
state = State.OPERATOR;
currentToken.append(currentChar);
} else {
state = State.INVALID;
currentToken.append(currentChar);
}
break;
case NUMBER:
if (Grammar.isDigit(currentChar)) {
currentToken.append(currentChar);
} else {
tokens.add(new TokenNumber(currentToken.toString()));
currentToken.setLength(0);
state = State.INITIAL;
}
break;
case OPERATOR:
tokens.add(new TokenOperator(currentToken.toString()));
currentToken.setLength(0);
state = State.INITIAL;
continue;
case INVALID:
throw new InvalidExpressionException(String.format(MESSAGE_ERROR, currentToken));
}
}
finalizeToken(state, currentToken, tokens);
return tokens;
}
在NUMBER状态下，词法分析器要么继续将数字附加到现有token（对于多位数），要么创建新token并重置状态。由于本例中没有多字符运算符（如自增或自减运算符），OPERATOR状态的唯一转换是到INITIAL，这也包括创建新的TokenOperator。
finalizeToken()方法确保在输入结束时正确处理最后一个token。如果词法分析器以有效的NUMBER状态结束，则将token添加到列表中。否则，如果以INVALID或OPERATOR状态结束，则抛出异常表示词法分析错误：
private static void finalizeToken(State state, StringBuilder currentToken, ArrayList<Token> tokens) {
if (State.INVALID == state || State.OPERATOR == state) {
throw new InvalidExpressionException(String.format(MESSAGE_ERROR, currentToken));
} else if (State.NUMBER == state) {
tokens.add(new TokenNumber(currentToken.toString()));
}
}
基于正则表达式的方法是FSM词法分析器的替代方案，适用于更简单的场景。
4.2. 正则表达式词法分析器
要定义使用正则表达式对输入字符串进行词法分析的词法分析器，首先需要定义必要的正则表达式：
private static final String NUMBER_REGEX = "\\d+";
private static final String OPERATOR_REGEX = "[+\\-*/]";
private static final String WHITESPACE_REGEX = "\\s+";
private static final String VALID_EXPRESSION_REGEX = "^(" + NUMBER_REGEX + "(" + OPERATOR_REGEX + NUMBER_REGEX + ")*|" + NUMBER_REGEX + " )$";
private static final Pattern TOKEN_PATTERN = Pattern.compile(NUMBER_REGEX + "|" + OPERATOR_REGEX + "|" + WHITESPACE_REGEX);
我们还将数字、运算符和空白的正则表达式组合为单个模式。tokenize()方法使用Matcher在输入字符串中查找这些模式的匹配项，并创建相应的token（TokenNumber或TokenOperator）：
public List<Token> tokenize(Expression expression) {
List<Token> tokens = new ArrayList<>();
Matcher matcher = TOKEN_PATTERN.matcher(expression.getValue());
if (!expression.getValue()
.matches(VALID_EXPRESSION_REGEX)) {
throw new InvalidExpressionException(String.format(MESSAGE_ERROR, expression));
}
while (matcher.find()) {
String match = matcher.group();
createToken(match).ifPresent(tokens::add);
}
return tokens;
}
private static Optional<Token> createToken(String match) {
if (match.matches(NUMBER_REGEX)) {
return Optional.of(new TokenNumber(match));
} else if (match.matches(OPERATOR_REGEX)) {
return Optional.of(new TokenOperator(match));
} else if (match.matches(WHITESPACE_REGEX)) {
return Optional.empty();
} else {
throw new InvalidExpressionException(String.format(MESSAGE_ERROR, match));
}
}
如果match是空白字符，则忽略；如果不匹配任何有效模式，则抛出自定义的InvalidExpressionException。
5. 测试词法分析器
现在测试我们的词法分析器。通过修改测试类中的字段，可以轻松切换不同实现。 为验证词法分析器在遇到无效输入时抛出异常，我们将创建参数化测试并提供一组错误表达式：
private final Lexer lexer = new LexerFsm();
@ParameterizedTest
@ValueSource(strings = { "1 + 2 $ 3", "1 - 2 #", "- 1 + 2", "+ 1 2" })
void givenInputContainsInvalidCharacters_whenTokenize_thenExceptionThrown(String input) {
assertThrows(Exception.class, () -> lexer.tokenize(new Expression(input)));
}
测试通过，因为提供的值都不是有效表达式。
接下来，使用简单表达式检查词法分析器是否返回正确的token：
@Test
void givenInputIsSimpleExpression_whenTokenize_thenValidTokensIsReturned() {
String input = "3 + 50";
List<Token> tokens = lexer.tokenize(new Expression(input));
assertAll(() -> assertEquals(3, tokens.size(), "Token数量不匹配"),
() -> assertToken(tokens.get(0), TokenType.NUMBER, "3"),
() -> assertToken(tokens.get(1), TokenType.OPERATOR, "+"),
() -> assertToken(tokens.get(2), TokenType.NUMBER, "50"));
}
private void assertToken(Token token, TokenType expectedType, String expectedValue) {
assertAll(() -> assertEquals(expectedType, token.getType(), "Token类型不匹配"),
() -> assertEquals(expectedValue, token.getValue(), "Token值不匹配"));
}
首先检查token数量是否匹配预期数量。然后使用assertToken()辅助方法断言每个token具有正确的类型和值。最后验证第一个token是数字"3"，第二个是运算符"+"，第三个是数字"50"。
最后，确保词法分析器正确处理空字符串：
@Test
void givenInputIsEmptyExpression_whenTokenize_thenEmptyListIsReturned() {
String input = "";
List<Token> tokens = lexer.tokenize(new Expression(input));
assertTrue(tokens.isEmpty(), "输入表达式为空时词法分析器应返回空列表");
}
此测试验证当输入表达式为空时，词法分析器正确返回空列表。 同时检查空输入不会生成任何token。
6. 结论
本文介绍了词法分析的概念，并演示了如何用Java构建简单的算术词法分析器。我们使用FSM和正则表达式方法实现了词法分析器，以说明对输入进行词法分析的不同方式。
后者简单有效，适用于处理数字和运算符等简单token模式。另一方面，FSM提供了更大的灵活性，更适合处理复杂任务，例如区分不同类型的运算符或管理嵌套结构。
最后，我们查看了一组基本测试，以确保词法分析器正常工作。