天泣記

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 に導入可能なものも多いと思う。

2025-08-26 (Tue)

#1 SGLR と CAS+LR をもとにどんなツールが作られたのか

SGLR と CAS+LR に性質の違いがあるとして、それぞれを使ってどういうツールが作られたのか調べてみた。

parser と lexer の関係が単純でない言語はそういうツールでどう扱われることになるのだろうか。

#2 SDF3

Multi-purpose Syntax Definition with SDF3 を眺めると、 SGLR を前提とした文法記述だが、parser と lexer に相当する記述は分かれている。

これは、トークン間の空白 (およびコメント) を文法としてぜんぶ書くのは面倒くさいので、 自動的に規則に空白の記述を挿入するためのようだ。 (なお、空白のことをレイアウトと呼んでいる。Python などのように indent 依存な文法を記述する方法もあって面白い)

ところで、lex などの lexer generator には最長一致といった規則があって、これは曖昧なパターンを解決する規則とみなせる。 これをそのまま SGLR で扱うと、曖昧なパターンから曖昧な構文木が生成されてしまうが、それを防ぐ方法がある。

まず、通常 lexer は最長一致で動作する。 たとえば、識別子が英数字として、foobar という入力を先頭から読む場合、識別子として f, fo, foo, foob, fooba, foobar のいずれかを認識可能である。 最長一致では foobar だけが認識される。ここではこの foobar がユーザが欲しいトークンだとしよう。

あと、最長一致したパターンが複数ある場合、(旧来的な lexer では) どれかひとつを選ばなければならない。 たとえば、if は IF というトークンとし、[a-zA-Z][a-zA-Z0-9]* は ID というトークンとする場合、 入力が if ならば、IF と ID のどちらが生成されてもおかしくない。 旧来的には (lex とかでは)、先に書いておいたほうが生成される。 また、if を常に ID にしてほしいなら IF の規則は不要なので、おそらく IF を優先してほしいというのが意図だろう。 (ここでは Ruby のように文脈に応じて変化するというのは考えない)

このように最長一致とキーワードの認識を SGLR ベースで実現するために、SDF3 は follow restriction と reject production という記述が可能になっていて、以下のように書けば実現できるようだ。

ID = [a-zA-Z] [a-zA-Z0-9]*
ID -/- [a-zA-Z0-9]
ID = "if" {reject}

最初の ID = [a-zA-Z] [a-zA-Z0-9]* が基本的な識別子の規則で、 ID -/- [a-zA-Z0-9] が follow restriction, ID = "if" {reject} が reject production である。

follow restriction により、ID が認識された直後に [a-zA-Z0-9] が出現した場合にはそのように認識する選択肢は除去する。 reject production により、"if" という 2文字が ID として認識された場合にはその選択肢は除去する。

これらにより、旧来的な lexer が行う最長一致とキーワードの認識を実現している。 (もちろん、if を IF にする規則は別に記述する必要がある)

follow restriction と reject production では済まない場合にどうしたらいいかというと、 複数の選択肢が残っている曖昧な構文木が生成されるので、後からどうにかする、という手段はある。

これで、最長一致とキーワードの認識が実現できることはわかったが、他の問題に対応することは可能だろうか。 (たとえば、Ruby の lexer を実現できるだろうか。)

そういうことを考えると、SGLR で、曖昧な木が生成されたときにそれを刈り込むコードを記述できればもっとも一般的だろうと思う。 でも、SDF3 でパースの最中に、なにかコードを実行して選択肢を刈り込むことが可能かというと、 そういう方法はこの論文では説明されていない (と思う)。 ただ、SDF3 では文法の記述をパースだけじゃなくていろいろな用途に使う。 なので、そういうなにが起こるかわからないコードを動かすのはパース以外の処理でどう扱っていいか分からないので、導入困難だと思う。 というわけで、そういう方法は存在しないか、あったとしても使ってほしくない機能になるだろう。 あと、SDF3 はプログラミング言語ではないので、そういうコードをどんな言語で記述するか、という問題もあるか。

でもそうだとすると、lexer と parser の難しいインタラクションは曖昧な構文木が生成されるから、パースが終わったあとで処理する、という形になるのだろうな。

#3 Silver

Silver: An extensible attribute grammar system を眺めると、 これは lexer と parser の厄介な関係にはほとんど触れられていない。 この論文では属性文法をどう使っているかという話が主題。

Context-Aware Scanning for Parsing Extensible Languages [PDF] とかで 説明されている Context-aware scanner のままということだろう。

属性文法については、煩雑だけど、ここで扱おうとしている言語の組み合わせ (ホスト言語に DSL を埋め込むとか) をシステムが支援するにはそういうのもひとつの方法かな、というくらいの感想をもった。

