2008-05-23

LL(*) について

The Definitive ANTLR Reference に次のような節があった.

以下は LL(*).

decl : modifier* 'int' ID '=' INT ';'
     | modifier* 'int' ID ';'

modifier
     : 'static'
     | 'register'
     ;

以下は LL(*) でない.

decl : 'int' declarator '=' INT ';'
     | 'int' declarator ';'

declarator
     : ID
     | '*' declarator
     ;

理由として書いてあるのは,選択肢(右辺)が再帰的な規則への参照を持っているから,ということである.この理由は,プッシュダウンオートマトンではなく DFA を利用して選択肢を決定していることから帰結されるとも書いてある.

よく考えてみなくてはならない.

ちなみに上のどちらも LALR(1) で問題なく受理される.

2008-05-15

字句解析・構文解析の調査

プログラミング言語の字句解析・構文解析を調べている.

今回の調査の目的は,既に文法定義が存在する言語の字句解析・構文解析プログラムを作成する際の注意点を列挙することである.新しい言語の定義を行う際の注意点の列挙や,字句解析・構文解析プログラムの自動生成プログラムを作成する方法の調査は今回の目的ではない.

注意点の概要をまとめる.

  • 字句解析については特段に注意すべき点はない.
  • 構文解析アルゴリズムは LL(1) または LALR(1) のどちらか.
  • LL(1) は手書きに適している.
  • LALR(1) は自動生成プログラムが必要.
  • 構文解析における文法記述では,左再帰性・右再帰性に注意する必要がある.
    • LL(1) は最左導出を行うので,左再帰性があると構文解析ができない.
    • LALR(1) は最右導出を行うので,右再帰性があると効率が悪い.
  • LALR(1) についてはシフト還元構文解析の考え方を理解する必要がある.
    • 理解するには LR 状態や LR マーカ(ポインタ)の考え方を利用する.
    • 理解しなければならないわけは,構文解析プログラムの自動生成の際に発生するエラーに対処するため.
  • 文法のあいまいさを解決するには,
    • 文法を書き換える.
    • 演算子の優先度,結合性などのあいまいさ除去規則を利用する.
    という方法があるが,除去規則を用いたほうが効率がよく見通しがよい.

いつも間違えるのだが,最左導出とは,文法形式(規則の右辺)の中の非終端記号のうち,最も左のものを最初に(構文木の「上」のほうで)展開する導出である.右辺の選択肢(|による列挙)のうちの左右は関係ない.

参考文献

[1] 佐々政孝 「プログラミング言語処理系」 第4章.

[2] Levine et al. 「lex & yacc プログラミング」 第8章.

2008-05-12

OCaml 関連のパッケージ

OCaml 関連で便利そうなパッケージ.Debian の ocaml-core が依存しているパッケージをあげてみる.

ocaml-findlib
OCaml のパッケージ(関連するモジュールの集合)を扱うライブラリとコマンド.
ocaml-tools
よりよい vim 用のインデントサポート omlet.
camlidl
OCaml コードと C のグルーを IDL から生成するツール.
ocamlweb
OCaml 用の Knuth web システム.
libounit-ocaml-dev
ユニットテスト.
cameleon
グラフィカルな IDE.
cmigrep
ocamldsort
OCaml のソースファイルを依存関係によってソートして表示する.
ledit
otags
ctags for OCaml.
OCamlMakefile
OCaml 用の Makefile を書くためのヘルパー.
camlp4, camlp4-extra
OCaml 用のマクロ.

2008-05-06

Module::Starter::PBP による Perl モジュール雛形の作成

Perl のモジュールの雛形を作るには h2xs を使うのが定番だが,最近では Module::Starter を使うのがナウいということだ.さらに,Module::Starter::PBP を使うと Perl Best Practice に倣ったテンプレートでモジュールを作成できる.

まずインストール.

$ sudo aptitude install libmodule-starter-perl

説明書.

$ perldoc Module::Starter
$ perldoc Module::Starter::PBP

方法.

$ perl -MModule::Starter::PBP=setup
$ module-starter --module=Your::Module::Name
Unknown placeholder <MAIN PM FILE> in Makefile.PL

Ugh!

See TAKESAKO @ Yet another Cybozu Labs: [訂正] Webプログラミング実力アップ Part1 正しいPerl/CGIの書き方:ITpro

参考