2

ブールクエリの次の文法があるとします。

 Query     := <Atom> [ <And-Chain> | <Or-Chain> ]
 Atom      := "(" <Query> ")" | <Var> <Op> <Var> 
 And-Chain := "&&" <Atom> [ <And-Chain> ]
 Or-Chain  := "||" <Atom> [ <Or-Chain> ] 
 Var       := "A" | "B" | "C" | ... | "Z"
 Op        := "<" | ">" | "="

この文法のパーサーには、次の疑似コードがあります。

 parse(query) :=
   tokens <- tokenize(query)
   parse-query(tokens)
   assert-empty(tokens)

 parse-query(tokens) :=
   parse-atom(tokens)
   if peek(tokens) equals "&&" 
     parse-chain(tokens, "&&")
   else if peek(tokens) equals "||"
     parse-chain(tokens, "||")

 parse-atom(tokens) :=
   if peek(tokens) equals "("
     assert-equal( "(", shift(tokens) )
     parse-query(tokens)
     assert-equal( ")", shift(tokens) )
   else
     parse-var(tokens)
     parse-op(tokens)
     parse-var(tokens)

 parse-chain(tokens, connector) :=
   assert-equal( connector, shift(tokens) )
   parse-atom(tokens)
   if peek(tokens) equals connector
      parse-chain(tokens, connector)

 parse-var(tokens) :=
   assert-matches( /[A-Z]/, shift(tokens) )

 parse-op(tokens) :=
   assert-matches( /[<>=]/, shift(tokens) )

ただし、確認したいのは、パーサーが有用な解析エラーを報告することです。たとえば、で始まるクエリの場合、次の"( A < B && B < C || ..."ようなエラーが必要です。

found "||" but expected "&&" or ")"

これの秘訣は、パーサーのさまざまな部分から期待値を収集することです。これを行う方法を考え出すことはできますが、すべてが少しぎこちなく感じられます。

同様に、Java ではGreedyError、"&&" または "||" を覗こうとするとa をスローすることがあります。

// in parseAtom
if ( tokens.peek() == "(" ) {
    assertEqual( "(", tokens.shift() );
    try {
        parseQuery(tokens);
        caught = null;
    }
    catch (GreedyError e) {
        caught = e;
    }
    try { 
        assertEqual( ")", tokens.shift() );
    }
    catch (AssertionError e) {
        throw e.or(caught);
    }
}
// ...
// in parseChain
assertEqual( connector, tokens.shift() );
parseAtom(tokens);
if (tokens.peek() == connector) {
    parseChain(tokens, connector);
}
else {
    new GreedyError(connector);
}

または、Haskell ではWriterT、現在のトークンの最後の失敗した比較を追跡するために を使用し、censorトークンの一致が成功するたびに消去するために を使用するかもしれません。

しかし、これらのソリューションはどちらも、少しハックされていて扱いにくいと感じます。これをエレガントに処理できる基本的なパターン、パターンが欠けているように感じます。それは何ですか？

4

1 に答える 1

1

L(AL)R(1) ステート マシンを構築します。LALR の詳細については、こちらを参照してください。

エラー報告に使用したいのは、各状態のドットに設定された FIRSTOF です。この答えは、パーサーの状態がどのように生成されるかを理解している場合に意味があります。

このような一連の状態がある場合は、各状態で FIRSTOF セットの結合を記録できます。次に、その状態で遷移が不可能な場合、エラーメッセージは「Exepect (firstof currentstate)」です。

FIRST セットを記録したくない場合は、状態テーブルをたどって再構築するアルゴリズムを簡単に作成できます。それは、「先をのぞく」のアルゴリズムに相当します。

于 2013-03-13T02:09:58.193 に答える