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 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 enum OptionType {INT, STR, NONE} public class AutoCutInserter extends Visitor<Expression, AutoCutInserter.Context>
  implements Translator<Ast.Grammar, Ast.Grammar> {
  static final class Context {
    PEG2DFATranslator toDfa;
    Map<Symbol, Boolean> succeedRules;
    int countCutInserted;
    Context(PEG2DFATranslator toDfa, Map<Symbol, Boolean> succeedRules) {
      this.toDfa = toDfa;
      this.succeedRules = succeedRules;
    }
  }
  

  public Grammar translate(Grammar grammar) {
    List<Rule> rules = list();
    Map<Symbol, Expression> mapping = CollectionUtil.map();
    for(Rule r:grammar) {
      mapping.put(r.name(), r.body());
    }
    PEG2DFATranslator toDfa = new PEG2DFATranslator(
      RefGraphMaker.INSTANCE.translate(grammar), mapping
    );
    Map<Symbol, Boolean> succeedRules =
      SucceedRuleDetector.INSTANCE.translate(grammar);
    Context context = new Context(toDfa, succeedRules);
    for(Rule r:grammar) {
      rules.add(
        new Rule(
          r.pos(),
          r.flags(),
          r.name(),
          r.type(),
          accept(r.body(), context),
          r.code()
        )
      );
    }
    return new Grammar(grammar.pos(), grammar.name(), grammar.macros(), rules);
  }

  @Override
  protected Expression visit(Action node, Context context) {
    return new Action(node.pos(), accept(node.body(), context), node.code());
  }

  @Override
  protected Expression visit(AndPredicate node, Context context) {
    return new AndPredicate(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(CharClass node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Cut node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Empty node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Fail node, Context context) {
    return node;
  }
  
  @Override
  protected Expression visit(N_Alternation node, Context context) {
    List<Expression> body = node.body();
    List<Expression> result = list();
    // for e_1 / e_2 / e_3 ... / e_n, do following process.
    OUTER:
    for(int i = 0; i < body.size() - 1; i++) {
      // If e_i is not N_Sequence(a_1 a_2 ... a_m), skip following process
      // since i'ts unable to insert cut in e_i.
      Expression e = body.get(i);
      if(!(e instanceof N_Sequence)) {
        result.add(accept(e, context));
        continue OUTER;
      }
      List<Expression> es = ((N_Sequence)e).body();
      for(int j = 1; j < es.size(); j++) {
        if(
           allDisjoint(
             new N_Sequence(e.pos(), es.subList(0, j)), 
             body.subList(i + 1, body.size()),
             context.toDfa
           ) 
        || // if the last element of a sequence is a certainly succeed rule,
           // enable to insert cut before it.
           (j == es.size() - 1 && 
            es.get(j) instanceof NonTerminal &&
            context.succeedRules.get(((NonTerminal)es.get(j)).name())
           ) 
        ){
          //it's enable to insert cut
          List<Expression> esResult = list();
          for(Expression e2:es.subList(0, j)) {
            esResult.add(accept(e2, context));
          }
          esResult.add(new Cut(new Position(-1, -1)));
          for(Expression e2:es.subList(j, es.size())){
            esResult.add(accept(e2, context));
          }
          result.add(new N_Sequence(e.pos(), esResult));
          continue OUTER;
        }
      }
      result.add(accept(e, context));
    }
    result.add(accept(body.get(body.size() - 1), context));
    return new N_Alternation(node.pos(), result);
  }

  @Override
  protected Expression visit(N_Sequence node, Context context) {
    List<Expression> result = list();
    for(Expression e:node) {
      result.add(accept(e, context));
    }
    return new N_Sequence(node.pos(), result);
  }

  @Override
  protected Expression visit(NonTerminal node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(NotPredicate node, Context context) {
    return new NotPredicate(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(Optional node, Context context) {
    return new Optional(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(Repetition node, Context context) {
    return new Repetition(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(RepetitionPlus node, Context context) {
    return new RepetitionPlus(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(SemanticPredicate node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(SetValueAction node, Context context) {
    return new SetValueAction(
      node.pos(), accept(node.body(), context), node.code()
    );
  }

  @Override
  protected Expression visit(StringLiteral node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Wildcard node, Context context) {
    return node;
  }
  
  private boolean allDisjoint(
    Expression a, List<Expression> bs, PEG2DFATranslator toDfa
  ) {
    Automata.DFA dfaA = toDfa.translate(a);
    if(dfaA == Automata.DFA.ERROR) return false;
    for(Expression b:bs) {
      if(b instanceof N_Sequence) {
        List<Expression> seq = ((N_Sequence)b).body();
        int i = seq.size();
        for(; i > 0; i--) {
          Automata.DFA dfaB = toDfa.translate(
            new N_Sequence(b.pos(), seq.subList(0, i))
          );
          if(dfaB == Automata.DFA.ERROR) continue;
          Automata.DFA andDfa = dfaA.and(dfaB);
          if(andDfa.isEmpty()) break;
        }
        if(i == 0) return false;
      }else {
        Automata.DFA dfaB = toDfa.translate(b);
        if(dfaB == Automata.DFA.ERROR) return false;
        if(!dfaA.and(dfaB).isEmpty()) return false;
      }
    }
    return true;
  }
} public class AutoCutInserterUsingFirstSet extends Visitor<Expression, AutoCutInserterUsingFirstSet.Context>
  implements Translator<Ast.Grammar, Ast.Grammar> {  
  static final class Context {
    Map<Symbol, Expression> bindings;
    Set<Expression> nul;
    Set<Expression> fail;
    Set<Expression> finite;
    FirstSetCollector firstSet;
        int countCutInserted;
    public Context(Map<Symbol, Expression> bindings, Set<Expression> nul, Set<Expression> fail, Set<Expression> finite) {
      this.bindings = bindings;
      this.fail = fail;
      this.nul = nul;
      this.finite = finite;
      this.firstSet = new FirstSetCollector(bindings, nul, fail);
    }    
  }
  
  private final int limit;
  
  public AutoCutInserterUsingFirstSet(int limit) {
    this.limit = limit;
  }

  public Grammar translate(Grammar from) {
    List<Rule> rules = list();
    Set<Expression> nul = new NulExpressionCollector().translate(from);
    Set<Expression> fail = new FailExpressionCollector().translate(from);
    Set<Expression> finite = new FiniteLengthExpressionCollector().translate(from);
    Map<Symbol, Expression> mapping = CollectionUtil.map();
    for(Rule r:from) {
      mapping.put(r.name(), r.body());
    }
    Context context = new Context(mapping, nul, fail, finite);
    for(Rule r:from) {
      rules.add(
        new Rule(
          r.pos(),
          r.flags(),
          r.name(),
          r.type(),
          accept(r.body(), context),
          r.code()
        )
      );
    }
    return new Grammar(from.pos(), from.name(), from.macros(), rules);
  }

  @Override
  protected Expression visit(Action node, Context context) {
    return new Action(node.pos(), accept(node.body(), context), node.code());
  }

  @Override
  protected Expression visit(AndPredicate node, Context context) {
    return new AndPredicate(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(CharClass node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Cut node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Empty node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Fail node, Context context) {
    return node;
  }
  
  @Override
  protected Expression visit(N_Alternation node, Context context) {
    List<Expression> body = node.body();
    List<Expression> result = list();
    //Because a FirstSetCollector computes FIRST set using AST node's identity,
    //FIRST set of `e` must not be computed by the result of `e`.accept(...).
    OUTER:
    for(int i = 0; i < body.size() - 1; i++) {
      Expression e1 = body.get(i);
      Set<Expression> f_e1 = context.firstSet.translate(e1);
      Set<Expression> f = CollectionUtil.set();
      for(int j = i + 1; j < body.size(); j++) {
        Expression e2 = body.get(j);
        Set<Expression> f_e2 = context.firstSet.translate(e2);
        if((!ExpressionUtil.disjoint(f_e1, f_e2)) || context.nul.contains(e1) || context.nul.contains(e2)) {
          result.add(accept(e1, context)); continue OUTER;
        }
        f.addAll(f_e2);
      }
      if(context.finite.contains(e1) || (limit >= 0 && f.size() > limit)) {
        result.add(accept(e1, context));
      }else{
        result.add(
          new Ast.N_Sequence(
            node.pos(),
            list(
              new Ast.NotPredicate(node.pos(), ExpressionUtil.newAlternation(node.pos(), ExpressionUtil.compact(f))),
              new Ast.Cut(node.pos()),
              accept(e1, context)
            )
          )
        );
      }
    }
    result.add(accept(body.get(body.size() - 1), context));
    return new N_Alternation(node.pos(), result);
  }
  
  @Override
  protected Expression visit(N_Sequence node, Context context) {    
    List<Expression> result = list();
    for(Expression e:node){
      result.add(e.accept(this, context));
    }
    return new Ast.N_Sequence(node.pos(), result);
  }

  @Override
  protected Expression visit(NonTerminal node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(NotPredicate node, Context context) {
    return new NotPredicate(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(Optional node, Context context) {
    return new Optional(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(Repetition node, Context context) {
    return new Repetition(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(RepetitionPlus node, Context context) {
    return new RepetitionPlus(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(SemanticPredicate node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(SetValueAction node, Context context) {
    return new SetValueAction(
      node.pos(), accept(node.body(), context), node.code()
    );
  }

  @Override
  protected Expression visit(StringLiteral node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Wildcard node, Context context) {
    return node;
  }
  
  /**
   * Check whether e1 is prefix of e2 or not.
   * @param e1
   * @param e2
   */
  static boolean isPrefixOf(Expression e1, Expression e2) {
    if(e1 instanceof StringLiteral) {
      if(e2 instanceof StringLiteral) {
        return ((StringLiteral)e2).value().startsWith(((StringLiteral)e1).value());
      }else if(e2 instanceof CharClass) {
        String e1v = ((StringLiteral)e1).value();
        if(e1v.length() > 1) return false;
        char first = e1v.charAt(0);
        return isEqual(first, (CharClass)e2);
      }else if(e2 instanceof Wildcard) {
        return false;
      }else throw new AssertionError("should not reach here");
    }else if(e1 instanceof CharClass) {
      if(e2 instanceof StringLiteral) {
        return isContained(((StringLiteral)e2).value().charAt(0), (CharClass)e1);
      }else if(e2 instanceof CharClass) {
        CharClass c1 = (CharClass)e1;
        CharClass c2 = (CharClass)e2;
        for(CharClass.Element ce:c2.elements){
          if(ce instanceof CharClass.Range) {
            char start = ((CharClass.Range)ce).start;
            char end = ((CharClass.Range)ce).end;
            for(int i = start; i<= end; i++) {
              if(c2.positive != isContained((char)i, (CharClass)c1)) return false;
            }
          }else {
            if(c2.positive != isContained(((CharClass.Char)ce).value, c1)) return false;
          }
        }
        return true;
      }else if(e2 instanceof Wildcard) {
        return false;
      }else throw new AssertionError("should not reach here");
    }else if(e1 instanceof Wildcard) {
      return true;
    }else throw new AssertionError("should not reach here");
  }
  
  public static boolean isEqual(char codePoint, CharClass c) {
    return c.positive
         && c.elements.size() == 1 
         && c.elements.get(0) instanceof CharClass.Char
         && codePoint == ((CharClass.Char)c.elements.get(0)).value;
  }

  public static boolean isContained(char codePoint, CharClass c) {
    boolean contained = false;
    OUTER:
    for(CharClass.Element ce:c.elements){
      if(ce instanceof CharClass.Range) {
        char start = ((CharClass.Range)ce).start;
        char end = ((CharClass.Range)ce).end;
        for(int i = start; i <= end; i++) {
          if(codePoint == i) {
            contained = true;
            break OUTER;
          }
        }
      }else {
        if(codePoint == ((CharClass.Char)ce).value) {
          contained = true;
          break OUTER;
        }
      }
    }
    return c.positive == contained;
  }
  
  private static Set<String> toStringSet(Set<Expression> es) {
    Set<String> s = CollectionUtil.set();
    for(Expression e:es) {
      if(e instanceof StringLiteral) {
        s.add(((StringLiteral)e).value());
      }else if(e instanceof Wildcard) {
        s.addAll(ALPHABETS);
      }else if(e instanceof CharClass) {
        CharClass c = (CharClass)e;
        for(CharClass.Element ce:c.elements) {
          if(ce instanceof CharClass.Range) {
            char start = ((CharClass.Range)ce).start;
            char end = ((CharClass.Range)ce).end;
          }
        }
      }
    }
    return s;
  }
  
  static final Set<String> ALPHABETS = CollectionUtil.set();
  static { 
    for(int i = 0; i <= Character.MAX_VALUE; i++) {
      ALPHABETS.add(Character.toString((char)i));
    }
  }
} public class AutoCutInserterUsingFollowSet extends Visitor<Expression, AutoCutInserterUsingFollowSet.Context>
  implements Translator<Ast.Grammar, Ast.Grammar> {  
  static final class Context {
    Map<Symbol, Expression> bindings;
    Set<Expression> nul;
    Set<Expression> fail;
    Set<Expression> finite;
    FirstSetCollector firstSet;
    FollowSetCollector followSet;
    EofDetector eofDetector;
    int countCutInserted;
    public Context(Map<Symbol, Expression> bindings, Set<Expression> nul, Set<Expression> fail, Set<Expression> finite) {
      this.bindings = bindings;
      this.fail = fail;
      this.nul = nul;
      this.finite = finite;
      this.firstSet = new FirstSetCollector(bindings, nul, fail, false);
      this.followSet = new FollowSetCollector(bindings, nul, fail);
      this.eofDetector = new EofDetector(bindings);
    }
  }
  
  public AutoCutInserterUsingFollowSet() {
  }

  public Grammar translate(Grammar from) {
    List<Rule> rules = list();
    Set<Expression> nul = new NulExpressionCollector().translate(from);
    Set<Expression> fail = new FailExpressionCollector().translate(from);
    Set<Expression> finite = new FiniteLengthExpressionCollector().translate(from);
    Map<Symbol, Expression> mapping = CollectionUtil.map();
    for(Rule r:from) {
      mapping.put(r.name(), r.body());
    }
    Context context = new Context(mapping, nul, fail, finite);
    for(Rule r:from) {
      rules.add(
        new Rule(
          r.pos(),
          r.flags(),
          r.name(),
          r.type(),
          accept(r.body(), context),
          r.code()
        )
      );
    }
    return new Grammar(from.pos(), from.name(), from.macros(), rules);
  }

  @Override
  protected Expression visit(Action node, Context context) {
    return new Action(node.pos(), accept(node.body(), context), node.code());
  }

  @Override
  protected Expression visit(AndPredicate node, Context context) {
    return new AndPredicate(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(CharClass node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Cut node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Empty node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Fail node, Context context) {
    return node;
  }
  
  @Override
  protected Expression visit(N_Alternation node, Context context) {
    List<Expression> result = list();
    for(Expression e:node.body()) {
      result.add(e.accept(this, context));
    }
    return new Ast.N_Alternation(node.pos(), result);
  }
  
  @Override
  protected Expression visit(N_Sequence node, Context context) {
    List<Expression> result = list();
    for(Expression e:node.body()) {
      result.add(e.accept(this, context));
    }
    return new Ast.N_Sequence(node.pos(), result);
  }

  @Override
  protected Expression visit(NonTerminal node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(NotPredicate node, Context context) {
    return new NotPredicate(node.pos(), accept(node.body(), context));
  }

  @Override
  protected Expression visit(Optional node, Context context) {
    throw new UnsupportedOperationException("This operation is not supported");
  }

  @Override
  protected Expression visit(Repetition node, Context context) {
    List<Expression> follows = new ArrayList<Expression>(context.followSet.translate(node));
    Set<Expression> f_e1 = context.firstSet.translate(node.body());    
    if((!context.finite.contains(node.body())) 
     && follows.size() == 1 
    ) {
      if( (!context.nul.contains(follows.get(0)))
       && (!context.nul.contains(node.body()))
       && ExpressionUtil.disjoint(f_e1, context.firstSet.translate(follows.get(0)))
      ) {
        try {
          Expression predE = 
            ExpressionUtil.newAlternation(
              node.pos(),
              ExpressionUtil.compact(context.firstSet.translate(follows.get(0)))
            );
          return new Ast.Repetition(
            node.pos(),
            new Ast.N_Sequence(
              node.pos(),
              list(
                new Ast.NotPredicate(node.pos(), predE),
                new Ast.Cut(node.pos()),
                node.body().accept(this, context)
              )
            )
          );
        }catch(FirstSetCannotBeComputed ex) {
          return new Repetition(node.pos(), accept(node.body(), context));
        }
      }else if(context.eofDetector.translate(follows.get(0))){
        return new Ast.Repetition(
          node.pos(),
          new Ast.N_Sequence(
            node.pos(),
            list(
              new Ast.NotPredicate(node.pos(), 
                new Ast.NotPredicate(node.pos(),
                  new Ast.Wildcard(node.pos(), null)
                )
              ),
              new Ast.Cut(node.pos()),
              node.body().accept(this, context)
            )
          )
        );
      }else {
        return new Repetition(node.pos(), accept(node.body(), context));
      }
    } else {
      return new Repetition(node.pos(), accept(node.body(), context));
    }
  }

  @Override
  protected Expression visit(RepetitionPlus node, Context context) {
    throw new UnsupportedOperationException("This operation is not supported");
  }

  @Override
  protected Expression visit(SemanticPredicate node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(SetValueAction node, Context context) {
    return new SetValueAction(
      node.pos(), accept(node.body(), context), node.code()
    );
  }

  @Override
  protected Expression visit(StringLiteral node, Context context) {
    return node;
  }

  @Override
  protected Expression visit(Wildcard node, Context context) {
    return node;
  }
  
  private static boolean disjoint(Set<Expression> f1, Set<Expression> f2) {
    for(Expression e1:f1) {
      for(Expression e2:f2) {
        if(isPrefixOf(e1, e2) || isPrefixOf(e2, e1)) return false;
      }
    }
    return true;
  }
  
  private static Expression newAlternation(Position pos, Set<Expression> elements) {
    List<Expression> newElements = CollectionUtil.list();
    newElements.addAll(elements);
    Collections.sort(newElements, new Comparator<Expression>() {
      public int compare(Expression o1, Expression o2) {
        if(o1 instanceof StringLiteral) {
          if(o2 instanceof StringLiteral) {
            int length1 = ((StringLiteral)o1).value().length();
            int length2 = ((StringLiteral)o2).value().length();
            return length1 > length2 ? -1 :
                    length1 < length2 ? 1 :
                    0;
          }else{
            return 1;
          }          
        } else {
          return 0;
        }
      }
    });
    return new Ast.N_Alternation(pos, newElements);
  }
    
  /**
   * Check whether e1 is prefix of e2 or not.
   * @param e1
   * @param e2
   */
  private static boolean isPrefixOf(Expression e1, Expression e2) {
    if(e1 instanceof StringLiteral) {
      if(e2 instanceof StringLiteral) {
        return ((StringLiteral)e2).value().startsWith(((StringLiteral)e1).value());
      }else if(e2 instanceof CharClass) {
        String e1v = ((StringLiteral)e1).value();
        if(e1v.length() > 1) return false;
        char first = e1v.charAt(0);
        return isContained(first, (CharClass)e2);
      }else if(e2 instanceof Wildcard) {
        return true;
      }else throw new AssertionError("should not reach here");
    }else if(e1 instanceof CharClass) {
      if(e2 instanceof StringLiteral) {
        return isContained(((StringLiteral)e2).value().charAt(0), (CharClass)e1);
      }else if(e2 instanceof CharClass) {
        CharClass c1 = (CharClass)e1;
        for(CharClass.Element ce:c1.elements){
          if(ce instanceof CharClass.Range) {
            char start = ((CharClass.Range)ce).start;
            char end = ((CharClass.Range)ce).end;
            for(int i = start; i<= end; i++) {
              if(c1.positive == isContained((char)i, (CharClass)e2)) return true;
            }
          }else {
            if(c1.positive == isContained(((CharClass.Char)ce).value, (CharClass)e1)) return true;
          }
        }
        return false;
      }else if(e2 instanceof Wildcard) {
        return true;
      }else throw new AssertionError("should not reach here");
    }else if(e1 instanceof Wildcard) {
      return true;
    }else throw new AssertionError("should not reach here");
  }

  private static boolean isContained(char codePoint, CharClass c) {
    boolean contained = false;
    OUTER:
    for(CharClass.Element ce:c.elements){
      if(ce instanceof CharClass.Range) {
        char start = ((CharClass.Range)ce).start;
        char end = ((CharClass.Range)ce).end;
        for(int i = start; i <= end; i++) {
          if(codePoint == i) {
            contained = true;
            break OUTER;
          }
        }
      }else {
        if(codePoint == ((CharClass.Char)ce).value) {
          contained = true;
          break OUTER;
        }
      }
    }
    return c.positive == contained;
  }
  
  private static Set<String> toStringSet(Set<Expression> es) {
    Set<String> s = CollectionUtil.set();
    for(Expression e:es) {
      if(e instanceof StringLiteral) {
        s.add(((StringLiteral)e).value());
      }else if(e instanceof Wildcard) {
        s.addAll(ALPHABETS);
      }else if(e instanceof CharClass) {
        CharClass c = (CharClass)e;
        for(CharClass.Element ce:c.elements) {
          if(ce instanceof CharClass.Range) {
            char start = ((CharClass.Range)ce).start;
            char end = ((CharClass.Range)ce).end;
          }
        }
      }
    }
    return s;
  }
  
  static final Set<String> ALPHABETS = CollectionUtil.set();
  static { 
    for(int i = 0; i <= Character.MAX_VALUE; i++) {
      ALPHABETS.add(Character.toString((char)i));
    }
  }
} public class BoundedQualifierCounter extends DepthFirstVisitor<Object> implements Translator<Grammar, Grammar> {
  private int nQualifiedRules;
  private int nQualifiedExpressions;
  public Grammar translate(Grammar from) {
    nQualifiedRules = 0;
    nQualifiedExpressions = 0;
    for(Rule r:from) {
      r.accept(this, null);
    }
    System.err.println("bounded rules = " + nQualifiedRules);
    System.err.println("bounded expressions = " + nQualifiedExpressions);
    return from;
  }
  @Override
  protected Void visit(BoundedExpression node, Object context) {
    nQualifiedExpressions++;
    return null;
  }
  @Override
  protected Void visit(Rule node, Object context) {
    super.visit(node, context);
    if((node.flags() & Rule.BOUNDED) != 0) {
      nQualifiedRules++;
    }
    return null;
  }
} public class CodeGeneratorFromIst 
  extends Visitor<Void, CodeGeneratorFromIst.CodeContext> 
  implements Translator<Ist.ParserUnit, Void> {
  static class CodeContext {
    Symbol type;
  }
  
  private static final int INDENT_SPACE = 2;
  private static final int CHUNK_SIZE   = 10;
  private static final String FUNC_PREFIX     = "parse"     ;
  private static final String MEMO_PREFIX     = "memo"      ;
  private static final String VALUE_NAME      = "value"     ;
  private static final String BASE_NAME       = "baseIndex" ;
  private static final String REGISTER_NAME   = "result"    ;
  private static final String CURSOR_NAME     = "cursor"    ;
  private static final String LOCAL_DEPTH     = "localDepth";
  private static final String DEPTH           = "depth"     ;
  private static final String INDEX_METHOD    = "realIndex" ;
  private static final String IS_ZERO         = "isZero"    ;

  private String dstPackage;
  private File dstDir;
  private PrintWriter out;
  private int indentLevel;
  private boolean joinColumns;

  public CodeGeneratorFromIst(String dstPackage, File dstDir, boolean joinColumns) {
    this.dstPackage = dstPackage;
    this.dstDir = dstDir;
    this.joinColumns = joinColumns;
  }

  
  public Void translate(ParserUnit from) {
    File dstFile = new File(dstDir + FILE_SEPARATOR + from.getName() + ".java");
    try {
      out = new PrintWriter(new FileWriter(dstFile));
      try {
        from.accept(this, new CodeContext());
        out.flush();
        return null;
      }finally{
        out.close();
      }
    }catch(IOException e) {
      throw new CompilationException(e);
    }
  }
    
  @Override
  public Void visit(Accept node, CodeContext context) {
    n("%s = %s;", DEPTH, LOCAL_DEPTH);
    n("return new Result<%s>(%s, %s);", context.type, CURSOR_NAME, VALUE_NAME);
    return null;
  }


  @Override
  public Void visit(ActionStatement node, CodeContext context) {
    n("%s", node.getCode());
    return null;
  }


  @Override
  public Void visit(BackupCursor node, CodeContext context) {
    n("%s = %s;", node.getVar(), CURSOR_NAME);
    return null;
  }


  @Override
  public Void visit(Block node, CodeContext context) {
    Symbol label = node.getLabel();
    if(label != null) {
      n("%s: {", label);
      indent();
      for(Ist.Statement s : node.getStatements()) s.accept(this, context);
      dedent();
      n("}");
    }else{
      for(Ist.Statement s : node.getStatements()){
        if(s == null) {
          System.out.println("s == null!");
        }
        s.accept(this, context);
      }
    }
    return null;
  }


  @Override
  public Void visit(DecrDepth node, CodeContext context) {
    n("%s--;", DEPTH);
    n("tryOptimize(%s);", CURSOR_NAME);
    return null;
  }


  @Override
  public Void visit(EscapeFrom node, CodeContext context) {
    n("if(true) break %s;", node.getLabel());
    return null;
  }


  @Override
  public Void visit(Fail node, CodeContext context) {
    n("if(%s()){", IS_ZERO);
    n("  if(true) return createFailure(%s, \"fail\");", CURSOR_NAME);
    n("}else{");
    n("  %s = %s; if(true) return Result.fail();", DEPTH, LOCAL_DEPTH);
    n("}");
    return null;
  }


  @Override
  public Void visit(Function node, CodeContext context) {
    Symbol name = node.getName();
    Symbol type = node.getType();
    String func = FUNC_PREFIX + "_" + name;
    context.type = type;
    n("");
    n("private Result<%s> %s(int %s) {", type, func, CURSOR_NAME);
    indent();
    n("int %s = %s;", LOCAL_DEPTH, DEPTH);
    n("%s %s = null;", type, VALUE_NAME);
    n("Result<? extends Object> %s = null;", REGISTER_NAME);
    if(node.getCode() != null){
      n("%s", node.getCode());
    }
    node.getStatement().accept(this, context);
    dedent();
    n("}");
    n("");
    return null;
  }


  @Override
  public Void visit(GenerateSuccess node, CodeContext context) {
    n("%s = new Result<%s>(%s, null);", REGISTER_NAME, context.type, CURSOR_NAME);
    return null;
  }
  
  private String escapeQuote(String src) {
    StringBuilder builder = new StringBuilder();
    for(char c: src.toCharArray()) {
      if(c == '\"') builder.append('\\');
      else if(c == '\\') builder.append('\\');
      builder.append(c);
    }
    return new String(builder);
  }
  
  @Override
  public Void visit(GenerateFailure node, CodeContext context) {    
    n("if(%s()){", IS_ZERO);
    n("  %s = createFailure(%s, \"expected: %s\");", REGISTER_NAME, CURSOR_NAME, escapeQuote(node.expected()));
    n("}else{");
    n("  %s = Result.fail();", REGISTER_NAME);
    n("}");
    return null;
  }

  @Override
  public Void visit(IncrDepth node, CodeContext context) {
    n("%s++;", DEPTH);
    return null;
  }


  @Override
  public Void visit(Loop node, CodeContext context) {
    if(node.getLabel() != null){
      n("%s:", node.getLabel());
    }
    n("while(true){");
    indent();
    for(Ist.Statement s : node.getStatements()) s.accept(this, context);
    dedent();
    n("}");
    return null;
  }


  @Override
  public Void visit(MatchAny node, CodeContext context) {
    n("%s = match(%s);", REGISTER_NAME, CURSOR_NAME);
    n("if(%s.isFailure()){", REGISTER_NAME);
    n("  if(%s()){", IS_ZERO);
    n("    %s = createFailure(%s, \"expected: except EOF\");", REGISTER_NAME, CURSOR_NAME);
    n("  }");
    if(node.getLabel() == null){
      n("  %s = %s;", DEPTH, LOCAL_DEPTH);
      n("  if(true) return (Result<%s>)%s;", context.type, REGISTER_NAME);
    }else{
      n("  if(true) break %s;", node.getLabel());
    }
    n("}else{");
    n("  %s = %s.getPos();", CURSOR_NAME, REGISTER_NAME);
    n("}");
    return null;
  }


  @Override
  public Void visit(MatchCharClass node, CodeContext context) {
    if(node.isPositive()){
      n("%s = matchPositive(%s, %s);", REGISTER_NAME, CURSOR_NAME, node.getName());
    }else{
      n("%s = matchNegative(%s, %s);", REGISTER_NAME, CURSOR_NAME, node.getName());
    }
    n("if(%s.isFailure()){", REGISTER_NAME);
    n("  if(%s()){", IS_ZERO);
    n("    %s = createFailure(%s, \"expected: \");", REGISTER_NAME, CURSOR_NAME);
    n("  }");
    if(node.getLabel() == null){
      n("  %s = %s;", DEPTH, LOCAL_DEPTH);
      n("  if(true) return (Result<%s>)%s;", context.type, REGISTER_NAME);
    }else{
      n("  if(true) break %s;", node.getLabel());
    }
    n("}else{");
    n("  %s = %s.getPos();", CURSOR_NAME, REGISTER_NAME);
    n("}");
    return null;
  }


  @Override
  public Void visit(MatchRule node, CodeContext context) {
    n("%s = %s(%s);", REGISTER_NAME, node.getRule(), CURSOR_NAME);
    n("if(%s.isFailure()){", REGISTER_NAME);
    if(node.getLabel() == null){
      n("  %s = %s;", DEPTH, LOCAL_DEPTH);
      n("  if(true) return (Result<%s>)%s;", context.type, REGISTER_NAME);
    }else{
      n("  if(true) break %s;", node.getLabel());
    }
    n("}else{");
    n("  %s = %s.getPos();", CURSOR_NAME, REGISTER_NAME);
    n("}");
    return null;
  }


  @Override
  public Void visit(MatchString node, CodeContext context) {
    n("%s = match(%s, \"%s\");", REGISTER_NAME, CURSOR_NAME, node.getValue());
    n("if(%s.isFailure()){", REGISTER_NAME);
    n("  if(%s()){", IS_ZERO);
    n("    %s = createFailure(%s, \"expected: %s\");", REGISTER_NAME, CURSOR_NAME, node.getValue());
    n("  }");
    if(node.getLabel() == null){
      n("  %s = %s;", DEPTH, LOCAL_DEPTH);
      n("  if(true) return (Result<%s>)%s;", context.type, REGISTER_NAME);
    }else{
      n("  if(true) break %s;", node.getLabel());
    }
    n("}else{");
    n("  %s = %s.getPos();", CURSOR_NAME, REGISTER_NAME);
    n("}");
    return null;
  }


  @Override
  public Void visit(NewCursorVar node, CodeContext context) {
    n("int %s = 0;", node.getName());
    return null;
  }


  @Override
  public Void visit(Nop node, CodeContext context) {
    return null;
  }


  @Override
  public Void visit(ParserUnit node, CodeContext context) {
    Symbol startName = node.getStartName();
    Symbol startType = node.getStartType();
    if(dstPackage != null){
      n("package %s;", dstPackage);
    }
    n("import java.util.*;");
    n("import java.io.*;");
    n("import com.github.kmizu.yapp.runtime.*;");
    n("public class %s extends %s<%s> {", node.getName(), "AbstractPackratParser", startType);
    indent();
    n("private int %s = 0;", DEPTH);
    n("private boolean %s() { return %s == 0; }", IS_ZERO, DEPTH);
    n("private void tryOptimize(int cursor) {");
    n("  if(%s == 0) {", DEPTH);
    n("    %s(cursor);", BASE_NAME);
    n("  }");
    n("}");
    Map<Symbol, Set<Character>> map = node.getNameToCharSet();
    for(Symbol name : map.keySet()){
      n("private static final CharacterSet %s = new TreeCharacterSet();", name);
    }
    int count = 0;
    n("private static void initialize0() {");
    indent();
    for(Map.Entry<Symbol, Set<Character>> e : map.entrySet()){
      for(Character c : e.getValue()){
        n("%s.add('%s');", e.getKey(), escape(Character.toString(c)));
        count++;
        if(count % 1000 == 0){
          dedent();
          n("}");
          n("private static void initialize%d() {", count / 1000);
          indent();
        }
      }
    }
    dedent();
    n("}");
    n("static {");
    indent();
    for(int i = 0; i <= count / 1000; i++){
      n("initialize%d();", i);
    }
    dedent();
    n("}");
    n("");
    n("public %s(String input) {", node.getName());
    n("  super(input);");
    n("}");
    n("");
    n("public %s(Reader input) {", node.getName());
    n("  super(input);");
    n("}");
    n("");
    n("");
    if(joinColumns) {
      int columnIndex = 0;
      int chunkIndex = 0;
      Map<String, Integer> chunkMap = CollectionUtil.map();
      n("private static class ResultColumn {");
      for(Function fn : node.getRules()){
        if(!fn.isMemoized()) continue;
        if(columnIndex == 0) {
          n("  static final class Chunk%d {", chunkIndex);
        }
        chunkMap.put(MEMO_PREFIX + "_" + fn.getName(), chunkIndex);
        n("    Result<%s> %s;", fn.getType(), MEMO_PREFIX + "_" + fn.getName());
        if(columnIndex == CHUNK_SIZE - 1){
          n("  }");          
          columnIndex = 0;
          chunkIndex++;
        }else {
          columnIndex++;
        }
      }
      
      if(columnIndex != 0) {
        n("  }");
      }else{
        chunkIndex--;
      }
      for(int i = 0; i <= chunkIndex; i++){
        n("  Chunk%d chunk%d;", i, i);
      }
      n("}");
      n("private CircularSpreadArray<ResultColumn> columns = new CircularSpreadArray<ResultColumn>();");
      for(Function fn : node.getRules()){
        Symbol name = fn.getName();
        Symbol type = fn.getType();
        String func = FUNC_PREFIX + "_" + name;
        if(fn.isMemoized()){
          String memo = MEMO_PREFIX + "_" + name;
          n("public Result<%s> %s(int cursor) {", type, name);
          n("  ResultColumn column = columns.get(%s(cursor));", INDEX_METHOD);
          n("  if(column == null){");
          n("    column = new ResultColumn();");
          n("    if(cursor >= %s()){", BASE_NAME);
          n("      columns.set(%s(cursor), column);", INDEX_METHOD);
          n("    }");
          n("  }");
          int chunkNumber = chunkMap.get(memo);
          n("  if(column.chunk%d == null){", chunkNumber);
          n("    column.chunk%d = new ResultColumn.Chunk%d();", chunkNumber, chunkNumber);
          n("  }");
          n("  if(column.chunk%d.%s == null){", chunkNumber, memo);
          n("    column.chunk%d.%s = %s(cursor);", chunkNumber, memo, func);
          n("  }");
          n("  return column.chunk%d.%s;", chunkNumber, memo);
          n("}");
        }else{
          n("public Result<%s> %s(int cursor) {", type, name);
          n("  return %s(cursor);", func);
          n("}");
        }
      }
      n("");
      n("@Override");
      n("protected void truncate(int toIndex) {");
      n("  super.truncate(toIndex);");
      n("  columns.truncate(toIndex);");
      n("}");
    }else {
      for(Function fn : node.getRules()){
        n("");
        Symbol name = fn.getName();
        Symbol type = fn.getType();
        String func = FUNC_PREFIX + "_" + name;
        if(fn.isMemoized()){
          String memo = MEMO_PREFIX + "_" + name;
          n("private CircularSpreadArray<Result<%s>> %s = new CircularSpreadArray<Result<%s>>();", type, memo, type);
          n("public Result<%s> %s(int cursor) {", type, name);
          n("  Result<%s> result = %s.get(%s(cursor));", type, memo, INDEX_METHOD);
          n("  if(result == null){");
          n("    result = %s(cursor);", func);
          n("    if(cursor >= %s()){", BASE_NAME);
          n("      %s.set(%s(cursor), result);", memo, INDEX_METHOD);
          n("    }");
          n("  }");
          n("  return result;");
          n("}");
        }else{
          n("public Result<%s> %s(int cursor) {", type, name);
          n("  return %s(cursor);", func);
          n("}");
        }
      }
      n("");
      n("@Override");
      n("protected void truncate(int toIndex) {");
      n("  super.truncate(toIndex);");
      for(Function fn : node){
        if(fn.isMemoized()){
          n("  %s.truncate(toIndex);", MEMO_PREFIX + "_" + fn.getName());
        }
      }
      n("}");
    }
    n("");
    n("public Result<%s> %s() {", startType, FUNC_PREFIX);
    n("  return %s(0);", startName);
    n("}");
    for(Function fn : node){
      fn.accept(this, context);
    }
    dedent();
    n("}");
    return null;
  }


  @Override
  public Void visit(RewindCursor node, CodeContext context) {
    n("%s = %s;", CURSOR_NAME, node.getVar());
    return null;
  }


  @Override
  public Void visit(SetSemanticValue node, CodeContext context) {
    n("%s = %s;", VALUE_NAME, node.getCode());
    return null;
  }

  private void indent() {
    indentLevel++;
  }
  
  private void dedent() {
    indentLevel--;
  }
  
  private void n(String format, Object... args) {
    int spaces = indentLevel * INDENT_SPACE;
    for(int i = 0; i < spaces; i++) out.print(" ");
    out.printf(format, args);
    out.println();
  }
  
  private String escape(String src) {
    StringBuffer buffer = new StringBuffer();
    for(int i = 0; i < src.length(); i++){
      char c = src.charAt(i);
      switch(c){
      case '\r':
        buffer.append("\\r");
        break;
      case '\n':
        buffer.append("\\n");
        break;
      case '\t':
        buffer.append("\\t");
        break;
      case '\b':
        buffer.append("\\b");
        break;
      case '\f':
        buffer.append("\\f");
        break;
      case '\'':
        buffer.append("\\'");
        break;
      case '\\':
        buffer.append("\\\\");
        break;
      default:
        buffer.append(c);
        break;
      }
    }
    return new String(buffer);
  }
} public class ComposableTranslator<F, T> implements Translator<F, T> {
  private final Translator<F, T> impl;
  public ComposableTranslator(Translator<F, T> impl) {
    this.impl = impl;
  }
  public T translate(F from) {
    return impl.translate(from);
  }
  public final <H> ComposableTranslator<F, H> compose(final Translator<T, H> obj) {
    return new ComposableTranslator<F, H>(null) {
      public H translate(F from) {
        return obj.translate(ComposableTranslator.this.translate(from));
      }
    };
  }
  public static <F, T> ComposableTranslator<F, T> wrap(Translator<F, T> translator) {
    return new ComposableTranslator<F, T>(translator);
  }
  public static <F> ComposableTranslator<F, F> empty() {
    return new ComposableTranslator<F, F>(null) {
      public F translate(F from) {
        return from;
      }
    };
  }
} public class CutCounter extends IdentityTranslator<Ast.Grammar> {
  @Override
  public Grammar translate(Grammar from) {
    final int[] count = {0};
    Visitor<Void, Void> counter = new Ast.DepthFirstVisitor<Void>() {
      @Override
      protected Void visit(Cut node, Void context) {
        count[0]++;
        return null;
      }
    };
    from.accept(counter, null);
    System.out.println("count of cut = " + count[0]);
    return from;
  }
} public class DeadRuleEliminator 
  implements Translator<Ast.Grammar, Ast.Grammar> {
  public Grammar translate(Grammar from) {
    DirectedGraph<Symbol, Boolean> graph = RefGraphMaker.INSTANCE.translate(from);
    Set<Symbol> mark = CollectionUtil.set(from.getRules().get(0).name());
    while(true) {
      Set<Symbol> tmp = CollectionUtil.setFrom(mark);
      for(Symbol s1:mark) {
        for(Symbol s2:graph.neighbors(s1)){
          tmp.add(s2);
        }
      }
      if(mark.size() == tmp.size()) break;
      mark = tmp;
    }
    List<Ast.Rule> rules = CollectionUtil.list();
    for(Ast.Rule r:from) {
      if(mark.contains(r.name())) rules.add(r);
    }
    return new Ast.Grammar(
      from.pos(), from.name(), from.macros(), rules
    );
  }
} public class GrammarToIstTranslator extends Ast.Visitor<Ist.Statement, GrammarToIstTranslator.Context> 
  implements Translator<Ast.Grammar, Ist.ParserUnit> {
  private boolean eliminateMemo;
  
  static class Context {
    private Map<Symbol, Boolean> ruleToMemoize;
    private Map<Symbol, Set<Character>> nameToCharSet;
    private Map<Symbol, Symbol> typeMaps;
    private Set<Symbol> ruleNames;
    private Symbol currentRuleName;
    private Stack<Symbol> failures;
    private SymbolGenerator symgen;
    private SymbolGenerator vargen;
    private boolean cutEnabled;

    public Context(Map<Symbol, Boolean> ruleToMemoize) {
      this.ruleToMemoize = ruleToMemoize;
      this.ruleNames = new HashSet<Symbol>();
      this.nameToCharSet = new TreeMap<Symbol, Set<Character>>();
      this.failures = new Stack<Symbol>();
      this.typeMaps  = new HashMap<Symbol, Symbol>();
      this.cutEnabled = false;
    }

    public boolean shouldBeMemoized(Symbol rule) {
      return ruleToMemoize == null ?  true : ruleToMemoize.get(rule);
    }

    public void clearTypeMaps() {
      typeMaps.clear();
    }

    public void putType(Symbol ruleName, Symbol type) {
      typeMaps.put(ruleName, type);
    }

    public Symbol getType(Symbol ruleName) {
      return typeMaps.get(ruleName);
    }

    public Set<Symbol> getRuleNames() {
      return ruleNames;
    }

    public void putCharSet(Symbol name, Set<Character> charSet) {
      nameToCharSet.put(name, charSet);
    }

    public Map<Symbol, Set<Character>> getNameToCharSet() {
      return nameToCharSet;
    }

    public void push(Symbol label) {
      failures.push(label);
    }

    public Symbol pop() {
      return failures.pop();
    }

    public Symbol peek() {
      return failures.peek();
    }

    public boolean isEmpty() {
      return failures.isEmpty();
    }

    public int size() {
      return failures.size();
    }

    public void setCurrentRuleName(Symbol currentRuleName) {
      this.currentRuleName = currentRuleName;
      this.failures = new Stack<Symbol>();
      this.symgen = new SymbolGenerator(currentRuleName.key().toUpperCase());
      this.vargen = new SymbolGenerator("var");
    }

    public Symbol getCurrentRuleName() {
      return currentRuleName;
    }

    public void setCutEnabled(boolean cutEnabled){
      this.cutEnabled = cutEnabled;
    }

    public boolean isCutEnabled() {
      return cutEnabled;
    }

    public Symbol gensym() {
      return symgen.gensym();
    }
    
    public Symbol genvar() {
      return vargen.gensym();
    }
  }
  
  public GrammarToIstTranslator(boolean eliminateMemo) {
    this.eliminateMemo = eliminateMemo;
  }
  
  public Ist.ParserUnit translate(Ast.Grammar node) {
    Context context = new Context(
      eliminateMemo ? new NeedlessMemoDetector().detect(node) : null
    );
    List<Ist.Function> rules = list();
    for(Ast.Rule rule : node){
      Symbol name = rule.name();
      Symbol type = rule.type() == null ? intern("Object") : rule.type();
      context.putType(name, type);
    }
    for(Ast.Rule rule : node){
      rules.add(translate(rule, context));
    }
    Rule start = node.iterator().next();
    Symbol startName = start.name();
    Symbol startType = start.type();
    if(startType == null) startType = intern("Object");
    return new Ist.ParserUnit(
      node.pos(),
      node.name(),
      context.getNameToCharSet(), 
      startName,
      startType,
      rules
    );
  }
  
  public Ist.Function translate(Rule node, Context context) {
    context.setCurrentRuleName(node.name());
    return new Ist.Function(
      node.pos(), node.name(), 
      context.getType(node.name()), 
      node.code(),
      context.shouldBeMemoized(node.name()),
      new Ist.Block(
        node.body().pos(), null,
        node.body().accept(this, context),
        new Ist.Accept(node.body().pos())
      )
    );
  }
  
  @Override
  protected Statement visit(Action node, Context context) {
    return new Ist.Block(
      node.pos(),
      null,
      node.body().accept(this, context),
      new Ist.ActionStatement(node.pos(), node.code())
    );
  }

  @Override
  protected Statement visit(N_Alternation node, Context context) {
    boolean backupCutEnabled = context.isCutEnabled();    
    List<Ist.Statement> stmts = list();
    
    List<Expression> expressions = node.body();
    Symbol success = context.gensym();
    Symbol swap = context.genvar();
    stmts.add(new Ist.NewCursorVar(node.pos(), swap));
    for(int i = 0; i < expressions.size() - 1; i++){
      Expression e = expressions.get(i);
      Symbol failure = context.gensym();
      context.setCutEnabled(true);
      context.push(failure);
      Ist.Statement body = accept(e, context);
      if(context.isCutEnabled()){
        context.pop();
      }
      stmts.add(
        new Ist.Block(
          e.pos(),
          failure,
          new Ist.BackupCursor(e.pos(), swap),
          new Ist.IncrDepth(e.pos()),
          body,
          context.isCutEnabled() ?  new Ist.DecrDepth(e.pos()) :
                                    new Ist.Nop(e.pos()),
          new Ist.EscapeFrom(e.pos(), success)
        )
      );
      stmts.add(new Ist.RewindCursor(e.pos(), swap));
      stmts.add(new Ist.DecrDepth(e.pos()));
    }
    context.setCutEnabled(false);
    stmts.add(accept(expressions.get(expressions.size() - 1), context));

    context.setCutEnabled(backupCutEnabled);
    return new Ist.Block(
      node.pos(), success,
      stmts
    );
  }

  @Override
  protected Statement visit(CharClass node, Context context) {
    boolean positive = node.positive;
    Set<Character> chars = new HashSet<Character>();
    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 c = rangeS; c <= rangeE; c++) chars.add((char)c);
      }
    }
    Symbol name = context.gensym();
    context.putCharSet(name, chars);
    Ist.Var var = new Ist.Var(node.var(), Symbol.intern("Character"));
    if(context.isEmpty()){
      return new Ist.MatchCharClass(node.pos(), name, var, positive, null);
    }else{
      return new Ist.MatchCharClass(node.pos(), name, var, positive, context.peek());
    }
  }

  @Override
  protected Statement visit(Cut node, Context context) {
    if(context.isCutEnabled() && !context.isEmpty()){
      context.pop();
      context.setCutEnabled(false);
      return new Ist.DecrDepth(node.pos());
    }
    return new Ist.Nop(node.pos());
  }

  @Override
  protected Statement visit(Empty node, Context context) {
    return new Ist.GenerateSuccess(node.pos());
  }

  @Override
  protected Statement visit(Fail node, Context context) {
    return context.isEmpty() ? new Ist.Fail(node.pos()) :
                                new Ist.EscapeFrom(node.pos(), context.peek());
  }

  @Override
  protected Statement visit(NonTerminal node, Context context) {
    Ist.Var var = null;
    if(node.var() != null) {
      var = new Ist.Var(node.var(), context.getType(node.var()));
    }
    return new Ist.MatchRule(
      node.pos(), var, node.name(), context.isEmpty() ? null : context.peek()
    );
  }

  @Override
  protected Statement visit(Repetition node, Context context) {
    boolean backupCutEnabled = context.isCutEnabled();
    Symbol failure = context.gensym();
    context.setCutEnabled(true);
    context.push(failure);
    Ist.Statement body = node.body().accept(this, context);
    if(context.isCutEnabled()){
      context.pop();
    }
    Symbol swap = context.genvar();
    Ist.Block block = new Ist.Block(
      node.pos(), null,
      new Ist.NewCursorVar(node.pos(), swap),
      new Ist.Loop(
        node.body().pos(), failure,
        new Ist.BackupCursor(node.body().pos(), swap),
        new Ist.IncrDepth(node.body().pos()),
        body,
        context.isCutEnabled() ? new Ist.DecrDepth(node.body().pos()) :
                                 new Ist.Nop(node.body().pos())
      ),
      new Ist.RewindCursor(node.body().pos(), swap),
      new Ist.DecrDepth(node.body().pos()),
      new Ist.GenerateSuccess(node.body().pos())
    );
    context.setCutEnabled(backupCutEnabled);
    return block;
  }
  
  /**
   *   !X
   *    |
   *    v
   * LABEL: {
   *   [compile(X);]
   *   fail
   * }
   * success
   */
  @Override
  protected Statement visit(NotPredicate node, Context context) {
    boolean backupCutEnabled = context.isCutEnabled();
    Symbol failure = context.gensym();
    Symbol swap = context.genvar();
    context.setCutEnabled(false);
    context.push(failure);
    Ist.Statement body = node.body().accept(this, context);
    context.pop();
    Ist.Block block = new Ist.Block(
      node.pos(), null,
      new Ist.NewCursorVar(node.pos(), swap),
      new Ist.BackupCursor(node.pos(), swap),
      new Ist.IncrDepth(node.pos()),
      new Ist.Block(
        node.pos(), failure,
        body,
        new Ist.RewindCursor(node.pos(), swap),
        new Ist.DecrDepth(node.pos()),
        context.isEmpty() ? 
          new Ist.Fail(node.pos()) :
          new Ist.Block(
            node.pos(), null,
            new Ist.GenerateFailure(node.pos(), "not " + node.body().toString()),
            new Ist.EscapeFrom(node.pos(), context.peek())
          )
      ),
      new Ist.RewindCursor(node.pos(), swap),
      new Ist.DecrDepth(node.pos()),
      new Ist.GenerateSuccess(node.pos())
    );
    context.setCutEnabled(backupCutEnabled);
    return block;
  }
  
  @Override
  protected Statement visit(AndPredicate node, Context context) {
    throw new UnsupportedOperationException();
  }

  @Override
  protected Statement visit(N_Sequence node, Context context) {
    List<Statement> stmts = list();
    for(Expression e : node.body()){
      stmts.add(e.accept(this, context));
    }
    return new Ist.Block(node.pos(), null, stmts.toArray(new Statement[0]));
  }

  @Override
  protected Statement visit(SetValueAction node, Context context) {
    return new Ist.Block(
      node.pos(),
      null,
      node.body().accept(this, context),
      new Ist.SetSemanticValue(node.pos(), node.code())
    );  
  }

  @Override
  protected Statement visit(StringLiteral node, Context context) {
    return new Ist.MatchString(
      node.pos(), 
      new Ist.Var(node.var(), Symbol.intern("String")), 
      node.value(),
      context.isEmpty() ? null : context.peek()
    );
  }

  @Override
  protected Statement visit(Wildcard node, Context context) {
    return new Ist.MatchAny(
      node.pos(), 
      new Ist.Var(node.var(), Symbol.intern("String")), 
      context.isEmpty() ? null : context.peek()
    );
  }  
} public class IdentityTranslator<T> implements Translator<T, T> {
  public T translate(T from) {
    return from;
  }
} public class MacroExpander extends 
  AbstractGrammarExpander<MacroExpander.MacroEnvironment> implements Translator<Ast.Grammar, Ast.Grammar> {
  private final Map<Symbol, MacroDefinition> macroBindings = new HashMap<Symbol, MacroDefinition>();
  public static class MacroEnvironment {
    public final Map<Symbol, Expression> bindings = new HashMap<Symbol, Expression>();
  }
  @Override
  public Grammar translate(Grammar from) {
    return expand(from);
  }
  @Override
  public Grammar expand(Grammar node, MacroEnvironment env) {
    for(MacroDefinition macro:node.macros()){
      macroBindings.put(macro.name(), macro);
    }
    return super.expand(node, env);
  }
  @Override
  public MacroEnvironment newContext() {
    return new MacroEnvironment();
  }
  @Override
  protected Expression visit(MacroCall node, MacroEnvironment env) {
    MacroDefinition target = macroBindings.get(node.name());
    MacroEnvironment newEnv = new MacroEnvironment();
    List<Symbol> formalParams = target.formalParams();
    for(int i = 0; i < formalParams.size(); i++){
      newEnv.bindings.put(formalParams.get(i), node.params().get(i));
    }
    return target.body().accept(this, newEnv);
  }
  @Override
  protected Expression visit(MacroVariable node, MacroEnvironment env) {
    return env.bindings.get(node.name()).accept(this, env);
  }  
} public class MacroExpanderEx extends MacroExpander {
  @Override
  protected Expression visit(BoundedExpression node, MacroEnvironment env) {
    return new BoundedExpression(node.body().accept(this, env));
  }
} public class MemoizedCountPrinter implements
  Translator<Pair<Ast.Grammar, Map<Symbol, Boolean>>, Void> {
  public Void translate(Pair<Ast.Grammar, Map<Symbol, Boolean>> from) {
    Ast.Grammar g = from.fst();
    Map<Symbol, Boolean> map = from.snd();
    int countMemoized = 0;
    for(Boolean v : map.values()) if(v) countMemoized++;
    System.out.printf("%d --> %d%n", g.getRules().size(), countMemoized);
    return null;
  }
} public class NeedlessMemoDetector extends Ast.Visitor<Void, NeedlessMemoDetector.Context> 
  implements Translator<Grammar, Pair<Grammar, Map<Symbol, Boolean>>> {
  static class Context {
    Stack<Boolean> cutUsable;
    Stack<Boolean> backtrack;
    Map<Symbol, Boolean> ruleToContext;
    Map<Symbol, List<Symbol>> referenceGraph;
    Symbol currentRule;
    
    Context() {
      cutUsable = new Stack<Boolean>();
      backtrack = new Stack<Boolean>();
      ruleToContext = new HashMap<Symbol, Boolean>();
      referenceGraph = new HashMap<Symbol, List<Symbol>>();
    }
        
    void setCurrentRule(Symbol currentRule) {
      this.currentRule = currentRule;
    }
    
    Symbol getCurrentRule() {
      return currentRule;
    }
    
    void addRule(Symbol rule) {
      ruleToContext.put(rule, false);
      referenceGraph.put(rule, new ArrayList<Symbol>());
    }
    
    void setRuleContext(Symbol rule, boolean context) {
      ruleToContext.put(rule, context);
    }
    
    boolean getRuleContext(Symbol rule) {
      return ruleToContext.get(rule);
    }
    
    public void addReferer(Symbol referenced, Symbol referer) {
      List<Symbol> referers = referenceGraph.get(referenced);
      referers.add(referer);
    }
    
    public List<Symbol> getReferers(Symbol referenced) {
      return referenceGraph.get(referenced);
    }
    
    public Map<Symbol, Boolean> getContexts() {
      return ruleToContext;
    }
  }
  
  public NeedlessMemoDetector() {
  }
  
  public Pair<Grammar, Map<Symbol, Boolean>> translate(Grammar from) {
    return Pair.make(from, detect(from));
  }

  public Map<Symbol, Boolean> detect(Grammar grammar) {
    Context context = new Context();
    grammar.accept(this, context);
    return context.getContexts();
  }

  @Override
  public Void visit(Action node, Context context) {
    node.body().accept(this, context);
    return null;
  }
  
  @Override
  public Void visit(SetValueAction node, Context context) {
    node.body().accept(this, context);
    return null;
  }

  @Override
  public Void visit(N_Alternation node, Context context) {

    List<Expression> expressions = node.body();

    for(int i = 0; i < expressions.size() - 1; i++){
      context.backtrack.push(true);
      context.cutUsable.push(true);
      int size = context.backtrack.size();
      {
        expressions.get(i).accept(this, context);
      }
      if(context.backtrack.size() == size){
        context.backtrack.pop();
        context.cutUsable.pop();
      }
    }

    expressions.get(expressions.size() - 1).accept(this, context);

    return null;
  }

  @Override
  public Void visit(Cut node, Context context) {
    if(context.cutUsable.peek()){
      context.backtrack.pop();
      context.cutUsable.pop();
    }
    return null;
  }

  @Override
  public Void visit(Fail node, Context context) {
    return null;
  }

  @Override
  public Void visit(AndPredicate node, Context context) {
    context.backtrack.push(true);
    context.cutUsable.push(false);
    node.body().accept(this, context);
    context.backtrack.pop();
    context.cutUsable.pop();
    return null;
  }

  @Override
  public Void visit(NotPredicate node, Context context) {
    context.backtrack.push(true);
    context.cutUsable.push(false);
    node.body().accept(this, context);
    context.backtrack.pop();
    context.cutUsable.pop();
    return null;
  }

  @Override
  public Void visit(Empty node, Context context) {
    return null;
  }

  @Override
  public Void visit(Grammar node, Context context) {
    for(Rule rule : node){
      context.addRule(rule.name());
    }
    for(Rule rule : node){
      rule.accept(this, context);
    }
    boolean changed = true;
    while(changed) {
      changed = false;
      OUTER:
      for(Rule rule : node) {
        boolean rc = context.getRuleContext(rule.name());
        if(rc) continue;
        for(Symbol referer : context.getReferers(rule.name())){
          if(context.getRuleContext(referer)){
            context.setRuleContext(rule.name(), true);
            changed = true;
            continue OUTER;
          }
        }
      }
    }
    return null;
  }

  @Override
  public Void visit(NonTerminal node, Context context) {
    Symbol name = node.name();
    List<Symbol> referers = context.getReferers(name);
    if(referers.indexOf(context.getCurrentRule()) == -1) {
      referers.add(context.getCurrentRule());
    }
    if(context.backtrack.peek()){
      context.setRuleContext(name, true);
    }
    return null;
  }

  @Override
  public Void visit(Repetition node, Context context) {
    context.backtrack.push(true);
    context.cutUsable.push(true);
    int size = context.backtrack.size();
    {
      node.body().accept(this, context);
    }
    if(context.backtrack.size() == size){
      context.backtrack.pop();
      context.cutUsable.pop();
    }

    return null;
  }

  @Override
  public Void visit(RepetitionPlus node, Context context) {
    throw new UnsupportedOperationException("visit(RepetitionPlus node, Context context)");
  }

  @Override
  public Void visit(Optional node, Context context) {
    throw new UnsupportedOperationException("visit(Optional node, Context context)");
  }

  @Override
  public Void visit(Rule node, Context context) {
    context.setCurrentRule(node.name());
    context.backtrack.push(false);
    context.cutUsable.push(false);
    node.body().accept(this, context);
    context.backtrack.pop();
    context.cutUsable.pop();
    return null;
  }

  @Override
  public Void visit(N_Sequence node, Context context) {
    List<Expression> expressions = node.body();
    for(Expression expression : expressions.subList(0, expressions.size() - 1)){
      expression.accept(this,  context);
    }
    expressions.get(expressions.size() - 1).accept(this, context);
    return null;
  }

  @Override
  public Void visit(StringLiteral node, Context context) {
    return null;
  }

  @Override
  public Void visit(CharClass node, Context context) {
    return null;
  }

  private static <T> List<T> list(T... args) {
    return new ArrayList<T>(Arrays.asList(args));
  }
} public class Parser implements Translator<File, Ast.Grammar> {
  private String prefix;
  public Parser(String prefix) {
    this.prefix = prefix;
  }
  public Ast.Grammar translate(File input) {
    try {
      FileReader in = new FileReader(input);
      try {
        YappParser parser = new YappParser(in);
        Ast.Grammar grammar = parser.parse();
        if(grammar.name() == null) {
          String fileName = input.getName();
          grammar.setName(
            Symbol.intern(prefix + fileName.substring(0, fileName.lastIndexOf('.')))
          );
        }
        return grammar;
      }finally{
        in.close();
      }
    }catch(FileNotFoundException e) {
      throw new CompilationException(e);
    }catch(IOException e){
      throw new CompilationException(e);
    }catch(ParseException e) {
      throw new CompilationException(e);
    }
  }

} public class RuleCounter extends IdentityTranslator<Ast.Grammar> {
  @Override
  public Grammar translate(Grammar from) {
    int count = 0;
    for(Rule r:from) {
      count++;
    }
    System.out.println("count of rules = " + count);
    return from;
  }
} public class RuleInliner extends AbstractGrammarExpander<RuleInliner.Context> {
  static class Context {
    LinkedHashMap<Symbol, Rule> env;
    int     depth;
    boolean changed;
  }
  
  private final int inlineLimit;
  
  public RuleInliner(int inlineLimit) {
    this.inlineLimit = inlineLimit;
  }  
  
  @Override
  public Context newContext() {
    return new Context();
  }
  
  @Override
  public Grammar expand(Grammar node, Context context) {
    context.env = new LinkedHashMap<Symbol, Rule>();
    for(Rule rule : node) {
      context.env.put(rule.name(), rule);
    }
    for(Rule rule : node) {
      context.env.put(rule.name(), expand(rule, context));
    }
    return new Grammar(node.pos(), node.name(), node.macros(), new ArrayList<Rule>(context.env.values()));
  }
  
  @Override
  public Rule expand(Rule node, Context context) {
    Expression e = node.body();
    context.depth = 0;
    context.changed = true;
    while(context.changed && context.depth < inlineLimit){
      context.changed = false;
      e = e.accept(this, context);
    }
    return new Rule(node.pos(), node.flags(), node.name(), node.type(), e, node.code());
  }
  
  @Override
  protected Expression visit(NonTerminal node, Context context) {
    context.changed = true;
    context.depth++;
    return context.env.get(node.name()).body();
  }
} public class SpaceComplexityChecker extends Visitor<Boolean, Set<Symbol>> 
  implements Translator<Grammar, List<UnboundedContext>> {
  private class BoundedExpressionCollector extends Visitor<Boolean, Set<Symbol>> {
    private Set<Expression> boundedExpressions;
    
    public Set<Expression> collect() {
      boundedExpressions = new HashSet<Expression>();
      for(Symbol name:bindings.keySet()){
        if(boundedRules.contains(name)) {
          boundedExpressions.add(bindings.get(name));
        }
      }
      int oldSize;
      do {
        oldSize = boundedExpressions.size();
        for(Symbol name:bindings.keySet()) {
          bindings.get(name).accept(this, null);
        }
      }while(oldSize != boundedExpressions.size());
      return boundedExpressions;
    }

    @Override
    protected Boolean visit(Action node, Set<Symbol> context) {
      if(node.body().accept(this, context)) {
        boundedExpressions.add(node);
        return true;
      }
      return false;
    }

    @Override
    protected Boolean visit(AndPredicate node, Set<Symbol> context) {
      if(node.body().accept(this, context)) {
        boundedExpressions.add(node);
        return true;
      }
      return false;
    }

    @Override
    protected Boolean visit(CharClass node, Set<Symbol> context) {
      boundedExpressions.add(node);
      return true;
    }

    @Override
    protected Boolean visit(Cut node, Set<Symbol> context) {
      boundedExpressions.add(node);
      return true;
    }

    @Override
    protected Boolean visit(Empty node, Set<Symbol> context) {
      boundedExpressions.add(node);
      return true;
    }

    @Override
    protected Boolean visit(Fail node, Set<Symbol> context) {
      boundedExpressions.add(node);
      return true;
    }

    @Override
    protected Boolean visit(N_Alternation node, Set<Symbol> context) {
      boolean hasUnbounded = false;
      for(Expression e:node) {
        if(!e.accept(this, context)) hasUnbounded = true;
      }
      if(hasUnbounded) {
        return false;
      }else {
        boundedExpressions.add(node);
        return true;
      }
    }

    @Override
    protected Boolean visit(N_Sequence node, Set<Symbol> context) {
      boolean hasUnbounded = false;
      for(Expression e:node) {
        if(!e.accept(this, context)) hasUnbounded = true;
      }
      if(hasUnbounded) {
        return false;
      }else {
        boundedExpressions.add(node);
        return true;
      }
    }
    
    @Override
    protected Boolean visit(BoundedExpression node, Set<Symbol> context) {
      node.body().accept(this, context);
      boundedExpressions.add(node);
      return true;
    }

    @Override
    protected Boolean visit(NonTerminal node, Set<Symbol> context) {
      if(boundedRules.contains(node.name())) {
        boundedExpressions.add(node);
        return true;
      }
      Expression body = bindings.get(node.name());
      if(boundedExpressions.contains(body)) {
        boundedExpressions.add(node);
        return true;
      }
      return false;
    }

    @Override
    protected Boolean visit(NotPredicate node, Set<Symbol> context) {
      if(node.body().accept(this, context)) {
        boundedExpressions.add(node);
        return true;
      }
      return false;
    }

    @Override
    protected Boolean visit(Optional node, Set<Symbol> context) {
      if(node.body().accept(this, context)) {
        boundedExpressions.add(node);
        return true;
      }
      return false;
    }

    @Override
    protected Boolean visit(Repetition node, Set<Symbol> context) {
      node.body().accept(this, context);
      return false;
    }

    @Override
    protected Boolean visit(RepetitionPlus node, Set<Symbol> context) {
      node.body().accept(this, context);
      return false;
    }

    @Override
    protected Boolean visit(SemanticPredicate node, Set<Symbol> context) {
      boundedExpressions.add(node);
      return true;
    }

    @Override
    protected Boolean visit(SetValueAction node, Set<Symbol> context) {
      if(node.body().accept(this, context)) {
        boundedExpressions.add(node);
        return true;
      }
      return false;
    }

    @Override
    protected Boolean visit(StringLiteral node, Set<Symbol> context) {
      boundedExpressions.add(node);
      return true;
    }

    @Override
    protected Boolean visit(Wildcard node, Set<Symbol> context) {
      boundedExpressions.add(node);
      return true;
    }
    
  }
  private Map<Symbol, Expression> bindings;
  private Set<Symbol> boundedRules;
  private Set<Expression> boundedExpressions;
  private List<UnboundedContext> unboundedExpressions;
  private Symbol current;
  
  private boolean passed;
  public SpaceComplexityChecker() {
  }
  public List<UnboundedContext> translate(Grammar grammar) {
    passed = true;
    bindings = new HashMap<Symbol, Expression>();
    boundedRules = new HashSet<Symbol>();    
    unboundedExpressions = new ArrayList<UnboundedContext>();
    for(Rule r:grammar) {
      bindings.put(r.name(), r.body());
      if((r.flags() & Rule.BOUNDED) != 0){
        boundedRules.add(r.name());
      }
    }
    boundedExpressions = new BoundedExpressionCollector().collect();
    Rule start = grammar.getRules().get(0);
    current = start.name();
    boolean sbounded = start.body().accept(this, Sets.add(new HashSet<Symbol>(), start.name()));
    if(!sbounded) {
      return unboundedExpressions;
    }else{
      unboundedExpressions = new ArrayList<UnboundedContext>();
      return unboundedExpressions;
    }
  }
  @Override
  protected Boolean visit(Action node, Set<Symbol> context) {
    if(passed) {
      return node.body().accept(this, context);
    }else {
      boolean bounded = boundedExpressions.contains(node);
      if(!bounded) {
        unboundedExpressions.add(new UnboundedContext(current, node.body()));
      }
      return bounded;
    }
  }
  @Override
  protected Boolean visit(AndPredicate node, Set<Symbol> context) {
    boolean bounded = boundedExpressions.contains(node.body());
    if(!bounded) {
      unboundedExpressions.add(new UnboundedContext(current, node.body()));
    }
    return bounded;
  }
  @Override
  protected Boolean visit(CharClass node, Set<Symbol> context) {
    return true;
  }
  @Override
  protected Boolean visit(Cut node, Set<Symbol> context) {
    if(passed) throw new RuntimeException("illegal usage of cut operator");
    passed = true;
    return true;
  }
  @Override
  protected Boolean visit(Empty node, Set<Symbol> context) {
    return true;
  }
  @Override
  protected Boolean visit(Fail node, Set<Symbol> context) {
    return true;
  }
  @Override
  protected Boolean visit(N_Alternation node, Set<Symbol> context) {
    boolean old = passed;
    for(Expression e:node.body().subList(0, node.body().size() - 1)){
      passed = false;
      if(!e.accept(this, context)) return false;
    }
    passed = old;
    boolean sbounded =  node.body().get(node.body().size() - 1).accept(this, context);
    if(passed) {
      return sbounded;
    }else {
      boolean bounded = boundedExpressions.contains(node);
      if(!bounded){
        unboundedExpressions.add(new UnboundedContext(current, node));
      }
      return bounded;      
    }
  }
  @Override
  protected Boolean visit(N_Sequence node, Set<Symbol> context) {
    for(Expression e:node) {
      if(!e.accept(this, context)) return false;
    }
    if(passed){
      return true;
    }else {
      boolean bounded = boundedExpressions.contains(node);
      if(!bounded){
        unboundedExpressions.add(new UnboundedContext(current, node));
      }
      return bounded;
    }
  }
  @Override
  protected Boolean visit(NonTerminal node, Set<Symbol> context) {
    if(boundedRules.contains(node.name())) return true;
    if(passed) {
      boolean old = passed;
      Symbol oldCurrent = current;
      passed = true;
      current = node.name();
      boolean sbounded = context.contains(node.name()) ? true : bindings.get(node.name()).accept(this, Sets.add(context, node.name()));
      passed = old;
      current = oldCurrent;
      return sbounded;
    }else {
      boolean bounded = boundedExpressions.contains(node);
      if(!bounded){
        unboundedExpressions.add(new UnboundedContext(current, node));
      }
      return bounded;
    }
  }
  @Override
  protected Boolean visit(NotPredicate node, Set<Symbol> context) {
    boolean bounded = boundedExpressions.contains(node.body());
    if(!bounded) {
      unboundedExpressions.add(new UnboundedContext(current, node.body()));
    }
    return bounded;
  }
  @Override
  protected Boolean visit(Optional node, Set<Symbol> context) {
    if(passed) {
      boolean old = passed;
      passed = false;
      boolean sbounded = node.body().accept(this, context);
      passed = old;
      return sbounded;
    }else {
      boolean bounded = boundedExpressions.contains(node.body());
      if(!bounded) {
        unboundedExpressions.add(new UnboundedContext(current, node.body()));
      }
      return bounded;
    }
  }
  @Override
  protected Boolean visit(Repetition node, Set<Symbol> context) {
    if(passed) {
      boolean old = passed;
      passed = false;
      boolean sbounded = node.body().accept(this, context);
      passed = old;
      return sbounded;
    }else {
      boolean bounded = boundedExpressions.contains(node.body());
      if(!bounded) {
        unboundedExpressions.add(new UnboundedContext(current, node.body()));
      }
      return bounded;
    }
  }
  @Override
  protected Boolean visit(RepetitionPlus node, Set<Symbol> context) {
    if(passed) {
      boolean old = passed;
      passed = false;
      boolean sbounded = node.body().accept(this, context);
      passed = old;
      return sbounded;
    }else {
      boolean bounded = boundedExpressions.contains(node.body());
      if(!bounded) {
        unboundedExpressions.add(new UnboundedContext(current, node.body()));
      }
      return bounded;
    }
  }
  @Override
  protected Boolean visit(SemanticPredicate node, Set<Symbol> context) {
    return true;
  }
  @Override
  protected Boolean visit(SetValueAction node, Set<Symbol> context) {
    if(passed) {
      return node.body().accept(this, context);
    }else {
      boolean bounded = boundedExpressions.contains(node.body());
      if(!bounded) {
        unboundedExpressions.add(new UnboundedContext(current, node.body()));
      }
      return bounded;
    }
  }
  @Override
  protected Boolean visit(StringLiteral node, Set<Symbol> context) {
    return true;
  }
  @Override
  protected Boolean visit(Wildcard node, Set<Symbol> context) {
    return true;
  }
  @Override
  protected Boolean visit(BoundedExpression node, Set<Symbol> context) {
    return true;
  }
} public class SyntaxSugarExpander extends AbstractGrammarExpander<Void> {  
  @Override
  protected Expression visit(AndPredicate node, Void context) {
    return new NotPredicate(
      node.pos(),
      new NotPredicate(
        node.pos(),
        node.body().accept(this, context)
      )
    ).accept(this, context);
  }

  @Override
  protected Expression visit(Optional node, Void context) {
    return new N_Alternation(
      node.pos(), list(
        node.body().accept(this, context),
        new Empty(node.pos())
      )
    );
  }

  @Override
  protected Expression visit(RepetitionPlus node, Void context) {
    Expression expanded = node.body().accept(this, context);
    return new N_Sequence(
      node.pos(), list(
        expanded,
        new Repetition(node.pos(), expanded)
      )
    );
  }

  private static <T> List<T> list(T... args) {
    return new ArrayList<T>(Arrays.asList(args));
  }
} public interface Translator<F, T> {
  T translate(F from);
} public class UnboundedContext {
  public final Symbol parent;
  public final Expression unboundedExpression;
  public UnboundedContext(Symbol parent, Expression unboundedExpression) {
    super();
    this.parent = parent;
    this.unboundedExpression = unboundedExpression;
  }
} public class VoidTranslator<T> implements Translator<T, Void> {
  public Void translate(T from) {
    return null;
  }
} public class SystemProperties {
  public static final String LINE_SEPARATOR = System.getProperty("line.separator");
  public static final String PATH_SEPARATOR = File.pathSeparator;
  public static final String FILE_SEPARATOR = File.separator;
}
import java.io.File;
import java.io.IOException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import com.github.kmizu.yapp.Ast;
import com.github.kmizu.yapp.SemanticException;
import com.github.kmizu.yapp.CompilationException;
import com.github.kmizu.yapp.Pair;
import com.github.kmizu.yapp.Symbol;
import com.github.kmizu.yapp.Ast.Grammar;
import com.github.kmizu.yapp.parser.ParseException;
import com.github.kmizu.yapp.parser.Token;
import com.github.kmizu.yapp.tools.CommandLineParser.OptionType;
import com.github.kmizu.yapp.translator.AutoCutInserter;
import com.github.kmizu.yapp.translator.AutoCutInserterUsingFirstSet;
import com.github.kmizu.yapp.translator.AutoCutInserterUsingFollowSet;
import com.github.kmizu.yapp.translator.BoundedQualifierCounter;
import com.github.kmizu.yapp.translator.CodeGeneratorFromIst;
import com.github.kmizu.yapp.translator.ComposableTranslator;
import com.github.kmizu.yapp.translator.CutCounter;
import com.github.kmizu.yapp.translator.DeadRuleEliminator;
import com.github.kmizu.yapp.translator.GrammarToIstTranslator;
import com.github.kmizu.yapp.translator.IdentityTranslator;
import com.github.kmizu.yapp.translator.MacroExpander;
import com.github.kmizu.yapp.translator.MacroExpanderEx;
import com.github.kmizu.yapp.translator.MemoizedCountPrinter;
import com.github.kmizu.yapp.translator.NeedlessMemoDetector;
import com.github.kmizu.yapp.translator.Parser;
import com.github.kmizu.yapp.translator.RuleCounter;
import com.github.kmizu.yapp.translator.RuleInliner;
import com.github.kmizu.yapp.translator.SpaceComplexityChecker;
import com.github.kmizu.yapp.translator.SyntaxSugarExpander;
import com.github.kmizu.yapp.translator.Translator;
import com.github.kmizu.yapp.translator.UnboundedContext;
import com.github.kmizu.yapp.translator.VoidTranslator;
import static com.github.kmizu.yapp.util.SystemProperties.*;
package com.github.kmizu.yapp.tools;






public class YappMain {
  private final String USAGE;
  
  private File srcFile;
  private File dstDir;
  
  CommandLineParser parser = new CommandLineParser();
  
  public YappMain(String... args) throws CommandLineException {    
    parser.opt("pre",      "--pre",      OptionType.STR,  "--pre        specify parser class' prefix")
          .opt("time",     "--time",     OptionType.NONE, "--time       measure time elapsed")
          .opt("package",  "--package",  OptionType.STR,  "--package    specify parser class' package")
          .opt("pm",       "--pm",       OptionType.NONE, "--pm         print the number of rules that should be memoized")
          .opt("edr",      "--edr",      OptionType.NONE, "--edr        eliminate dead rules")
          .opt("em",       "--em",       OptionType.NONE, "--em        eliminate needless memoizations")
          .opt("reg",      "--reg",      OptionType.NONE, "--reg        insert cut automatically by regex like method")
          .opt("Onj",      "--Onj",      OptionType.NONE, "--Onj        turn off 'join column optimization'")
          .opt("ac",       "--ac",       OptionType.NONE, "--ac         turn on 'auto cut insertion' optimization")
          .opt("inl",      "--inl",      OptionType.INT,  "--inl        inline nonterminal expression")
          .opt("ACfirst",  "--ACfirst",  OptionType.INT,  "--ACfirst    auto cut insertion by first set method")
          .opt("ACfollow", "--ACfollow", OptionType.NONE, "--ACfollow   auto cut insertion by follow set method")
          .opt("space",    "--space",    OptionType.NONE,  "--space      calculate space complexity of specified rule");
    StringBuilder usage = new StringBuilder();
    usage.append("Usage: java com.github.kmizu.yapp.tools.YappMain [options ...] <file name> [<dest dir>]" + LINE_SEPARATOR)
         .append("options:" + LINE_SEPARATOR);
    for(String desc:parser.descriptions) {
      usage.append("  " + desc + LINE_SEPARATOR);
    }
    USAGE = new String(usage);
    parser.parse(args);
    if(parser.values.size() == 0) {
      throw new CommandLineException(USAGE);
    }
    srcFile = new File(parser.values.get(0));
    dstDir = parser.values.size() > 1 ?          
      new File(parser.values.get(1)) :
      new File(".");  
  }
  
  public static void main(String[] args) throws Exception {
    try {
      new YappMain(args).generate();
    }catch(CommandLineException e) {
      System.err.println(e.getMessage());
    }
  }
  
  public boolean generate() throws IOException {
    try {
      generateMain();
      return true;
    }catch(CompilationException ex){
      if(ex.reason() instanceof ParseException){
        ParseException e = (ParseException)ex.reason();
        Token error = e.currentToken.next;
        String expected = e.tokenImage[e.expectedTokenSequences[0][0]];
        System.err.printf(
          "%d:%d: expected %s, but %s.%n", 
          error.beginLine, error.beginColumn,
          expected, error
        );
      }else if(ex.reason() instanceof SemanticException){
        SemanticException e = (SemanticException)ex.reason();
        System.err.println(e.getErrorMessage());
      }else{
        ex.printStackTrace();
      }
      return false;
    }
  }
  
  private static <T> void removeDuplicated(List<T> list) {
    Set<T> set = new HashSet<T>();
    for(Iterator<T> it = list.iterator(); it.hasNext();) {
      T t = it.next();
      if(set.contains(t)) {
        it.remove();
      }
      set.add(t);
    }
  }

  private void generateMain() {
    long start = -1;
    if(has("time")) {
      start = System.currentTimeMillis();
    }
    if(has("ac")) {
      Translator<File, Void> compiler = ComposableTranslator.<File>empty()
        .compose(new Parser(getString("pre", "")))
        .compose(new MacroExpander())
        .compose(new SyntaxSugarExpander())
        .compose(has("ACfirst") ? new AutoCutInserterUsingFirstSet(getInt("ACfirst")) : new IdentityTranslator<Grammar>())
        .compose(new CutCounter())
        .compose(has("ACfollow") ? new AutoCutInserterUsingFollowSet() : new IdentityTranslator<Grammar>())
        .compose(new CutCounter())
        .compose(new GrammarToIstTranslator(false))
        .compose(new CodeGeneratorFromIst(has("package") ? getString("package") : null, dstDir, !has("Onj")));        