37 式グラマーの解析

Emacs Lispはテキストのパースとマッチングのために正規表現(正規表現を参照)から完全なLRグラマーパーサー(Left-to-Right grammar parsers: LR構文解析器; (bovine)Bovine parser developmentを参照)に至るツールを複数提供しています。PEG (Parsing Expression Grammars: パース式グラマー、式解析構文)とは正規表現と比べてより構造的かつ構成可能性をもち、文脈に依らない構文に比べて複雑度が少ないテキスト解析を提案する別のアプローチのことです。

PEG (Parsing Expression Grammar: パース式グラマー、解析式構文)は言語内の文字列を認識する一連のルールという観点から形式言語を記述します。EmacsではPEGパーサーは名前つきルールとして定義されており、ルールはそれぞれテキストパターンにたいするマッチおよび/または他のルールへの参照を含んでいます。パースは関数peg-runまたはマクロpeg-parse (以下参照)によって初期化されて、与えられた一連のルールを用いてカレントバッファーのポイントの後にあるテキストのパースを行います。

PEG内のルールはそれぞれPEX (parsing expression: パース式、解析式)として参照されます。PEXはリテラル文字列、regexpに似た文字範囲や文字セット、Emacs Lisp関数の呼び出しに似たPEG固有の構文、他のルールへの参照、あるいはこれらの組み合わせとして指定できます。グラマーはルールのツリーとして表現され、通常は1つのルールは“ルート(root)”または“エントリーポイント(entry-point)”として扱われます。たとえば:

((number sign digit (* digit))
 (sign   (or "+" "-" ""))
 (digit  [0-9]))

グラマーを一度定義してしまえば、それを使ってカレントバッファーのポイントの後にあるテキストさまざまな方法でパースできます。一番シンプルなのはpeg-parseマクロでしょう:

Macro: peg-parse &rest pexs ¶

ポイント位置でpexsをマッチする。

(peg-parse
  (number sign digit (* digit))
  (sign   (or "+" "-" ""))
  (digit  [0-9]))

このマクロはソースコード内にルールを直接記述しなければならないので、シンプルですが柔軟性があります。他の関数やマクロを組み合わせて使用すれば、さらなる柔軟性を獲得することができるでしょう。

Macro: with-peg-rules rules &rest body ¶

rules (PEXのリスト)の効力の下でbodyを実行する。BODY内ではpeg-run呼び出しによってパースが開始される。

Function: peg-run peg-matcher &optional failure-function success-function ¶

この関数は、名前つきルールにpeg (以下参照)を呼び出した結果(通常は大きなグラマーのエントリーポイント)である単一のpeg-matcherを受け取る。

パースの最後にパースの結果に応じてfailure-functionかsuccess-functionのいずれかが呼び出される。success-functionが提供された場合には、唯一の引数としてパース中のスタック上のすべてのアクションを実行する無名関数を受け取る関数であること。デフォルトではこの関数は単にそのまま実行される。パースが失敗した場合には、パース中に失敗したPEG式のリストとともにfailure-functionとして提供された関数が呼び出される。このリストはデフォルトでは破棄される。

peg-runに渡されるpeg-matcherはpegを呼び出すことによって生成されます:

Macro: peg &rest pexs ¶

pexsをpeg-runに渡すのに適した単一のpeg-matcherに変換する。

上述したpeg-parseの例はこれらの関数への一連の呼び出しを展開したものであり、以下のようにして完全に記述することができます:

(with-peg-rules
    ((number sign digit (* digit))
     (sign   (or "+" "-" ""))
     (digit  [0-9]))
  (peg-run (peg number)))

このアプローチではパースの“エントリーポイント”にたいするより明白な制御、および異なるソースのルールを組み合わせることが可能になります。

マクロdefine-peg-ruleを使用すれば、よりdefunに似た構文を用いて個別にルールを定義することもできます:

Macro: define-peg-rule name args &rest pexs ¶

引数argsを受け取りポイント位置にpexsをマッチするPEGルールとしてnameを定義する。

たとえば:

(define-peg-rule digit ()
  [0-9])

PEGルールにたいしてfuncallすることにより、ルールに引数を提供できます(PEX定義を参照)。

別の可能性として挙げられるのは、define-peg-rulesetにより名前つきルールセットを定義する方法です。

Macro: define-peg-ruleset name &rest rules ¶

rulesにたいする識別子としてnameを定義する。

(define-peg-ruleset number-grammar
        '((number sign digit (* digit))
          digit  ;; 上記定義への参照
          (sign (or "+" "-" ""))))

この方法で定義したルールおよびルールセットは、後でpeg-runやwith-peg-rulesでの呼び出しにおいて名前で参照できます:

(with-peg-rules number-grammar
  (peg-run (peg number)))

デフォルトではpeg-runやpeg-parseの呼び出しによって出力は生成されず、パースによって単にポイントが移動するだけです。パースした文字列をリターンしたりそれにもとづいたアクションを行う場合には、ルールに(actions)を含めることができます。アクションの解析を参照してください。

• PEX定義
• アクションの解析
• PEGルールの記述