仕事でもしかしたら相応の複雑さの構文解析を行わなければならないかもしれないので、いい機会という事で構文解析のライブラリを作っている。（※正確には昔の仕事で作ったPython用の構文解析ライブラリのJavaへの移植）なんでこんなものを作ったのかというと、ANTLRとかyaccとか、パーザージェネレーターは昔からあまり使っていて気分が良くなかったので、それなら自分でライブラリを作ってしまおうという感じ。
topdown-java
https://github.com/ckuwata/topdown-java
MITライセンスなので、ご利用はご自由にどうぞ。
構文解析の手法としては、再帰下降構文解析、実質無限先読みで、もうちょい手を加えれば解析表現文法で表現できる言語を解析できる。（はず。きちんと証明はしていない。）とりあえずサンプルを見れば、雰囲気が伝わるかと。
サンプル：四則演算
とりあえず四則演算の文法の定義を以下に示す。
<expr> ::= <term> (('+'|'-') <term>)*
<term> ::= <factor> (('*'|'/') <factor>)*
<factor> ::= <number> | '(' <expr> ')'
<number> ::= -?([1-9][0-9]+|[0-9])これに対応したパーザーをtopdown-javaで書いてみる。以下はexampleの四則演算のサンプルより抜粋。（ExprとかNumberNodeとかの定義は省略）
public class Calculator {
public Result<Expr> parse(String expr) {
var seq = CharacterSequence.builder().source(expr).autoRemoveWS(true).build();
return new CalculatorParser().parse(seq);
}
class CalculatorParser implements Parser<Expr> {
@Override
public Result<Expr> parse(CharacterSequence source) {
var ret = new ExprParser().parse(source);
if (!source.isEof()) {
return Result.end(new ParsingError(source.rest()));
}
return ret;
}
}
class ExprParser implements Parser<Expr> {
@Override
public Result<Expr> parse(CharacterSequence source) {
return new ChainLeft<Expr>(new TermParser(), new AddSubParser()).parse(source);
}
}
class AddSubParser implements Parser<BiFunction<Expr, Expr, Expr>> {
@Override
public Result<BiFunction<Expr, Expr, Expr>> parse(CharacterSequence source) {
return Choice.of(new Token("+"), new Token("-")).parse(source).then(op -> {
return Result.success((l, r) -> {
return new OperatorNode(op, l, r);
});
});
}
}
class MulDivParser implements Parser<BiFunction<Expr, Expr, Expr>> {
@Override
public Result<BiFunction<Expr, Expr, Expr>> parse(CharacterSequence source) {
return Choice.of(new Token("*"), new Token("/")).parse(source).then(op -> {
return Result.success((l, r) -> {
return new OperatorNode(op, l, r);
});
});
}
}
class TermParser implements Parser<Expr> {
@Override
public Result<Expr> parse(CharacterSequence source) {
return new ChainLeft<Expr>(new FactorParser(), new MulDivParser()).parse(source);
}
}
class NumberParser implements Parser<Expr> {
private Regex delegate = new Regex("-?(([1-9][0-9]+)|([0-9]))");
@Override
public Result<Expr> parse(CharacterSequence source) {
return delegate.parse(source).then(res -> {
return Result.success(new NumberNode(Long.parseLong(res)));
});
}
}
class FactorParser implements Parser<Expr> {
@Override
public Result<Expr> parse(CharacterSequence source) {
var n = new NumberParser().parse(source);
if (n.failed()) {
return new Str("(").parse(source).then(o -> {
return new ExprParser().parse(source).then(ret -> {
return new Str(")").parse(source).then(c -> Result.success(ret));
});
});
}
return n;
}
}
}Parserを実装しているクラスの中を見ていくと、
- 一番上のExprParserは、TermParserとAddSubParserの組み合わせを呼び出している=
<term> (('+'|'-') <term>)* - AddSubParserは、+と-のどちらかをパーズする。（後述のMulDivParserも同様。）
- TermParserは、FactorParserとMulDivParserの組み合わせを呼び出している。=
<factor> (('*'|'/') <factor>)* - FactorParserは、まずNumberParserを呼び出し、その結果が解析失敗だったら '()' で囲まれた
exprを解析するよう試みる。=<number> | '(' <expr> ')' - NumberParserは単純に正規表現で数値をパーズしているだけ。
流石にコードにすると冗長に見えるが、構文定義を割とそのまま素直にコードに落としていると思う。
以下はコードをざっと読んだだけでわかる人があまり居なさそうな部分の解説。
new ChainLeft<Expr>(new TermParser(), new AddSubParser()).parse(source);これは<term> (('+'|'-') <term>)*の部分に相当し、「termをパーズした後に+-をパーズ、+-のパーズに成功した場合はtermをパーズ、+-とtermの組をパーズできる限り続け、+-のパーズ結果のBiFunctionに+-の前後のtermを適用する」という動きになる。少し回りくどいが、要するに
- 4 + 5 - 3
という表現を
- +
- 4
- -
- 5
- 3
という木構造にするようなものである。なお、これを以下のようなツリーにするChainRightもある。
- -
- +
- 4
- 5
- 3
- +
サンプル：プログラミング言語
コードの抜粋でも相当な分量なので掲載はしないが、概ね以下のような仕様のミニプログラミング言語のパーザーもサンプルとして書いてみた。
- トップレベルの構文要素は変数定義、関数定義、構造体定義
- 文として認められているのは、変数へのアサイン（ローカル定義も含む）、if-else文、for文、return文、関数呼び出しなどの式文。
- 変数、関数の仮引数、関数の戻り値は型付。
- 型名は英数字かつ数字始まりにはできない。
構文定義はこんな感じになる。
<program> ::= {<function_definition> | <variable_definition> | <struct_definition> }+
<function_definition> ::= <identifier> '(' [<parameter_list>] ')' ':' <type> '{' <statement>* '}'
<type> ::= <identifier>
<struct_type> ::= 'struct' <identifier>
<parameter_list> ::= <parameter> {',' <parameter>}*
<parameter> ::= <identifier> ':' <type>
<variable_definition> ::= <identifier>: <type> '=' <expression> ';'
<statement> ::= <variable_definition> ';'
| <assignment> ';'
| <expression> ';'
| <if_statement>
| <for_statement>
| <return_statement> ';'
| '{' <statement>* '}'
<assignment> ::= <identifier> {<array_access> | <structure_access>}* '=' <expression>
<array_access> :: = '[' <expression> ']'
<structure_access> :: = '.' <identifier>
<function_call> ::= <identifier> '(' [<argument_list>] ')'
<argument_list> ::= <expression> {',' <expression>}*
<if_statement> ::= 'if' '(' <condition> ')' <statement> ['else' <statement>]
<for_statement> ::= 'for' '(' [<assignment>] ';' [<condition>] ';' [<assignment>] ')' <statement>
<return_statement> ::= 'return' [<expression>]
<expression> ::= { <number>
| <string>
| <identifier>
| <function_call>
| <binary_expression>
| '(' <expression> ')'
} {<array_access> | <structure_access>}*
<binary_expression> ::= <term> (<binary_operator1> <term>)*
<term> ::= <factor> (<binary_operator2> <factor>)*
<factor> ::= <expression> | '(' <binary_expression> ')'
<binary_operator1> ::= '+' | '-' | '==' | '!=' | '<' | '>' | '<=' | '>=' | '&&' | '||'
<binary_operator2> ::= ('*'|'/')
<condition> ::= <expression>
<identifier> ::= [a-zA-Z_] [a-zA-Z_0-9]*
<integer> ::= [0-9]+
<float> ::= [0-9]+ '.' [0-9]+
<string> ::= '"' {<any_character>}* '"'
<struct_definition> ::= 'struct' <identifier> '{' <member_list> '}'
<member_list> ::= {<member_declaration>}+
<member_declaration> ::= <identifier> ':' <type> ';'これを解析するためのコードは https://github.com/ckuwata/topdown-java/tree/main/example/src/main/java/info/return0/topdown/example/minilang/parser にて。
今後の予定
- 構文解析エラーの表示を一切考慮していないので、それへの対応。
- テストコードの追加。
- サンプルで作ったミニ言語のインタープリタ。（優先度は低い。）