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

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

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

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

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

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

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

  public Symbol var() {
    return var;
  }

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

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

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

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

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

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

  @Override
  public String toString() {
    return "fail";
  }
} public static class N_Alternation extends VarArgExpression {
  public N_Alternation(Position pos, List<Expression> expressions){
    super(pos, expressions);
  }


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

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

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

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

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

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

  public Symbol name() {
    return name;
  }

  public Symbol var() {
    return var;
  }

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

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

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

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

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

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

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

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

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

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

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

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

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

  public Expression body() {
    return body;
  }

  public String code() {
    return code;
  }

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

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

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

  public String value() {
    return value;
  }

  public Symbol var() {
    return var;
  }

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

  @Override
  public <R, C> R accept(Visitor<R, C> visitor, C context) {
    return visitor.visit(this, context);
  }
} public static abstract class Terminal extends Expression {
  public Terminal(Position pos){
    super(pos);
  }
} 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 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 class CollectionUtil {
  public static <T> List<T> list(T... elements) {
    return new ArrayList<T>(Arrays.asList(elements));
  }
  
  public static <A, B> Pair<A, B> t(A fst, B snd) {
    return new Pair<A, B>(fst, snd);
  }
  
  public static <K, V> Map<K, V> map(Pair<? extends K, ? extends V>... elements) {
    Map<K, V> map = new HashMap<K, V>();
    for(Pair<? extends K, ? extends V> e:elements) {
      map.put(e.fst(), e.snd());
    }
    return map;
  }
  
  public static <T> Set<T> set(T... elements) {
    return new HashSet<T>(Arrays.asList(elements));
  }
  
  public static <T> Set<T> setFrom(Collection<? extends T> collection) {
    return new HashSet<T>(collection);
  }
}
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import com.github.kmizu.yapp.Symbol;
import com.github.kmizu.yapp.Ast.Action;
import com.github.kmizu.yapp.Ast.AndPredicate;
import com.github.kmizu.yapp.Ast.CharClass;
import com.github.kmizu.yapp.Ast.Cut;
import com.github.kmizu.yapp.Ast.Empty;
import com.github.kmizu.yapp.Ast.Expression;
import com.github.kmizu.yapp.Ast.Fail;
import com.github.kmizu.yapp.Ast.N_Alternation;
import com.github.kmizu.yapp.Ast.N_Sequence;
import com.github.kmizu.yapp.Ast.NonTerminal;
import com.github.kmizu.yapp.Ast.NotPredicate;
import com.github.kmizu.yapp.Ast.Optional;
import com.github.kmizu.yapp.Ast.Repetition;
import com.github.kmizu.yapp.Ast.RepetitionPlus;
import com.github.kmizu.yapp.Ast.SemanticPredicate;
import com.github.kmizu.yapp.Ast.SetValueAction;
import com.github.kmizu.yapp.Ast.StringLiteral;
import com.github.kmizu.yapp.Ast.Terminal;
import com.github.kmizu.yapp.Ast.Visitor;
import com.github.kmizu.yapp.Ast.Wildcard;
import com.github.kmizu.yapp.util.CollectionUtil;
package com.github.kmizu.yapp.translator;



public class FirstSetCollector extends Visitor<Void, Set<Expression>>
  implements Translator<Expression, Set<Expression>> {
  public static class FirstSetCannotBeComputed extends RuntimeException {}
  private Map<Symbol, Expression> bindings;
  private Set<Expression> nul;
  private Set<Expression> fail;
  private boolean notPredicateAsError;
  
  public FirstSetCollector(
    Map<Symbol, Expression> bindings, Set<Expression> nul, Set<Expression> fail
  ) {
	this(bindings, nul, fail, false);
  }
  
  public FirstSetCollector(
    Map<Symbol, Expression> bindings, Set<Expression> nul, Set<Expression> fail,
    boolean notPredicateAsError
  ) {
    this.bindings = bindings;
    this.nul = nul;
    this.fail = fail;
    this.notPredicateAsError = notPredicateAsError;
  }
  
  public Set<Expression> translate(Expression from) {
    Set<Expression> first = CollectionUtil.set();
    from.accept(this, first);
    Set<Expression> FIRST = CollectionUtil.set();
    for(Expression e:first) {
      if(e instanceof Empty || !(e instanceof Terminal)) continue;
      if((e instanceof StringLiteral) && ((StringLiteral)e).value().equals("")) continue;
      FIRST.add(e);
    }
    return FIRST;
  }

  @Override
  protected Void visit(Action node, Set<Expression> context) {
    context.add(node);
    node.body().accept(this, context);
    return null;
  }

  @Override
  protected Void visit(AndPredicate node, Set<Expression> context) {
    context.add(node);
    node.body().accept(this, context);
    return null;
  }

  @Override
  protected Void visit(CharClass node, Set<Expression> context) {
    context.add(node);
    return null;
  }

  @Override
  protected Void visit(Cut node, Set<Expression> context) {
    context.add(node);
    return null;
  }

  @Override
  protected Void visit(Empty node, Set<Expression> context) {
    context.add(node);
    return null;
  }

  @Override
  protected Void visit(Fail node, Set<Expression> context) {