1. はじめに

Common LispでLALR(1)のparserを作りたくなりました。
ここでは、ただひたすらparserを作っていきます。

テストコードですが完成版を先に置いておきます。
https://github.com/nptcl/parser/blob/main/blog/parser.lisp

2. parserの説明

parserは、構文解析器(syntax analyzer)と呼ばれます。
種類がいろいろありますが、ここで作るのは次の2つ。

LR(1)
LALR(1)

いちおう説明を混ぜつつ作っていく予定ですが、理解したいだけなら参考資料を見た方が早いです。
というか、私自身全然理解できてません。
見たサイトを紹介します。

LR(1)パーサジェネレータを自作して構文解析をする第1回:かんたん構文解析入門
http://tatamo.81.la/blog/2016/12/22/lr-parser-generator-implementation/
日本語で分かりやすく書かれていてよかったです。
2016年度コンパイラ理論の講義資料
http://www.sakurai.comp.ae.keio.ac.jp/classes/2016Compiler.html
http://www.sakurai.comp.ae.keio.ac.jp/classes/DENDAI/2016/08LR.pdf
大学の講義資料のようで、難しかったけどずっと見てました。
LR構文解析
 https://www.slideshare.net/ichikaz3/lr-parsing
これ本当に良かったです。
絶対見た方がいいです。

3. token

まずはtokenについて。
tokenとは、parserの前段である字句解析が出力するものです。
でも今回は字句解析を作成しません。
そのかわり、Common Lispのreaderを使います。

字句解析は、入力に文字列を受け取り、tokenの列を返却します。
たとえば、

10 + 20 + 30

という文字列を受け取ったら、

INT PLUS INT PLUS INT

のようなtokenの列を返却します。
INTは構造体だと思ってください。
本来であればちゃんと、10とか20のような値を取り出せます。
でも今回はtokenをCommon Lispのsymbolで表したいと思います。
上記の例の場合、

(int + int + int)

のような列でいいのではないでしょうか。

4. 文法

文法を定義しましょう。
文法は次の3つくらいから成り立ちます。

終端記号 (terminal symbol)
規則 (rule)
開始記号 (start symbol)

順番に作っていきます。

4.1 終端記号

終端記号とは、それ以上展開がない記号の事です。
設定は、次のように行うことを考えます。

(parse-terminal + * [ ] int)

これは、+, *, [, ], intの5つの記号を終端記号に設定しています。
コードは次の通り。

(defvar *terminal* nil)

(defun read-terminal (cdr)
  (dolist (x cdr)
    (pushnew x *terminal*)))

