22.7.1.5 非力なパーサーの使用

SMIEが使用するパーステクニックは、異なるコンテキストでトークンが異なる振る舞いをすることを許容しません。ほとんどのプログラミング言語にたいして、これは順位の競合によりBNF文法を変換するとき明らかになります。

その文法を若干異なるように表現することにより、これらの競合を回避できる場合があります。たとえばModula-2にたいしては以下のようなBNF文法をもつことが自然に思えるかもしれません:

  ...
  (inst ("IF" exp "THEN" insts "ELSE" insts "END")
        ("CASE" exp "OF" cases "END")
        ...)
  (cases (cases "|" cases)
         (caselabel ":" insts)
         ("ELSE" insts))
  ...

しかしこれは"ELSE"にたいする競合を生み出すでしょう。その一方でIFルールは、(他の多くのものの中でも特に)"ELSE" = "END"を暗示します。しかしその一方で"ELSE"はcases内に出現しますが、casesは"END"の左に出現するので、わたしたちは"ELSE" > "END"も得ることになります。これは以下を使用して解決できます:

  ...
  (inst ("IF" exp "THEN" insts "ELSE" insts "END")
        ("CASE" exp "OF" cases "END")
        ("CASE" exp "OF" cases "ELSE" insts "END")
        ...)
  (cases (cases "|" cases) (caselabel ":" insts))
  ...

または

  ...
  (inst ("IF" exp "THEN" else "END")
        ("CASE" exp "OF" cases "END")
        ...)
  (else (insts "ELSE" insts))
  (cases (cases "|" cases) (caselabel ":" insts) (else))
  ...

文法書き換えによる競合の解決には欠点があります。なぜならSMIEはその文法がコードの論理的構造を反映すると仮定するからです。そのためBNFと意図する抽象的構文木の関係を密接に保つことが望まれます。

注意深く考慮した結果、これらの競合が深刻ではなく、smie-bnf->prec2のresolvers引数を通じて解決する決心をする場合もあるでしょう。これは通常はその文法が単に不明瞭だからです。その文法により記述されるプログラムセットは競合の影響を受けませんが、それらのプログラムにたいする唯一の方法はパースだけです。'((assoc "|"))のようなリゾルバ(resolver: 解決するもの)を追加したいと望むような場合、通常それはセパレーターと2項結合演算子にたいするケースです。これが発生し得る他のケースは'((assoc "else" "then"))を使用するような場合における、古典的なぶら下がりelse問題(dangling else problem)です。これは実際に競合があり解決不能なものの、実際のところ問題が発生しそうにないケースにたいしても発生し得ます。

最後に多くのケースではすべての文法再構築努力にも関わらず、いくつかの競合が残るでしょう。しかし失望しないでください。パーサーをより賢くすることはできませんが、あなたの望むようにlexerをスマートにすることは可能です。その方法は競合が発生したら競合を引き起こしたトークンを調べて、それらのうちの1つを2つ以上の異なるトークンに分割する方法です。たとえばトークン"begin"にたいする互換性のない2つの使用を文法が区別する必要があり、見つかった"begin"の種類によってlexerに異なるトークン(たとえば"begin-fun"と"begin-plain")をリターンさせる場合です。これはlexerにたいして異なるケースを区別する処理を強制し、そのためにlexerは特別な手がかりを見つけるために周囲のテキストを調べる必要があるでしょう。