LISPUSER

CL-Yacc は Common Lisp のための LALR(1) パーサージェネレータです． ちょうど Yacc, GNU Bison, Zebu, lalr.cl, lalr.scm のようなものです．

最新版の CL-Yacc は 公式ページ で見つける事ができます．

このマニュアルの原作者は Juliusz Chroboczek です．

CL-Yacc は提供するシンボルを `yacc` パッケージからエクスポートしています．

(use-package 'yacc)

パーサーは字句解析器 (lexer) の出力を消費してゆきます．字句解析器は終端 記号のストリームを出力します． CL-Yacc は字句解析器が二つのシンボルを返 す，引数を取らない関数である事を仮定しており，字句解析された結果を構文 規則から導かれたアクションへと渡します．字句解析器は入力情報がなくなっ たら，単に `nil` を返さなければなりません．

非常に単純な，リストからトークンを取りだしてゆく字句解析器を示します．

(defun list-lexer (list)
  #'(lambda ()
      (let ((value (pop list)))
        (if (null value)
            (values nil nil)
            (let ((terminal
                   (cond ((member value '(+ - * / |(| |)|)) value)
                         ((integerp value) 'int)
                         ((symbolp value) 'id)
                         (t (error "Unexpected value ~S" value)))))
              (values terminal value))))))

次のような文法 (grammer) を実装しましょう．

expression ::= expression + expression
expression ::= expression - expression
expression ::= expression * expression
expression ::= expression / expression
expression ::= term

term ::= id
term ::= int
term ::= - term
term ::= ( expression )

この文法はあいまいですから，演算子の優先順位と結合規則を指定する必要が あります．演算子 `*` と `*` は最も優先順位が高く， `+` と `-` は低くな ります．全ての演算子は左結合するものとします．

CL-Yacc はたいていの場合適切なデフォルトの意味論的動作を提供します．こ の文法から Lisp ライクな構文木を構築するためには，二つのアドホックなア クションが必要なだけです．

(eval-when (compile load eval)
  (defun i2p (a b c) 
    "Infix to prefix"
    (list b a c))

  (defun k-2-3 (a b c)
    (declare (ignore a c))
    b)
)

パーサーの定義は

(define-parser *expression-parser*
  (:start-symbol expression)
  (:terminals (int id + - * / |(| |)|))
  (:precedence ((:left * /) (:left + -)))

  (expression
   (expression + expression #'i2p)
   (expression - expression #'i2p)
   (expression * expression #'i2p)
   (expression / expression #'i2p)
   term)

  (term
   id
   int
   (- term)
   (|(| expression |)| #'k-2-3)))

パーサーはスペシャル変数 `*expression-parser*` の値となり， `parse-with-lexer` 関数に渡す事ができるようなります．

(parse-with-lexer (list-lexer '(x * - - 2 + 3 * y)) *expression-parser*)
=> (+ (* X (- (- 2))) (* 3 Y))

パーサーのエントリーポイントは `parse-with-lexer` です．

parse-with-lexer lexer parser

パラメータ `lexer` で指定された字句解析からの入力をパラメータ `parser` で指定した
パーサーを使って解析します．

`lexer` パラメータで指定される字句解析器は二つの値を返す，引数を取らな
い関数でなければなりません．二つの値は終端記号を表わすシンボルと，その
値（生成規則に引数として渡されます) です．入力の終端に到達した時には

`(values nil nil)` を返さなくてはなりません．

`parser` パラメータは `define-parser` や `make-parser` で作成された
`parser` 構造体でなければなりません．

define-grammar name option... production...

option ::= ( keyword value )
production ::= ( symbol} rhs... )
rhs ::= symbol
rhs ::= ( symbol... [action] )

`name` スペシャル変数に文法から構築したパーサーを作成します．

全ての導出規則は，非終端記号と一つまたは複数の右辺のリストで表現されま
す．右辺 (rhs) はシンボルかもしくはシンボルのリストです．

アクションはレキシカル環境で評価される関数を表わすフォームでなければな
りません．デフォルトでは最初の形式では `#'identity` が，二番目の形式で
は #'list が設定されます．

指定可能なオプションは以下の通りです．

:start-symbol    文法を開始するシンボルを定義します．必須です．                  

:terminals       文法中の終端記号を表わすシンボルのリストを定義します．必須です．

:precedence      このオプションの値は結合規則と終端記号の cons ペア              
                 (結合規則 . 終端記号リスト) を要素とするリストです．          
                 結合規則は :left, :right, :nonassoc のいずれか，          
                 終端記号リストは終端記号シンボルのリストです．                  
                 結合規則は終端記号の結合規則を指定し，また，リストの前方に      
                 ある要素ほど優先順位が高くなります．                            

define-parser name option... production...

パーサーは name で指定されたスペシャル変数の値として構築されます．
構文は，define-grammar と同様ですが，以下のようなオプションが指定可
能です．

:muffle-conflicts

   nil (デフォルト)   全ての衝突に対して警告が表示されます．
   :some              衝突の数がサマリとして表示されます．
   t                  衝突があっても警告は何も表示されない．
   (ss rr)            ss, rr は整数
                      ss: shift-reduce の衝突
                      rr: reduce-reduce の衝突
                      で，それぞれ指定した数を超えた衝突が
                      見つかった場合に警告が表示されます．

:print-derives-epsilon

    真の値が指定されたら空の文字列を導出する非終端記号のリストを表
    示します．

:print-first-terminals

   もし真ならば，全ての非終端記号の先頭となる終端記号のリストを表示します．

:print-states

   もし真ならば，LR(0) 要素として計算された要素を表示します．

:print-goto-graph

   もし真ならば，計算された goto グラフを表示します．

:print-lookaheads

   もし真ならば，先読みとともに LR(0) 要素を表示します．

`define-parser` や `define-parser` マクロは `make-load-form` の魔術に適 した `defparameter`, `make-parser`, `make-grammar`, `make-production` の呼び出しへと展開されます．これは，ロード時よりもコンパイル時にパーサ の生成を行います．異なる文法を設計したい場合には，内部で使用される関数 はこれらのエクスポート済された関数が自動的に生成規則を作成します．

シンボル `yacc-eof-symbol` は EOF トークンを作るために使用されます．そ れは決っして生成規則中には出現しませんし，また字句解析器がこれを返すこ ともありません．これは，パースエラー中に EOF に到達した場合のコンディショ ンハンドラのためにエクスポートされています．

make-production symbol derives &key action action-form

パラメータ symbol で指定される非終端記号とパラメータ derives で指定
される右辺からなる生成規則を返します．パラメータ action は規則に対
するアクションとして関数を指定する必要があります．デフォルトでは
#'list が指定されます．パラメータ action-form は空のレキシカル環境
でアクションとして評価されるフォームを指定します．もし null （デフォ
ルト）が指定されるとたとえ構文やパーサーがそれを使用していても，ダ
ンプされなくなります．

make-grammar &key name start-symbol terminals precedence productions

文法を返します．パラメータ name は文法につける名前です．パラメータ
start-symbol, terminals, precedence は define-grammar のものと同じ
意味です．パラメータ productions は生成規則のリストです．

make-parser grammar &key discard-memos muffle-conflicts
                         print-derives-epsilon print-first-terminals
                         print-states print-goto-graph print-lookaheads

パラメータ grammar で指定された文法のためのパーサーを作成して返しま
す．パラメータ discard-memos は廃棄された文法と関連している一時デー
タを廃棄すべきかどうかを指定します．パラメータ muffle-conflicts,
print-derives-epsilon, print-first-terminals, print-states,
print-goto-graph, print-lookaheads は define-parser のものと同様です．

CL-Yacc にあいまいな文法を与えると， 衝突が発見されるたびに `conflict-warning` 型の警告が通知されます．そして， `conflict-summary-warning` 型の警告がパーサー生成直後に通知されます．

Condition conflict-warning kind state terminal

衝突が発見されるたびに通知されます．kind は :shift-reduce,
:reduce-reduce のいずれかです．state (数値)， terminal (シンボル)
は衝突を起こした状態と終端記号です．

Condition conflict-summary-warning shift-reduce reduce-reduce

パーサー生成後に衝突が発生していた場合に通知されます．shift-reduce
と reduce-reduce はそれぞれいくつ衝突が生じたかを示します．

入力データが解析不能だった場合には，パーサーは `yacc-parse-error` を通 知します．`yacc-parse-error` からはリカバリできるように restart を呼ぶ ことが可能であるべきですが，現在はまだ実装されていません．

Condition yacc-parse-error terminal value expected-terminals

入力が解析不能になった場合に即座に通知されます．terminal で表わされ
るシンボルは受け付けらなかった終端記号で，value はその値です．
`expected-terminals` はその状態で受け付けられる終端記号のリストです．

CL-Yacc を実装するにあたって助力を与えてくれた Marc Zeitoun, Antonio Bucciarelli, そして特に Guy Cousineau に感謝します．

Copyright (C) 2005 by Juliusz Chroboczek

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

$Date: 2006/03/30 23:58:04 $