モノイド的構文解析(3) - 非専門的シンギュラリティー研究所

モノイド的構文解析言語 MonParser - 構文木の構成

文字列から構文木を作ることができるようにします。この言語を MonParser と呼ぶことにします。

文字の集合 $C$ で生成された自由モノイド $C^*$ の冪集合 $C^{**}$ (これを表す一般的な記法は知らないのでここではこう書きます)は冪等半環となります。

文字列 $s \in C^*$ を構文木に変換します。構文木の集合を $T$ とします。構文木は構文木のコンストラクターによって文字列から再帰的に構成されるとします。

構文の記述の中に構文木のコンストラクターを記述することができるようにします。同じ構文が繰り返されるとき少なくとも一文字は決まるとすると、ある有限の文字列に対して無限に繰り返されることはありません。構文はこのように記述されているとします。

文字列 $s \in C^*$ の構文解析が成功したとき構文木 $t \in T$ が決まります。構文解析が失敗したとき $\bot$ とすると、構文解析の写像 $p: C^* \to T + \{\bot\}$ を定義することができます( $+$ は集合の直和)。

構文木のコンストラクターの記述を以下のように追加します。

「式 -> コンストラクター」は式から構文木を構成します。
「式1 &* 式2 -> コンストラクター」は二項演算(左結合)の構文木を構成します。
「式1 *& 式2 -> コンストラクター」は二項演算(右結合)の構文木を構成します。
「&*」と「*&」にコンストラクターを記述しないときはリストを構成します。
「&*」と「*&」の優先順位は「&」と「|」の間とします。
「式 *」と「式 +」はリストを構成します。
「->」の優先順位は「&*」(または「*&」)と「|」の間とします。
「/」で囲まれた部分には文字列を書くことができるとします。記号を書くときは記号の前に「\」をつけるとします。「/」で囲まれた部分は構文木の中で文字列として使えるとします。
「'」で囲まれた部分には文字列を書くことができるとします。「'」で囲まれた部分は構文木の中で文字列として使えるとします。
「"」で囲まれた部分は構文木の中では使わないとします。

前回 C# 版に合わせて数値の演算を追加したのですが、不足していたので修正します。かっこも使えるようになっていなかったので修正します。

以下で「Program」のように先頭が大文字になっているものはコンストラクターです。

def program = statement &* ";" -> Program;

def statement =
      definition
    | expression_statement;

def definition =  "def" & identifier & "(" & (parameter_name &* ",") & ")" & "=" & expression -> Definition;

def expression_statement = expression -> ExpressionStatement ;

def expression = term &* "&" -> Expression;

def term =
      domain_expression
    | function
    | domain_function;

def function = "$" & identifier & "(" & (expression &* ",") & ")" -> Function;

def domain_function = identifier & "(" & (domain_expression &* ",") & ")" -> DomainFunction;

def domain_sum_operator = '+' | '-';

def domain_expression = domain_product &* "+" -> DomainBinary;

def domain_product_operator = '*' | '/' | '%';

def domain_product = domain_unary &* domain_product_operator  -> DomainBinary;

def domain_unary_operator = '-';

def domain_unary =
      domain_term;
    | domain_unary_operator & domain_unary -> DomainUnary;

def domain_term =
      "(" & domain_expression & ")"
      identifier
    | number;

def parameter_name = /([A-Z]|[a-z]|[_])&([A-Z]|[a-z]|[0-9]|[_])*/ -> ParameterName;
def identifier = /([A-Z]|[a-z]|[_])&([A-Z]|[a-z]|[0-9]|[_])*/ -> Identifier;
def number = /[0-9]+/ -> Number;

program