なおこの論文においては、属性文法は lexer の動作には影響しないと思う。 Context-aware scanner は LR parser の lookahead 集合を lexer に渡すというだけで、属性文法から lexer に影響を与える方法は述べられていないと思う。 あと、Silver において属性の計算はパース時に行うと限定されておらず、一般には属性の計算結果を使って lexer に影響を与えるのは無理。 (属性文法をつかって lexer に影響を与えるなら、パース時に属性計算を行って lexer に情報を提供する必要がある)

#4 lexer と parser のモジュール化

SDF3 や Silver を眺めながら考えると、結局、lexer と parser を分けるのはモジュール化なので、一般のモジュール化の利点欠点がここでも成り立つのかもしれないと思いついた。

SDF3 が SGLR で parser と lexer をいっしょくたにして扱うといっても、人間は parser と lexer を分けて記述するわけだし、 モジュール化には利点があるのだろう。

Grok にモジュール化の利点欠点を尋ねたところ、以下の回答が返ってきた。 まぁそれっぽい。

利点

欠点

これを lexer と parser のモジュール分割について考えてみる。

利点

欠点

こんなもんかなぁ。 parser と lexer の話に限定した話を取り出すと、以下くらいかな。

利点

欠点

なんにせよ、lexer と parser の間のよいインターフェースのデザインが問題と思う。

#5 LR 構文解析と並行処理

parser の理解のしやすさについて考えていてふと思ったのだが、LR parser の動作は非決定的な処理を並行に進めるというものなので、 並列プログラミング同様に、人間の理解を越えがちという問題はあるかもしれない。

そう考えると、 並列プログラミングにおいてモデルチェッカで到達可能な状態をすべて確認するのと、 LR parser generator が決定的オートマトンを作って conflict を検出するのは対応しているのかもしれない。 それらによって、到達可能なすべての状態においてなにが起こるかを確認し、変な事が起きないことを静的に保証できる。

GLR で CFG をなんでもパースするというのは、そういう静的解析を使わない並行プログラミングなのかもな。

あと、手書きでパーザを書くのは素直には並行処理になるものをがんばって逐次処理で書くことになるのかもしれない。

2025-08-27 (Wed)

#1 GLR を使った Ruby のパーサ

気がついたのだが、GLR を使って Ruby のパーサを書いた例があるようだ。

The ruby intermediate language [著者ページ]

これは dypgen という parser generator を使っている。

dypgen -- Self-extensible parsers and lexers for OCaml

選択肢の刈り込みは OCaml のコードで行うみたいだな。

#2 SDF3 の仕様

論文だと全部は説明できないのはしょうがないので、マニュアルはないか探すと、以下がそうなのかなぁ。

しかし、SDF で記述されていて、自然言語による説明はあまりない感じ?

2025-08-29 (Fri)

#1 Elizabeth Scott と Adrian Johnstone の論文

構文解析の論文を探していて、以下のふたりがいろいろ書いているのに気がついた。

気になる文献がいくつかある。

まず、lexer が token の並びではなく、TWE (Token With Extents) の集合を生成する、というアイデアの話があった。 extents というのは token の開始位置と終了位置なので、字句解析があいまいでなければ位置でソートすれば token の並びと同じになる。 でも字句解析がそこまで決定的にするのが難しければ、複数の可能性を残して構文解析のほうでどうにかするという話のようだ。

あと、以下のふたつも気になった。

2025-08-30 (Sat)

#1 IELR で parse.y を処理すると do の難しさが解決されるか

RubyKaigi 2025 follow up でちょっと質問した話を自分で試してみた。 (質問のときは canonical LR と言った気がするけど、試すのは IELR だよな)

parse.y を LALR じゃなくて IELR で処理することによって、 キーワード do の衝突をどうにかできるのではないかという話なのだが、 bison では IELR を使えるので、bison を使っていた頃の Ruby を使えばすぐに試せるのではないか。

lrama が入ったのは Ruby 3.3.0 のようなので、Ruy 3.2.9 で試してみよう。

parse.c の生成を観察すると、まず parse.y から parse.tmp.y を作り、 parse.tmp.y から bison で y.tab.c を作っている。

なので、parse.tmp.y をいじって、keyword_do_cond, keyword_do_block, keyword_do_LAMBDA を消して keyword_do にしてしまう。 また、%define lr.type ielr を追加する。 これで、conflict した文法を IELR で処理することになる。

