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

構文解析をモノイドで表す方法について調べます。さらに和集合を和とすると冪等半環(dioid)となるので冪等半環で表す方法について調べます。

自由モノイドのイテレーター(6) - エレファント・ビジュアライザー調査記録の Python の lark モジュールの例は自由モノイド(文字列の集合と考えます)の部分集合を得るための規則となっています。

この記法の左辺は構文の要素の名前で、右辺はその要素を変換した先の冪等半環の元となっています。変換先は構文の要素を含むことができます。この場合さらに変換を繰り返して最終的に冪等半環の一つの元となります。

構文解析は、ある文字列がこの集合に含まれるかどうかを調べることを表しますが、すべての場合について調べるのは効率が悪いので何かの制限を加えることになります。

冪等半環 $R$ の積の演算子は「&」、和の演算子は「|」とします。規則は「自由モノイドのイテレーター」での定義の記法に合わせて
def 構文要素名 = 冪等半環の式;
または
型名構文要素名 => 冪等半環の式;
と書くことにします(後者は C# の形式)。有限個の規則の集合によってある冪等半環の式を変換して得られた文字列の集合に、ある文字列が含まれるかどうかを調べます。

上記の例を書き直します。「parameter_name」を追加します。文字列リテラルと正規表現を書くことができるとします。文字列リテラルと正規表現の内部以外では空白は無視されるとします。

def program = statement_block;

def statement_block =
      statement
    | statement & ";" & statement_block;

def statement =
      definition
    | expression_statement;

def definition =  "def" & identifier & "(" & parameter_list & ")" & "=" & expression;

def parameter_list =
      parameter_name
    | parameter_name & "," & parameter_list;

def expression_statement = expression;

def expression = product;

def product =
      term
    | term & "&" & product;

def term =
      domain_expression
    | function
    | domain_function;

def function = "$" & identifier & "(" & expression_list & ")";

def expression_list =
      expression
    | expression & "," & expression_list;

def domain_function = identifier & "(" & domain_expression_list & ")";

def domain_expression_list =
      domain_expression
    | domain_expression & "," & domain_expression_list;

def domain_expression = domain_sum;

def domain_sum =
      domain_term
    | domain_term & "+" & domain_sum;

def domain_term =
      identifier
    | number;

def parameter_name = /[A-Za-z_][A-Za-z0-9_]*/;
def identifier = /[A-Za-z_][A-Za-z0-9_]*/;
def number = /[0-9]+/;

program