2

私は、書き換え規則の RHS に 1 つの非終端記号のみを含む任意の文法 (例: S -> aaSb | aaSa | aSa) に対して、トップダウン バックトラッキング パーサーを実装するプロジェクトを割り当てられました。

mainこれまでのところ、入力文字列の有効性のチェックを処理するために使用される を含む 3 つのメソッドがあります。

私の目標はchar[][]、文法の配列を使用して、入力文字列の各文字を文法に対してチェックし、true文字列が文法に含まれているかどうかを返すことです。

public class TDBP {
    public static void main(String[] args) {
        char[][] g = new char[][] 
            { {'a', 'a', 'S', 'b'}, 
              {'a', 'a', 'S', 'a'}, 
              {'a', 'S', 'a'}, 
              {'\0'} };

        SP(g);
    }
    public static void SP(char[][] g) {
        Scanner s = new Scanner(System.in);
        boolean again = true; int pn = 0;
        String test;

        while(again) {
            System.out.print("Next string? ");
            test = s.nextLine();

            if(S(pn, test, g))
                System.out.println("String is in the language");
            else
                System.out.println("String is not in the language");

            if(s.nextLine() == "\n") again = false;
        }

        s.close();
    }
    public static boolean S(int pn, String test, char[][] g) {
        char[] c = test.toCharArray();
        boolean exists = false;

        for(int i = pn; i < g.length; i++) {
            for(int j = 0; j < g[i].length; j++) {
                if(c[j] == 'S')
                    S(++pn, test, g);
                if(c[j] == g[i][j])
                    exists = true;
            }
        }

        return exists;
    }
}

私のアルゴリズムでpnは、現在見ている文法のどの生成を追跡し、同じ文法を 2 回スキャンしないようにするための整数です (たとえば、pn上記の文法の 1 は に対応しaaSaます)。また、\0空の文字列を表しています。

文字列を正しく解析していますか?

ありがとうございました！

4

2 に答える 2

2

これは、再帰降下のトップダウン解析を使用して、より簡単な方法で解決できます。

あなたのグラマーが

S -> aaSb | ああさ | アサ | # # は空の文字列を表します。

左因数分解後、次のようになります

S  -> aS' | #
S' -> aSS" | Sa
S" -> b | a

次に、各ルールを個別のメソッドで定義し、以下に示すように再帰的に呼び出します。

最初のルール: S -> aS' | #

function S(char[] input, int &i) {
     if(input[i]=='a') {
       i++;
       return S1(input, i);
      } 
      return true;   //For empty string
}

2 番目のルール: S' -> aSS" | Sa

function s1(char[] input, int &i) {
    if(input[i]=='a') {
       i++;
       S(input, i);
       return S2(input, i);
    } else {
       S(input, i);
       if(input[i]=='a') {
          return true;
       } else {
          return false;
       }
    }
}

このように 3 番目の関数も定義します (i は参照渡しでなければならないことに注意してください)。

詳細については、トップダウンの解析チュートリアルを参照できます。Uはこれも参照できます。

これが役立つことを願っています。

于 2014-11-26T15:23:37.640 に答える
1

私はCSクラスに少し慣れていません:しかし、次のコードは私にとってはうまくいきました:

public static boolean fullCheck(char[] toTest, char[][] g) {
    int val = checkOnAll(0, toTest, g);

    if (val == toTest.length) {
        return true;
    }
    return false;
}

public static int checkOnAll(int charPos, char[] toTest, char[][] g) {
    for(int i = 0; i < g.length; i++) {
        int val = checkOne(charPos, toTest, g[i], g);
        if (val != -1) {
            return val;
        }
    }
    return -1;
}

//also needs length checks
public static int checkOne(int charPos, char[] toTest, char[] rule, char[][] rules) {
    for(int j = 0; j < rule.length; j++) {
        if (charPos >= toTest.length) {
            return -1;
        }
        if(rule[j] == 'S') {
            int value = checkOnAll(charPos, toTest, rules);
            if (value == -1) {
                return -1;
            } else {
                charPos = value - 1;
            }
        } else if (toTest[charPos] != rule[j]) {
            return -1;
        }
        charPos++;
    }
    return charPos;
}

「S」関数の代わりに、fullCheck 関数を使用します (入力を char 配列として新しいメソッドに渡します)。また、「g」配列を次のように変更しました。

        char[][] g = new char[][]
            { {'a', 'a', 'S', 'b'},
              {'a', 'a', 'S', 'a'},
              {'a', 'S', 'a'},
              {} };

（「\ 0」は長さのチェックで問題を引き起こしました。上記の変更が最も簡単な解決策でした）。

私はあなたのコードにいくつかの問題を見つけました.私自身のコードにバグがないかどうかは完全にはわかりません.無視されます。2. 「pn」は、ルール char ではなく、どのテスト char にあるかを知ることに制限する必要があります。3. 返された値が true の場合でも、テスト文字列の一部だけでなく、テスト文字列全体を確認する必要があります。私はあなたがそうするのを見ませんでした。4. 非常に長いルールが 1 つあるのに入力が短い場合、テスト文字列の長さをまったく確認しないため、範囲外の例外が発生する可能性があります。

さまざまな入力で独自のコードを試してみましたが、何かを見逃しているような気がしますが、見つけることができませんでした。問題を見つけたら、私に知らせてください:)

幸運を。

于 2014-11-24T16:43:51.100 に答える