% diff -u parse.tmp.y- parse.tmp.y
--- parse.tmp.y-        2025-08-30 22:43:42.024243269 +0900
+++ parse.tmp.y 2025-08-30 22:49:29.173601547 +0900
@@ -11,6 +11,8 @@

 %require "3.0"

+%define lr.type ielr
+
 %{

 #if !YYPURE
@@ -519,9 +521,6 @@
       TOKEN2ID(keyword_retry);
       TOKEN2ID(keyword_in);
       TOKEN2ID(keyword_do);
-      TOKEN2ID(keyword_do_cond);
-      TOKEN2ID(keyword_do_block);
-      TOKEN2ID(keyword_do_LAMBDA);
       TOKEN2ID(keyword_return);
       TOKEN2ID(keyword_yield);
       TOKEN2ID(keyword_super);
@@ -1416,9 +1415,6 @@
         keyword_retry        "`retry'"
         keyword_in           "`in'"
         keyword_do           "`do'"
-        keyword_do_cond      "`do' for condition"
-        keyword_do_block     "`do' for block"
-        keyword_do_LAMBDA    "`do' for lambda"
         keyword_return       "`return'"
         keyword_yield        "`yield'"
         keyword_super        "`super'"
@@ -3748,7 +3744,7 @@
                    }
                ;

-k_do_block     : keyword_do_block
+k_do_block     : keyword_do
                    {
                        token_info_push(p, "do", &@$);
                    /*%%%*/
@@ -3823,7 +3819,7 @@
                ;

 do             : term
-               | keyword_do_cond
+               | keyword_do
                ;

 if_tail                : opt_else
@@ -4172,7 +4168,7 @@
                        token_info_pop(p, "}", &@3);
                        $$ = $2;
                    }
-               | keyword_do_LAMBDA
+               | keyword_do
                    {
                    /*%%%*/
                        push_end_expect_token_locations(p, &@1.beg_pos);
@@ -9771,11 +9767,11 @@
            if (kw->id[0] == keyword_do) {
                if (lambda_beginning_p()) {
                    p->lex.lpar_beg = -1; /* make lambda_beginning_p() == FALSE in the body of "-> do ... end" */
-                   return keyword_do_LAMBDA;
+                   return keyword_do;
                }
-               if (COND_P()) return keyword_do_cond;
+               if (COND_P()) return keyword_do;
                if (CMDARG_P() && !IS_lex_state_for(state, EXPR_CMDARG))
-                   return keyword_do_block;
+                   return keyword_do;
                return keyword_do;
            }
            if (IS_lex_state_for(state, (EXPR_BEG | EXPR_LABELED | EXPR_CLASS)))

さて、このパッチでは %define lr.type ielr をつけているが、これをつければ IELR でつけなければ LALR である。 (LALR をしてするのに lalr と書いてもよい。また、canonical LR を指定するには canonical-lr と書く。)

Bison Manual - 5.8.1 LR Table Construction

で、LALR と IELR (と、ついでに Canonical LR) で bison を動かしてみた。

LALR の場合:

% bison -d  -o y.tab.c parse.tmp.y
parse.tmp.y: エラー: シフト/還元衝突: 4 個が見つかりました, 0 個は期待通りです
parse.tmp.y: エラー: 還元/還元衝突: 3 個が見つかりました, 0 個は期待通りです
parse.tmp.y: ノート: '-Wcounterexamples' オプションをつけて競合の反例を生成するために再実行

IELR の場合:

% bison -d  -o y.tab.c parse.tmp.y
parse.tmp.y: エラー: シフト/還元衝突: 4 個が見つかりました, 0 個は期待通りです
parse.tmp.y: エラー: 還元/還元衝突: 3 個が見つかりました, 0 個は期待通りです
parse.tmp.y: ノート: '-Wcounterexamples' オプションをつけて競合の反例を生成するために再実行

Canonical LR の場合:

% bison -d  -o y.tab.c parse.tmp.y
parse.tmp.y: エラー: シフト/還元衝突: 199 個が見つかりました, 0 個は期待通りです
parse.tmp.y: エラー: 還元/還元衝突: 759 個が見つかりました, 0 個は期待通りです
parse.tmp.y: ノート: '-Wcounterexamples' オプションをつけて競合の反例を生成するために再実行
...数分待っても終了しない...

これを見るかぎり、LALR から IELR に買えても衝突の数は変化しない。 (シフト/還元衝突が4個、還元/還元衝突が3個)

(ついでに、Canonical LR は遅すぎて使い物にならなさそうなことがわかる。)

というわけで、少なくとも IELR にするだけですぐに問題が解決する、というわけではない。

IELR でなにか変化が起こるかもしれないけれど、それが役に立つかどうかはここからはわからない。

[latest]

田中哲