Rzubr - ピュア Ruby なおもちゃの LALR(1) 構文解析器 - Tociyuki::Diary
Ruby で記述してある LALR(1) 構文解析ツールといえば Racc だ、 と相場は決まっていて、私も便利に利用しています。ただし、Racc は実用性優先で、あまりに Bison を意識しすぎている上に、速度優先、内部のオブジェクトの構造がつくりこまれすぎときて、いじくって余計な機能をつけて遊んでみようとか、機能をちょっと変えてみようとかするには、まったくもって向いていません。 実用性よりも、内部をいじって遊ぶのに向いた小気味の良いピュア Ruby な LALR(1) 構文解析器もあって良いのではないかと考えて、作ってみました。構文解析表の生成部と駆動部をすべて組み込んで、500 行程度のコンパクトな解析器処理系です。構文記述はハッシュと配列に優先順位と生成規則のインスタンスを並べるだけで良いのですが、少しは記述性を上げてみようとの試みで、Ruby の組み込み演算子を使って生成規則を
instaparseで遊ぶ - みどりねこ日記
この記事はClojure Advent Calendar 2013 - Qiita [キータ]１９日目の記事です。 instaparse 本記事ではinstaparseというライブラリを使って遊んでみます。 instaparseはEBNFやABNFで記述された文脈自由文法から自動的にパーサを生成してくれます。 左再帰、右再帰、曖昧性など、いかなる文脈自由文法でも動作します。 生成されたパーサは文字列からenliveまたはhiccup風の木構造を生成します。 今回は型なしラムダ計算を題材にします。 型なしラムダ計算 型なしラムダ計算は、型がない（または型がひとつしかない）ラムダ計算です。 ラムダ計算はとてもシンプルで、すべての計算が関数定義と関数適用だけで実現可能です。 ラムダ計算の構文は以下の３つからなります。 t ::= 項 x 変数 | \x . t ラムダ抽象 | t t 関数適用
Emacs の Major Mode におけるインデント計算を楽にする smie.el - Qiita
Writing a good indentation function can be difficult and to a large extent it is still a black art. -- Emacs Lisp Reference Manual 良いインデント関数を書くのは困難であり、 現在においても広い範囲に置いて黒魔術である。 ここではEmacs 24.3の新機能である、インデント計算エンジン smie.elを紹介する。 Emacs の Major Mode の実装 Emacs の Major Mode は、様々なプログラミング言語やテキストフォーマット 用に色付けやインデントなどの編集機能を提供する。 Emacsは多くのプログラミング言語用にMajor Mode が用意されているが、例外 もある。また、独自に言語を設計した場合も、Major Mode を自作することに
smitti's p4js at master - GitHub
This repository is private. All pages are served over SSL and all pushing and pulling is done over SSH. No one may fork, clone, or view it unless they are added as a member. Every repository with this icon () is private. This repository is public. Anyone may fork, clone, or view it. Every repository with this icon () is public.
ANTLR
What is ANTLR? ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. It's widely used to build languages, tools, and frameworks. From a grammar, ANTLR generates a parser that can build and walk parse trees. Terence Parr is a tech lead at Google and until 2022 was a professor of data science /
B3 OS/Programming
シラバス 本コースは、プログラミングの基本について、ひととおりの技術を学び終えた受講者を対象とする。コースの目的は、実際のソフトウェアを開発する際に、具体的にどのようにプログラムを設計し、またどのように OS の機能を利用していけばよいか、感覚をつかんでもらうことである。このため、本コースは講義中心ではなく、いくつかのソフトウェアの作成演習をとおして、そのソフトウェアのプログラムはなぜそのように設計されているのか等を考えてもらう。 1. 簡単な C コンパイラ 言語仕様を簡略化したCコンパイラを作成し、言語処理系の基本構成を学ぶ。また関数呼び出しや配列参照など、C言語の各基本機能が実際にどのような機械語に変換されていくのかを学ぶ。 実際に作成する処理系は2つで、まずはじめに字句解析の練習として、ごく簡単なLispインタプリタを作る。 その後、構文解析、コード生成の演習のため、C言語風の手続
Top Down Operator Precedence
Douglas Crockford 2007-02-21 This is chapter 9 of Beautiful Code. Introduction Vaughan Pratt presented "Top Down Operator Precedence" at the first annual Principles of Programming Languages Symposium in Boston in 1973. In the paper Pratt described a parsing technique that combines the best properties of Recursive Descent and Floyd's Operator Precedence. It is easy to use. It feels a lot like Recur
部分継続による Python 風ジェネレータ - (new Hatena).blog()
ここ数日 HTML パーサーの開発に取り組んでいたんですが、その過程で次のような問題にぶつかりました。 HTML を構文解析して木構造を作る際に、トークン (字句) を一つずつ返してくれるジェネレータが欲しい、と思ったんです。 一般に、言語の解析は字句解析と構文解析の2段階から成りますが (参照: Wikipedia:構文解析) 字句を一つ取り出してその都度構文解析に回したい、と考えたわけです。 例えば、 <body> <p>text with <a href="foo.htm">anchor</a> in between</p> </body> のような HTML 片があった時に、次のようにして一つずつのトークンを得たい、ということなんです: (body) (p) "text with " (a (@ (href "foo.htm"))) "anchor" (/ a) " in betw
inforno :: OreScriptがはやってるならパーサコンビネータの需要もあるのかな？
近頃、 JavascriptでOreScript なんてのがちょっとはやっていたりしまして。 OreScript書くのにある程度ちゃんと動くパーサコンビネータがあれば便利かも、とおもったので以前書いたパーサコンビネータをいじってみました。 変更点 メソッド名などをHaskellにあわせた よくもわるくも、記号含有率をあげた(and -> $に、or -> l に) 相互再帰をサポートした 左再帰(chainl1)をサポートした 右再帰(chanr1)をサポートした ということで、そこそこの用途に耐えるものになったと思います。 ダウンロード 完全にアンドキュメントです。すみません。ただ、ソースは200行くらいなんで見ればわかるかと。というか、HaskellのParsecのマニュアルを読めば基本一緒なので使い方がわかると思います。 ダウンロード サンプル id:amachangさんが書いていた
とらドラ （Modern Compiler Implementation in C と Compilers: Principles, Techniques, and Tools 的な意味で) - なつたん
とらドラ （Modern Compiler Implementation in C と Compilers: Principles, Techniques, and Tools 的な意味で) ざっとModern Compiler Implementation in C（タイガーブック）目を通しました。Compilers: Principles, Techniques, and Tools（ドラゴンブック）との比較してみます。実際に比較できるのは、ある程度内容を理解しているレキサーとパーサーの部分だけですが、参考にはなるかと思います。 全体的にタイガーブックは、ドラゴンブックに比べると、内容が実践的で練習問題がわかりやすいです。ドラゴンブックの練習問題は、抽象的（本質的）な問題が多いように思いますが、タイガーブックは実践的な問題が多いように感じます。 タイガーブックの方が、小さい処理系を作る
ゆの in yacc - daily dayflower
パーサかませばなんでもありだな…… %{ #include <stdio.h> #include <string.h> %} %union { char *str; } %token X %token <str> STRING %type <str> face mouths left_part right_part mouth %% sayhello: face '<' STRING '!' { fputs($1, stdout); fputc(' ', stdout); fputs($3, stdout); fputc('!', stdout); fputs("\n", stdout); free($1); } face: left_part mouths right_part { $$ = malloc(strlen($1) + strlen($2) + strlen($3) + 1)
正規表現ベースの字句解析器を書くときは - 最速チュパカブラ研究会
正規表現ベースの字句解析器を書くときは、narcissusというJSベースのJS処理系のコードを見るといいです http://mxr.mozilla.org/mozilla/source/js/narcissus/jsparse.js 面倒な正規表現の模範解答が載ってます。下手に自分で考えて誤爆するより、一流の人が書いたものを使いましょう 正規表現リテラル /^\/((?:\\.|[^\/])+)\/([gimy]*)/ 文字列（ダブルクォート、シングルクォート共）/^"(?:\\.|[^"])*"|^'(?:[^']|\\.)*'/ → 訂正 Cスタイルコメント（一行、ブロック共） /^\/(?:\*(?:.|\n)*?\*\/|\/.*)/ ↓narcissusについてはyukobaさんのプレゼンを(去年のShibuya.es) http://accelart.jp/shibuyajs
LispUser.net : 最高にキモい Lisp コードを書いてみよう with 100 行リーダーマクロ
LISPUSERLISPMEMOLisp is like a ball of mud - you can throw anything you want into it, and it's still Lisp. -- Anonymous Ruby 方面でみかけたネタに触発されました．Lisp はプログラマブルな言語な のでリーダーもプログラマブルです．そこでリーダーをいじって let や defun などの構文を括弧じゃなくて end にでもしてみましょうか． 100 行程度を目標にトライしました．使ったライブラリは CL-Yacc のみです． できあがったのがこちら． #@suck-lisp defun fib (n) if (< n 0) (error "oops") elif (= n 0) 0 elif (= n 1) 1 else let x <- (fib (- n 1))
JSON Parser with Monadic Parser Combinators - (new Hatena).blog()
PLT Scheme には既に JSON のパーサーが2つあるんですが: http://www.lshift.net/blog/2005/08/22/json-for-mzscheme-and-a-portable-packrat-parsing-combinator-library http://planet.plt-scheme.org/display.ss?package=json.plt&owner=dherman 気にせず作ってみました。 JSON 自体は文法が簡単なので短時間で作れたんですが、その過程でライブラリの重大な欠点も見つかりました。Scheme の #f の値をパース失敗と見なす方式だったために、JavaScript の "false" の値を #f に変換できない、という問題が判明したんです。 そのような問題修正やブラッシュアップを施したコードはこちらです (まだパ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「C 言語の宣言を読みやすくするスクリプト」を Rzubr で - Tociyuki::Diary
GitHub - VincentToups/parseltongue: A monadic parser combinator library for Common Lisp.
GitHub - drewc/smug: Super Monadic Über Go-into : parser combinators for Common Lisp
CL-peg
正規表現に見切りをつけるとき
NameBright - Coming Soon