(defmacro parse-terminal (&rest args)
  `(read-terminal ',args))

ただ、*terminal*という変数にpushするだけです。
あと、read-terminalをparse-terminalで囲っているのは、ただ、symbolをquoteするのが面倒だっただけです。
いやなら直接read-terminalを使ってください。

終端記号かどうかの判定は、*terminal*に存在するかどうかを調べます。

(defun terminalp (x)
  (and (member x *terminal*) t))

4.2 規則

規則とは、例えば次のようなものです。

expr -> expr + term
expr -> term
term -> term * fact
term -> fact
fact -> ( expr )
fact -> int

これをLispの式で表します。

(parse-rule expr -> expr + term)
(parse-rule expr -> term)
(parse-rule term -> term * fact)
(parse-rule term -> fact)
(parse-rule fact -> [ expr ])
(parse-rule fact -> int)

parse-ruleは、規則を制定するときに使います。
->は、左辺と右辺を区切る記号です。
ちょっと困ったのが[ expr ]です。
本当は( expr )であり、数式をまとめるやつなんですが、 ()にしてしまうと、Lispのreaderが色々やってしまうので構文解析ができません。
仕方がなく[]のカッコにしました。
今回は説明のためだけの対処なので、もし本番を作る場合は、そもそもtokenにsymbolなんか使わずに、 classやらstructureやら使ってください。
ひとまずこれでいきます。

規則は、専用の構造体を用意します。

(defstruct rule index left right accept)

例えば次の規則の場合。

A -> B C D

leftにはAが、rightには、(B C D)が入ります。
indexは通し番号が入ります。
acceptは通常nilですが、開始記号の場合はtを入れます。
これはあとあとの処理で役立ちます。

まずは構造体のインスタンスを作成する処理を示します。

(defvar *rule-index* 0)

(defun rule-instance (left right &optional accept)
  (prog1 (make-rule :index *rule-index* :left left :right right :accept accept)
    (incf *rule-index*)))

rule-instanceは、leftとrightを値に受け取り、インスタンスを生成します。
acceptもオプションで設定可能です。
indexは自動で設定されます。

規則はどこかにまとめて保存しておく必要があります。
今回は、*rule*という変数にリストとして保存することにします。

(defvar *rule* nil)

(defun read-rule (cdr)
  (destructuring-bind (left check . right) cdr
    (unless (eq check '->)
      (error "Invalid rule, ~S." cdr))
    (unless right
      (error "right value error, ~S." cdr))
    (push (rule-instance left right) *rule*)))

(defmacro parse-rule (&rest args)
  `(read-rule ',args))

(defun non-terminal-p (x)
  (and (member x *rule* :key #'rule-left) t))

read-rule関数は、なにやらごちゃごちゃしていますが、ただインスタンスを*rule*にpushしてるだけです。

non-terminal-pは、非終端記号かどうかを調べます。

4.3 開始記号

最後に開始記号です。

(defvar *start-symbol* (make-symbol "START"))
(defvar *start* nil)

(defun read-start (cdr)
  (destructuring-bind (start) cdr
    (when *start*
      (error "start already exist, ~S." *start*))
    (push (rule-instance *start-symbol* (list start) t) *rule*)
    (setq *start* start)))

(defmacro parse-start (&rest args)
  `(read-start ',args))

何をしているのかというと、

(parse-start expr)

が実行されたら、*start*変数にexprを保存したあと、

(parse-rule #:start -> expr)

という規則を*rule*に追加します。
#:startはgensymになっているため、仮にstartという非終端記号が現れても競合しません。

4.4 まとめ

例ですが、今後使っていく文法を下記に示します。

(parse-terminal + * [ ] int)
(parse-start expr)
(parse-rule expr -> expr + term)
(parse-rule expr -> term)
(parse-rule term -> term * fact)
(parse-rule term -> fact)
(parse-rule fact -> [ expr ])
(parse-rule fact -> int)

それっぽくなってきました。
入力はリストになります。
例えば次のようになると思います。

(int * int + int)

5. 構文解析器

まずは、最終的に何を作るのかを解説します。
構文解析器は、

tokenの列を入力として受け取り
stackを用いて文法を判定します

それでは、まずは入力を何とかしましょう。

(defvar *end* (make-symbol "END"))
(defvar *input*)

(defun set-input (x)
  (setq *input* x))

(defun pop-input ()
  (if *input*
    (pop *input*)
    *end*))

(defun top-input ()
  (if *input*
    (car *input*)
    *end*))

set-inputで入力の列を設定します。
pop-inputで入力から一つ値を取り出します。
top-inputは先頭の入力を返却しますが、取り出しはしません。

例として、aaa + bbbという入力を設定します。

(set-input '(aaa + bbb))

入力をpopしてみましょう。

(pop-input)
-> AAA
(pop-input)
-> +
(pop-input)
-> BBB
(pop-input)
-> #:END
(pop-input)
-> #:END

入力が終わったら、#:ENDというgensymが出力されるのがわかります。

次は、処理の中枢となるスタックを作ります。

(defvar *stack* nil)

(defun push-stack (x)
  (push x *stack*))

(defun pop-stack ()
  (unless *stack*
    (error "pop-stack error"))
  (pop *stack*))

(defun top-stack ()
  (unless *stack*
    (error "top-stack error"))
  (car *stack*))

(defun init-stack ()
  (setq *stack* nil))

ただpushとpopを隠蔽しているだけです。
作成したinputとstackを使い、次の2つの処理を実装します。

shift処理
reduce処理

このshiftとreduceという処理が、構文解析でとても大切なものになります。
この2つをちゃんと覚えておいて下さい。

shiftは、たんに入力をstackにpushするだけです。
reduceは、文法から非終端記号に変換します。

実際にやってみて説明します。
まずはshiftから。

(defun shift-test ()
  (push-stack
    (pop-input)))

これはとても簡単な処理です。
動作確認なんかもしたいので、stackとinputを出力する関数を用意します。

(defun output-stack-input ()
  (format t "~S~30T~S~%" (reverse *stack*) *input*))

inputだけを設定した時の動作を見てみましょう。

* (set-input '(int * [ int + int ]))
* (output-stack-input)

出力結果は下記の通り。

NIL                           (INT * [ INT + INT ])

stackがNILで、inputが(INT * [ INT + INT ])という意味です。
この状態でshiftを1回行うと、先頭のINTがstackに移動します。

* (shift-test)
* (output-stack-input)
(INT)                         (* [ INT + INT ])

さらにもう一度。

* (shift-test)
* (output-stack-input)
(INT *)                       ([ INT + INT ])

次にreduceを見ていきましょう。
reduceは、引数の規則を適用して、stackの状態を変える操作です。

(defun reduce-call (left right)
  (let (list)
    (dolist (ignore right)
      (push (pop-stack) list))
    (unless (equal right list)
      (error "reduce error, ~S /= ~S." right list)))
  (push-stack left))

(defun reduce-test (x)
  (destructuring-bind (left check . right) x
    (unless (and (eq check '->))
      (error "operator error, ~S." x))
    (unless right
      (error "right value error, ~S." x))
    (reduce-call left right)))

何やら複雑そうですが、例えば下記の実行を考えます。

(reduce-test '(fact -> int))

reduce-test関数は、単純に次のような実行に変えるだけです。

(reduce-call 'fact '(int))

reduce-callは少し複雑ですが、大したことはしていません。
stackの先頭にあるintをfactに置き換えているだけです。

次のような状況を考えてみましょう。

* (set-input '(int * [ int + int ]))
* (shift-test)
* (output-stack-input)
(INT)                         (* [ INT + INT ])

ここで、(fact -> int)を用いてreduceしてみます。

* (reduce-test '(fact -> int))
* (output-stack-input)
(FACT)                        (* [ INT + INT ])

stackのintがfactに変わったのが分かります。
もう少し複雑な例としてはこんな感じ。

* (output-stack-input)
([ [ EXPR + TERM)             (+ INT + INT ] ])

* (reduce-test '(expr -> expr + term))
* (output-stack-input)
([ [ EXPR)                    (+ INT + INT ] ])

stack上のexpr + termが、exprにreduceされました。

さて、shiftとreduceの動作が分かったところで、 (int * [ int + int ])の構文解析をしてみましょう。
shiftとreduceを順番に実行して、最終的にstartであるexprにまでreduceできたら構文解析は終了です。

ではどういう順番で実行したらいいでしょうか？

テストのために、まずはoutput-stack-inputを合わせて実行する、 shift*とreduce*を定義します。

(defun shift* ()
  (shift-test)
  (output-stack-input))

(defun reduce* (x)
  (reduce-test x)
  (output-stack-input))

自分が適当に実行してみた結果を下記に示します。

(set-input '(int * [ int + int ]))
(output-stack-input)

(shift*)
(reduce* '(fact -> int))
(reduce* '(term -> fact))
(shift*)
(shift*)
(shift*)
(reduce* '(fact -> int))
(reduce* '(term -> fact))
(reduce* '(expr -> term))
(shift*)
(shift*)
(reduce* '(fact -> int))
(reduce* '(term -> fact))
(reduce* '(expr -> expr + term))
(shift*)
(reduce* '(fact -> [ expr ]))
(reduce* '(term -> term * fact))
(reduce* '(expr -> term))

実行結果は下記の通り。

NIL                           (INT * [ INT + INT ])
(INT)                         (* [ INT + INT ])
(FACT)                        (* [ INT + INT ])
(TERM)                        (* [ INT + INT ])
(TERM *)                      ([ INT + INT ])
(TERM * [)                    (INT + INT ])
(TERM * [ INT)                (+ INT ])
(TERM * [ FACT)               (+ INT ])
(TERM * [ TERM)               (+ INT ])
(TERM * [ EXPR)               (+ INT ])
(TERM * [ EXPR +)             (INT ])
(TERM * [ EXPR + INT)         (])
(TERM * [ EXPR + FACT)        (])
(TERM * [ EXPR + TERM)        (])
(TERM * [ EXPR)               (])
(TERM * [ EXPR ])             NIL
(TERM * FACT)                 NIL
(TERM)                        NIL
(EXPR)                        NIL

うまくいきました！
終了です！
とはなりません。
そもそもshift*とreduce*の実行は、どうやって決めたの？ってなりませんか？

自分が適当に実行してみたと書きましたが、本当に適当にというか、試行錯誤してやった結果です。
しかしそんなの本番で使えるわけがありません。
本来であれば、入力に応じて、 shiftとreduceの実行内容は自動的に決まるものなのです。
そして、その決める方法をLR(1)とか、LALR(1)と呼びます。

ここまででshiftとreduceの動作は理解できたと思います。
ここからは、LR(1)法を用いて、shiftとreduceの実行内容を決める方法を見ていきます。

続きます

Common LispでLALR(1)のparserを作る2 - nptclのブログ

nptclのブログ

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

Common LispでLALR(1)のparserを作る1