The asteroid to kill this dinosaur is still in orbit. - Lex Manual Page A compiler or interptreter for a programminning language is often decomposed into two parts: Read the source program and discover its structure. Process this structure, e.g. to generate the target program. Lex and Yacc can generate program fragments that solve the first task. The task of discovering the source structure again
この構文を解析するパーサを Racc で作ってみます。 以下が Racc のソースになります。 とりあえず字句解析はしていません。parse メソッド内で擬似的にトークンを作っています(「1.」を想定)。 class MyParser # パーサクラス定義 (クラス名は任意) rule # rule 〜 end の間にパーサ文法を書く statement : NUMBER '.' # 『数字 '.'』を表す文法 end # 「---- inner」にはパーサクラス内部のコードを書く ---- inner def parse # MyParser#parse メソッド。(メソッド名は任意) @q = [] @q << [:NUMBER,'1'] # トークンを作る(ここでは擬似的に作る。「1.」が入力された想定) @q << ['.', '.'] # 〃 do_parse # do_pars
Racc は文法規則から Ruby で書かれたパーサを生成するパーサジェネレータです。 パーサ生成アルゴリズムには yacc などと同じ LALR(1) を使用しています。 yacc を知っている人は記述法の違いだけわかれば使えると思います。 yacc を知らない人は 拙著『Ruby を 256 倍使うための本 無道編』(青木峰郎著、ASCII) などを一読していただくのがよいかと思います。 他の UNIX コマンドなどとは異なり、 いきなり使うだけで Racc を理解するのはかなり困難です。 Racc とはなにか Racc は文法を処理するツールです。 文字列はただの文字の列で、コンピュータにとっては意味を持ちません。 しかし人間はその文字の列の中になにか意味を見出すことができます。 コンピュータにもそのようなことを、部分的にでも、させられたら便利でしょう。 Racc はその手伝いをして
この記事は言語実装 Advent Calendar 2016の1日目の記事です。 2週間前くらいからFortran 90の規格に準拠したパーサーを書こうとして苦労した話を書きます。 あまり大変だよ~という読み物になっており結論はありません。 なお実装は未完成です、、、 GitHub - nomaddo/f90: a tiny subset of fortran 90 written in ocaml. 経緯 SIMDの論文を読んでいたら実験したくなっていい感じのフロントエンドが欲しかった。 が、当初の目的は明後日に行ってパーサーを書いている。 道具 案の定OCaml + Menhirです。 私はヴァリアントのない言語でバグらずに実装できる気がしません。 (最近はCで書かれたコンパイラもよく読むのですが) OCamlでコンパイラを作るというのは僕の中では普通の選択肢です。 世間の皆様はCやC
このページは最後に更新されてから1年以上経過しています。情報が古い可能性がありますので、ご注意ください。 The Objective Caml system release 3.10 この章では ocamllex と ocamlyacc の解説をします。ocamllex は、正規表現の集合と、それに対応するセマンティクスから字句解析器を生成し、ocamlyacc は文法と、それに対応するセマンティクスから構文解析器を生成します。 このプログラム生成ツールは、C 言語環境で有名な lex と yacc ととてもよく似ています。この章は lex と yacc の知識があることを前提としています。ocamllex と ocamlyacc に与えるソースの文法や lex と yacc との主な相違点などは解説しますが、lex と yacc での字句解析器や構文解析器の基本的な書き方は解説しません。
この記事は Go その 3 Advent Calendar 2015 の 22 日目の記事です。 go tool の中には yacc というコマンドがあります。これはパーサジェネレータである yacc の Go 言語版です。この記事ではこれをつかって簡単な jq のクエリパーサっぽいものを作ってみようと思います。 (この記事のコードは https://github.com/zoncoen-sample/goyacc-jq-query-parser にあります。あとこの記事で話してるものを使って雑に作った jq like TOML processor が https://github.com/zoncoen/tq に上がってます。) ご存知の方も多いかと思いますが一応簡単に紹介しておくと、 jq は標準入力から受けとった JSON 文字列から値を取り出したり加工したりする事ができるコマンドラ
vol.1と言いつつvol.2を執筆しないと定評の高いerukitiです。こんにちは。(全文検索やrxjsの続き書こうと思いつつ…) 今日はGolangとPEGを使って、言語処理系を作る話の第一弾として、pointlander/peg の解説をします。 PEG? PEGでぐぐると、胃ろうとかいうのがヒットしますがそれじゃなくて、Parsing Expression Grammar です。簡単に言うとlexとyaccを足したみたいなジャンルの処理系で、字句解析付きのコンパイラコンパイラとか言えばピンと来るかもしれません。RFCを読んでる人ならBNFとか身近だと思うんですが、まぁその手の言語ルールを形式化したものの一種ですね。僕には学術的説明をするほどの知識はないので、厳密な話を知りたい人はいろいろぐぐってみてください。 expression <- additive additive <- m
goにはコンパイラ以外にもいくつか便利なツールがついてきていて、goyaccもその一つだ。yaccはパーサージェネレータで、プログラミング言語みたいな言語を読み取るためのプログラムを生成してくれる。goyaccはそのGo言語バージョンとなっている。 この文章では、簡単な言語を処理するプログラムを作りながら、goyaccを用いた構文解析の方法について説明する。 プログラム全体はdraftcode/goyacc_sampleで参照できる。文章中では抜粋しか載せないので、足りない部分はこちらをみて補って欲しい。 生成する言語 実際に字句解析器や構文解析器を作りながら説明するため、簡単な計算機のようなものを作ることにしよう。作る言語は次のような構文を持つ言語だ。 字句解析器 字句解析器は、文字列としてのソースコードからトークン列としてのソースコードへ変換するプログラムだ。 プログラムのソースコード
go toolにはyaccというものがある。 これはunixの言語処理系で広く使われるyaccというパーサジェネレータのGoバージョンである。 本稿はその使い方を説明するチュートリアルである。 対象読者 goyaccを使う - Qiitaという記事があって、これはgoのyaccを使って簡単な言語の構文解析をして使い方を説明している。 しかし、yaccについての基本的な説明が完全ではなく(例えば%%とか)、yaccを触ったことがない人には若干難しい。 従って、私のようなGoの文法は理解しているがyaccを使ったことがない人向けにごく簡単な使い方を説明する。 参考資料 yacc - The Go Programming Languageが公式のドキュメントっぽいが、これもyaccの文法自体は他に任せている。 RHGの速習yaccがとても参考になると思う。 本稿はあくまで取っ付き易いチュートリア
YACC の shift/reduce, reduce/reduce conflict の解消はパーサーの教科書もしくはネット情報に沢山書かれているます。まず、YACC の基本動作原理とともにそれなりに理解してください。たとえば http://guppy.eng.kagawa-u.ac.jp/2006/ProgLang/bison-1.2.8/bison-ja_8.html など。 どの教科書にもありますが、だいたい、 ルールが大雑把過ぎるのが原因であることが多いので、ジェネレータが conflict で迷わないようになるまでルールを書き下す。 トークンの優先順位と結合方向を指定することで適用可能なルールの数を減らす reduce/reduce は解消したほうがよい shift/reduce の場合は shift 優先なので、それで満足ならほっておく (ただしあなたの YACC 経験値は上
近年、Linuxやcygwinの普及によってだれでもyacc/lexを使って新しい言語を作成し、その処理系を作成することができるようになってきた。 G・フリードマンの「Cコンパイラ設計」は、yacc/lexの使い方を丁寧に説明した名著であるが、英語の原本も日本語本も絶版で、amazonのオークションでも買えないため日本語訳本を借り、OCRから復刻することにした。 Linux、cygwinではbison, flexが使われているので若干本書と内容が異なる部分があるが、それも別枠で整理してみたいと考えている。 4章以降は、竹本 浩のページ(Wiki)に追加中2008/05/15 コンピュータの発達とともに、これまでにCOBOL,FORTRAN、Pasca1,Lisp、C等、数多くのコンピュータ言語が作られてきました。一般には,新たなコンピュータ言語、あるいはそのコンパイラを作るなどということは
概要 パーサとスキャナ プログラム言語のパーサの書きかたは昔からしつこく研究されてきており、 かなりしっかりした定石がある。よほど変な(または曖昧な)文法でない 限り、定石にのっていけば解決できるものだ。 まず最底辺には文字列を単語(トークンとも言う)の列に切り出す部 分がある。これをスキャナ(scanner)とかレクサ(lexer)と言 う。日本語で言うと字句解析器だが、言いにくいのでスキャナと呼ぼう。 スキャナというものが出てくる根底にはそもそも「単語の区切りには空白ある でしょ」という常識がある。そして実際にたいていのプログラミング 言語はそういう仕様になっている。そのほうが楽だからだ。 例えば古いFortranでは空白が意味を持たなかった。つまり空白を入れても 単語区切りとは限らないし、変数の途中で何の前触れもなく空白を挿入したり することもできた。ところが解析が恐ろしく面倒なもの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く