Next: , Previous: , Up: SMIE   [Contents][Index]


22.7.1.5 Living With a Weak Parser

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

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