Ruby Parser開発日誌 (6) - parse.yのMaintainabilityの話 - かねこにっき
前回のあらすじ Ruby Parser開発日誌 (5) - Lrama LALR (1) parser generatorを実装した - かねこにっき Error Recoveryを実装するためにLrama LALR (1) parser generatorを実装しました。 Error Recoveryについては目処がたったので今回はparse.yのMaintainabilityをいかにして改善するか考えたいと思います。 parse.yの難しさ Rubyのparse.yの難しさについては聞く人によって異なる回答が返ってくるところですが、おおよそ以下のようにまとめることができると思います。 ファイルの行数が多い shift/reduce conflictやreduce/reduce conflict時に何が起きているか分かりにくい Bisonが原始的な記法しか提供していないので全ての規則を書
第9章 速習yacc
概要 パーサとスキャナ プログラム言語のパーサの書きかたは昔からしつこく研究されてきており、 かなりしっかりした定石がある。よほど変な（または曖昧な）文法でない 限り、定石にのっていけば解決できるものだ。 まず最底辺には文字列を単語（トークンとも言う）の列に切り出す部 分がある。これをスキャナ（scanner）とかレクサ（lexer）と言 う。日本語で言うと字句解析器だが、言いにくいのでスキャナと呼ぼう。 スキャナというものが出てくる根底にはそもそも「単語の区切りには空白ある でしょ」という常識がある。そして実際にたいていのプログラミング 言語はそういう仕様になっている。そのほうが楽だからだ。 例えば古いFortranでは空白が意味を持たなかった。つまり空白を入れても 単語区切りとは限らないし、変数の途中で何の前触れもなく空白を挿入したり することもできた。ところが解析が恐ろしく面倒なもの
gojqのパーサーを書き直しました - プログラムモグモグ
jqはJSONを絞り込むツールですが、実はれっきとしたプログラミング言語です。 算術演算子、論理演算子、分岐構文、try・catch、そして関数定義があり、ループは再帰関数で実装します。 単に .foo とか .[0] とかでJSONを辿るだけのツールだと思われている方は、builtin関数の定義を見ていただくと良いかと思います。 selectやmapのように、よく使われる関数でさえ内部実装になっていない (Cで書かれていない) のは面白いですね。 jqのクエリを思ったように書けないという経験から、jqをより深く知るためにGo言語で再実装したのがgojqです。 去年の4月から開発を始め、8月にブログ記事を書きました。 jqのほぼすべての機能を実装しており、pure Goで書かれているのでGo言語のツールに簡単に組み込むことができます。 この記事公開以降も開発を続けています。 --arg,
プログラミング言語を作る yaccとlex
yacc/lexとは Cでプログラミング言語の処理系を実装するのであれば、 多くの場合、yaccとlexというツールを使います。 実のところ、Cとyacc/lexで簡単なプログラミング言語を作る、というのは、 以前、「C言語ヨタ話 」で書いた「 電卓を作ってみよう」 の焼き直しになります。yaccとlexの説明もそちらに簡単に書いたので、 そちらを見てください――と言いたいところですが、 まあここでも軽く説明します。 内容的には重複、というかコピペしている部分もありますが。 プログラミング言語の処理系は、通常、以下のような手順を取ります。 字句解析 ソースプログラムを、「字句(トークン)」の並びに分割する処理です。 構文解析 トークンの並びから、解析木を構築する処理です。 この後、Cなどの機械語を吐くコンパイラや Javaのようなバイトコードを吐くコンパイラなら、 「コード生成」という処理
HTTPパーサにおけるSSE4.2最適化の威力と注意点 - Cybozu Inside Out | サイボウズエンジニアのブログ
こんにちは、サイボウズ・ラボの光成です。 PicoHTTPParserは@kazuhoさんたちが開発している高速なHTTPパーサです。 同じ作者によるHTTPサーバH2Oにも使われています。 11月4日の開発ブログによると、その時点でNode.jsなどに使われているhttp-parserの10倍程度の速度を誇るそうです（現在はhttp-parserも速度向上しその差は縮まりました。それでも4倍以上の差があるようです）。 該当ブログにはその高速化のためのノウハウが書かれていて大変興味深いです。ただIntel系CPUに搭載されているSIMD命令は用いられていませんでした。今回、@kazuhoさんと一緒に文字列処理専用のSSE4.2を用いることで1.7～1.9倍の高速化を達成しました（Improving Parser Performance using SSE Instructions (in
PythonでElementTreeを使ってXMLを処理する方法 - hikm's blog
ElementTreeはpythonでXMLを扱うためのライブラリです。バージョン2.5からはpythonに標準で内蔵されています。 このライブラリを使うと、XMLをパースしてプログラム内で利用しやすい形に変換したり、XMLファイルを生成したりすることが出来ます。そこで今回は、XMLをパースして利用する方法についてまとめたいと思います。 準備 Python2.5以降にはElementTreeが標準で内蔵されているため、パッケージを個別で入手する必要はありません。 以下のようにインポートするだけで利用できます。 from xml.etree.ElementTree import * Python2.5より古いバージョンを利用している場合は、 http://effbot.org/zone/element-index.htm からパッケージを入手し、以下のようにインポートして下さい。 from
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
