演算子順位法によるパーサ

rowl

リンカが問題なく動くようになったので、ようやく次の処理系(rowl1)作りを開始しました。
レキサはこれまでと同じく状態遷移図を手で作成しました。rowl2の開発時にはレキサの自動生成が出来るくらい、言語が高級になっていると良いなぁと思っています。

現在はパーサを作っていますが、試みに演算子順位法を中心にして作っています。演算子順位法は一般的なLALR法より扱える文法が少ないのですが構文解析器の構造がシンプルなので実装が簡単で効率が良いという特徴があります。また、言語の文法は演算子の種類(前置・後置・中置・・)とその演算子順位のみ与えれば決まるので、例えばユーザレベルで新しい構文を追加する機能などを容易に提供できるという利点もあります。

構文はできるだけシンプルにしたいという気持ちがあったのだけど、S式だと見た目が最悪なので試しに演算子順位法でやってみるかというのが動機です。

演算子順位法

演算子順位法は演算子順位文法で記述された文法しか解析できません。つまりA、B、Cを非終端記号として、以下の文法規則が含まれてはなりません。

  1. A → ε
  2. A → …BC…

前者については例えばC言語の

return;

や

for(;;) {
    ...
}

のような物が空式(ε)を含むのでダメです。
後者に関しては、例えばC言語の

int x;

等がダメで、他にはHaskellやO'Camlなどの関数適用

f a

などがダメです。

演算子順位法は上向き構文解析法の一種で、LALR法などと同じくシフト・還元動作を繰り返す事により行われます。
詳しくはhttp://www.amazon.co.jp/%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E3%81%AE%E6%A7%8B%E6%88%90%E3%81%A8%E6%9C%80%E9%81%A9%E5%8C%96-%E4%B8%AD%E7%94%B0-%E8%82%B2%E7%94%B7/dp/4254121393やWeb上の資料を参照してください。

rowl1の文法

演算子文法はさすがに表現力が低すぎるので、一部だけ先読みを行うなどの処理をしています。
とりあえず暫定的に決めた物を書きます。ちゃんとした定義はもう少し出来あがってから。

  • コメントは#で始まる行
  • 項 (Term)
    • リテラル：整数(2進・8進・16進・10進)、浮動小数点数、キャラクタ、文字列、シンボル
    • タプル: (Expr, Expr, ...)
      • ただし(Expr)はタプルではなくExprと同じ
    • 配列: [Expr, Expr, ...]
    • リスト: {Expr Expr ...}
      • カンマはない。演算子文法でないので特別処理。
    • 呼び出し: Term(Expr, Expr, ..)
    • 添え字: Term[Expr, Expr, ..]
  • 式 (Expr)
    • 項
    • 中置演算子式 : Expr op Expr
    • 前置演算子式 : op Expr
    • 後置演算子式 : Expr op
      • 中置演算子は左右どちらかの結合性を持つ。組み込みの演算子はなくユーザが任意に定義する。演算子は"!$%&=^|@*:;/\\?<>~`"を1つ以上並べたものもしくは識別子。前置演算子と中置演算子は文脈で区別可能なので同じシンボルを使っても良い(前置の-と中置の-など)。後置演算子は2手先読みが必要でめんどいので、ユニークでなければならないとする。
    • コンストラクト式: constructor Expr Expr ... (n個)
      • 組み込みのコンストラクタはなくユーザが任意に定義する。nは引数の数で、後続のExprは必ずn個ちょうどでなければならない。演算子文法ではないので特別処理。

説明中の「配列」とか「呼び出し」とかあるのはただの名前で、実際にそれをどう処理するかは後のフェーズで決定される。

取り合えずこんな感じでやってみて、可読性などで問題が出たらLALRに書きなおすつもりです。
あと、タプルや配列など括弧で囲まれた式は演算子順位法の中で扱えるので、[| 1, 2, 3 |]みたいなのを新しくユーザが定義できるようにするのも可能ですが、すぐには必要にならなそうなので後で考える事にします。

例

現在までに実装したところだと、

constr "def" 2 1    # (引数2つ、順位1)
constr "return" 1 2
constr "if" 2 3
infixl "<" 4
infixl "+" 5
infixl "-" 5

みたいにコンストラクタと演算子を定義すると、下の様なコードが正しく構文木化できます。

def fib(n) {
    if (n < 3)
        return 1
    return fib(n-1) + fib(n-2)
}

上の文法でリストをカンマ区切りにしなかったのは、こんな感じでリストをコードブロックの為に使う用途を想定している為。
次はデフォルトでロードするコンストラクタ・演算子を設計した後、意味解析の実装です。