Common LispでLALR(1)のparserを作る5
前回:Common LispでLALR(1)のparserを作る4 - nptclのブログ
1. 続きです
Common LispでLALR(1)を作りました!
次にやることはでっかい構文を読み込ませることです。
ここではC言語の文法について見ていきます。
2. 大きな構文解析
C言語の構文解析をしてみましょう。
文法は仕様書に書かれています。
;; JTC1/SC22/WG14 - C ;; WG14/N1256 Committee Draft - Septermber 7, 2007 ISO/IEC 9899:TC3 ;; http://www.open-std.org/JTC1/SC22/WG14/ ;; http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf ;; ;; A.2 Phrase structure grammar
今回は、私の大好きなc99でやってみます。
文法の部分だけ抽出したファイルは下記の通り。
https://github.com/nptcl/parser/blob/main/c99/c99.lisp
こいつを読み込ませるためのソースを追記します。
(defun read-call-parse (x) (destructuring-bind (car . cdr) x (ecase car (terminal (read-terminal cdr)) (rule (read-rule cdr)) (start (read-start cdr))))) (defun read-parse (file) (with-open-file (input file) (read-call input #'read-call-parse))) (read-parse #p"c99.lisp")
さあ実行しようとmake-table
でShift表を作ったら、とんでもなく遅いんです。
びっくりするくらい遅い!
実は今までnpt
を使っていたのですけど、ついに力不足になりました。
sbcl
先生お願いします!
それでも遅い!
すごいですね、LR(1)って適当に作っただけなら全然ダメ見たいです。
ということで、できる限りの高速化を行ったものを下記に示します。
https://github.com/nptcl/parser/blob/main/c99/parser.lisp
今までテストコードとして作成したparser.lisp
は超遅いですが、
もともと実用を目指していないので、それはそれで価値があると思います。
ということで、今後バグは修正する予定ですが、高速化せずにそのまま残してあります。
(c99/parser.lispが早い方で、
blog/parser.lispがもともとの遅い方)
高速化のポイントを簡単に説明すると、
- リストの検索部分を
hash-table
にする length
やfind
などを極力減らす- 状態はソートして集合の比較を高速化
それでも遅いんです。
LR(1)ってとんでもないんですね。
自分の作りが甘いのは確かなのですが、それにしたって大変な処理というのは間違いないでしょう。
遅いのは受け入れることにします。
速度の改善を考えるのではなく、途中の処理をファイルに保存して再開できるような仕組みを考えます。
make-table
を実行した後は、save-table.lisp
というファイルに状態を保存できるようにしました。
今まで通りソースの解説をしたい気持ちはあるのですが、
元のソースからだいぶ変更が入りましたので、説明はやめておきます。
それより文法の解説をしなければならないことがあります。
3. C言語の文法を見る
仕様書n1256.pdf
から、構文ファイルc99.lisp
を作成するにあたっての注意点を書きます。
まず最初にopt
について。
仕様書を見ると、よくopt
と書かれている文法に遭遇します。
例えばこんな感じです。
(6.7.2.1) struct-declarator: declarator declarator_opt : constant-expression
declare_opt
という部分が該当します。
正直よくわからないんですけど、たぶん省略可能という意味なのではないでしょうか。
ということで、次のように書き換えをします。
(6.7.2.1) struct-declarator: declarator : constant-expression declarator : constant-expression
あとは仕様書通りに文法ファイルを作っていけると思います。
ただし元のソースだとだと、誤字脱字の検出ができなかったので結構苦労しました。
最新のソースはそのあたりができるように、
terminalp
とnon-terminal-p
を修正しています。
そうやってできた文法c99.lisp
を読み込み、make-table
を実行してみましょう。
時間がかかるので、中間ファイルを生成します。
(read-parse #p"c99.lisp") (make-table) (save-table #p"save-table.lisp")
もし再開したいなら、上記の3行は次の一つに置き換えることができます。
(load-table #p"save-table.lisp")
中間ファイルは6MByteくらいあるので、結構な情報が保存されるようです。
内容はLispの式であらわされますので、テキストエディタで確認できます。
4. Reduceの衝突
さあ問題はmake-reduce
です。
実行すると衝突が発生してエラーになります。
しかし、実は衝突が起こるのは分かっていたことなので、
エラーで中断させるのではなくwarning
が出力するように改造しておきましょう。
state-action-check
を下記のように書き換えます。
(defun state-action-check (list a b c) (destructuring-bind (x y z) list (unless (state-action-check-p y z b c) ;(error "~S/~S error, ~S, ~S." y b list (list a b c)) (when (rule-p z) (setq z (rule-left z))) (when (rule-p c) (setq c (rule-left c))) (warn "~S/~S error, ~A, ~A." y b (list x y z) (list a b c)))))
それでは実行してみます。
WARNING: S/R error, (ELSE S 1886), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1886), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1757), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1757), (ELSE R SELECTION-STATEMENT). WARNING: R/R error, (( R PRIMARY-EXPRESSION), (( R TYPEDEF-NAME). WARNING: R/R error, (* R PRIMARY-EXPRESSION), (* R TYPEDEF-NAME). WARNING: R/R error, (; R PRIMARY-EXPRESSION), (; R TYPEDEF-NAME). WARNING: R/R error, (( R PRIMARY-EXPRESSION), (( R TYPEDEF-NAME). WARNING: R/R error, (* R PRIMARY-EXPRESSION), (* R TYPEDEF-NAME). WARNING: R/R error, (; R PRIMARY-EXPRESSION), (; R TYPEDEF-NAME). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 1), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: S/R error, (IDENTIFIER S 846), (IDENTIFIER R DECLARATION-SPECIFIERS). WARNING: R/R error, () R IDENTIFIER-LIST), () R TYPEDEF-NAME). WARNING: R/R error, (, R IDENTIFIER-LIST), (, R TYPEDEF-NAME). WARNING: R/R error, (( R DIRECT-DECLARATOR), (( R TYPEDEF-NAME). WARNING: R/R error, () R DIRECT-DECLARATOR), () R TYPEDEF-NAME). WARNING: R/R error, ([ R DIRECT-DECLARATOR), ([ R TYPEDEF-NAME). WARNING: R/R error, (( R PRIMARY-EXPRESSION), (( R TYPEDEF-NAME). WARNING: R/R error, () R PRIMARY-EXPRESSION), () R TYPEDEF-NAME). WARNING: R/R error, (* R PRIMARY-EXPRESSION), (* R TYPEDEF-NAME). WARNING: R/R error, ([ R PRIMARY-EXPRESSION), ([ R TYPEDEF-NAME). WARNING: S/R error, (IDENTIFIER S 22), (IDENTIFIER R SPECIFIER-QUALIFIER-LIST). WARNING: S/R error, (IDENTIFIER S 22), (IDENTIFIER R SPECIFIER-QUALIFIER-LIST). WARNING: S/R error, (IDENTIFIER S 22), (IDENTIFIER R SPECIFIER-QUALIFIER-LIST). WARNING: S/R error, (IDENTIFIER S 22), (IDENTIFIER R SPECIFIER-QUALIFIER-LIST).
うーん、なんだこれ。
予想していたのは、いわゆるdangling elseというものだったのですが、
明らかにelse
以外の衝突が発生しています。
Shift/Reduce
だけだったら見ないふりできたんですけど、
Reduce/Reduce
も起きてませんか?
これって何なんだ。
先に言っておきますが、
WARNING: S/R error, (ELSE S 1757), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1757), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1886), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1886), (ELSE R SELECTION-STATEMENT).
このelse
の衝突は、dangling elseと呼ばれるものです。
Shiftを優先すれば解決できるという絶対起こるものなので
いまは気にしなくていいです。
しかしそのほかのやつは一体何なんだ?
5. 問題を見ていく
この衝突は迷いました。
衝突の内容を追いかけていく限りだと、
おそらくはtypedef
によって定義された型の名前が、
変数名と競合しているようです。
まずは下記の競合を見てみましょう。
WARNING: R/R error, (( R PRIMARY-EXPRESSION), (( R TYPEDEF-NAME). WARNING: R/R error, (* R PRIMARY-EXPRESSION), (* R TYPEDEF-NAME). WARNING: R/R error, (; R PRIMARY-EXPRESSION), (; R TYPEDEF-NAME). WARNING: R/R error, (( R PRIMARY-EXPRESSION), (( R TYPEDEF-NAME). WARNING: R/R error, (* R PRIMARY-EXPRESSION), (* R TYPEDEF-NAME). WARNING: R/R error, (; R PRIMARY-EXPRESSION), (; R TYPEDEF-NAME).
これはprimary-expression
とtypedef-name
のReduce/Reduceの衝突です。
両方をたどって行くと、identifier
で衝突が生じているようです。
identifier
は、変数名や関数名などを表す終端記号です。
primary-expression
は式に関する非終端記号であり、
さらにたどって行くとblock-item
という非終端記号に到着します。
block-item
とは、関数なんかのボディ部であり、{
と}
で囲まれた部分のことです。
void aaa(void) { /* ここです */ }
block-item
は、宣言declaration
と文statement
の2つの構文を取ります。
;; (6.8.2) (rule block-item -> declaration) (rule block-item -> statement)
宣言declaration
とは
int a;
みたいなものであり、文statement
とは
a = 10 + 20;
のようなものです。
それでは、次の記述はいったいなんだと思いますか?
hello;
これが競合の元です。
宣言declaration
なのか文statement
なのか、区別がつかないと言っています。
分かりづらいと思いますので、例文を示します。
typedef int hello; void aaa(void) { hello; }
上記の場合は、変数がひとつも無い宣言です。
変数宣言って
int a, b, c;
みたいに記載できますが、
どうも変数がひとつもなくてもぎりぎりセーフらしいです。
例えばこんな感じ。
int;
まあしっかり警告が出ますけどね。
続いて式の例を示します。
int hello = 100; void aaa(void) { hello; }
上記の場合は、変数がただ配置された式です。
もちろん意味は全くないです。
構文解析においては、両者の区別がつかず、
意味解析の時点でようやく判定できるというものです。
下手すりゃあ意味解析でも無理かもしれません。
確認する方法があります。
typedef
の型を表す構文は下記の通り。
;; (6.7.7) (terminal identifier) (rule typedef-name -> identifier)
これがidentifier
と競合するからおかしなことになっているわけです。
そこで一時的にtypedef
の型を使う場合の文法を変更してしまいます。
;; (6.7.7) (terminal aaa identifier) (rule typedef-name -> aaa identifier)
aaa
という文言がないとtypedef
の型を使えないようにしました。
C言語で表すならこんな感じ。
typedef int hello; aaa hello a, b, c;
それではmake-table
を実行します。
WARNING: S/R error, (ELSE S 1886), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1886), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1757), (ELSE R SELECTION-STATEMENT). WARNING: S/R error, (ELSE S 1757), (ELSE R SELECTION-STATEMENT).
衝突が全部消えてしまった。
一個か二個くらい消えてくれればラッキーと思ってたのですが、全部消えたの?
つまりはただtypedef-name
だけが問題だったということになります。
いちおう言っておきますが、上に出てる4つの衝突はdangling elseなので問題ありません。
というか、これ本当にあってるの?
なんとなくだけどparser.lisp
が悪いわけではなさそうなんですよね。
構文があっているとしても衝突は実際に生じているわけで、
それをどう処理していいのか迷います。
ぜんぜんわかりませんでした。
さんざん悩んでて検索したら、この話題がありました。
- y2q_actionman’s ゴミクズチラ裏
CL-Yacc と C言語文法の微妙な関係
https://y2q-actionman.hatenablog.com/entry/cl_yacc_and_the_lexer_hack
y2q_actionmanさん、すごく勉強になりました!
どうもそういうものらしいです。
たぶん合ってるっぽい。
話を見る限りだと、字句解析と構文解析が連携してtokenを決定する必要があるようです。
そんなことしなきゃダメなのか。
ちょっと勉強し直してきます。
とりあえず対処はこんな感じにしました。
;; (6.7.7) ;(terminal identifier) ;(rule typedef-name -> identifier) (terminal typedef-identifier) (rule typedef-name -> typedef-identifier)
identifier
ではなく、typedef-identifier
という別のtokenにしてごまかしました。
字句解析ががんばってidentifier
とtypedef-identifier
を使い分ければいいのではないでしょうか。
make-reduce
も問題なく通りました。
あと、忘れてましたがelse
は放置したのでどうなってるのか知りません。
それではLR(1)で次のC言語っぽいソースを読み込ませてみます。
int main() { return 0; }
それがこちら。
(execute-parse '(int identifier #\( #\) #\{ return constant #\; #\}))
どこがmain
関数なんだよといった見た目をしております。
実行結果は下記の通り。
NIL (INT IDENTIFIER #\( #\) #\{ RETURN CONSTANT #\; #\}) (INT) (IDENTIFIER #\( #\) #\{ RETURN CONSTANT #\; #\}) (TYPE-SPECIFIER) (IDENTIFIER #\( #\) #\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS) (IDENTIFIER #\( #\) #\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS IDENTIFIER) (#\( #\) #\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DIRECT-DECLARATOR) (#\( #\) #\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DIRECT-DECLARATOR #\() (#\) #\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DIRECT-DECLARATOR #\( #\)) (#\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DIRECT-DECLARATOR) (#\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DECLARATOR) (#\{ RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{) (RETURN CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN) (CONSTANT #\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN CONSTANT) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN PRIMARY-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN POSTFIX-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN UNARY-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN CAST-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN MULTIPLICATIVE-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN ADDITIVE-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN SHIFT-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN RELATIONAL-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN EQUALITY-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN AND-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN EXCLUSIVE-OR-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN INCLUSIVE-OR-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN LOGICAL-AND-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN LOGICAL-OR-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN CONDITIONAL-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN ASSIGNMENT-EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN EXPRESSION) (#\; #\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ RETURN EXPRESSION #\;) (#\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ JUMP-STATEMENT) (#\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ STATEMENT) (#\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ BLOCK-ITEM) (#\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ BLOCK-ITEM-LIST) (#\}) (DECLARATION-SPECIFIERS DECLARATOR #\{ BLOCK-ITEM-LIST #\}) NIL (DECLARATION-SPECIFIERS DECLARATOR COMPOUND-STATEMENT) NIL (FUNCTION-DEFINITION) NIL (EXTERNAL-DECLARATION) NIL (TRANSLATION-UNIT) NIL ACCEPT
うまくいってるように見えます。
6. おわり
最後はLALR(1)です。
こちらも、難なくうまくいきました!
とはいっても出力は同じなので結果は出しません。
かわりに、状態数をカウントしたものを出します。
LR(1)は、状態2004個
LALR(1)は、状態451個
どこかで、LR(1)は10000くらい生成されて、
LALR(1)では10分の1になるって書いてた気がします。
C++とかならそうなるのかな?
もし今回やったことを自分でもやってみたいなら、
githubのc99/
ディレクトリを保存して
$ sbcl --script main.lisp
みたいに実行すればいいと思います。