3

我试图弄清楚从哪里开始这个项目。也许有人可以引导我朝着正确的方向前进。

我得到了一种小语言，我必须为其编写解释器。该语言由括号中的表达式组成：

(integer integer operator)

或由以下形式的表达式组成的算术 IF 语句：

IF exp1 exp2 exp3 exp4

其中，如果 exp1 为负数，则返回 exp2，如果 exp1 为零，则返回 exp3，如果 exp1 为正数，则返回 exp4。

运算符是 + 或 x（分别用于加法和乘法）。

我必须一起实现一个扫描器/解析器，然后是输出结果的解释器。解释器部分并不难，但我无法弄清楚如何开始扫描/解析过程。

我从使用 Java 开始，并让 Scanner 对象收集输入并将其存储在字符串中。然后我将字符串拆分为一个字符串数组，不使用任何内容作为分隔符（这样每个字符、符号、空格等都存储在它自己的字符串索引中）。这可能不是最好的方法，因为我不知道从这里去哪里。我无法掌握的部分是如果不遵循此语法如何返回错误，或者如何检测括号和/或 IF 等。

这是我在上一段中描述的代码片段：

public void run() {
    Scanner sc = new Scanner(System.in);

    while (sc.hasNext()) {
        String sLine = sc.nextLine();
        String[] scanned = sLine.split("");

输入示例：

(7 2 +)

Output: 9

IF (2 -2 +) (5 2 +) (5 -2 x) (5 2 x)

Output: -10

如果有人对我有好的方向，请分享。:)

4

4 回答 4

3

您可以使用基于堆栈的算法来处理后缀表达式。一个简单的想法是将整数压入堆栈，当遇到运算符时，从堆栈中弹出整数并执行运算符提到的操作，如 + ， - 。

于 2013-01-30T05:01:32.033 回答
3

我认为使用 ANTLR、JavaCC、SampleCC 或其他解析器生成器工具将使用大锤来破解坚果。如果语法定义中没有递归，那么几个方法就足够了。以下代码给出了一个基本思路（它可能无法编译或工作，我从头开始编写它作为说明如何开始）：

public int parse(String input) {
Scanner scanner = new Scanner(input);

    return consumeLine(scanner);
}

public int consumeLine(Scanner scanner) {
    if( scanner.hasNext("(") ) {
        return consumeExpression(scanner);

    } else if( scanner.hasNext("IF") ) {
        return consumeIf(scanner);
    }
}


public int consumeExpression(Scanner scanner) {
    scanner.next("(");
    int a = scanner.nextInt();
    int b = scanner.nextInt();
    String op = scanner.next("[+-/*]");
    scanner.next(")");

    if( "+".equals(op) ) {
        return a + b;

    } else if( "-".equals(op) ) {
        return a - b;
    } ...

    throw new RuntimeException("parsing error");
}

public int consumeIf(Scanner scanner) {
    scanner.next("IF");
    int exp1 = consumeExpression(scanner);
    int exp2 = consumeExpression(scanner);
    int exp3 = consumeExpression(scanner);
    int exp4 = consumeExpression(scanner);

    if( exp1 < 0 ) {
        return exp2;
    } else if( exp1 == 0 ) {
        return exp3;
    } ...

    throw new RuntimeException("should not be here (TM)");
}
于 2013-01-30T05:47:23.563 回答
1

如果您喜欢 java，使用 javacc 很容易。您可以以紧凑和简单的方式提及您的令牌以及如何处理它们，然后在编译它时，它会在 java 源代码中生成执行逻辑所需的所有代码。

javacc 简介

javacc 常见问题

于 2013-01-30T04:35:54.973 回答
0

我建议你使用 C++ 和 boost 精神库....

于 2013-01-30T04:54:43.443 回答