天泣記

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

A trustworthy mechanized formalization of R [PDF]

GNU R は改行を無視するかどうかを lexer hack で実装している。

function () break + 1 で、function や + の直後に改行を挿入しても意味は変わらないが、break の直後に挿入すると意味が変わる。
Context-Aware Scanning for Parsing Extensible Languages [PDF]
- その時点で受付可能なトークンの集合を lexer に渡す (でも、LALR だとすると、reduce してから error になる場合を考慮してないような気がする)
- Java 1.5 で List<List<Integer>> の最後の >> をひとつのトークン (right shift) じゃなくてふたつの > (less than) というトークンにする
- Java の中に SQL を埋め込む
Context-aware scanning and determinism-preserving grammar composition, in theory and practice

上の Context-Aware Scanning for Parsing Extensible Languages の著者の一人の D論で、 Background and related work のところにどういうのがいいのかという考え方や他の手法に関する見解がいろいろ書かれている。

事前に決定的に構文解析できる (ただひとつの構文木が得られる) ことを保証できるのが重要で、 GLR みたいに複数の構文木が得られる可能性があったり、 PEG のようにひとつの構文木が得られるにしてもそれが正しいものなのかの保証がないのはよろしくない、という立場のようである。
Context in Parsing: Techniques and Applications

Context-Aware Scanning for Parsing Extensible Languages のもうひとりの著者による SGLR (scannerless generalized-LR parsing) と CAS+LR (context-aware scanning used with deterministic LR parsers) の比較。 (著者は CAS+LR を開発している。)

SGLR は文字をトークンとして GLR を使い、文法が曖昧で複数の構文木が出てくる場合には後でフィルタする。フィルタにより確実にひとつの構文木が残るかどうかは保証されない。

CAS+LR は LALR parser の状態に応じて受付可能なトークンを lexer が生成する。曖昧な文法は LALR でコンフリクトが検出される。ただし曖昧でなくてもコンフリクトが検出されることはあり、そのような場合は文法を LALR で扱える形に変形する必要がある。

ということで、その変形のコストは静的な保証にみあうものなのか、という問題になるのだが、この論文の著者は言語を作るのは言語の専門家を想定していて CAS+LR で必要になる変形は許容可能と想定しているのに対して、 SGLR (を使ったツールを開発している研究者) はもっと普通の開発者が言語を作ることを想定していてその変形はつらい、という立場の違いに起因するということのようだ。
Parsing and Analyzing C/C++ code in Eclipse

Eclipse はパフォーマンスの都合でヘッダファイルを読み込まずに 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 で型か変数か区別できるといいのかも。

#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 がいちばん問題というかどうにもならなさそう、と思った。

#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つの用途があげられている。

Error message support : LR スタックを調べられるので、それを利用したエラーメッセージを表示できる
Generalized lexer hack : parser の状態を lexer に渡して lexer がそれに依存した動作を行える
Simulating local GLR parsing : parser のある状態で複数のアクションを行えるなら、(conflict としてしまうのではなく) すべてのアクションを行って、ありうる状態すべてを求めるようににすれば、GLR っぽい動作になる。

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

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

天泣記

2025-08-16 (Sat)

2025-08-15 (Fri)

2025-07-31 (Thu)

2025-06-28 (Sat)

2025-05-29 (Thu)

2025-04-18 (Fri)