構文解析と木構文

新しいプログラミング言語を設計するさいの留意点いろいろ:

が書かれた記事が面白かったのですが、操作的意味論の構文の話が載ってないなと思ったので書いてみました。

通常の構文解析を考える場合は文字列を構文解析してASTを作るようなことを考えます。そのために BNF や EBNF、 PEG や パーサコンビネータ を使ってパーサを作るということがあります。文字列から構文解析するパーサを作るのは慣れると楽しいですし、高速に動作するので実運用上は必要な処理となります。

しかしながら、研究用の論文を読むとか、言語を100個作るとかいうことをやり始めますと、構文解析器を作る手間が気になり始めます。

そこで用いたいのが木構文です。代数的データ型やXML Schema、JSON Schema などが木構文定義の典型的な例です。

例えば四則演算のパーサを考えてみましょう。

次の例は Ohmエディタ での構文定義です:

Exp
    = AddExp

  AddExp
    = AddExp "+" MulExp  -- plus
    | AddExp "-" MulExp  -- minus
    | MulExp

  MulExp
    = MulExp "*" ExpExp  -- times
    | MulExp "/" ExpExp  -- divide
    | ExpExp

  ExpExp
    = PriExp "^" ExpExp  -- power
    | PriExp

  PriExp
    = "(" Exp ")"  -- paren
    | "+" PriExp   -- pos
    | "-" PriExp   -- neg
    | ident
    | number

  ident  (an identifier)
    = letter alnum*

  number  (a number)
    = digit* "." digit+  -- fract
    | digit+             -- whole 

これはテキストからの構文解析の意味をうまく表現されています。
具象構文と言います。

OCaml の代数的データ型で木構文を考えると以下のように書けます:

type exp =
  | Num of float
  | Add of exp * exp
  | Sub of exp * exp
  | Mul of exp * exp
  | Div of exp * exp

こちらは抽象構文(AST)と言いますね。
抽象構文を使うとカッコやテキスト表現は消えてスッキリしますが、具象構文がなくなってしまいます。

数学的なBNFを使うと以下のように書けます:

Exp ::=
  | Number
  | Exp + Exp
  | Exp - Exp
  | Exp * Exp
  | Exp / Exp

数学的な BNF は Union Types のある言語で AST を表現した形で構文と型の両方をうまく表現できます。
論文などではこの表現を1文字の記号で表すことが多く以下のように記述します:

t ::= n | t + t | t - t | t * t | t / t

図1. 構文

t は四則演算の式を表し n は浮動小数点数 t + t は加算、
t - t は減算、 t * t は加算 t / t は割り算を表します。

普通のプログラマにとって短い変数名はループ変数など以外は基本的にタブーですが、論文を書く際には当たり前のように１文字の変数を使います。

これは慣れないと気持ち悪いでしょうが、慣れると簡潔に書けるので便利ですから覚えると良いです。