@section 形式文法によるパーサ生成

形式文法を使用して、ファイルや文字列を解析するパーサを生成することができます。@*
このライブラリでは、LALR(1)文法のクラスにある形式文法のパーサを生成することができます。@*
正規表現を使用して文字列をトークナイズする字句解析器も生成できます。@*
このパーサで使用する字句解析器は終端記号を表すシンボルとsemanticsな解析結果の2値を返す手続きならばどのようなものでも使用できます。@*
使用できる正規表現は以下の通りです。

@multitable @columnfractions .15 .6
@item rs @tab rとsの連結
@item r|s @tab rまたはs
@item r* @tab rの0回以上の繰り返し
@item r+ @tab rの1回以上の繰り返し
@item r? @tab rの0または1回の出現
@item (r) @tab rそのもの
@item . @tab 改行以外の任意の文字
@item [a-zA] @tab 文字セット
@item [^a-zA] @tab 補文字セット
@end multitable
(注) Java標準の正規表現は使用できません。

@defun make-grammar grammar
戻り値: 解析された形式文法オブジェクト@*
与えられた形式文法を解析します。解析された文法は parse-grammar手続きで使用することができます。@*
形式文法は、以下のような形式で与えます。

@example
((生成規則の左辺 (生成規則の右辺 @dots{}) reduceされたときに実行される手続き
 @dots{})
@end example

終端記号および非終端記号はシンボルで与えます。開始記号はシンボルS(大文字)で与えられます。@*
"reduceされたときに実行される手続き"は右辺の semanticsな解析結果を引数として呼び出されます。@*
例えば、

@example
S → S + T
S → S - T
S → T
T → T * F
T → T / F
T → F
F → lparen S rparen
F → num
@end example

という文法(この文法は一般的な四則演算を定義します)を定義し、この文法に従って計算するときの文法の定義は、

@example
  (make-grammar
    `((S (S + T)     ,(lambda (t1 x t2) (+ t1 t2)))
      (S (S - T)     ,(lambda (t1 x t2) (- t1 t2)))
      (S (T)         ,(lambda (t1) t1))
      (T (T * F)     ,(lambda (f1 x f2) (* f1 f2)))
      (T (T / F)     ,(lambda (f1 x f2) (* f1 f2)))
      (T (F)         ,(lambda (f1) f1))
      (F (lparen S rparen)
         ,(lambda (x s1 y) s1))
      (F (num)
         ,(lambda (v1) (string->number v1)))))
@end example

のように指定します。シンボルlparen, rparen, numは字句解析器により与えられます。@*
文法に"競合"(conflict)が発生してもこの手続きはエラー・警告を出しません。競合を取得したいときはget-conflicts手続きを使用してください。@*
@end defun

@defun parse-grammar parser-object lexer
戻り値: パース結果のsemanticsのスタックトップ@*
与えられた字句解析器を使用してパースします。@*
字句解析器は終端記号を表すシンボルとsemanticsな解析結果の2値を返す手続きです。
@end defun

@defun get-conflicts parser-object
戻り値: 競合のリスト@*
文法における"競合"を取得します。競合は以下の形で取得されます。

@example
(@dots{}
 (shift-reduce  シフトする終端記号
                還元する文法規則)   ;シフト-還元競合
 (reduce-reduce 還元する文法規則
                還元する文法規則)   ;還元-還元競合
 @dots{}) 
@end example

文法規則は(生成規則の左辺 (生成規則の右辺 @dots{}))の形のリストで取得されます。
@end defun

@defun make-regexp-tokenize-pattern lexer-patterns
戻り値: トークナイザパターン@*
正規表現によるトークナイザパターンを生成します。パターンは以下の形で与えます。

@example
((正規表現を表す文字列 . 終端記号を表すシンボル)
 @dots{})
@end example

例:四則演算子と数値を解析するトークナイザ

@example
(make-regexp-tokenize-pattern
    '(("[0-9]+(\\.[0-9]+)?" . num
      ("[ 	
      ]+" . whitespace)  ; 空白+タブ+改行
      ("\\(" . lparen
      ("\\)" . rparen
      ("\\+" . +
      ("-" . -
      ("\\*" . *
      ("\\/" . /))
@end example
@end defun


@defun make-regexp-tokenizer-string tokenizer-pattern string
戻り値: トークナイザ@*
文字列に対してパターンを適用するトークナイザを取得します。
@end defun

@defun make-regexp-tokenizer-port tokenizer-pattern iport
戻り値: トークナイザ@*
入力ポートに対してパターンを適用するトークナイザを取得します。
@end defun

@defun tokenize tokenizer
戻り値: 終端記号のシンボルと一致した部分の文字列の2値@*
トークナイザを用いて入力を区切り、その結果を返します。 
@end defun

