2

テーブル駆動の LR(1) パーサーをコーディングしましたが、非常にうまく機能していますが、解析を構文ツリー/抽象構文ツリーに変換する段階で少し切断されています。これは私が非常に情熱を注いでいるプロジェクトですが、ここで行き詰まりを迎えました。よろしくお願いいたします。

編集: また、私のパーサーは、2 次元配列とアクション オブジェクトを使用して、次に移動する場所や、移動先とポップするアイテムの数を減らすかどうかを指示します。多くの人がビジターパターンを使用していることに気付きました。彼らがどのタイプのノードを作成するかをどのように知っているかわかりません。

コンテキストのプッシュダウンオートマトンは次のとおりです

 while (lexer.hasNext() || parseStack.size() > 0) {
        Action topOfStack = parseStack.peek();
        token = parseStack.size() > 0 ? lexer.nextToken() : new Token(TokenType.EOF, "EOF");
        topOfStack.setToken(token);

        int row = topOfStack.getTransitionIndex();
        int column = getTerminalIndex(token.getLexeme());

        column = token.getType() == TokenType.IDENTIFIER
                && !terminalsContain(token.getLexeme()) ? 0 : column;

        Action action = actionTable[row][column];

        if (action instanceof Accept) {
            System.out.println("valid parse!!!!!!");
        } else if (action instanceof Reduction) {
            Reduction reduction = (Reduction) action;

            popStack(parseStack, reduction.getNumberOfItemsToPop());
            column = reduction.getTransitionIndex();
            row = parseStack.peek().getTransitionIndex();

            parseStack.push(new Action(gotoTable[row][column]));
            lexer.backupTokenStream();
        } else if (action != null) {
            parseStack.push(actionTable[row][column]);
        } else {
            System.out.println("Parse error");
            System.out.println("On token: " + token.getLexeme());
            break;
        }
4

1 に答える 1

3

LR 解析プロセスの各縮小は、解析ツリーの内部ノードに対応します。削減されるルールは内部 AST ノードであり、スタックからポップされた項目はその内部ノードの子に対応します。goto でプッシュされたアイテムは内部ノードに対応し、shift アクションによってプッシュされたアイテムは AST のリーフ (トークン) に対応します。

これらすべてをまとめると、リダクションを行うたびに新しい内部ノードを作成し、すべてを適切に接続することで、簡単に AST を構築できます。

于 2015-05-25T20:47:21.747 に答える