週1でも日記

  • このサイトに書かれていることは間違っているかもしれませんので、ご注意ください。
  • 非推奨環境: フォントの大きさが Unreadable な xterm 上のテキストブラウザ
2005][07][08][09][10][11][12][
2006][01][02][03][04][05][06][07][08][09][10][11][12][
2007][01][02][03][04][05][06][07][08][09][10][11][12][
2008][01][02][03][04][05][06][07][08][09][10][11][12][
2009][01][02][03][04][05][06][07][08][09][10][11][12][
2010][01][02][03][04][05][06][07][08][09][10][11][12][
2011][01][02][03][04][05][06][07][08][09][10][11][12][
2012][01][02][03][04][05][06][07][08][09][10][11][12][
2013][01][02][03][04][05][06][07][08][09][10][11][12][
2014][01][02][03][04][05][06][07][08][09][10][11][12][
2015][01][02][03][04][05][06][07][08][09][10][11][12][
2016][01][02][03][04][05][

2016年21週143日星期0 12:00:00 AM 00:00:00

トラックバック - http://d.hatena.ne.jp/yshl/20160522

2016年17週115日星期0 12:00:00 AM 00:00:00

トラックバック - http://d.hatena.ne.jp/yshl/20160424

2016年14週100日星期6 12:00:00 AM 00:00:00

トラックバック - http://d.hatena.ne.jp/yshl/20160409

2016年13週087日星期0 12:00:00 AM 00:00:00

構文解析できないの私だ 23:31 構文解析できないの私だを含むブックマーク

テキストファイル構文解析しようとしたんですよ。全体は行の集まりで、各行はなんやかんやあって改行文字で終わる、見たいなやつ。空行は許すような感じの。

で、Ruby でかっこいい構文で PEG パーサが書けるらしいという評判の Parslet を使ってこんなパーサ書いたんですよ。

#!/usr/bin/ruby
require 'parslet'

class AAAParser < Parslet::Parser
    root :all
    rule(:all){
        # 全体は line の 0 回以上の繰り返し
        line.repeat
    }
    rule(:line){
        # line は statement の後に newline を付けたもの
        statement >> newline
    }
    rule(:statement){
        # statement は文字 a の 0 回以上の繰り返し
        str('a').repeat
    }
    rule(:newline){
        # newline は文字 "\n"
        str("\n")
    }
end

ap=AAAParser.new
p ap.parse("aaaaa\naaa\n") # OK
begin
    ap.parse("aabaa\n") # エラー
rescue Parslet::ParseFailed => e
    puts e.message
end

で、テキストファイルの終わりの改行が無いことって結構あるじゃないですか。で、改行文字は省略可能にしてみたんですよ。こんな感じに。

#!/usr/bin/ruby
require 'parslet'

class AAAParser < Parslet::Parser
    root :all
    rule(:all){
        # 全体は line の 0 回以上の繰り返し
        line.repeat
    }
    rule(:line){
        # line は statement の後に newline が付いているかもしれない
        statement >> newline.maybe
    }
    rule(:statement){
        # statement は文字 a の 0 回以上の繰り返し
        str('a').repeat
    }
    rule(:newline){
        # newline は文字 "\n"
        str("\n")
    }
end

ap=AAAParser.new
p ap.parse("aaaaa\naaa\n") # 無限ループ
begin
    ap.parse("aabaa\n") # 無限ループ
rescue Parslet::ParseFailed => e
    puts e.message
end

で、これだと無限ループになってしまう。line が 0 文字文字列 "" にもマッチするようになったので、全部読み終わった後も lineマッチし続けて終わらないのだろうと思って、line には何か 1 文字存在するという制限をつけてみたわけです。

#!/usr/bin/ruby
require 'parslet'

class AAAParser < Parslet::Parser
    root :all
    rule(:all){
        # 全体は line の 0 回以上の繰り返し
        line.repeat
    }
    rule(:line){
        # line は 1文字以上あり、
        any.present? >>
        # statement の後に newline が付いているかもしれない
        statement >> newline.maybe
    }
    rule(:statement){
        # statement は文字 a の 0 回以上の繰り返し
        str('a').repeat
    }
    rule(:newline){
        # newline は文字 "\n"
        str("\n")
    }
end

ap=AAAParser.new
p ap.parse("aaaaa\naaa\n") # OK
begin
    ap.parse("aabaa\n") # 無限ループ
rescue Parslet::ParseFailed => e
    puts e.message
end

構文解析成功する場合はいいんですけど、失敗する場合は、まだ無限ループになってしまう。

上の例をパーサの気持ちになって考えると、こんなことになっているっぽい。

  1. "aabaa\n" に対して 1 回目の line が初めの "aa" にマッチ
  2. 続く "baa\n" に対して 2 回目の line の any.present? で "b" にマッチして、続く statement と newline が "" にマッチし、line 全体は "" にマッチする。
  3. 再び "baa\n" に対して lineマッチするか試す。そして "" にマッチする。これを無限に繰り返す。

結局 newline に maybe を付けてしまうと "" にマッチして面倒な事になるのだから、こうすべきだったっぽい。

#!/usr/bin/ruby
require 'parslet'

class AAAParser < Parslet::Parser
    root :all
    rule(:all){
        # 全体は line の 0 回以上の繰り返しの後に
        line.repeat >>
        # statement があるかもしれない
        statement.maybe
    }
    rule(:line){
        # line は statement の後に newline を付けたもの
        statement >> newline
    }
    rule(:statement){
        # statement は文字 a の 0 回以上の繰り返し
        str('a').repeat
    }
    rule(:newline){
        # newline は文字 "\n"
        str("\n")
    }
end

ap=AAAParser.new
p ap.parse("aaaaa\naaa\n") # OK
begin
    ap.parse("aabaa\n") # エラー
rescue Parslet::ParseFailed => e
    puts e.message
end

で、ですね。無限ループになった原因は私が間抜けだったからなんですが、どうすれば間抜けなパーサを書いてしまうのを防げるのか、間抜けなパーサを書いた時にどうやって修正するのか、という点が知りたい。

  • ダメパターンを予習しようにも、検索しても PEG では左再帰はだめくらいしか見当たらなかったのですが、失敗を繰り返して自分で覚えていくしかないんでしょうか。
  • Parslet じゃなくて他の何かだったら、コンパイル時に警告を出したり、エラーにしてくれたりするんでしょうか。
  • 上の例だと人間パーサになって挙動を順番に調べているけど、パーサや文字列が複雑化したら難しくなってくるのですが、どうすればいいんでしょうか。
  • センスのない奴はパーサを書くなって事ならすみません

[]Plamo Linuxタイムゾーン 23:31 Plamo Linux のタイムゾーンを含むブックマーク

Plamo Linuxタイムゾーンが、いつのまにやら GMT になっていた。多分、タイムゾーン情報を timezone-2015g-x86_64-P1.txz にアップデートしたせいだろう。

対処法としては、timeconfig コマンドで設定しなおせばよい。

トラックバック - http://d.hatena.ne.jp/yshl/20160327

2016年12週081日星期1 12:00:00 AM 00:00:00

トラックバック - http://d.hatena.ne.jp/yshl/20160321
2005)(07)(08)(09)(10)(11)(12)(
2006)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2007)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2008)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2009)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2010)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2011)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2012)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2013)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2014)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2015)(01)(02)(03)(04)(05)(06)(07)(08)(09)(10)(11)(12)(
2016)(01)(02)(03)(04)(05)(
354548