在 Java 中建立詞法分析器
1. 簡介
詞法分析（也稱為 lexing 或掃描）是編譯過程的第一階段。它將一系列字元轉換為有意義的單元（稱為標記），這些單元是進一步進行句法和語義分析的基礎。
在本教程中，我們將探討詞法分析的基礎知識並用 Java 建立一個簡單的算術詞法分析器。精心設計的詞法分析器透過將原始輸入構造成明確定義的標記來提高編譯器的效率和可維護性。
2.什麼是詞法分析器？
詞法分析器或詞法分析器讀取字元流並將它們組織成稱為詞素的單元。
詞素是與標記模式相符的原始字元序列。將這些附加資料與詞素值結合會建立一個標記 - 一個分類元素，例如關鍵字、運算子或文字。換句話說，標記是詞素的結構化表示，由類型和可選的屬性值組成。
舉例來說，表達式「1 + 2」中的詞素是「1」、「+」和「2」。詞法分析器對這些進行分類並產生以下標記：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();
}
// standard getter
}最後，我們將建立一個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()方法。此方法需要從輸入中逐個字元讀取，直到能夠識別下一個詞素並為其產生標記。
為了簡單起見，我們不允許輸入字串以運算子開頭，這意味著有效表達式的第一個字元必須是數字。換句話說，所有運算子都將被視為右邊結合的。
建構詞法分析器的方法有很多種，我們來探索其中幾種。
4.1.有限狀態機 (FSM) 詞法分析器
我們可以使用狀態機構建詞法分析器。我們將建立一個State枚舉來追蹤標記化的當前狀態：
private enum State {
INITIAL,
NUMBER,
OPERATOR,
INVALID
}INITIAL狀態是起始狀態。這裡，詞法分析器需要一個數字、一個運算子或一個空格。如果是空格，則繼續處理下一個字元。如果詞法分析器遇到數字，它會將狀態移到NUMBER ，表示處理單一或一系列數字，形成一個數字。
同樣， OPERATOR狀態表示詞法分析器正在處理操作符。此外，我們必須新增檢查以確保沒有表達式以OPERATOR開頭。最後一種狀態處理與有效標記模式不符的無效字元或意外符號：
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()) { // to ensure there are no expressions starting with an 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狀態下，詞法分析器將繼續將數字附加到現有標記（對於多位數字的情況）或建立新標記並重設狀態。由於在我們的範例中沒有多字元運算符（例如增量或減量運算子），因此從OPERATOR狀態的唯一轉換是到INITIAL ，其中還包括建立一個新的TokenOperator 。
finalizeToken()方法確保詞法分析器在輸入結束時正確處理最後一個標記。如果詞法分析器以有效的NUMBER狀態結束，它會將該標記新增到清單中。否則，如果它以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在輸入字串中尋找這些模式的符合項目並建立對應的標記（ 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)));
}測試通過，因為提供的值都不是有效的表達式。
接下來，讓我們使用一個簡單的表達式檢查詞法分析器是否會回傳正確的標記：
@Test
void givenInputIsSimpleExpression_whenTokenize_thenValidTokensIsReturned() {
String input = "3 + 50";
List<Token> tokens = lexer.tokenize(new Expression(input));
assertAll(() -> assertEquals(3, tokens.size(), "Token count mismatch"),
() -> 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 type mismatch"),
() -> assertEquals(expectedValue, token.getValue(), "Token value mismatch"));
}首先，我們檢查令牌數是否與預期的令牌數相符。然後，我們使用assertToken()輔助方法斷言每個標記都有正確的類型和值。最後，我們驗證第一個標記是數字“ 3 ”，第二個標記是運算符“ + ”，第三個標記是數字“ 50 ”。
最後，讓我們確保我們的詞法分析器正確處理空字串：
@Test
void givenInputIsEmptyExpression_whenTokenize_thenEmptyListIsReturned() {
String input = "";
List<Token> tokens = lexer.tokenize(new Expression(input));
assertTrue(tokens.isEmpty(), "Lexer should return an empty list when the input expression is empty");
}此測試驗證當輸入表達式為空時，詞法分析器是否正確傳回空列表。它還檢查是否為空輸入產生任何標記。
6. 結論
在本文中，我們學習了詞法分析的概念，並示範如何在 Java 中建立一個簡單的算術詞法分析器。我們使用 FSM 和 Regex 方法實作了詞法分析器，以說明標記輸入的不同方式。
後者對於處理簡單的標記模式（例如數字和運算子）非常直接且有效。另一方面， FSM 提供了更大的靈活性，更適合處理複雜的任務，例如區分不同類型的運算子或管理巢狀結構。
最後，我們進行了一組基本測試以確保我們的詞法分析器正常運作。
與往常一樣，完整的源代碼可在 GitHub 上取得。