C#でパーサを作ろうと思ったら酷い目に合った話 - 私が気にする100の事象
こんにちは、skytomoです。 春、ですね。（なんやこいつ） これは春休みに起こったことです。 春休みに何もせず、ただぼーっと生きてんじゃねえよとチコちゃんに叱られるのは嫌 *1 なので、何かしらプログラミングをしたりします。 長期休暇は、僕を何か作ろう、という気にさせます。いい機会です。 休みのうちの最初はAtCoderでスキルアップしてました。 しかし、途中でロジバンという人工言語が気になりだし、 「そうだ、ロジバンのパーサをC#で書こう」となり、実際にそれに取り組みました。 （ロジバンってなんぞという人は後で説明しますので、ここでは無視してください。） しかし、想像以上にそれは困難を極めました。パーサを作るためにしたことを列挙するとこんな感じです。 ロジバンはPEGというもので書かれていることを知る C#でPEGを使ったパーサを生成するライブラリを探す peg-sharpを使ってみ
Cで作るPEGパーザコンビネータ - kmizuの日記
これまでPEGパーザコンビネータ作ってきた言語は、全て、レキシカルスコープの無名関数やそれに類似の機能を持っていたため、容易に作ることができましたが、C言語には無名関数のような機能が無いため、ちょっと頭をひねりました。とりあえず作ることを優先させたので、メモリ管理とか、ライブラリとしての再利用しやすいようにヘッダファイルに宣言を適切に分離するとか一切考慮してません。たとえば、動的なメモリ確保は、mallocした後、そのまま放置で、freeしてません。あと、C言語は普段使わないので、C言語バリバリに使っている方からすると、メモリ管理とか以外の基本的なところで、ツッコミどころ満載な気もするので、その辺も指摘していただければと思います。 #include <stdio.h> #include <string.h> #include <stdlib.h> #define RULE(name) Pa
C#でPEGパーサー - Kokudoriing
PEGって何？って方はWikipediaを御覧ください。 (正直ボクもよくわかってない・・) ざっくりと、BNFよりも曖昧性のないものを扱うのが得意みたいで、Shift/Reduceコンフリクトが発生しないとのこと。 Perl6がPerl6 rulesとかで言語レベルに組み込んでるアレです。 PEG自体の解説はkmizushimaさんのPEG基礎文法最速マスターを見ていただくとして、 以下はC#で使えるPEGパーサー、peg-sharpについてのお話し。 昨日辺りから触りだして、ようやく簡単なJSONパーサー作ってみました。 https://gist.github.com/kokudori/5252810 Xxx.pegにPEGを書いて、peg-sharpでパーサーをジェネレートして使う感じです。 ただ、PEGファイル内でバッククォート(`)で囲まれた部分がC#として解析されます。 この時
Javaで作るPEGパーザコンビネータ - kmizuの日記
パーサジェネレータを作る簡単さで言うと、 PEG <<<< LL(1) <<<< LALR(1) くらいな感じのイメージです。 http://twitter.com/kmizu/statuses/1183248403 なんて偉そうなこと書いたので、(パーザジェネレータじゃないけど)PEGパーザコンビネータを実際にJavaで書いてみた。文字クラスを除くPEGの機能のほぼフルセットをサポートするのを目標に書いたので、やや煩雑になっている。 package jp.gr.java_conf.mizu; import java.util.*; import static java.lang.String.format; public class PEGParserCombinators { public static final class Pair<A, B> { public final A _
Scalaで作るPEGパーザコンビネータ - kmizuの日記
といっても、昨日Javaで作ったPEGパーザコンビネータライブラリをScalaで書き直しただけのものだけど。Java版に比べて、1/3くらいの行数になっている。 object PEGParserCombinator { abstract class Parser[+A] extends (String => Option[(A, String)]) { def /[B >: A](that: => Parser[B]): Parser[B] = parserOf((in) => { this(in) orElse that(in) }) def ~[B](that: => Parser[B]): Parser[(A, B)] = parserOf((in) => { for((r1, rest1) <- this(in); (r2, rest2) <- that(rest1)) yield
C#で作るPEGパーザコンビネータ - kmizuの日記
id:tad0さんのコメント： C#版きぼんぬ http://d.hatena.ne.jp/kmizushima/20090226/1235619468#c1235739906 ということで、C#版も書いてみました。C#については時々調べたりするものの、ほとんど全くと言っていいほど使っていないので(たとえば、今回、C# 3.0のラムダ式を初めて使った)、なんか変な点があればご指摘ください。 using System; using System.Collections.Generic; public class Pair<A, B> { public A _1 { get; private set; } public B _2 { get; private set; } public Pair(A _1, B _2) { this._1 = _1; this._2 = _2; } publi
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
PEG parser implementation
Simplified Parsing Expression Derivatives
Derivatives of Parsing Expression Grammars