このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

構文解析木とタグ付きJSON

Catyの主たるデータ構造はXJSONです。XJSONは、JSONにわずかな拡張を加えたものです。データ構造としての拡張はタグが付けられる点だけです。例えば、@mony @yen 1200 とか、@person {"name" : "坂東トン吉", "gender" : "MALE"} などがタグ付きデータの例です。

タグ付きデータも通常のJSONと相互変換できますが、表層構文上はJSONと非互換になります。この非互換性の理由から、XJSONのタグをあまり派手に使うのは“はばかられる”気分がしてたのですが、タグは便利なので積極的に使おうと最近思い直しました。

で、タグの応用例として構文解析木の表現をやってみます。

例題:算術式

例題として、整数値と変数をもとにして、足し算と掛け算から作られる算術式を考えます。次は算術式の例です。

  1. 3
  2. x
  3. y + 1
  4. x*x
  5. 2*(y + 1)
  6. x*x + 2*(y + 1) + 3

算術式の構文は次のBNFで定義しておきます。


Expr ::= Term | Term '+' Term ('+' Term)*
Term ::= Factor | Factor '*' Factor ('*' Factor)*
Factor ::= Const | Var | '(' Expr ')'

/* Constは整数リテラル、Varは変数名 */

タグ付きJSONによる算術式の表現

足し算を@SUM、掛け算を@MULT、括弧(parentheses)によるグルーピングを@PARというタグで表すことにします。整数値はそのまま、変数は文字列とします。次は算術式をタグ付きJSONで表した例です。

  1. 3
  2. "x"
  3. @SUM ["y", 1]
  4. @MULT ["x", "x"]
  5. @MULT [2, @SUM ["y", 1]]
  6. @SUM [@MULT ["x", "x"], @MULT [2, @PAR [@SUM ["y", 1]], 3]]

括弧も捨てないで@PARにより残しています。

算術式を表すタグ付きJSONデータの型をスキーマで定義できます。このスキーマは、BNFとほとんど1:1対応します。先のBNFと見くらべてください*1


type Expr = Term | @SUM [Term, Term, Term*];
type Term = Factor | @MULT [Factor, Factor, Factor*];
type Factor = Const | Var | @PAR [Expr];

type Const = integer;
type Var = string;

別な表現方法

演算子をタグにするのではなくて、構文定義の非終端記号をタグにしてみます。先にBNFと、それに対応するスキーマ定義を出します*2


Expr ::= Term ('+' Term)*
Term ::= Factor ('*' Factor)*
Factor ::= Const | Var | FactorExpr
FactorExpr ::= '(' Expr ')'


type Expr = @Expr [Term, Term*];
type Term = @Term [Factor, Factor*];
type Factor = Const | Var | FactorExpr;
type FactorExpr= @Factor Expr;

type Const = integer;
type Var = string;

この方式だと、同じ式でも(部分式としての)出現場所により表現が変わります。例えば定数3は、次のような表現があり得ます。

  1. 3
  2. @Term [3]
  3. @Expr [@Term [3]]

先の例を、それぞれを単独の算術式(部分式ではない)とみなしてこの方法で表現してみます。

  1. @Expr [@Term [3]]
  2. @Expr [@Term ["x"]]
  3. @Expr [@Term ["y", 1]]
  4. @Expr [@Term ["x", "x"]]
  5. @Expr [@Term [2, @Factor @Expr [@Term ["y"], @Term [1]]]]
  6. @Expr [@Term ["x", "x"], @Term [2, @Factor @Expr [@Term ["y"], @Term [1]]], @Term [3]]

Catyのvalidateというコマンドを使って実際に試してみると次のような感じです。


caty:test> @Expr [@Term ["x", "x"]] | validate arith:Expr
@OK @Expr [@Term ["x", "x"]]
caty:test> @Term ["x", "x"] | validate arith:Expr
@NG "タグが Expr と一致していません: Term"
caty:test> @Term ["x", "x"] | validate arith:Term
@OK @Term ["x", "x"]
caty:test> @Term ["x", "x"] | validate arith:Const
@NG "タグ付きの値が渡されました: Term"
caty:test> "x" | validate arith:Const
@NG "x は整数ではありません"
caty:test> "x" | validate arith:Var
@OK "x"
caty:test>

テキストで表現されたデータ構造を構文解析してその結果をXJSONで表現しておけば、色々な処理や加工が容易になります。例えば、テンプレートエンジンに渡して綺麗に表示してもらうとか。「色々な処理や加工」のためには、XJSONを扱う環境をもう少し整備しないといけないのですがね。

*1:@PAR [Expr] は、@PAR Expr でもいいはずですが、現在の実装でエラーが起きるので、冗長になっています。

*2:@Factor Expr はエラーしないので、@Factor [Expr] とはしませんでした。現在の実装の都合だけの理由です。