public class Ast {
  public static class Action extends Expression {
    private Expression body;
    private String  code;

    public Action(Position pos, Expression body, String code) {
      super(pos);
      this.body = body;
      this.code = code;
    }

    public Expression body() {
      return body;
    }
    
    public String code() {
      return code;
    }

    @Override
    public String toString() {
      return body + " <[" + code + "]>";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }
  
  public static class BoundedExpression extends Expression {
    private Expression body;
    public BoundedExpression(Expression body) {
      super(body.pos());
      this.body = body;
    }
    
    public Expression body() {
      return body;
    }
    
    @Override
    public String toString() {
      return "bounded{" + body + "}";
    }
    
    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }    
  }

  public static class SetValueAction extends Expression {
    private Expression body;
    private String code;

    public SetValueAction(Position pos, Expression body, String code) {
      super(pos);
      this.body = body;
      this.code = code;
    }

    public Expression body() {
      return body;
    }

    public String code() {
      return code;
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return body + " %{" + code + "}";
    }
  }


  public static class N_Alternation extends VarArgExpression {
    public N_Alternation(Position pos, List<Expression> expressions){
      super(pos, expressions);
    }


    @Override
    public String toString() {
      StringBuffer buf = new StringBuffer();
      buf.append("(");
      buf.append(body.get(0).toString());
      for(Expression e : body.subList(1,  body.size())){
        buf.append(" / ");
        buf.append(e.toString());
      }
      buf.append(")");
      return new String(buf);
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static abstract class BinaryExpression extends Expression {
    private Expression lhs;
    private Expression rhs;

    public BinaryExpression(Position pos, Expression lhs, Expression rhs){
      super(pos);
      this.lhs = lhs;
      this.rhs = rhs;
    }

    public Expression lhs() {
      return lhs;
    }

    public Expression rhs() {
      return rhs;
    }
  }
  
  public static class Cut extends Expression {
    public Cut(Position pos){
      super(pos);
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return "^";
    }
  }

  public static class Fail extends Expression {
    public Fail(Position pos){
      super(pos);
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }

    @Override
    public String toString() {
      return "fail";
    }
  }

  public static class Empty extends Terminal {
    public Empty(Position pos){
      super(pos);
    }

    public String toString() {
      return "()";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static abstract class Expression extends Node {
    public Expression(Position pos){
      super(pos);
    }
  }
  
  public static abstract class Terminal extends Expression {
    public Terminal(Position pos){
      super(pos);
    }
  }

  public static class Grammar extends Node implements Iterable<Rule> {
    private Symbol name;
    private final List<MacroDefinition> macros;
    private final List<Rule> rules;

    public Grammar(Position pos, Symbol name, List<MacroDefinition> macros, List<Rule> rules){
      super(pos);
      this.name = name;
      this.macros = macros;
      this.rules = rules;
    }

    public Iterator<Rule> iterator() {
      return rules.iterator();
    }

    public Symbol name() {
      return name;
    }
    
    public void setName(Symbol name) {
      this.name = name;
    }
    
    public List<MacroDefinition> macros() {
      return macros;
    }

    public List<Rule> getRules() {
      return rules;
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      StringBuffer buf = new StringBuffer();
      buf.append("grammar " + name + ";");
      buf.append(SystemProperties.LINE_SEPARATOR);
      buf.append(SystemProperties.LINE_SEPARATOR);
      for(Rule r : rules) {
        buf.append(r);
        buf.append(SystemProperties.LINE_SEPARATOR);
        buf.append(SystemProperties.LINE_SEPARATOR);
      }
      return new String(buf);
    }
  }

  public static abstract class Node {
    private Position pos;

    public Node(Position pos) {
      this.pos = pos;
    }

    public Position pos() {
      return pos;
    }

    public abstract <R, C> R accept(Visitor<R, C> visitor, C context);
  }

  public static class NonTerminal extends Expression {
    private Symbol name;
    private Symbol var;

    public NonTerminal(Position pos, Symbol name, Symbol var) {
      super(pos);
      this.name = name;
      this.var  = var;
    }

    public NonTerminal(Position pos, Symbol name){
      this(pos, name, null);
    }

    public Symbol name() {
      return name;
    }

    public Symbol var() {
      return var;
    }

    @Override
    public String toString() {
      return var != null ? var + ":" + name.toString() : name.toString();
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }
  
  public static class MacroVariable extends Expression {
    private final Symbol name;
    private final Symbol var;
    
    public MacroVariable(Position pos, Symbol name, Symbol var) {
      super(pos);
      this.name = name;
      this.var = var;
    }

    public Symbol name() {
      return name;
    }
    
    public Symbol var() {
      return var;
    }
    
    @Override
    public String toString() {
      return var != null ? var + ":" + name.toString() : name.toString();
    }
    
    public <R, C> R accept(Ast.Visitor<R,C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }
  
  public static class MacroCall extends Expression {
    private final Symbol name;
    private final List<Expression> params;
    
    public MacroCall(Position pos, Symbol name, List<Expression> params) {
      super(pos);
      this.name = name;
      this.params = params;
    }

    public Symbol name() {
      return name;
    }
    
    public List<Expression> params() {
      return params;
    }
    
    @Override
    public String toString() {
      return name + "(" + params + ")";
    }
    
    @Override
    public <R, C> R accept(Ast.Visitor<R,C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class NotPredicate extends Expression {
    private Expression body;
    
    public NotPredicate(Position pos, Expression body){
      super(pos);
      this.body = body;
    }
    
    public Expression body() {
      return body;
    }

    @Override
    public String toString() {
      return "!(" + body + ")";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class AndPredicate extends Expression {
    private Expression body;
    public AndPredicate(Position pos, Expression expr){
      super(pos);
      this.body = expr;
    }
    public Expression body() {
      return body;
    }
    @Override
    public String toString() {
      return "&(" + body + ")";
    }
    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }
  
  public static class SemanticPredicate extends Expression {
    private String predicate;
    
    public SemanticPredicate(Position pos, String expression){
      super(pos);
      this.predicate = expression;
    }
    public String predicate() {
      return predicate;
    }

    @Override
    public String toString() {
      return "&{" + predicate + "}";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class Repetition extends Expression {
    private Expression body;
    public Repetition(Position pos, Expression expr){
      super(pos);
      this.body = expr;
    }
    public Expression body() {
      return body;
    }

    @Override
    public String toString() {
      return "(" + body + ")*";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class RepetitionPlus extends Expression {
    private Expression body;
    
    public RepetitionPlus(Position pos, Expression body){
      super(pos);
      this.body = body;
    }
    
    public Expression body() {
      return body;
    }

    @Override
    public String toString() {
      return "(" + body + ")+";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class Optional extends Expression {
    private Expression body;
    
    public Optional(Position pos, Expression expr){
      super(pos);
      this.body = expr;
    }
    
    public Expression body() {
      return body;
    }

    @Override
    public String toString() {
      return "(" + body + ")?";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }
  
  public static class MacroDefinition extends Node {
    private final Symbol name;
    private final List<Symbol> formalParams;
    private final Expression body;
    public MacroDefinition(Position pos, Symbol name,
      List<Symbol> formalParams, Expression body) {
      super(pos);
      this.name = name;
      this.formalParams = formalParams;
      this.body = body;
    }
    public Symbol name() { 
      return name; 
    }
    public List<Symbol> formalParams() {
      return formalParams;
    }
    public Expression body() {
      return body;
    }
    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      if(formalParams.size() > 0) {
        builder.append(formalParams.get(0));
        for(Symbol formalParam:formalParams.subList(1, formalParams.size())) {
          builder.append(", " + formalParam);
        }
      }
      return String.format(
        "macro %s(%s) = %s", name, new String(builder), body
      );
    }
    @Override
    public <R, C> R accept(Ast.Visitor<R,C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class Rule extends Node {
    public static final int BOUNDED = 1;
    private int flags;
    private Symbol name;
    private Symbol type;
    private Expression expression;
    private String code;

    public Rule(Position pos, int flags, Symbol name, Symbol type, Expression expression, String code){
      super(pos);
      this.flags = flags;
      this.name = name;
      this.type = type;
      this.expression = expression;
      this.code = code;
    }
    
    public int flags() {
      return flags;
    }

    public Symbol name() {
      return name;
    }

    public Symbol type() {
      return type;
    }

    public Expression body() {
      return expression;
    }

    public String code() {
      return code;
    }

    @Override
    public String toString() {
      return ((flags & BOUNDED) != 0 ? "bounded " : "") + 
              name + " = " +  expression +  " ;";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class N_Sequence extends VarArgExpression {
    public N_Sequence(Position pos, List<Expression> expressions) {
      super(pos, expressions);
    }

    @Override
    public String toString() {
      StringBuffer buf = new StringBuffer();
      buf.append("(");
      buf.append(body.get(0).toString());
      for(Expression e : body.subList(1,  body.size())){
        buf.append(" ");
        buf.append(e.toString());
      }
      buf.append(")");
      return new String(buf);
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }

  public static class StringLiteral extends Terminal {
    private String value;
    private Symbol var;

    public StringLiteral(Position pos, String value, Symbol var){
      super(pos);
      this.value = value;
      this.var = var;
    }

    public StringLiteral(Position pos, String value){
      this(pos, value, null);
    }

    public String value() {
      return value;
    }

    public Symbol var() {
      return var;
    }

    @Override
    public String toString() {
      return "\"" + value + "\"";
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
  }
  
  public static class Wildcard extends Terminal {
    private final Symbol var;
    
    public Wildcard(Position pos, Symbol var) {
      super(pos);
      this.var = var;
    }
    
    public Symbol var() {
      return var;
    }
    
    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return ".";
    }
  }

  public static class CharClass extends Terminal {
    public abstract static class Element {}
    public static class Char extends Element {
      public final char value;
      public Char(char value) {
        this.value = value;
      }
    }
    public static class Range extends Element {
      public final char start;
      public final char end;
      public Range(char start, char end) {
        this.start = start;
        this.end = end;
      }
    }
    private Symbol var;
    public final boolean positive;
    public final List<Element> elements;

    public CharClass(Position pos, boolean positive, List<Element> elements){
      this(pos, positive, elements, null);
    }

    public CharClass(
      Position pos, boolean positive, List<Element> elements, Symbol var
    ){
      super(pos);
      this.positive = positive;
      this.elements = Collections.unmodifiableList(elements);
      this.var = var;
    }

    public Symbol var() {
      return var;
    }

    @Override
    public String toString() {
      StringBuffer buf = new StringBuffer();
      if(var != null) {
        buf.append(var);
        buf.append(':');
      }
      buf.append('[');
      if(!positive) {
        buf.append('^');
      }
      for(Element e:elements) {
        if(e instanceof Char) {          
          switch(((Char)e).value) {
          case '\t': buf.append("\\t"); break;
          case '\f': buf.append("\\f"); break;
          case '\r': buf.append("\\r"); break;
          case '\n': buf.append("\\n"); break;
          default: buf.append(((Char)e).value); break;
          }
        }else {
          buf.append(((Range)e).start);
          buf.append('-');
          buf.append(((Range)e).end);
        }
      }
      buf.append(']');
      return new String(buf);
    }

    @Override
    public <R, C> R accept(Visitor<R, C> visitor, C context) {
      return visitor.visit(this, context);
    }    
  }


  public static abstract class VarArgExpression extends Expression implements Iterable<Expression> {
    protected List<Expression> body;

    public VarArgExpression(Position pos, List<Expression> expressions){
      super(pos);
      this.body = expressions;
    }

    public List<Expression> body() {
      return body;
    }

    public Iterator<Expression> iterator() {
      return body.iterator();
    }

    @Override
    public String toString() {
      StringBuffer buf = new StringBuffer();
      buf.append(body.get(0).toString());
      for(Expression e : body.subList(1, body.size())){
        buf.append(" | ");
        buf.append(e.toString());
      }
      return new String(buf);
    }
  }

  public static class Visitor<R, C> {
    protected R visit(Empty node, C context){
      return null;
    }
    protected R visit(Action node, C context){ 
      return null;
    }
    protected R visit(SetValueAction node, C context){ 
      return null;
    }
    protected R visit(N_Alternation node, C context){ 
      return null;
    }
    protected R visit(Cut node, C context){ 
      return null;
    }
    protected R visit(Fail node, C context){ 
      return null;
    }
    protected R visit(SemanticPredicate node, C context) { 
      return null;
    }
    protected R visit(AndPredicate node, C context){ 
      return null;
    }
    protected R visit(NotPredicate node, C context){ 
      return null;
    }
    protected R visit(Grammar node, C context){ 
      return null;
    }
    protected R visit(NonTerminal node, C context){ 
      return null;
    }
    protected R visit(MacroCall node, C context){
      return null;
    }
    protected R visit(MacroVariable node, C context){
      return null;
    }
    protected R visit(Repetition node, C context){ 
      return null;
    }
    protected R visit(RepetitionPlus node, C context){ 
      return null;
    }
    protected R visit(Optional node, C context){ 
      return null;
    }
    protected R visit(Rule node, C context){ 
      return null;
    }
    protected R visit(MacroDefinition node, C context) {
      return null;
    }
    protected R visit(N_Sequence node, C context){ 
      return null;
    }
    protected R visit(StringLiteral node, C context){ 
      return null;
    }
    protected R visit(CharClass node, C context){ 
      return null;
    }
    protected R visit(Wildcard node, C context){ 
      return null;
    }
    protected R visit(BoundedExpression node, C context){ 
      return node.body().accept(this, context);
    }
    
    /**
     * using this method, node.accept(this, context) can be written to
     * accept(node, context).
     * @param node
     * @param context
     * @return
     */
    protected final R accept(Node node, C context) {
      return node.accept(this, context);
    }
  }
  
  public static class DepthFirstVisitor<C> extends Visitor<Void, C> {
    @Override
    protected Void visit(Action node, C context) {
      return node.body().accept(this, context);
    }

    @Override
    protected Void visit(AndPredicate node, C context) {
      return node.body().accept(this, context);
    }

    @Override
    protected Void visit(CharClass node, C context) {
      return null;
    }

    @Override
    protected Void visit(Cut node, C context) {
      return null;
    }

    @Override
    protected Void visit(Empty node, C context) {
      return null;
    }

    @Override
    protected Void visit(Fail node, C context) {
      return null;
    }

    @Override
    protected Void visit(Grammar node, C context) {
      for(Rule r:node){
        r.body().accept(this, context);
      }
      return null;
    }

    @Override
    protected Void visit(N_Alternation node, C context) {
      for(Expression e:node){
        e.accept(this, context);
      }
      return null;
    }

    @Override
    protected Void visit(N_Sequence node, C context) {
      for(Expression e:node){
        e.accept(this, context);
      }
      return null;
    }

    @Override
    protected Void visit(NonTerminal node, C context) {
      return null;
    }
    
    @Override
    protected Void visit(MacroVariable node, C context) {
      return null;
    }
    
    @Override
    protected Void visit(MacroCall node, C context) {
      for(Expression param:node.params) param.accept(this, context);
      return null;
    }

    @Override
    protected Void visit(NotPredicate node, C context) {
      return node.body().accept(this, context);
    }

    @Override
    protected Void visit(Optional node, C context) {
      return node.body().accept(this, context);
    }

    @Override
    protected Void visit(Repetition node, C context) {
      return node.body.accept(this, context);
    }

    @Override
    protected Void visit(RepetitionPlus node, C context) {
      return node.body.accept(this, context);
    }
    
    protected Void visit(BoundedExpression node, C context) {
      return node.body.accept(this, context);
    }

    @Override
    protected Void visit(Rule node, C context) {
      return node.body().accept(this, context);
    }
    
    protected Void visit(MacroDefinition node, C context) {
      return node.body().accept(this, context);
    }

    @Override
    protected Void visit(SemanticPredicate node, C context) {
      return null;
    }

    @Override
    protected Void visit(SetValueAction node, C context) {
      return node.body().accept(this, context);
    }

    @Override
    protected Void visit(StringLiteral node, C context) {
      return null;
    }

    @Override
    protected Void visit(Wildcard node, C context) {
      return null;
    }    
  }
} public class DirectedGraph<N, ExtraInfo> implements Iterable<N> {
  private final Set<N> nodes = new HashSet<N>();
  private final Map<N, Set<N>> edges = new HashMap<N, Set<N>>();
  private final Map<N, ExtraInfo> infoMap = new HashMap<N, ExtraInfo>();
  private ExtraInfo defaultInfo;
  
  public DirectedGraph(ExtraInfo defaultInfo) {
    this.defaultInfo = defaultInfo;
  }
  
  public DirectedGraph() {    
  }
  
  public void add(N node) {
    if(!nodes.contains(node)) {
      edges.put(node, new HashSet<N>());
    }
    nodes.add(node);
    infoMap.put(node, defaultInfo);
  }
  
  public void setInfo(N node, ExtraInfo info) {
    infoMap.put(node, info);
  }
  
  public ExtraInfo getInfo(N node) {
    return infoMap.get(node);
  }
  
  public boolean contains(N node) {
    return nodes.contains(node);
  }
  
  public void addEdge(N from, N to) {
    edges.get(from).add(to);
  }
  
  public Set<N> neighbors(N from) {
    return Collections.unmodifiableSet(edges.get(from));
  }
  
  public Iterator<N> iterator() {
    return nodes.iterator();
  }
  
  public boolean hasCyclicity(N start) {
    return hasCyclicity(start, start, new HashSet<N>());
  }
  
  @Override
  public String toString() {
    StringBuffer buf = new StringBuffer();
    for(N n:nodes) {
      buf.append(n);
      buf.append(" -> ");
      buf.append(edges.get(n));
      buf.append(System.getProperty("line.separator"));
    }
    return new String(buf);
  }
  
  private boolean hasCyclicity(N start, N current, Set<N> visit) {
    if(visit.contains(current)) {
      return true;
    }
    try {
      visit.add(current);
      for(N s:neighbors(current)){
        if(hasCyclicity(start, s, visit)) return true;
      }
      return false;
    }finally{
      visit.remove(current);
    }
  }
} public class Regex {
  public static abstract class Expression {
    public abstract <R, C> R accept(Visitor<C, R> visitor, C context);
  }
  
  public static abstract class BinaryExpression extends Expression {
    public final Expression lhs;
    public final Expression rhs;
    
    public BinaryExpression(Expression lhs, Expression rhs) {
      this.lhs = lhs;
      this.rhs = rhs;
    }    
  }
  
  /**
   * An repetition expression (A*) of RE.
   * @author Kota Mizushima
   *
   */
  public static class Repetition extends Expression {
    public final Expression body;
    
    public Repetition(Expression body) {
      this.body = body;
    }
        
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return "(" + body + "*)";
    }
  }
  
  /**
   * An alternation expression (A | B) of a RE.
   * @author Kota Mizushima
   *
   */
  public static class Alternation extends BinaryExpression {
    public Alternation(Expression lhs, Expression rhs) {
      super(lhs, rhs);
    }
    
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return "(" + lhs + "|" + rhs + ")";
    }
  }
  
  /**
   * A sequence expression(A B) of a RE.
   * @author Kota Mizushima
   *
   */
  public static class Sequence extends BinaryExpression {
    public Sequence(Expression lhs, Expression rhs) {
      super(lhs, rhs);
    }
    
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return (lhs.toString() + rhs.toString());
    }
  }
  
  /**
   * A dot expression(.) of a RE.
   * @author Kota Mizushima
   *
   */  
  public static class All extends Expression {
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return ".";
    }
  }

  /**
   * An empty expression of a RE.
   * @author Kota Mizushima
   *
   */  
  public static class Empty extends Expression {
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return "";
    }
  }
  
  /**
   * A character expression of a RE.
   * @author Kota Mizushima
   *
   */  
  public static class Char extends Expression {
    private final char chr;
    
    public Char(char chr) {
      this.chr = chr;
    }
    
    public char getChar() {
      return chr;
    }
    
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return "" + chr;
    }
  }
  
  /**
   * A character set expression of a RE.
   * @author Kota Mizushima
   *
   */  
  public static class CharClass extends Expression {
    private final boolean not;
    private final Set<Character> chars;
    
    public CharClass(boolean not, Set<Character> chars) {
      this.not = not;
      this.chars = chars;
    }
    
    public boolean isNot() {
      return not;
    }
    
    public Set<Character> getChars() {
      return chars;
    }
    
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      StringBuffer buf = new StringBuffer();
      buf.append('[');
      if(not) {
        buf.append('^');
      }
      for(char c:chars) {
        buf.append(c);
      }
      buf.append(']');
      return new String(buf);
    }
  }
  
  /**
   * This class represents an error.
   */
  public static class Error extends Expression {
    private Error() {}
    @Override
    public <R, C> R accept(Visitor<C, R> visitor, C context) {
      return visitor.visit(this, context);
    }
    
    @Override
    public String toString() {
      return "_|_";
    }
  }
  
  public static final Error ERROR = new Error();
  
  /**
   * A visitor to visit an AST of a RE.
   * @author Kota Mizushima
   *
   * @param <C>
   */
  public static abstract class Visitor<C, R> {
    protected R visit(All expression, C context){ return null; }
    protected R visit(Alternation expression, C context){ return null; }
    protected R visit(Char expression, C context){ return null; }
    protected R visit(CharClass expression, C context){ return null; }
    protected R visit(Empty expression, C context){ return null; }
    protected R visit(Repetition expression, C context){ return null; }
    protected R visit(Sequence expression, C context){ return null; }
    protected R visit(Error expression, C context) { return null; }
  }
} public class Regex2DFA extends Regex.Visitor<NFA, Pair<Integer, Integer>> {
  public static final Regex2DFA INSTANCE = new Regex2DFA();
  private Regex2DFA() {
  }
  
  public Automata.DFA compile(Regex.Expression expression) {
    if(expression == Regex.ERROR) return Automata.DFA.ERROR;
    NFA nfa = compileToNfa(expression);
    return Automata.fromNFA2DFA(nfa);
  }
  
  private NFA compileToNfa(Regex.Expression expression) {
    NFA nfa = new NFA();
    Pair<Integer, Integer> result = expression.accept(this, nfa);
    nfa.startNum = result.fst();
    nfa.finalNum = result.snd();
    return nfa;
  }

  @Override
  protected Pair<Integer, Integer> visit(All expression, NFA context) {
    int startNum = context.addState();
    int finalNum = context.addState();
    for(int i = 0; i < Automata.NUM_ALPHABETS; i++) {
      context.addTransition(startNum, (char)i, finalNum);
    }
    return Pair.make(startNum, finalNum);
  }

  @Override
  protected Pair<Integer, Integer> visit(Alternation expression, NFA context) {
    int startNum = context.addState();
    int finalNum = context.addState();
    Pair<Integer, Integer> resultL = expression.lhs.accept(this, context);
    Pair<Integer, Integer> resultR = expression.rhs.accept(this, context);
    context.addEpsilon(startNum, resultL.fst());
    context.addEpsilon(startNum, resultR.fst());
    context.addEpsilon(resultL.snd(), finalNum);
    context.addEpsilon(resultR.snd(), finalNum);
    
    return Pair.make(startNum, finalNum);
  }

  @Override
  protected Pair<Integer, Integer> visit(Char expression, NFA context) {
    int startNum = context.addState();
    int finalNum = context.addState();
    context.addTransition(startNum, expression.getChar(), finalNum);
    return Pair.make(startNum, finalNum);
  }

  @Override
  protected Pair<Integer, Integer> visit(CharClass expression, NFA context) {
    int startNum = context.addState();
    int finalNum = context.addState();
    for(int i = 0; i < Automata.NUM_ALPHABETS; i++) {
      if(expression.isNot() == expression.getChars().contains((char)i)) continue;
      context.addTransition(startNum, (char)i, finalNum);
    }
    return Pair.make(startNum, finalNum);
  }

  @Override
  protected Pair<Integer, Integer> visit(Empty expression, NFA context) {
    int startNum = context.addState();
    int finalNum = context.addState();
    context.addEpsilon(startNum, finalNum);
    
    return Pair.make(startNum, finalNum);
  }

  @Override
  protected Pair<Integer, Integer> visit(Repetition expression, NFA context) {
    int startNum = context.addState();
    int finalNum = context.addState();
    Pair<Integer, Integer> result = expression.body.accept(this, context);
    context.addEpsilon(startNum, result.fst());
    context.addEpsilon(startNum, finalNum);
    context.addEpsilon(result.snd(), result.fst());
    context.addEpsilon(result.snd(), finalNum);
    
    return Pair.make(startNum, finalNum);
  }

  @Override
  protected Pair<Integer, Integer> visit(Sequence expression, NFA context) {
    Pair<Integer, Integer> resultL = expression.lhs.accept(this, context);
    Pair<Integer, Integer> resultR = expression.rhs.accept(this, context);
    context.addEpsilon(resultL.snd(), resultR.fst());
    
    return Pair.make(resultL.fst(), resultR.snd());
  }
} public static class Action extends Expression {
  private Expression body;
  private String  code;

  public Action(Position pos, Expression body, String code) {
    super(pos);
    this.body = body;
    this.code = code;
  }

  public Expression body() {
    return body;
  }
    
  public String code() {
    return code;
  }

  @Override
  public String toString() {
    return body + " <[" + code + "]>";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class AndPredicate extends Expression {
  private Expression body;
  public AndPredicate(Position pos, Expression expr){
    super(pos);
    this.body = expr;
  }
  public Expression body() {
    return body;
  }
  @Override
  public String toString() {
    return "&(" + body + ")";
  }
  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class CharClass extends Terminal {
  public abstract static class Element {}
  public static class Char extends Element {
    public final char value;
    public Char(char value) {
      this.value = value;
    }
  }
  public static class Range extends Element {
    public final char start;
    public final char end;
    public Range(char start, char end) {
      this.start = start;
      this.end = end;
    }
  }
  private Symbol var;
  public final boolean positive;
  public final List<Element> elements;

  public CharClass(Position pos, boolean positive, List<Element> elements){
    this(pos, positive, elements, null);
  }

  public CharClass(
    Position pos, boolean positive, List<Element> elements, Symbol var
  ){
    super(pos);
    this.positive = positive;
    this.elements = Collections.unmodifiableList(elements);
    this.var = var;
  }

  public Symbol var() {
    return var;
  }

  @Override
  public String toString() {
    StringBuffer buf = new StringBuffer();
    if(var != null) {
      buf.append(var);
      buf.append(':');
    }
    buf.append('[');
    if(!positive) {
      buf.append('^');
    }
    for(Element e:elements) {
      if(e instanceof Char) {          
        switch(((Char)e).value) {
        case '\t': buf.append("\\t"); break;
        case '\f': buf.append("\\f"); break;
        case '\r': buf.append("\\r"); break;
        case '\n': buf.append("\\n"); break;
        default: buf.append(((Char)e).value); break;
        }
      }else {
        buf.append(((Range)e).start);
        buf.append('-');
        buf.append(((Range)e).end);
      }
    }
    buf.append(']');
    return new String(buf);
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }    
} public static class Cut extends Expression {
  public Cut(Position pos){
    super(pos);
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
    
  @Override
  public String toString() {
    return "^";
  }
} public static class Empty extends Terminal {
  public Empty(Position pos){
    super(pos);
  }

  public String toString() {
    return "()";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static abstract class Expression extends Node {
  public Expression(Position pos){
    super(pos);
  }
} public static class Fail extends Expression {
  public Fail(Position pos){
    super(pos);
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }

  @Override
  public String toString() {
    return "fail";
  }
} public static class Grammar extends Node implements Iterable<Rule> {
  private Symbol name;
  private final List<MacroDefinition> macros;
  private final List<Rule> rules;

  public Grammar(Position pos, Symbol name, List<MacroDefinition> macros, List<Rule> rules){
    super(pos);
    this.name = name;
    this.macros = macros;
    this.rules = rules;
  }

  public Iterator<Rule> iterator() {
    return rules.iterator();
  }

  public Symbol name() {
    return name;
  }
    
  public void setName(Symbol name) {
    this.name = name;
  }
    
  public List<MacroDefinition> macros() {
    return macros;
  }

  public List<Rule> getRules() {
    return rules;
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
    
  @Override
  public String toString() {
    StringBuffer buf = new StringBuffer();
    buf.append("grammar " + name + ";");
    buf.append(SystemProperties.LINE_SEPARATOR);
    buf.append(SystemProperties.LINE_SEPARATOR);
    for(Rule r : rules) {
      buf.append(r);
      buf.append(SystemProperties.LINE_SEPARATOR);
      buf.append(SystemProperties.LINE_SEPARATOR);
    }
    return new String(buf);
  }
} public static class N_Alternation extends VarArgExpression {
  public N_Alternation(Position pos, List<Expression> expressions){
    super(pos, expressions);
  }


  @Override
  public String toString() {
    StringBuffer buf = new StringBuffer();
    buf.append("(");
    buf.append(body.get(0).toString());
    for(Expression e : body.subList(1,  body.size())){
      buf.append(" / ");
      buf.append(e.toString());
    }
    buf.append(")");
    return new String(buf);
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class N_Sequence extends VarArgExpression {
  public N_Sequence(Position pos, List<Expression> expressions) {
    super(pos, expressions);
  }

  @Override
  public String toString() {
    StringBuffer buf = new StringBuffer();
    buf.append("(");
    buf.append(body.get(0).toString());
    for(Expression e : body.subList(1,  body.size())){
      buf.append(" ");
      buf.append(e.toString());
    }
    buf.append(")");
    return new String(buf);
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class NonTerminal extends Expression {
  private Symbol name;
  private Symbol var;

  public NonTerminal(Position pos, Symbol name, Symbol var) {
    super(pos);
    this.name = name;
    this.var  = var;
  }

  public NonTerminal(Position pos, Symbol name){
    this(pos, name, null);
  }

  public Symbol name() {
    return name;
  }

  public Symbol var() {
    return var;
  }

  @Override
  public String toString() {
    return var != null ? var + ":" + name.toString() : name.toString();
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class NotPredicate extends Expression {
  private Expression body;
    
  public NotPredicate(Position pos, Expression body){
    super(pos);
    this.body = body;
  }
    
  public Expression body() {
    return body;
  }

  @Override
  public String toString() {
    return "!(" + body + ")";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class Optional extends Expression {
  private Expression body;
    
  public Optional(Position pos, Expression expr){
    super(pos);
    this.body = expr;
  }
    
  public Expression body() {
    return body;
  }

  @Override
  public String toString() {
    return "(" + body + ")?";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class Repetition extends Expression {
  private Expression body;
  public Repetition(Position pos, Expression expr){
    super(pos);
    this.body = expr;
  }
  public Expression body() {
    return body;
  }

  @Override
  public String toString() {
    return "(" + body + ")*";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class RepetitionPlus extends Expression {
  private Expression body;
    
  public RepetitionPlus(Position pos, Expression body){
    super(pos);
    this.body = body;
  }
    
  public Expression body() {
    return body;
  }

  @Override
  public String toString() {
    return "(" + body + ")+";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class Rule extends Node {
  public static final int BOUNDED = 1;
  private int flags;
  private Symbol name;
  private Symbol type;
  private Expression expression;
  private String code;

  public Rule(Position pos, int flags, Symbol name, Symbol type, Expression expression, String code){
    super(pos);
    this.flags = flags;
    this.name = name;
    this.type = type;
    this.expression = expression;
    this.code = code;
  }
    
  public int flags() {
    return flags;
  }

  public Symbol name() {
    return name;
  }

  public Symbol type() {
    return type;
  }

  public Expression body() {
    return expression;
  }

  public String code() {
    return code;
  }

  @Override
  public String toString() {
    return ((flags & BOUNDED) != 0 ? "bounded " : "") + 
            name + " = " +  expression +  " ;";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class SemanticPredicate extends Expression {
  private String predicate;
    
  public SemanticPredicate(Position pos, String expression){
    super(pos);
    this.predicate = expression;
  }
  public String predicate() {
    return predicate;
  }

  @Override
  public String toString() {
    return "&{" + predicate + "}";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class SetValueAction extends Expression {
  private Expression body;
  private String code;

  public SetValueAction(Position pos, Expression body, String code) {
    super(pos);
    this.body = body;
    this.code = code;
  }

  public Expression body() {
    return body;
  }

  public String code() {
    return code;
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
    
  @Override
  public String toString() {
    return body + " %{" + code + "}";
  }
} public static class StringLiteral extends Terminal {
  private String value;
  private Symbol var;

  public StringLiteral(Position pos, String value, Symbol var){
    super(pos);
    this.value = value;
    this.var = var;
  }

  public StringLiteral(Position pos, String value){
    this(pos, value, null);
  }

  public String value() {
    return value;
  }

  public Symbol var() {
    return var;
  }

  @Override
  public String toString() {
    return "\"" + value + "\"";
  }

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static class Wildcard extends Terminal {
  private final Symbol var;
    
  public Wildcard(Position pos, Symbol var) {
    super(pos);
    this.var = var;
  }
    
  public Symbol var() {
    return var;
  }
    
  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
    
  @Override
  public String toString() {
    return ".";
  }
} public static class DFA {
  public static final DFA ERROR = new DFA(null, -1, null);
  public final int[][] table;
  public final int start;
  public final Set<Integer> finals;
  public DFA(int[][] table, int start, Set<Integer> finals){
    this.table = table;
    this.start = start;
    this.finals = finals;
  }
    
  public DFA and(DFA rhs) {
    int[][] newTable = new int[table.length * rhs.table.length][NUM_ALPHABETS];
    int newStart = rhs.table.length * start + rhs.start;
    Set<Integer> newFinals = set();
    for(int a : finals) {
      for(int b : rhs.finals) {
        newFinals.add(rhs.table.length * a + b);
      }
    }
    for(int a = 0; a < table.length; a++) {
      for(int b = 0; b < rhs.table.length; b++) {
        for(int input = 0; input < NUM_ALPHABETS; input++) {
          int nextA = table[a][input];
          int nextB = rhs.table[b][input];
          if(nextA == -1 || nextB == -1) {
            newTable[rhs.table.length * a + b][input] = -1;
          }else {
            newTable[rhs.table.length * a + b][input] = rhs.table.length * nextA + nextB;
          }
        }
      }
    }
    return new DFA(newTable, newStart, newFinals);
  }
          
  public boolean disjoint(DFA dfa) {
    return this.and(dfa).isEmpty();
  }
    
  public boolean isEmpty() {
    Set<Integer> reachable = set();
    mark(reachable, start);
    reachable.retainAll(finals);
    return reachable.isEmpty();      
  }
    
  public String toString() {
    int maxDigit = String.valueOf(table.length).length();
    if(maxDigit % 2 == 0) maxDigit++;
    final int ASCII_PRINTABLE_START = 32;
    final int ASCII_PRINTABLE_FINAL = 126;
    StringWriter buff = new StringWriter();
    PrintWriter w = new PrintWriter(buff);
    w.printf("start: %d%n", start);
    w.printf("final: ");
    for(int f:finals) {
      w.printf("%0" + maxDigit + "d ", f);
    }
    w.println();
    spacing(w, maxDigit + 1);
    for(int i = ASCII_PRINTABLE_START; i <= ASCII_PRINTABLE_FINAL; i++) {
      spacing(w, maxDigit / 2);
      w.printf("%c", (char)i);
      spacing(w, maxDigit / 2 + 1);
    }
    w.println();
    for(int i = 0; i < table.length; i++) {
      w.printf("%0" + maxDigit + "d ", i);
      for(int j = ASCII_PRINTABLE_START; j <= ASCII_PRINTABLE_FINAL; j++) {
        if(table[i][j] != -1) {
          w.printf("%0" + maxDigit + "d ", table[i][j]);
        }else {
          spacing(w, maxDigit / 2);
          w.print("X");
          spacing(w, maxDigit / 2 + 1);
        }
      }
      w.println();
    }
    w.flush();
    return new String(buff.getBuffer());
  }
    
  private void mark(Set<Integer> reachable, int stateNum) {
    if(reachable.contains(stateNum)) return;
    reachable.add(stateNum);
    for(int input = 0; input < NUM_ALPHABETS; input++){
      int next = table[stateNum][input];
      if(next != -1) mark(reachable, next);
    }
  }
    
  private static void spacing(PrintWriter w, int n) {
    for(int i = 0; i < n; i++) {
      w.print(" ");
    }
  }
} public class CollectionUtil {
  public static <T> List<T> list(T... elements) {
    return new ArrayList<T>(Arrays.asList(elements));
  }
  
  public static <A, B> Pair<A, B> t(A fst, B snd) {
    return new Pair<A, B>(fst, snd);
  }
  
  public static <K, V> Map<K, V> map(Pair<? extends K, ? extends V>... elements) {
    Map<K, V> map = new HashMap<K, V>();
    for(Pair<? extends K, ? extends V> e:elements) {
      map.put(e.fst(), e.snd());
    }
    return map;
  }
  
  public static <T> Set<T> set(T... elements) {
    return new HashSet<T>(Arrays.asList(elements));
  }
  
  public static <T> Set<T> setFrom(Collection<? extends T> collection) {
    return new HashSet<T>(collection);
  }
}
import java.util.Map;
import java.util.Set;
import com.github.kmizu.yapp.Ast;
import com.github.kmizu.yapp.DirectedGraph;
import com.github.kmizu.yapp.Regex;
import com.github.kmizu.yapp.Regex2DFA;
import com.github.kmizu.yapp.Symbol;
import com.github.kmizu.yapp.Ast.Action;
import com.github.kmizu.yapp.Ast.AndPredicate;
import com.github.kmizu.yapp.Ast.CharClass;
import com.github.kmizu.yapp.Ast.Cut;
import com.github.kmizu.yapp.Ast.Empty;
import com.github.kmizu.yapp.Ast.Expression;
import com.github.kmizu.yapp.Ast.Fail;
import com.github.kmizu.yapp.Ast.Grammar;
import com.github.kmizu.yapp.Ast.N_Alternation;
import com.github.kmizu.yapp.Ast.N_Sequence;
import com.github.kmizu.yapp.Ast.NonTerminal;
import com.github.kmizu.yapp.Ast.NotPredicate;
import com.github.kmizu.yapp.Ast.Optional;
import com.github.kmizu.yapp.Ast.Repetition;
import com.github.kmizu.yapp.Ast.RepetitionPlus;
import com.github.kmizu.yapp.Ast.Rule;
import com.github.kmizu.yapp.Ast.SemanticPredicate;
import com.github.kmizu.yapp.Ast.SetValueAction;
import com.github.kmizu.yapp.Ast.StringLiteral;
import com.github.kmizu.yapp.Ast.Wildcard;
import com.github.kmizu.yapp.Automata.DFA;
import com.github.kmizu.yapp.util.CollectionUtil;
package com.github.kmizu.yapp.translator;



public class PEG2DFATranslator extends Ast.Visitor<Regex.Expression, Void>
  implements Translator<Ast.Expression, DFA> {
  private final DirectedGraph<Symbol, Boolean> refGraph;
  private final Map<Symbol, Expression> mapping;
  
  public PEG2DFATranslator(
    DirectedGraph<Symbol, Boolean> refGraph,
    Map<Symbol, Expression> mapping) {
    this.refGraph = refGraph;
    this.mapping = mapping;
  }

  public DFA translate(Expression from) {
    Regex.Expression result = accept(from, null);
    if(result != Regex.ERROR) {
      result = new Regex.Sequence(
        result,
        new Regex.Repetition(new Regex.All())
      );
    }
    return Regex2DFA.INSTANCE.compile(result);
  }

  @Override
  protected Regex.Expression visit(Action node, Void context) {
    return node.body().accept(this, context);
  }

  @Override
  protected Regex.Expression visit(AndPredicate node, Void context) {
    return Regex.ERROR;
  }

  @Override
  protected Regex.Expression visit(CharClass node, Void context) {
    Set<Character> chars = CollectionUtil.set();
    for(CharClass.Element e:node.elements) {
      if(e instanceof CharClass.Char) {
        chars.add(((CharClass.Char)e).value);
      }else {
        char rangeS = ((CharClass.Range)e).start;
        char rangeE = ((CharClass.Range)e).end;
        for(int i = rangeS; i <= rangeE; i++) {
          chars.add((char)i);
        }
      }
    }
    return new Regex.CharClass(!node.positive, chars);
  }

  @Override
  protected Regex.Expression visit(Cut node, Void context) {
    return Regex.ERROR;
  }

  @Override
  protected Regex.Expression visit(Empty node, Void context) {
    return new Regex.Empty();
  }

  @Override
  protected Regex.Expression visit(Fail node, Void context) {