nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

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にする
  • lengthfindなどを極力減らす
  • 状態はソートして集合の比較を高速化

それでも遅いんです。
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

あとは仕様書通りに文法ファイルを作っていけると思います。
ただし元のソースだとだと、誤字脱字の検出ができなかったので結構苦労しました。
最新のソースはそのあたりができるように、 terminalpnon-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-expressiontypedef-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さん、すごく勉強になりました!
どうもそういうものらしいです。
たぶん合ってるっぽい。

話を見る限りだと、字句解析と構文解析が連携してtokenを決定する必要があるようです。
そんなことしなきゃダメなのか。
ちょっと勉強し直してきます。

とりあえず対処はこんな感じにしました。

;; (6.7.7)
;(terminal identifier)
;(rule typedef-name -> identifier)
(terminal typedef-identifier)
(rule typedef-name -> typedef-identifier)

identifierではなく、typedef-identifierという別のtokenにしてごまかしました。
字句解析ががんばってidentifiertypedef-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++とかならそうなるのかな?

もし今回やったことを自分でもやってみたいなら、 githubc99/ディレクトリを保存して

$ sbcl --script main.lisp

みたいに実行すればいいと思います。