2

以下を解析したいと思います。

name:name

ここで、名前は alnum で始まり、alnum で終わり、alnum とスペースの任意の組み合わせを内部に含めることができます。空白の場合もあります。これに対する私のルールは次のとおりです。

identifier = alnum (space* alnum)*;
name       = (identifier | zlen) >sName $pName %fName;

名前はコロンで区切ることができ、オプションで名前とコロンの間にスペースを入れることもできます。これに対する私のルールは次のとおりです。

sep = space* ":" space*;
main := name sep name;

space*どうやらinidentifierとspace*insepがパーサーを混同するため、これは機能しません。fName名前のすべてのスペースでアクションが実行されることになります。

sep を次のように変更した場合:

sep = ":";

その後、すべてが順調です。パーサーが意図したとおりに動作するように、これらのルールを変更するにはどうすればよいですか?

この質問のソース コード: https://gist.github.com/1661150

4

1 に答える 1

10

この種の問題には、2 つの基本的な解決策があります。

  1. 安全に複数回実行できるようにアクションを定義し、
  2. アクションが 1 回だけ実行されるように構文を変更します。

この場合、ハイブリッド アプローチを選択します。アクションを使用して a の開始位置と終了位置を記録しnameます。これらのアクションは位置を記録するだけなので、安全に何度でも実行できます。名前を過ぎたことを確認したら、一度だけ実行される別のアクションを実行します。

/* C code */
char *name_start, *name_end;

/* Ragel code */
action markNameStart { name_start = p; }
action markNameEnd { name_end = p; }
action nameAction {
    /* Clumsy since name is not nul-terminated */
    fputs("Name = ", stdout);
    fwrite(name_start, 1, name_end - name_start, stdout);
    fputc('\n', stdout);
}

name = space* %markNameStart
       (alnum+ %markNameEnd <: space*)+
       %nameAction ;
main := name ":" name ;

ここで、 の構文にnameは、任意のスペースと少なくとも 1 つの英数字が含まれています。最初の英数字が検出されると、その場所が に保存されname_startます。英数字の連続が終了するたびに、次の文字の位置が に保存されname_endます。これは技術的には不要ですが、アクションが実行される<:頻度を減らします。markNameEnd

そのような式をスペースの隣に配置しないでください。

上記のコードはテストしていません。使用する前に、状態マシンの Graphviz 視覚化を確認する必要があります。

レーゲルは何をしているのか

元のコードで、入力が次のようになっているとします。

ハローワールド：さようならワールド

Ragel マシンは左から右にスキャンし、 の開始を見つけ、name英数字をスキャンします。

ハローワールド：さようならワールド
    ↑

次の文字はスペースです。そのため、単語内のスペース、または単語の末尾の後の最初のスペースに遭遇しました。Ragel はどのように選択しますか?

Ragel は両方のオプションを同時に選択します。 これはとても重要です。Ragel は非決定論的な有限オートマトンをシミュレートしようとしていますが、コンピューターは決定論的であるため、これを行う最も簡単な方法は、NFA を無制限の数の NFA を並列でシミュレートする DFA に変換することです。NFA には有限数の状態があるため (名前の由来)、DFA にも有限数の状態があるため、この手法は機能します。

スペースに遭遇した後、次の状態の 1 つの NFA があり、残りの を探しますname。

識別子 = alnum (スペース* alnum)*;
                    ↑

メイン := 名前 sep 名;
        ↑

name2 番目の NFA は次の状態にあり、が既に終了していると想定します(そして、この NFA はfNameアクションを「時期尚早に」実行します)。

sep = スペース* ":" スペース*;
      ↑

メイン := 名前 sep 名;
             ↑

最初の NFA だけが正しいことは、あなたにも明らかですし、私にも明らかです。しかし、Ragel で作成されたマシンは、一度に 1 人のキャラクターしか見ておらず、どのオプションが正しいかを先に見ていません。2 番目の NFA は、最終的に が表示されると予想していた場所で英数字に遭遇します。これは":"許可されていないため、2 番目の NFA は表示されなくなります。

Ragelのドキュメントを見てください

の説明は次の%とおりです。

expr % action

退出アクション オペレータは、最終状態を介してマシンから出る遷移に埋め込むアクションをキューに入れます。

アクションは、解析の成功に必ずしも寄与しない遷移に対して実行されます。Ragel の非決定性の詳細については、Ragel ガイドの第 4 章「非決定性の制御」を参照してください。有限状態マシンでは許可されていません。

于 2012-01-23T07:18:35.710 に答える