天泣記

2025-08-15 (Fri)

#1 Menhir の Incremental API と lexer hack

yacc や bison といった parser generator が生成する parser では、parser が lexer を呼んでトークンを得る。 Menhir (parser generator) でもデフォルトでは同じなのだが、Incremental API というものを使うと、違う形式で parser を利用できる。

Menhir の Incremental API では parser の状態が値として表現されて、 トークンを与えると次の状態を得られる、という形で利用できる。 これを使うとこのトークンを試してうまくいかなかったらあのトークンを試す、 といったことができそうである。

Menhir Reference Manual - 9.2 Incremental API

これについて調べていたところ、どうも Incremental API は Merlin (OCaml 用 language server) のために実装されたもののようである。

Merlin: A Language Server for OCaml (Experience Report)

Merlin は language server なので、人間が行うプログラムの変更に追随して高速に解析を行う必要があり、 そのためにインクリメンタルに動作させられる API が必要だったということだろう。 (たぶん、プログラムの途中におけるパーサの状態をいろいろとっておいて、変更より前の状態のうちでいちばん先のものからパースし直すのではないかと思う)

ただ、この Incremental API は他の用途にも使えて、以下の3つの用途があげられている。

興味があるのはふたつめの lexer hack であり、これは想定範囲の用途なのだろう、とわかる。

ここですでに使われた例として shell script の構文解析があげられている。 これをみてみよう。

#2 シェルの構文解析

Menhir の Incremental API を使ってシェルの構文解析を行うという話がすでにある。

Morbig: A Static Parser for POSIX Shell [PDF]

シェルでは、文脈に応じて、キーワードに見える文字列が、キーワードになったりならなかったりという動作がある。 以下は論文にあげられている例である。

for i in a b ; do echo $i ; done
ls for i in a b

上記の1行めの "for i in a b ; do echo $i ; done" の中の for, in, do, done はキーワードであるが、 2行めの "ls for i in a b" の中の for, in はキーワードでない。

同様なことがコマンドに対する環境変数の設定でも起きる。

CC=gcc make
make CC=cc

"CC=gcc make" の中の CC=gcc は make コマンドに対する環境変数 CC を gcc に設定するという意味だが、 "make CC=cc" の中の CC=cc は、make コマンドの第1引数に CC=cc を与えるという意味である。

shell の構文解析を lexer と parser に分割して実装するなら、 キーワードや環境変数設定を受け付けられる文脈かそうでないかを lexer が (parser の状態に依存して) 判定する、という実装が可能だろう。

ただ、受け付けられないキーワードを生成しなければならないこともある。 以下は、else キーワードは先頭には出現できないので、parse error にならなければならない。

else echo foo

しかし、キーワードを受け付けられるときには lexer がキーワードなトークンを生成するというやりかただと、 else は受け付けられない (parse error になる) ので else がキーワードにならず、else コマンドを実行するということになるだろう。

なので論文では、parser の状態 (LR スタック) を調べて、このときもキーワードにする細工をしているのだが、これは素直でない気がする。

ちょっと考えるに、キーワードをキーワードとして扱うのは、parser がキーワードを受け付けるというよりはもうちょっと大雑把に、 コマンドの先頭では常にそうする、という感じに扱った方がいいのではないかと思う。

なお、論文には他にもいろいろ厄介な話がかいてあるが、alias がいちばん問題というかどうにもならなさそう、と思った。

#3 C の構文解析

もうひとつ興味深いものとして、C の構文解析の話をみつけた。 C の構文解析では typedef 名が問題というのはよく知られているが、ちゃんとやるのはそう簡単ではないようだ。

A Simple, Possibly Correct LR Parser for C11

これも Menhir を使っているのだが、Incremental API でトークンが受け付けられるかどうかを試すということはしておらず、 (いつもの) グローバル変数での parser から lexer へ情報を渡すということをしているようだ。

この論文でとくに面白いと思った例は以下である。

typedef int T;
void f(void) {
  for(int T; ;)
    if(1);
  T x;
  x = 0;
}

T という識別子がトップレベルでは型として宣言され、for 文では変数として宣言されている。 ここで for 文で行われた宣言はこの for 文の中だけで有効である。

で、for 文が終わった直後に T が使われていて、これは for 文の内部ではないので、変数ではなく、型として認識されなければならない。 そのためには、変数 T のスコープが終了したということを parser から lexer に伝えなければならない。 それは、for 文を reduce したときのアクションで伝えることになるだろう。 しかし、そのアクションが実行されるときにはすでにこの直後の T というトークンは先読みとして読まれているのである。 なんでかというと、if (1); の後にもし else が来ると文はまだ続くので、ここでは先読みして文が終わることを確認しないと reduce できないのである。

つまり、無理である。

が、暗黙の想定を壊せばどうにかなるもので、 論文ではこれを解決している。 どう解決しているかというと、識別子はひとつのトークンであるという想定を破壊し、識別子をトークンふたつに分けるということをしている。 NAME, TYPE, VARIABLE という 3つのトークンを用意し、 型は NAME TYPE という連続する 2つのトークンで表現し、 変数は NAME VARIABLE という連続する 2つのトークンで表現する。 こうすると、上の例で if 文を認識する reduce で先読みが起こるが、それは NAME トークンを先読みすることになる。 そして、(for 文を認識する) reduce のアクションでスコープの情報を lexer に渡すと、それに基づいて次のトークンが TYPE か VARIABLE か適切に判別される。

なんともトリッキーである。

なお、この文脈では型と変数の両方が受け付けられるので、シェルでやったような、parser にトークンが受け付けられるかどうか尋ねる、という方法では解決できない。 ではどうするのがきれいか考えると、parser で継承属性を扱えるようにして、スコープをそういう属性として定義し、そのスコープを参照して semantic predicate で型か変数か区別できるといいのかも。

#4 その他

他にもいくつか興味深いところがある論文があったのであげておく

2025-08-16 (Sat)

#1 SGLR を推す論文

SGLR (scannerless generalized-LR parsing) と CAS+LR (context-aware scanning used with deterministic LR parsers) を比較している Context in Parsing: Techniques and Applications で参照されていた、SGLR を推す論文を読んでみた。

Pure and declarative syntax definition: paradise lost and regained [PDF]

これはなかなか面白い。

SGLR の利点がたくさんあげられていてそれぞれ納得できるものではあるが、 文法の曖昧さを静的に確認できないという問題はある。

また、いろいろあげられている利点には、CAS+LR に導入可能なものも多いと思う。

[latest]

田中哲