esrap-peg パッケージを実際に使ってみる その3

esrap-peg 固有というより PEG の性質ですが、例えば末尾が ‘r’ な小文字アルファベット列が受理されるパーサを定義しようとして、Yacc と同様:

  G <- foo bar
  foo <- [a-z]*
  bar <- 'r'

とすると、”abcr” などを食わせると規則 foo が末尾の ‘r’ まで食べてしまい絶対もどさないので上の定義で作ったパーサは願ったようには動きません。規則 bar が不適合になって常に非受理です。
PEG の ‘*’ や ‘+’ は、最大適合まで食って戻さないためですが、それならばということで、

  G <- foo bar
  foo <- (foo [a-z]) / [a-z]
  bar <- 'r'

としてもなんら変わりません。
願ったような文字列を受理するパーサを定義するなら、foo の規則を例えば

  foo <- ([a-z] foo) / ([a-z] & bar)

などとなります。ただし、これでは規則 foo は単独では成り立たず、必ず後続して規則 bar を満たさないといけないので、規則(文法)G からの適用しかできません。

esrap のパーサは (esrap:parse ‘foo “…”) とすれば、単独の規則を受理するか試せます。

ちなみに “rrrr” をバースした構文解析木は、


(G ((FOO ("r" (FOO ("r" (FOO ("r" (BAR "r"))))))) (BAR "r")))

などとなってしまい、赤字の部分に若干の無駄があります。この例では、若干で澄んでますが、規則 bar がそれ以下長大な規則になっていると、ここもすごい大きい無駄になります。

赤字の部分は必ず付いてしまう無駄ですから、実際的な簡易な対応は、出来た構文解析木を刈り込んでしまうという手だと思います。構文解析木を作ったなら、それを使うタイミングがあるはずで、その手前で行うというところでしょう。

カテゴリー: LISP, エンジニアリング, ソフトウェア, プログラミング言語 パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください