人気ブログランキング | 話題のタグを見る

高階関数型 PEG パーサの欠陥

高階関数型のPEGパーサに重大な欠陥があった。再帰的な定義に対応できないのだ。

factor <- number / '(' expr ')'
term <- factor ('*' factor)*
expr <- term ('+' term)*

のように、expr が再帰する文法にはスタックエラーになってしまう。高階関数の戻値が、クロージャなので仕方がないのだが。

泥沼になってしまった。

まあ、treetop を使えばいいだけのことだけれど。

くやしいことに、無骨な mkpeg_eval.rb のほうは一発で働いてくれた。

ファイル名: arithmatic.rb

require 'mkpeg_eval.rb'

mk_terminal('spacing', '/\A\s/')
mk_terminal('number', '/\A[1-9][0-9]*\s*/')
mk_terminal('open', '/\A\(\s*/')
mk_terminal('close', '/\A\)\s*/')
mk_terminal('add', '/\+\s*/')
mk_terminal('mul', '/\*\s*/')

mk_star('term_star', 'add and term')
mk_slash('expr1', 'term and term_star')
mk_slash('expr', 'expr1', 'term')

mk_star('factor_star', 'mul and factor')
mk_slash('term1', 'factor and factor_star')
mk_slash('term', 'term1', 'factor')

mk_slash('factor1', 'open and expr and close')
mk_slash('factor', 'factor1', 'number')

実行例

C:\Users\******\Documents\Ruby>irb
irb(main):001:0> require 'arithmatic.rb'
=> true
irb(main):002:0> $line = '(1 + 2) * 3'
=> "(1 + 2) * 3"
irb(main):003:0> expr
=> true

これを使って本当のPEGコンパイラコンパイラを作ればいいだけのことだけど。力仕事になりそうだ。得てして愚直なプログラムのほうが信頼性が高かったりすることは良くあることだ。なんかつまらないが、そんなものなのだろう。
by tnomura9 | 2008-05-01 00:07 | Ruby | Comments(0)
<< PEG とは何か 原点に帰る >>