3

次のような単純な文法があるとします。

X -> number
T -> X
T -> T + X

したがって、たとえば、次のよう3 + 4 + 5に解析します。

     +
    / \ 
   +   5
 /  \
3    4

+これには、文法に「組み込まれている」という左右の結合性があります。

自明なLR（1）ですが、手書きのトップダウン解析を実行したいとします。

それは再帰的に残されているので、私はそうすることができません。それで、左にそれを因数分解させましょう：

X  -> number
T  -> X T'
T' -> + X T'
T' -> e    // empty

私が今それのためにパーサーを書くならば（疑似コード）：

parse_X:
    if lookahead is number
        return pop_lookahead

parse_T:
    return (parse_X, parse_T')

parse_T':
    if lookahead is +
         pop_lookahead
         return (parse_X, parse_T')
    else
         return ();

parse_T次に、の入力を呼び出すと、次の3 + 4 + 5ようなトレースが返されます。

parse_T
(parse_X, parse_T')
(3, parse_T')
(3, (parse_X, parse_T'))
(3, (4, parse_T'))
(3, (4, (parse_X, parse_T')))
(3, (4, (5, ())))

解析がどのように「逆方向」であるかを確認してください。このような構文解析から「素朴に」構築されたツリーは、次のようになります。

     +
    / \ 
   3   +
      / \
     4    5

これは間違った結合性を持っています。

誰かがこれを片付けることができますか？一般に、文法に組み込まれている関連性を保持する手書きのトップダウンパーサーを作成するにはどうすればよいですか？

4

1 に答える 1

2

1つの戦略は、再帰Tを反復に置き換えることですX（一般的に、演算子の再帰を次に高い優先順位の演算子の反復に置き換えます）。この場合、EBNFスタイルの表記を使用すると便利です

T -> X {+ X}

なぜなら、必要な反復が明らかになるからです。

parse_T:
  val = parse_X
  while lookahead is +
     pop_lookahead
     val = PLUS(val, parse_X)
  return val

ここで、PLUS()は、加算式を評価するために行うことを表します。たとえば、ツリーノードを作成します。

これをすべての演算子に適用すると、基本的に1つの関数に対応することになります。EXPRESSIONこれは、処理するときにのみ繰り返されます。

PRIMARY -> '(' EXPRESSION ')'

このようなアプローチは、かなり高速な式パーサーにつながります。単純な再帰下降を使用して式を解析することに対する一般的な反対意見の1つは、演算子の優先順位が複数ある場合、それぞれを解析するために20程度のネストされた関数呼び出しが簡単に必要にPRIMARYなる可能性があり、かなり遅くなる可能性があることです。反復アプローチでは、通常、ごとに1つの関数呼び出しのみが必要PRIMARYです。右結合演算子（べき乗など）がある場合は、再帰的アプローチを使用できます。

于 2013-03-07T04:56:41.143 に答える