java - 私の文法のための再帰的子孫パーサーを書く

Question

Recursive Descendent Parser Builder を使用して式を作成する必要があります。

これが私の文法です：

----RULES----
<cond> → <termb> [OR <termb>]*
<termb>→&lt;factb>[AND <factb>]*
<factb>→&lt;expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → [PLUS | MINUS] <term> [(PLUS <term>) | (MINUS <term>)]*
<term> → <termp> [(MULT <termp>) | (DIV <termp>) | (REM <termp>)]*
<termp> → <fact> [POWER <fact>]*
<fact> → ID | NUM | OPAR1 <expr> CPAR1
----TERMINALS----
ID → ("A" | ... | "Z" | "a" | ...| "z") [("A"| ... | "Z" | "a" | ...| "z" | "0" | ... | "9")]*
NUM → ("0" | ... | "9") [("0" | ... | "9")]*
OPAR → "("
CPAR → ")"
OPAR1 → "["
CPAR1 → "]"
RELOP → EQ | NEQ | GT | GE | LT | LE
EQ → "= ="
NEQ → "!="
GT → ">"
GE → ">="
LT → "<"
LE → "<="
POWER → "^"
DIV → "/"
REM → "%"
MULT → "*"
MINUS → "−"
PLUS → "+"
AND → “and” or “&amp;&”
OR → “or” or “||”
NOT → “not” or “!”

これで、端末ごとに 1 つのクラスを持つ Composite 構造ができました。上記の文法の規則に従って構築しようとしています。

アイデアは、文法規則ごとにメソッドが必要であり、このメソッドのそれぞれが式ツリーの一部を構築する必要があるということです。

より単純な文法 (たとえば、ブール式のみを許可する文法) で動作しますが、これにはいくつか問題があります。

主な問題はexpr、 + と - の単項バージョンでさえ、 のような式を許可することで作業を強制する規則から来てい+3-4ます。これには、オペランドを単項と見なす必要がある場合と、2 項と見なす必要がある場合を見つける必要があります。

これが私の Builder クラスのコードです。何かがイタリア語で書かれていることに注意してください。コメントを使用して、私の問題を含め、すべてを説明しました。また、疑似コードを使用した行が 1 行あるため、これはコンパイルできません。

package espressioniCondizionali;

import espressioniCondizionali.espressioni.*;

/**
 *
 * @author Stefano
 */
public class Builder6 {

    /**
     * This one is used just to parse the input String.
     * It has a prossimoSimbolo() method (something like a nextSymbol()) that returns a String with the next Symbol in the String
     */
    private GestoreInput gestoreInput;
    /**
     * Espressione is the Composite structure that represents and expression
     */
    private Espressione root = null;
    private String symbol = null;

    public Builder6(GestoreInput gestoreInput) {
        this.gestoreInput = gestoreInput;
    }

    public Espressione build() {
        buildCond();
        return root;
    }

    private void buildCond() {
        buildTermb();
        //I'm unsing a class named Simboli that holds every terminal symbol of my grammar. Symbol names are the same defined in the grammar.
        while (symbol.equalsIgnoreCase(Simboli.OR1) || symbol.equalsIgnoreCase(Simboli.OR2)) {
            Or or = new Or();
            or.setLeft(root);
            buildTermb();
            or.setRight(root);
            root = or;
        }
    }

    private void buildTermb() {
        buildFactb();
        while (symbol.equalsIgnoreCase(Simboli.AND1) || symbol.equalsIgnoreCase(Simboli.AND2)) {
            And and = new And();
            and.setLeft(root);
            buildFactb();
            and.setRight(root);
            root = and;
        }
    }

