パーサジェネレータ動くところまで
D言語だとみなさん喰い付きがいいですな…。
動くところまで持って行きましたので載せておきます。
k.inabaさんの指摘を受けてmixinを使うようにしました。正直mixinの存在なんて頭から消えてましたははは。
test.d
+ import testdriver; expression => | sum + int evaluate(); sum => | divide | add' x:sum "+" y:divide -- left rec | sub' x:sum "-" y:divide -- left rec divide => | product | div' x:divide "/" y:clause -- left rec product => | clause | mul' x:product "*" y:clause -- left rec clause => | "(" expression ")" | integer' n:#integer
test.d(text.txtから生成)
import testdriver; interface expression { int evaluate(); } interface sum { int evaluate(); } class add : sum, expression, clause, product, divide { sum x; divide y; mixin add_body; } class sub : sum, expression, clause, product, divide { sum x; divide y; mixin sub_body; } interface divide { int evaluate(); } class div : divide, sum, expression, clause, product { divide x; clause y; mixin div_body; } interface product { int evaluate(); } class mul : product, divide, sum, expression, clause { product x; clause y; mixin mul_body; } interface clause { int evaluate(); } class integer : clause, product, divide, sum, expression { Token* n; mixin integer_body; } expression parse_expression(Scanner scanner) { expression result; result = cast(expression)parse_sum(scanner); return result; } sum parse_sum(Scanner scanner) { sum result; result = cast(sum)parse_divide(scanner); while(scanner.next.is_keyword("+") || scanner.next.is_keyword("-")) { if(scanner.next.is_keyword("+")){ add r = new add; r.x = result; scanner.advance(); r.y = parse_divide(scanner); result = r; }else{ sub r = new sub; r.x = result; scanner.advance(); r.y = parse_divide(scanner); result = r; } } return result; } divide parse_divide(Scanner scanner) { divide result; result = cast(divide)parse_product(scanner); while(scanner.next.is_keyword("/")) { div r = new div; r.x = result; scanner.advance(); r.y = parse_clause(scanner); result = r; } return result; } product parse_product(Scanner scanner) { product result; result = cast(product)parse_clause(scanner); while(scanner.next.is_keyword("*")) { mul r = new mul; r.x = result; scanner.advance(); r.y = parse_clause(scanner); result = r; } return result; } clause parse_clause(Scanner scanner) { clause result; if(scanner.next.is_keyword("(")){ expression r; scanner.advance(); r = parse_expression(scanner); if(!scanner.next.is_keyword(")")) throw new Exception("error"); scanner.advance(); result = cast(clause)r; }else if(scanner.next.is_integer()){ integer r = new integer; scanner.advance(); result = r; } return result; }
testdriver.d
private import test; private import std.stream; struct Token { char[] keyword; int value; bit is_keyword(char[] word) { return (keyword.length > 0) && (keyword == word); } bit is_integer() { return keyword.length == 0; } bit is_end() { return is_keyword("$"); } } class Scanner { this(char[] source) { this.source = source; advance(); } char[] source; Token* next; void advance() { next = new Token; if(source.length == 0){ next.keyword = "$"; //EOF }else if(source[0] >= '0' && source[0] <= '9'){ next.keyword.length = 0; next.value = 0; do{ next.value = next.value * 10 + (source[0] - '0'); source = source[1..$]; }while(source.length > 0 && source[0] >= '0' && source[0] <= '9'); }else{ next.keyword = source[0..1]; source = source[1..$]; } } } template div_body() { int evaluate(){ return x.evaluate() / y.evaluate(); } } template mul_body() { int evaluate(){ return x.evaluate() * y.evaluate(); } } template sub_body() { int evaluate(){ return x.evaluate() - y.evaluate(); } } template add_body() { int evaluate(){ return x.evaluate() + y.evaluate(); } } template integer_body() { int evaluate(){ return n.value; } } int main() { Scanner s = new Scanner(stdin.readLine()); expression e = parse_expression(s); if(!s.next.is_end()){ throw new Exception("error!"); } printf("%d\n", e.evaluate()); return 0; }
再帰下降パーサとはいえ、ここまで自動生成できたらちょっとだけ感動と思うのですが、Boost::spiritな皆様にとってはちゃんちゃらおかしかったりするのでしょうか?
ソースは、最近書いたコードのなかでは破格に汚いので、smallタグふたつぐらい挿んでリンクしておきます。http://f22.aaa.livedoor.jp/~qwerty/private/junk/ypg.d