kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Macro PEGとParser Combinatorの関係に関するメモ

特に他の人が読むことを想定して書いていないので、あしからず。Parser Combinatorに関しては、Scala風味の記述で。

  • 0階PEGは、相互再帰的なlazyな値(=> Parser[T])の集まり（式はPrimitiveと基本的なCombinatorで構成される）
    • Primitive
      • 文字列リテラル: "str": Parser[String]
      • 空文字列: "": Parser[String]
      • 非終端記号の参照
    • 基本的なCombinator
      • 順序付き選択（e1 / e2):（Parser[T], Parser[T]) => Parser[T]
      • 繰り返し： e * or e+: Parser[T] => Parser[List[T]]
      • And述語： & e: Parser[T] => Parser[Unit]
      • Not述語： ! e: Parser[T] => Parser[Unit]
      • 0回または1回の繰り返し：e ?: Parser[T] => Parser[Option[T]]
  • Macro PEGは、0階PEGに対応するParser Combinatorに加え、Parser[T] => Parser[U]型の関数の定義を許したもの
    • たぶん、真に文脈自由言語を含む（そして、文脈依存言語のそこそこの部分がカバー可能？）
      • 自然数の加減乗除、累乗等が計算可能
    • 順列言語みたいなのが非常に簡単に書ける
  • 後方参照(str:e1 e2)の拡張は、Parser Combinatorでは、evalWithContinuation: (Parser[String] => (Parser[String] => Parser[T])) のような関数として考えることができる
    • e1を評価した結果、「消費された」文字列にマッチするようなParser[String]を引数にとり別のParser[T]を返す
  • Higer Order Macro PEGは、
    • Parser[A1] => Parser[A2] => ... Parser[An] のような型の関数を許す
      • 無名関数も書けるように（ただし、現状のMacro PEGでは、無名関数を置ける場所に制限あり）
  • 動的スコープVS.静的スコープ
    • 動的スコープ
      • 文脈を持ちまわる手間がはぶける
      • Parser Combinatorに素直に対応が付かない
    • 静的スコープ
      • Parser Combinatorに素直に対応が付く
      • レキシカルクロージャが定義できるが…
  • 値呼び出しと名前呼び出し
    • 何も考えずに定義すれば、名前呼び出しになる
    • Macro PEGにおける値呼び出しってなんだ？
  • to be continued ...