    private void buildFactb() {
        buildExpr();
        if (symbol.equalsIgnoreCase(Simboli.EQ) || symbol.equalsIgnoreCase(Simboli.NEQ) || symbol.equalsIgnoreCase(Simboli.GT) || symbol.equalsIgnoreCase(Simboli.LT) || symbol.equalsIgnoreCase(Simboli.LE) || symbol.equalsIgnoreCase(Simboli.GE)) {
            Operatore op = null;
            switch (symbol) {
                case Simboli.EQ: {
                    op = new Eq();
                    break;
                }
                case Simboli.NEQ: {
                    op = new Neq();
                    break;
                }
                case Simboli.GT: {
                    op = new Gt();
                    break;
                }
                case Simboli.GE: {
                    op = new Ge();
                    break;
                }
                case Simboli.LT: {
                    op = new Lt();
                    break;
                }
                case Simboli.LE: {
                    op = new Le();
                    break;
                }
                default: {
                    //Symbol not recognized, abort!
                    throw new RuntimeException("\"" + symbol + "\" non è un simbolo valido.");
                }
            }
            op.setLeft(root);
            buildExpr();
            op.setRight(root);
            root = op;
        } else if (symbol.equalsIgnoreCase(Simboli.NOT1) || symbol.equals(Simboli.NOT2)) {
            Not not = new Not();
            buildFactb();
            not.setRight(root);
            root = not;
        } else if (symbol.equalsIgnoreCase(Simboli.OPAR)) {
            buildCond();
            if (!symbol.equalsIgnoreCase(Simboli.CPAR)) { //If there's no closgin square bracket it means that our expression is not well formed
                throw new RuntimeException("Espressione non valida. Attesa una \")\", trovato \"" + symbol + "\"");
            }
        }
    }

    private void buildExpr() {
        Operatore op = null;
        if (symbol != null) { //Let's check if our expression starts with a + or a -
            if (symbol.equalsIgnoreCase(Simboli.PLUS)) {
                op = new Plus();
            } else if (symbol.equalsIgnoreCase(Simboli.MINUS)) {
                op = new Minus();
            }
        }
        buildTerm();
        //If our op is still null, we didn't found a + or a - so our operand will be a binary one
        //If op != null, our + or - is unary and we've got to manage it! A unary operand doesn't have a left son!
        if (op != null) {
            op.setRight(root);
            root = op;
        }
        //Since we can have something like -3+2+s-x we've got to check it
        while (symbol.equalsIgnoreCase(Simboli.PLUS) || symbol.equalsIgnoreCase(Simboli.MINUS)) {
            Operatore op1 = null; //We define a new Operatore that will be a + or a -
            switch (symbol) {
                case Simboli.PLUS: {
                    op1 = new Plus();
                    break;
                }
                case Simboli.MINUS: {
                    op1 = new Minus();
                    break;
                }
            }
            /*
             * Here comes a BIG problem. We used the first if/else to check if
             * our unary operand was at the beginning of the string, but now
             * we've got to see if our current operand is either binary or
             * unary! That's because we can have both a==-1+d and a==3-1+d. In
             * the first case, the - is unary, while is binary in the second.
             * So, how do we choose it?
             * 
             * EXAMPLE : (-a>2 || -b-12>0)
             * This one will be evaluated to -a > 2 || -12 > 0 that's clearly wrong!
             * -b is missing before -12. That's because the -12 is used as unary 
             * and so it won't have a left child (the -b part)
             */
            //--PSEUDOCODE
            if (op1 is not unary) {
                op1.setLeft(root);
            }
            //--END PSEUDOCODE
            //CURRENT IMPLEMENTATION OF THE PSEUDOCODE PART
            if (root != null && (root.getClass().equals(Num.class) || root.getClass().equals(Id.class))) { //It is binary if the previous value is a constant or a variable but not if it is an operand!                  
                op1.setLeft(root);
            }
            //END OF CURRENT IMPLEMENTATION OF THE PSEUDOCODE PART
            //Setting the right child must be done in both cases
            buildTerm();
            op1.setRight(root);
            root = op1;
        }
    }

