java实现递归下降分析 pl/0 语法分析器

递归下降分析是一种自顶向下的语法分析方法，它可以用来构建 LL(1) 语法分析器。下面是一个简单的 Java 实现，用于分析 PL/0 语法：

import java.util.*;

public class Parser {
    private final Scanner scanner;
    private Token lookahead;

    public Parser(Scanner scanner) {
        this.scanner = scanner;
        lookahead = scanner.nextToken();
    }

    private void match(TokenType expected) {
        if (lookahead.getType() == expected) {
            lookahead = scanner.nextToken();
        } else {
            throw new RuntimeException("Syntax error: expected " + expected + ", found " + lookahead.getType());
        }
    }

    public void parse() {
        program();
        match(TokenType.EOF);
    }

    private void program() {
        block();
    }

    private void block() {
        match(TokenType.BEGIN);
        statement();
        while (lookahead.getType() == TokenType.SEMICOLON) {
            match(TokenType.SEMICOLON);
            statement();
        }
        match(TokenType.END);
    }

    private void statement() {
        if (lookahead.getType() == TokenType.IDENTIFIER) {
            match(TokenType.IDENTIFIER);
            match(TokenType.ASSIGN);
            expression();
        } else if (lookahead.getType() == TokenType.IF) {
            match(TokenType.IF);
            condition();
            match(TokenType.THEN);
            statement();
            if (lookahead.getType() == TokenType.ELSE) {
                match(TokenType.ELSE);
                statement();
            }
        } else if (lookahead.getType() == TokenType.WHILE) {
            match(TokenType.WHILE);
            condition();
            match(TokenType.DO);
            statement();
        } else if (lookahead.getType() == TokenType.CALL) {
            match(TokenType.CALL);
            match(TokenType.IDENTIFIER);
        } else if (lookahead.getType() == TokenType.BEGIN) {
            block();
        } else {
            throw new RuntimeException("Syntax error: unexpected token " + lookahead.getType());
        }
    }

    private void condition() {
        expression();
        if (lookahead.getType() == TokenType.EQUAL || lookahead.getType() == TokenType.NOT_EQUAL ||
                lookahead.getType() == TokenType.LESS_THAN || lookahead.getType() == TokenType.LESS_THAN_OR_EQUAL ||
                lookahead.getType() == TokenType.GREATER_THAN || lookahead.getType() == TokenType.GREATER_THAN_OR_EQUAL) {
            match(lookahead.getType());
            expression();
        } else {
            throw new RuntimeException("Syntax error: expected a relational operator, found " + lookahead.getType());
        }
    }

    private void expression() {
        term();
        while (lookahead.getType() == TokenType.PLUS || lookahead.getType() == TokenType.MINUS) {
            match(lookahead.getType());
            term();
        }
    }

    private void term() {
        factor();
        while (lookahead.getType() == TokenType.TIMES || lookahead.getType() == TokenType.SLASH) {
            match(lookahead.getType());
            factor();
        }
    }

    private void factor() {
        if (lookahead.getType() == TokenType.IDENTIFIER) {
            match(TokenType.IDENTIFIER);
        } else if (lookahead.getType() == TokenType.NUMBER) {
            match(TokenType.NUMBER);
        } else if (lookahead.getType() == TokenType.LPAREN) {
            match(TokenType.LPAREN);
            expression();
            match(TokenType.RPAREN);
        } else {
            throw new RuntimeException("Syntax error: expected an identifier, number, or left parenthesis, found " + lookahead.getType());
        }
    }
}

在这个实现中，我们使用了 `Scanner` 类来读取 PL/0 源代码并生成 `Token` 流。`Token` 类表示 PL/0 中的一个词法单元，它包含一个 `TokenType` 和一个 `value`。`TokenType` 是一个枚举类型，它包含了所有 PL/0 中可能出现的词法单元类型，例如 `IDENTIFIER`、`NUMBER`、`PLUS`、`MINUS` 等等。

`Parser` 类的构造函数接受一个 `Scanner` 对象作为参数，并初始化 `lookahead` 指针，它指向下一个要分析的 `Token`。`match` 方法用于比较 `lookahead` 和 `expected` 是否相等，如果不相等，则抛出一个语法错误异常。`parse` 方法是语法分析器的入口，它调用 `program` 方法来分析整个 PL/0 程序，并期望最后一个 `Token` 是 `EOF`。

`program` 方法实现了 PL/0 中的 `program` 产生式，它只包含一个 `block`。`block` 方法实现了 `block` 产生式，它包含了多个语句，以 `BEGIN` 开始，以 `END` 结束。`statement` 方法实现了 `statement` 产生式，它包含了多种类型的语句，例如赋值语句、条件语句、循环语句、过程调用语句等等。`condition` 方法实现了 PL/0 中的条件表达式，它包含了一个关系运算符和两个表达式。`expression` 方法实现了 PL/0 中的算术表达式，它包含了加减运算符和多个项。`term` 方法实现了 PL/0 中的项，它包含了乘除运算符和多个因子。`factor` 方法实现了 PL/0 中的因子，它可以是一个标识符、一个数字或一个表达式。

这个实现中最重要的部分是 `match` 方法和各个产生式方法中的 `match` 调用。这些调用用于比较 `lookahead` 和期望的 `Token` 是否相等，并将 `lookahead` 指针向前移动。如果 `Token` 不匹配，则抛出一个语法错误异常。这些 `match` 调用的目的是消除左递归，从而使我们的语法分析器成为递归下降分析器。