kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

PEG

PEGでa1 + a2 + ... + an = bを判定する

このネタは parser.connpass.com でToshihiro Kogaさんに教えてもらったもので、私のオリジナルではないのですが、ちょっとおもしろいので貼ってみます。 まず、非負整数nについて、1の出現数によってエンコードします。 0 = 1 = 1 2 = 11 3 = 111 4 = 1111 …

Macro PEGで「一度現れたら再出現しない修飾子」+「相互排他的な修飾子」を表現してみる

gist.github.com とりあえずMacro PEGのコード。 「排他的な修飾子」とは何のことかというと、たとえば、public, private, protectedのように、「一度どれかが出現したら他のものは出現しない修飾子」のことです。最近のプログラミング言語の文法では、この…

Higer Order PEG(HOPEG)をMacro PEGに改名しました

タイトルの通りです。githubのプロジェクト名称、パッケージ名なども既に変更済みです。 github.com 元々、Higer Order PEGおよびFirst Order PEGは、Macro Grammarと呼ばれる、文脈自由文法を拡張して、非終端記号が引数を取れるようにしたものにインスパイ…

Higer Order PEGで「一度現れたら再出現しない修飾子」を表現してみる

gist.github.com とりあえずHOPEGのコードを貼り付けます。表題のような言語をHOPEGで表現する方法ですが、「一度見た修飾子の集合」をどこかに取っておく必要があります。それがModifersの引数AlreadyLookedです。一度どれかの修飾子を読むたびに、AlreadyL…

HOPEG 0.0.1リリースしました。

タイトル以上のことはほとんど書くことがないのですが、HOPEG、最初のリリースです。 詳しくは以下。 github.com hopeg 0.0.1をlibraryDependencyに追加して、利用コードの中で import com.github.kmizu.hopeg._ val grammar = HOPEGParser.parse( """ |S = …

構文解析勉強会Vol.2 開催します

parser.connpass.com の続編です。 parser.connpass.com 前回は、話題をPEGに限定していましたが、今回は、いわゆるTop-down構文解析全般を扱います。よく知られているLL(1)から、比較的最近のGLL、LL(*)までを取り扱えればと思います(あくまで努力目標です…

PEG基礎文法最速マスター

PEG

Scala基礎文法最速マスターを書こうか迷っていたら、既にyuroyoroさんに書かれてしまったので、ちょっと違う方向で。BNFを既に知っている人は、これを読めばPEGの基礎をマスターしてPEGを書くことができるようになるでしょう(ほんとか?)。 基本 Parsing Exp…

日本語ぽく書ける(?)パーザコンビネータ

以前作ったScalaのtoyプログラム色々眺めてたら、なんか発掘されたので、せっかくなので貼っておく。 object ぴーいーじーぱーざこんびねーた { type 構文規則 = 構文解析器[Any] abstract class 構文解析器[+A] extends (String => Option[(A, String)]) { …

前後の値も利用したシーケンス処理をScalaのパーザコンビネータで解いてみた

シーケンス中で連続して同じ値が入っている各箇所について,2 個目以降は削除したシーケンスが欲しい,という問題. http://d.hatena.ne.jp/NyaRuRu/20090311/p1 パーザコンビネータというと、とかく、文字列のパーズのためだけのものと思われがちですが、こ…

Cで作るPEGパーザコンビネータ

これまでPEGパーザコンビネータ作ってきた言語は、全て、レキシカルスコープの無名関数やそれに類似の機能を持っていたため、容易に作ることができましたが、C言語には無名関数のような機能が無いため、ちょっと頭をひねりました。とりあえず作ることを優先…

C#で作るPEGパーザコンビネータ

id:tad0さんのコメント: C#版きぼんぬ http://d.hatena.ne.jp/kmizushima/20090226/1235619468#c1235739906 ということで、C#版も書いてみました。C#については時々調べたりするものの、ほとんど全くと言っていいほど使っていないので(たとえば、今回、C# 3…

Scalaで作るPackrat Parserコンビネータ

【急募】PEGパーサのメモ化の実装 http://twitter.com/anatoo/status/1253132392 とかあったんで、せっかくなのでサクっと実装してみた。 ポイントは、PEGパーサコンビネータでは、ParserがString => Option[(A, String)]を継承していたのを、Int => Option[…

Onionで作るPEGパーザコンビネータ

せっかくなので、OnionでもPEGパーザコンビネータ書いてみた。しかし、自分で作った言語なのに、文法忘れてて文法定義ファイル見直してみたり、コンパイラが例外吐いて落ちたりして、コンパイラの不具合を避けてプログラムを書くために頭を悩ませるはめに…。…

Rubyで作るPEGパーザコンビネータ

調子に乗ってRubyでもPEGパーザコンビネータ書いてみた。Rubyは素人(コード自動生成とかにしか使ってない)なので、もうちょっとこうした方がいいよ、とか、こうした方がRubyっぽいよ、とかあったら教えてください。 module PEGParserCombinator class Parser…

Scalaで作るPEGパーザコンビネータ

といっても、昨日Javaで作ったPEGパーザコンビネータライブラリをScalaで書き直しただけのものだけど。Java版に比べて、1/3くらいの行数になっている。 object PEGParserCombinator { abstract class Parser[+A] extends (String => Option[(A, String)]) { …

"Some aspects of Parsing Expression Grammar", Roman Redziejowski

http://home.swipnet.se/redz/roman/papers/FI2008.pdf To appear in Fundamenta Informaticae. Preliminary version appeared in Proceedings of the CS&P'2007 Workshop, 594-605. らしい。著者の名前に見覚えがあるなと思ったら、以前読んだ、Parsing Exp…