JSON Schema っぽいものを作ってみた

JSON を使って言語を作るのであれば、構文検査はJSONのパーサに任せることができますが、さらに細かい構文チェックをしたくなります。
JSONを直接検査するプログラムを手書きするのも１つの手ですが、文法定義データを基にチェックできれば便利です。
そこでここでは、JSONによってJSONの構文を検査する簡単なプログラムを紹介したいと思います。

使い方

構文定義の例:

let syntax=bnf({
  "m": [
    ["Int","int"],
    ["Var","string"],
    ["Bool","boolean"],
    ["Add","m","m"],
    ["Mul","m","m"]
  ]
})

この例では、整数と変数、boolのプリミティブ型と加算と乗算のある式言語をJSONを用いて文法名 m として定義したものです。

※ 注意: ここでの BNF は狭義の意味での BNF ではなく、広義の意味での BNF です。木構造データに対する BNF を JSON を用いて記述したので BNF と書きました。

この構文を用いてJSONデータを構文検査するには以下のようにして使います:

console.log(syntax("int",0))
console.log(syntax("int",-10))
console.log(!syntax("int","abc"))
console.log(syntax("m",["Int",0]))
console.log(syntax("m",["Int",-10]))
console.log(!syntax("m","abc"))
console.log(syntax("m",["Int",0]))
console.log(syntax("m",["Int",-10]))
console.log(!syntax("m","abc"))
console.log(syntax("m",["Bool",true]))
console.log(syntax("m",["Bool",false]))
console.log(syntax("m",["Var","abc"]))
console.log(syntax("m",["Var","def"]))
console.log(syntax("m",["Add",["Int",1],["Int",2]]))
console.log(syntax("m",["Add",["Int",1],["Add",["Int",1],["Int",2]]]))
console.log(syntax("m",["Mul",["Int",1],["Int",2]]))
console.log(syntax("m",["Mul",["Int",1],["Mul",["Int",1],["Int",2]]]))

実行結果

true
true
true
true
true
true
true
true
true
true
true
true
true
true
true
true
true

全部 trueになります。assert関数を作ってfalseの時だけお知らせする仕組みがあるといい気もしますが、よしとしましょう。

このような検査をするJavaScriptのプログラムは以下のように書けます:

function bnf(bnf) {
  function f(G,V) {
    if (typeof(G) == "string") {
      if (G in bnf) {
        for (let g of bnf[G]) {
          if (f(g,V)) {
            return true;
          }
        }
      }
      switch(G) {
        case "int": return Number.isInteger(V);
        case "string": return typeof(V)=="string";
        case "boolean": return typeof(V)=="boolean"; 
        default: return (G==V);
      }
    }
    if (G instanceof Array) {
      if (G.length==2 && G[0]=="object") {
        if (V instanceof Object) {
          for (let i in V) {
            if (!f(G[1],V[i])) {
              return false;
            }
          }
          return true;
        }
      }
      if (V.length != G.length) {
        return false;
      }
      for (let i = 0; i < V.length;i++) {
        if (!f(G[i],V[i])) {
          return false;
        }
      }
      return true;
    }
    return false;
  }
  return f;
}

処理内容は文法定義データとJSONデータを照らし合わせながら再帰的にチェックするだけです。
意外と簡単に書けます。

考察

JSON データの構文検査は意外と簡単な再帰プログラムで書けました。
文字列から構文解析をする場合は構文検査だけではデータが得られないのでデータを構築する必要があります。
一方で JSON データを利用する場合はすでに構文データがあるので構文検査するだけですみます。
左再帰を含む文字列からの構文検査は単純な再帰プログラムでは無限ループになってしまいますが、JSONのような木構造データは必ず終端があるので無限ループに陥ることはありません。見た目上、左再帰があっても無限ループすることはありません。
以上の理由から木構造に対する構文検査プログラムは非常に簡潔に記述できます。

まとめ

JavaScript で JSON Schema のようなものの仕様を考えて実装してみました。
木構造に対しての文法検査は意外と簡単に作れることが示せたと思います。
ここで作成した構文検査プログラムは真か偽を返すだけなので利用しずらさがあります。
位置情報を何かしらの形で保存できれば、エラー表示をよりわかりやすくできるでしょう。