    private void buildTerm() {
        buildTermp();
        while (symbol.equalsIgnoreCase(Simboli.MULT) || symbol.equalsIgnoreCase(Simboli.DIV) || symbol.equalsIgnoreCase(Simboli.REM)) {
            Operatore op = null;
            switch (symbol) {
                case Simboli.MULT: {
                    op = new Mult();
                    break;
                }
                case Simboli.DIV: {
                    op = new Div();
                    break;
                }
                case Simboli.REM: {
                    op = new Rem();
                    break;
                }
            }
            op.setLeft(root);
            buildTermp();
            op.setRight(root);
            root = op;
        }
    }

    private void buildTermp() {
        buildFact();
        while (symbol.equalsIgnoreCase(Simboli.POWER)) {
            Power p = new Power();
            p.setLeft(root);
            buildFact();
            p.setRight(root);
            root = p;
        }
    }

    private void buildFact() {
        symbol = gestoreInput.prossimoSimbolo();
        if (symbol.equalsIgnoreCase(Simboli.OPAR1)) { //Sottoespressione            
            buildExpr();
            if (!symbol.equalsIgnoreCase(Simboli.CPAR1)) { //Se non c'è una parentesi chiusa vuol dire che l'espressione non valida
                throw new RuntimeException("Espressione non valida. Attesa una \"]\", trovato \"" + symbol + "\"");
            }
        } else if (symbol.matches("[A-Za-z][A-Za-z | 0-9]*")) { //Nome di una variabile!
            root = new Id(symbol);
            symbol = gestoreInput.prossimoSimbolo();
        } else if (symbol.matches("[0-9]*")) { //E' una costante!
            root = new Num(symbol);
            symbol = gestoreInput.prossimoSimbolo();
        }
    }
}

既知の問題:

(a<=b && c>1) || a==4に評価されますa <= b && c > 1

a==[-4]に評価されますa == a - 4

-4+3>c-2に評価されます+3 > c - 2

おそらく他にもいくつかのエラーがありますが、それらは最も一般的なエラーです。

だからここに私の質問があります：

まず、このコードには論理的な問題があると思いますか? つまり、文法が言うことをするのでしょうか、それとも私は何か本当に間違ったことをしましたか? expr単項およびバイナリ + または - オペランドの両方で機能するようにメソッドをどのように修正しますか?

私のコードが完全に間違っている場合、動作するバージョンを書くのを手伝ってくれる人はいますか? クラス名からわかるように、これは私が作成した6 番目の実装であり、次に何をすべきか本当にわかりません!

ありがとう。

Answer 1

ステップ1：文法について別の方法で考える

文法が非常に複雑なため、再帰下降パーサーの実装に問題があると思います。フォームによって表される任意の反復は[ ... ]*、頭を包み込むのが難しいです。代わりに、このように考えてみてください。

<cond> → <termb> <cond-tail>
<cond-tail> → OR <termb> <cond-tail> | EPSILON
<termb> → <factb> <termb-tail>
<termb-tail> → AND <factb> <termb-tail> | EPSILON
<factb> → <expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → <unary-op> <term> <expr-tail>
<unary-op> → PLUS | MINUS | EPSILON
<expr-tail> → ((PLUS <term>) | (MINUS <term>)) <expr-tail> | EPSILON
<term> → <termp> <term-tail>
<term-tail> → ((MULT <termp>) | (DIV <termp>) | (REM <termp>)) <term-tail> | EPSILON
<termp> → <fact> <termp-tail>
<termp-tail> → POWER <fact> <termp-tail> | EPSILON
<fact> → ID | NUM | OPAR1 <expr> CPAR1
EPSILON → ""

