4

バックトラッキングによるインデントにも適した再帰的降下パーサーアルゴリズムを見つけようとしています。しかし、私はこれに対する面倒な解決策を見つけ続けています。

インデントも扱うリソースはありますか?

ありがとう

4

1 に答える 1

3

あなたの質問に基づいて、インデントに敏感な言語用に独自の再帰降下パーサーを書いていると思います。

以前にインデントベースの言語を試したことがありますが、現在のインデント レベルを追跡する状態と、インデントに一致する 2 つの異なるターミナルを用意することで問題を解決しました。どちらもインデント単位 (2 つのスペースまたはタブなど) に一致し、それらをカウントします。matched_indentation一致したインデント レベルと現在のインデントレベルを呼び出しましょうexpected_indentation。

最初のものについては、それを呼びましょうindent:

  • の場合matched_indentation < expected_indentation、これはdedentであり、一致は失敗です。
  • の場合matched_indentation == expected_indentation、一致は成功です。マッチャーはインデントを消費します。
  • の場合matched_indentation > expected_indentation、構文エラー (どこからともなくインデント) があり、そのように処理する必要があります (例外または何かをスローします)。

2番目のものについては、それを呼びましょうdedent：

  • の場合matched_indentation < expected_indentation、一致は成功です。1減らしexpected_indentationますが、入力を消費しません。dedentこれは、複数の端末をチェーンして複数のスコープを閉じることができるようにするためです。

  • の場合matched_indentation == expected_indentation、一致は成功し、今回は入力を消費します (これは最後のdedent端末であり、すべてのスコープが閉じられています)。

    の場合matched_indentation > expected_indentation、一致は単に失敗します。ここにはありませんdedent。

インデントの増加が予想される端末および非端末はexpected_indentation、1 ずつ増加する必要があります。

Python のような if ステートメント (ここでは EBNF のような表記法を使用します) を実装するとします。これは次のようになります。

indented_statement : indent statement newline;    

if_statement : 'if' condition ':' newline indented_statement+ dedent ;

次に、次のコードを見て、 an がルールif_statementの一部であると仮定します。statement

1|if cond1:                 <- expected_indentation = 0, matched_indentation = 0
2|  if cond2:               <- expected_indentation = 1, matched_indentation = 1
3|    statement1            <- expected_indentation = 2, matched_indentation = 2
4|    statement2            <- expected_indentation = 2, matched_indentation = 2
5|                          <- expected_indentation = 2, matched_indentation = 0
  • 最初の 4 行で、indent端末を正常に一致させることができます
  • dedent最後の行で、2 つの端末を一致させ、両方のスコープを閉じて、次のようにします。expected_indentation = 0

注意すべきことの 1 つはindent、dedent端末をどこに置くかです。この場合、それはであり、すでにインデントを想定して if_statementいるため、ルールに必要ありません。statementindented_statement

また、改行の扱いにも注意してください。1 つの選択肢は、それらを一種のステートメント ターミネータとして使用することです。もう 1 つは、それらをインデントの前に配置することです。

于 2013-11-24T15:47:07.723 に答える