おまけ1

Prolog で同様のプログラムを書くと以下のように書けます:

mem(M,{M}). mem(M,{_,M1}):- mem(M,M1).
syntax(G,E):-G=..[O|Gs],E=..[O1|Es],O=@=O1,maplist(syntax,Gs,Es),!.
syntax(G,E):-bnf(O),mem(G_:Gs, O),G=@=G_,!,member(G1,Gs),syntax(G1,E),!.
syntax(X,I):-X=@="int",integer(I),!.
syntax(X,I):-X=@="string",string(I),!.
syntax(X,I):-X=@="bool",member(I,[true,false]),!.
syntax([X,_],{}):-X=@="object",!.
syntax([X,M],{Os}):-X=@="object",!,os(M,Os).
syntax([X,E],Ls) :- X=@="array",!,maplist(syntax(E),Ls).
os(M,K:V):-syntax("x",K),syntax(M,V),!. 
os(M,(KV1,KV2)):-os(M,KV1),!,os(M,KV2),!. 

bnf({
  "m": [["Int","int"],["Var","string"],["Bool","bool"],["Add","m","m"],["Mul","m","m"]]
}).

:- begin_tests(syntax).
  test(i) :- syntax("int",0),syntax("int",-10),\+syntax("int",abc).
  test(m_i) :- syntax("m",["Int",0]),syntax("m",["Int",-10]),\+syntax("m",abc).
  test(m_b) :- syntax("m",["Bool",true]),syntax("m",["Bool",false]).
  test(m_x) :- syntax("m",["Var","abc"]),syntax("m",["Var","def"]).
  test(m_add) :- syntax("m",["Add",["Int",1],["Int",2]]),syntax("m",["Add",["Int",1],["Add",["Int",1],["Int",2]]]).
  test(m_mul) :- syntax("m",["Mul",["Int",1],["Int",2]]),syntax("m",["Mul",["Int",1],["Mul",["Int",1],["Int",2]]]).
:- end_tests(syntax).
:- run_tests.
:- halt.

おまけ2

より BNF に近い形で文法定義をできるようにすると以下のように書けます:

:- op(1200,xfx,::=).
:- op(650,xfx,∈).
:- op(250,yf,*).
G∈{G}. G∈(G|_). G∈(_|G1):-G∈G1. G∈G.
syntax(S/[S2],AEs) :- compound_name_arguments(AEs,A,Es),syntax(S,A),syntax(S2,Es).
syntax(G,E):-G=..[O|Gs],E=..[O|Es],maplist(syntax,Gs,Es),!.
syntax(G,E):-(G::=Gs),!,G1∈Gs,syntax(G1,E),!.
syntax(i,I):-integer(I),!.
syntax(x,I):- string(I),!.
syntax(b,I):- member(I,[true,false]),!.
syntax(n,I):- member(I,[null,undefined]),!.
syntax(E*,Ls) :- maplist(syntax(E),Ls).

m ::= i | x | b | {} | {o} | (m*).
o ::= x:m,o | x:m.

:- begin_tests(syntax).
  test(i) :- syntax(i,0),syntax(i,-10),\+syntax(i,abc).
  test(m_i) :- syntax(m,0),syntax(m,-10),\+syntax(m,abc).
  test(m_b) :- syntax(m,true),syntax(m,false).
  test(m_x) :- syntax(m,"abc"),syntax(m,"def").
  test(m_o) :- syntax(m,{}),syntax(m,{"def":1}),syntax(m,{"def":1,"eee":"x"}),\+syntax(m,{1*2}).
  test(m_a) :- syntax(m,[]),syntax(m,[1]),syntax(m,[1,2,[1,2,3]]),\+syntax(m,[1*2]).
:- end_tests(syntax).
:- run_tests.
:- halt.

一階述語論理の規則として記述できたので、Coqなどの定理証明系のシステムなどでこのプログラムのさまざまな性質を証明するとより信頼性が増すでしょう。