読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Onionで作るPEGパーザコンビネータ

せっかくなので、OnionでもPEGパーザコンビネータ書いてみた。しかし、自分で作った言語なのに、文法忘れてて文法定義ファイル見直してみたり、コンパイラが例外吐いて落ちたりして、コンパイラの不具合を避けてプログラムを書くために頭を悩ませるはめに…。とりあえず、今回わかった不具合は修正しておこう。

import {
  java.util.*;
  Any = java.lang.Object;
}
class Pair {
  @_1: Any;
  @_2: Any;
public:
  new(_1: Any, _2: Any) {
    @_1 = _1;
    @_2 = _2;
  }
  _1: Any { return @_1; }
  _2: Any { return @_2; }
  toString: String { return String::format("(%s, %s)", [@_1, @_2].toArray); }
}
class ParseResult {
  @value: Any;
  @rest: String;
  public:
  new(value: Any, rest: Any) {
    @value = value;
    @rest = rest;
  }
  value: Any { return @value; }
  rest: String { return @rest; }
  toString: String { 
    return String::format("(value = %s, rest = %s)", [@value, @rest].toArray); 
  }
}
interface Parser {
  parse(input: String): ParseResult;
}
interface Transformer {
  apply(param: Any): Any;
}
class ParserProxy <: Parser {
  @target: Parser;
public:
  target: Parser { return @target; }
  target(target: Parser) { @target = target; }
  new(target: Parser) { @target = target; }
  parse(input: String): ParseResult {
    return @target.parse(input);
  }
}
class PEGParserCombinators {
public:
  proxy(p: Parser): ParserProxy { return new ParserProxy(p); }
  string(param: String): Parser {
    return #Parser.parse(input: String) {
      if(input.startsWith(param)) {
        return new ParseResult(param, input.substring(param.length));
      } else {
        return null;
      }
    };
  }
  any: Parser {
    return #Parser.parse(input: String) {
      if(input.length > 0) { 
        return new ParseResult(input.substring(0, 1), input.substring(1));
      } else {
        return null;
      }
    };
  }
  alt(p1: Parser, p2: Parser): Parser {
    return #Parser.parse(input: String) {
      r1 = p1.parse(input);
      if(r1 != null) { return r1; } else { return p2.parse(input); }
    };
  }
  seq(p1: Parser, p2: Parser): Parser {
    return #Parser.parse(input: String) {
      r1 = p1.parse(input);
      if(r1 == null) { return null; }
      r2 = p2.parse(r1.rest);
      if(r2 == null) { return null; } 
      return new ParseResult(new Pair(r1.value, r2.value), r2.rest);
    };
  }
  seqN(ps: List): Parser {
    return #Parser.parse(input: String) {
      rs = [];
      foreach p: Parser in ps {
        r = p.parse(input);
        if(r == null) { return null; }
        rs << r.value;
        input = r.rest;
      }
      return new ParseResult(rs, input);
    };
  }
  andp(p: Parser): Parser {
    return not(not(p));
  }
  not(p: Parser): Parser {
    return #Parser.parse(input: String) {
      r = p.parse(input);
      if(r == null) { return new ParseResult(null, input); } 
      else { return null; }
    };
  }
  opt(p: Parser): Parser {
    return alt(
      p, apply(string(""), #Transformer.apply(param: Any) { return null; })
    );
  }
  rep(p: Parser): Parser {
    return #Parser.parse(input: String) {
      rs = [];
      while((r = p.parse(input)) != null) {
        rs << r.value;
        input = r.rest;
      }
      return new ParseResult(rs, input);
    };
  }
  rep1(p: Parser): Parser {
    return apply(seq(p, rep(p)), #Transformer.apply(param: Any) {
      param$Pair._2$List << param$Pair._2;
     return param$Pair._2;
    });
  }
  apply(p: Parser, t: Transformer): Parser {
    return #Parser.parse(input: String) {
      r = p.parse(input);
      if(r == null) { return null; } 
      else { return new ParseResult(t.apply(r.value), r.rest); }
    };
  }
}

使い方は以下のような感じ。Onionにはstatic importが無いので、仕方なくクラスを継承することで、代用することに。

class User : PEGParserCombinators {
  @S: ParserProxy;
  @A: ParserProxy;
  @B: ParserProxy;
  public:
  new {
    @S = proxy(null);
    @A = proxy(null);
    @B = proxy(null);
    @S.target(
      seqN([
        andp(seq(@A, not(string("b")))),
        rep1(string("a")),
        @B,
        not(string("c"))
      ]));
    @A.target(seqN([string("a"), opt(@A), string("b")]));
    @B.target(seqN([string("b"), opt(@B), string("c")]));
  }
  def S: ParserProxy { return @S; }
}

System::out.println((new User).S.parse(args[0]));