3

例えば、

EBNF

A ::= B c;

B ::= T1 | T2 | ε

T1 ::= a

T2 ::= b

parseA()
{
switch(currentToken.kind){
case Token.a :
    parseT1();
case Token.b :
    parseT2();
break;

case <epsilon> :
    
break;
default:
    // report error
break;
}
}

Java でイプシロン (空の文字列のセット) を解析するパーサーの書き方は?

4

4 に答える 4

5

Javaであろうと他の言語であろうと、重要なのはトークンのストリームがあるということです。トークンを「取得」して何をするかを決めるのではありません。むしろ、次のトークンを「見て」、それを使用できる場合は、それを「受け入れ」ます。

違いを見ます？

「取得」してから「決定」しないでください。
「見て決定」してから「受け入れる」を行います。
これが「先読み」のコンセプトの核心です。

したがって、ParseAはParseBを呼び出します。

解析Bは、ストリーム内の次のトークンを調べます。
「a」の場合は、それを受け入れて戻ります。
「b」の場合は、それを受け入れて戻ります。
それ以外の場合は、（何も受け入れずに）単にParseAに戻ります。

次に、ParseAは次のトークンを調べます。
「c」の場合は、それを受け入れて戻ります。
それ以外の場合は失敗します。

わかる？

これを行うには、ストリームの最後に番兵トークンを追加する必要があります。これは決して受け入れられません。最後に、それがストリームに残っている唯一のトークンであるはずです。そうでない場合は、最後に余分なガベージで構成される構文エラーが発生します。

于 2010-07-31T19:13:39.267 に答える
4

epsilon「ここで許可されている空の文字列」のマーカーにすぎないため、何も解析する必要はありません。降下が終了しました。ただし、実際にそのためのトークンを持っている可能性は低いようです。利用可能なトークンがないかどうか、または次のトークンを別のプロダクションで使用できるかどうかを検出する必要があります。

たとえば、入力を取得する場合がありますc。これは production に一致することを認識する必要があります。これは、に還元できるA ::= B c;ためです。トークンはありません。B ルールはオプションであり、その場合は省略してに還元する必要があることを認識する必要があります。BepsilonepsiloncA

于 2010-07-31T18:20:02.667 に答える
3

現状では、これはパーサーとして非常に理にかなっているため、少し単純化されています。全体は単純な正規表現 "[ab]?c" で記述できます。どうしてもパーサーとして書きたい場合、コードは次のようになります。

Boolean parseA() { 
    // an A is a B followed by a `c`:
    return parseB() && (get_token() == Token.c);
}

Boolean parseB  {
    // Get a token. 
    //     If it's an `a` or a `b`, consume it. 
    //     Otherwise, throw it back (match null string by consuming nothing).
    // Either way, return true (successful match).
    //
    token current_token = get_token();
    if (token != Token.a && token != Token.b)
        push_back(current_token);
    return true;
}

編集（別の回答に対するコメントへの回答）：いいえ、Bに一致する場合は、Token.cを探すべきではありません。B が気にする限り、「a」に一致する、「b」に一致する、またはまったく一致しないという 3 つの可能性があります。次に、A を解析して、B の後に Token.c が続くことを確認する部分に任せます。

たとえば、文法を次のように変更するとします。

あ ::= 紀元前

B ::= a | b | ε

C ::= c | d

'B' の定義は同じなので、他の定義が変更されたからといって変更する必要はありません。同様に、(たとえば) B の後に C が続く任意の文字列を許可するように文法に追加することもできます。

于 2010-07-31T18:36:57.510 に答える
0

現在の非終端記号の FOLLOW セットに何かが表示されると、イプシロンを「解析」します。したがって、FOLLOW(B) = { 'c' } でcase Token.c:あるため、parseB のスイッチで使用します。

于 2010-07-31T19:15:54.050 に答える