OreScriptがはやってるならパーサコンビネータの需要もあるのかな？

近頃、JavascriptでOreScriptなんてのがちょっとはやっていたりしまして。

OreScript書くのにある程度ちゃんと動くパーサコンビネータがあれば便利かも、とおもったので以前書いたパーサコンビネータをいじってみました。

変更点

  • メソッド名などをHaskellにあわせた
  • よくもわるくも、記号含有率をあげた(and -> $に、or -> l に)
  • 相互再帰をサポートした
  • 左再帰(chainl1)をサポートした
  • 右再帰(chanr1)をサポートした

ということで、そこそこの用途に耐えるものになったと思います。

ダウンロード

完全にアンドキュメントです。すみません。ただ、ソースは200行くらいなんで見ればわかるかと。というか、HaskellのParsecのマニュアルを読めば基本一緒なので使い方がわかると思います。

ダウンロード

サンプル

id:amachangさんが書いていたような数式パーサを定義してみましょう。

残念ながらLexerはつくっていないので、空白は受け入れられません。

javascript code
  1. var ExprParser = Inforno.Parsec.Parsers.define(function(){with(this){
  2.   var mul = function(a,b){return a*b;};
  3.   var div = function(a,b){return a/b;};
  4.   var add = function(a,b){return a+b;};
  5.   var sub = function(a,b){return a-b;};
  6.  
  7.   this.numbers = many1( chrLike(function(c) { return (c >= '0' && c <= '9'); }) ) .ret(function(ns){
  8.                     return parseInt(ns.join(""));
  9.                   });
  10.   this.expr = chainl1(p("term"), p("addop"));
  11.   this.term = chainl1(p("factor"), p("mulop"));
  12.   this.factor = (between(chr("("), p("expr"), chr(")"))) .l (numbers)
  13.   this.mulop = (chr("*") .retval(mul)) .l (chr("/") .retval(div));
  14.   this.addop = (chr("+") .retval(add)) .l (chr("-") .retval(sub));
  15. }});
  16.  
  17. var test = "100*(100+200)/10";
  18.  
  19. var parser = new ExprParser(test);
  20. var parseResult = parser.expr.parse();
  21. if(parseResult.success()) {
  22.   alert(parseResult.result);
  23.   // => 3000
  24. }
  25.  

すごく、Parsecです･･･

こういうのを最近はやりのCodeReposでやればいいのかなあ。

07.27.08/12am
Posted at:
11.18.07/02am
Tags:
Comments:
(2)
Permalink

Javascriptでパーサジェネレータを書いてみた

ちょっと前にjavascriptで構文解析とかがはやった気がするので、javascriptのリハビリがてらかいてみた。

ググってみると

あたりがあるのだが、まぁ勉強ということで。javascriptらしく書いてみようかと。

ということで、モナドがどーたらとか難しい話はまぁおいておいて、簡単に値がとりだせますよ、という見栄え重視で作ってみた。基本的な機能しかない。けど拡張するのは簡単。せめて相互再帰くらいは実装したほうがよかったかな。まぁ、こんなの真剣に使う人もいないと思うので、要望があればってことで。ちなみに依存するライブラリはありません。

ダウンロード：Inforno.Parsec

たとえばこんな感じにCSVのパーサが定義できる。withを使ってDSLっぽくしてみた。

javascript code
  1. var CSVParser = Inforno.Parsec.Parsers.define(function(){with(this){
  2.   this.chars = chrLike(function(c){ return c != '' && c!=',' && c!='\n' && c!='"';});
  3.   this.quote = chr('"')
  4.   this.quoteInQuote = str('""') .ret(function(){return '"';});
  5.   this.charInQuote = chrLike(function(c){ return c!='"';});
  6.   this.quotedField = quote .and (rep((quoteInQuote) .or (charInQuote))) .and (quote)
  7.                       .ret(function(q1, cs, q2){
  8.                         return cs.join("");
  9.                       });
  10.   this.field = rep1(chars) .ret(Return.str)
  11.   this.record = sep( (field) .or (quotedField), chr(","), true) .ret(function(fields) {
  12.     return {fields: fields};
  13.   })
  14.   this.csv = sep(record, chr("\n"), true) .and(eof) .ret(function(records) {
  15.     return {records : records};
  16.   })
  17. }});
  18.  
  19. var testCsv = [
  20. '"aaa","b',
  21. 'bb","ccc",zzz,"y""Y""y",xxx'
  22. ].join("\n");
  23.  
  24. var parser = new CSVParser(testCsv);
  25. var parseResult = parser.csv.parse()
  26. if(parseResult.success()) {
  27.   var records = parseResult.result[0].records;
  28.   for(var i=0,l=records.length;i<l;i++){
  29.     alert("row("+i+") "+records[i].fields);
  30.   }
  31. }
  32.  