この文法はあなたが投稿したものと同じですが、私は[ ... ]*ルールをそれら自身の非終端記号に分割しました。EPSILONこれを行うために、非終端記号が一致することを許可するルール""（空の文字列）を追加しました。これは基本的に[ ... ]ルールと同じであり、実際に何かに一致する場合と一致しない場合があります。イプシロンルールは、「今すぐ一致させようとするのをやめる」という最後の選択肢にすぎません。たとえば、現在aを解析している場合cond-tailは、最初に入力のをチェックしORます。が表示されない場合はOR、次の選択肢であるに進みますEPSILON。つまりOR、この条件付きチェーンにはこれ以上条件がないため、これcond-tailは空の文字列と一致します。

expr-tail演算子をとでグループ化することにより、文法をさらに単純化できますterm-tail。

<cond> → <termb> <cond-tail>
<cond-tail> → OR <termb> <cond-tail> | EPSILON
<termb> → <factb> <termb-tail>
<termb-tail> → AND <factb> <termb-tail> | EPSILON
<factb> → <expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → <unary-op> <term> <expr-tail>
<unary-op> → PLUS | MINUS | EPSILON
<expr-tail> → (PLUS | MINUS) <term> <expr-tail> | EPSILON
<term> → <termp> <term-tail>
<term-tail> → (MULT | DIV | REM) <termp> <term-tail> | EPSILON
<termp> → <fact> <termp-tail>
<termp-tail> → POWER <fact> <termp-tail> | EPSILON
<fact> → ID | NUM | OPAR1 <expr> CPAR1
EPSILON → ""

ここで、戻ってソリューションをリファクタリングし、新しいルールごとに新しいメソッドを追加する必要があります。（代わりに、新しいルールのコードを元のルールのままにすることを選択できますが、コードのどの部分が何を実行しているかを追跡するのに役立つように、少なくとも異なるセクションにコメントを明確にマークしてください。）

これで、新しいメソッド（文法の新しいルールに対応）によって解析されるため、どの場合+に-単項演算子であるかが非常に明確になります。buildUnaryOpunary-op

新しい*-tailルールについては、厳密に再帰的に実装するか、長い式でスタックを吹き飛ばすことが心配な場合は、関数本体内でループを使用して実装するかを選択できます。

ステップ2：状態追跡を修正する

これがここでの主な問題です。

/**
 * Espressione is the Composite structure that represents and expression
 */
private Espressione root = null;
private String symbol = null;

インスタンスレベルのフィールドを使用して、再帰下降パーサーの状態を格納しています。メソッドのreturn-typeがvoid-少なくとも実際に抽象構文ツリーを構築している場合はそうではない、再帰下降パーサーを見たことがありません。ウィキペディアの例にはvoidreturn-typesがありますが、これは、実際に入力からASTを構築するのではなく、入力をチェックして結果を破棄するだけだからです。

状態をクラスレベルのフィールドに保存しているため、兄弟の呼び出しごとにフィールドが上書きされbuildExpr()、データが失われます。それはとにかく私の理論です。exprのようなsの長い文字列を作成することでテストできます"1+2+3+4+5"。最終的にすべての用語を前面に表示する必要があります。

パーサーを機能的に（メソッドを使用せずに.set*()）構築することをお勧めします。各build*()メソッドは、ASTから解析されたノードを返します。これには、子ノードを受け入れるようにすべてのコンストラクターを変更することが含まれます。ただし、それがより明確な場合は、代わりにミューテーションを使用できます。これがリファクタリングされたものbuildCondです：

private Espressione buildCond() {
      Espressione leftHandSide = buildTermb();
      if (symbol.equalsIgnoreCase(Simboli.OR1) || symbol.equalsIgnoreCase(Simboli.OR2)) {
          Or or = new Or();
          or.setLeft(leftHandSide);
          or.setRight(buildTermb());
          return or;
      }
      return leftHandSide;
  }

新しいものは次のbuild()ようになります。

public Espressione build() {
    return buildCond();
}

（インスタンスレベルのフィールドを使用して状態を保持するのではなく）この方法でツリーを構築するためにコードの残りの部分を作り直すと、はるかにうまく機能するはずです。

幸運を！