実はパーサコンビネータって簡単にかけるんだけど、世間的にちゃんと認識されているのかなあ。思うに、パーサコンビネータといえばHaskell界隈であり 、関数型界隈であり（もちろんちゃんとJAVAとかの実装もあるんだけど）、モナドでありそういうところって専門用語が多いから「ふつうの」プログラマからは簡単に見えてないような気がするなあ。

07.27.08/12am
Posted at:
09.08.07/12am
Tags:
Comments:
0
Permalink

Scalaでパーサコンビネータ

Scala 2.6.0-RC1 でscala.util.parsing.combinatorが標準パッケージになりました。というわけでリファレンスとちょっとしたサンプルくらしかなかったのだけど、とりあえず書いてみた。

どう書く?orgに投稿した、ExcelライクCSVのパーサ。

scala code
  1. import scala.util.parsing.combinator.{Parsers, ImplicitConversions, ~, mkTilde}
  2. import scala.util.parsing.input.CharArrayReader
  3. import Character.isISOControl
  4.  
  5. object CSVParser {
  6.  trait Base
  7.  case class Field(s:String) extends Base {
  8.    override def toString = s
  9.  }
  10.  case class Record(fields: List[Field]) extends Base
  11.  case class File(records :List[Record]) extends Base
  12.  
  13.  def mkString(cs :List[Any]) = cs.mkString("")
  14.  class CSVParser extends Parsers {
  15.    type Elem = Char
  16.    def notMeta(c:Elem) = c!=',' && c!='\n' && c!='"' && !isISOControl(c)
  17.  
  18.    lazy val file = record.*('\n') ^^ File
  19.    lazy val record = (field|quotedField|nullableField).*(',') ^^ Record
  20.    lazy val field = chars.+ ^^ {cs => Field(mkString(cs))}
  21.    lazy val nullableField = chars.* ^^ {cs => Field("")}
  22.    lazy val quotedField = '"' ~ (charsInQuote|quoteInQuote).* ~ '"' ^^ {cs => Field(mkString(cs))}
  23.    lazy val charsInQuote = elem("chars in field", _!='"')
  24.    lazy val quoteInQuote = repN(2, quote) ^^ {cs => '"'}
  25.    lazy val quote = '"' ^^ success
  26.    lazy val chars = elem("chars", notMeta)
  27.  }
  28. }
  29.  
  30. val data = """
  31. "aaa","b
  32. bb","ccc",zzz,"y""Y""y",xxx
  33. """.trim
  34.  
  35. (new CSVParser.CSVParser).file(new
  36. CharArrayReader(data.toCharArray)).map(file => {
  37.  file.records.map({record =>
  38.    val fields = record.fields
  39.    (1 to fields.length).foreach(i => println(i +" => " + fields(i-1)))
  40.  })
  41. })
  42.  

とりあえずこんな感じ。これはダイレクトにParsersクラスを直接継承してるけど、StdTokenParsersってかんじのParserもあるし、StdLexicalってかんじなLexerもあってこれはなかなか。

時間が出来たらもうちょっといじってみよう。よさげな解説してるサイトがあったら是非教えてください。

07.27.08/12am
Posted at:
07.30.07/07pm
Tags:
Comments:
0
Permalink

About

Author:yuin(http://inforno.net/)

文学部文化学科卒という生粋の文系趣味プログラマ。

主にRuby、Javascript、PHP、JAVA,Python,C,Scala,Schemeなどを使っています。今はPythonな感じかもしれない。今後作曲活動なども復活するかもしれない。

Links

Pages

Recently

Tags

DHT1 SF1 activesupport1 api4 binary3 blog1 book1 cltc1 compiler1 craftlaunch2 cui1 development9 drecom1 electronics1 emulator6 erlang1 essay10 fckeditor1 feed1 framework1 gae3 go1 gui2 javascript14 job4 kademlia1 language2 library14 life5 lingr1 linux1 nes5 network1 nicovideo1 nlp1 ocaml1 p2p1 parser6 programing2 prototype_js7 python39 python30001 rayphe1 ruby5 rubyonrails2 scala6 scheme1 scrap1 scriptaculous1 sexp1 tasktools1 template3 text3 tk1 typo2 vim2 webpy2 windows4 wordpress2 xrea2 yahoo4

Monthly Archives