import java.util.Vector;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
import java.util.Arrays;
import java.util.Comparator;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.FileInputStream;
import javax.swing.tree.DefaultMutableTreeNode;

/**
 * Implement CYK
 */
public class CYK {
    
    /*Entspricht einer Regel*/
    public static class Rule {
	String left;//linke Seite
	String right;//rechte Seite
	/*Constructor*/
	public Rule(String left, String right) {
	    this.left = left;
	    this.right = right;
	}

	/* Alle neuen Wörter erzeugen */
	String[] applyRule(String w) {
	    int i = -1;
	    i = w.indexOf(left,i+1);//suche ersten Index für linke Seite
	    Vector v = new Vector();
	    while (i>=0) {
		String nw = w.substring(0,i)+right+w.substring(i+left.length());//neues Wort
		                                                                //erzeugen
		v.add(nw);//neues Wort hinzufügen
		i = w.indexOf(left,i+1);//suche nächsten Index für linke Seite
	    }
	    //Rückgabeliste generieren
	    String[] rv = new String[v.size()];
	    for (i=0;i<v.size();++i) 
		rv[i] = (String)v.elementAt(i);
	    return rv;
	}

	/* Für Debbugen*/
	public String toString() {
	    return left+" -> "+right;
	}
    }

    /**
     * Data structure to quickly find rules
     */
    public static class RuleIndex {
	/*array ordered by rhs*/
	public Rule[] _rightOrdered;
	private HashMap  _rightBorders;
	/*array ordered by lhs*/
	public Rule[] _leftOrdered;
	private HashMap  _leftBorders;
	/*Constructor*/
	public RuleIndex(Vector rules) {
	    _leftOrdered = new Rule[rules.size()];
	    _rightOrdered = new Rule[rules.size()];
	    for (int i=0;i<rules.size();++i) {
		_leftOrdered[i] = (Rule)rules.elementAt(i);
		_rightOrdered[i] = (Rule)rules.elementAt(i);
	    }
	    Arrays.sort(_leftOrdered,new Comparator() {
		    public int compare(Object o1, Object o2) {
			Rule r1 = (Rule)o1;
			Rule r2 = (Rule)o2;
			return r1.left.compareTo(r2.left);
		    }
		});
	    Arrays.sort(_rightOrdered,new Comparator() {
		    public int compare(Object o1, Object o2) {
			Rule r1 = (Rule)o1;
			Rule r2 = (Rule)o2;
			return r1.right.compareTo(r2.right);
		    }
		});

	    //compute borders:
	    _rightBorders = new HashMap();
	    for (int i=0;i<_rightOrdered.length;++i) {
		if (i==0 || !(_rightOrdered[i-1].right.equals(_rightOrdered[i].right))) {
		    int j=i+1;
		    while (j<_rightOrdered.length && _rightOrdered[i].right.equals(_rightOrdered[j].right)) {
			j++;
		    }
		    _rightBorders.put(_rightOrdered[i].right,new int[]{i,j});
		}
	    }
	    _leftBorders = new HashMap();
	    for (int i=0;i<_leftOrdered.length;++i) {
		if (i==0 || !(_leftOrdered[i-1].left.equals(_leftOrdered[i].left))) {
		    int j=i+1;
		    while (j<_leftOrdered.length && _leftOrdered[i].left.equals(_leftOrdered[j].left)) {
			j++;
		    }
		    _leftBorders.put(_leftOrdered[i].left,new int[]{i,j});
		}
	    }
	}

	/* 
	 * returns two integers specifying the boundaries of rules 
	 * with the given left side in _leftOrdered.
	 */
	public int[] findLeftSide(String lhs) {
	    return (int[])_leftBorders.get(lhs);
	}
	/* 
	 * returns two integers specifying the boundaries of rules 
	 * with the given right side in _rightOrdered.
	 */
	public int[] findRightSide(String lhs) {
	    return (int[])_rightBorders.get(lhs);
	}
    }

    /*Hauptmethode erwarte zwei Argumente. 
      Erstes Argument: Grammatik-Datei
      Zweites Argument: Wort
      
      Die Grammatik-Datei ist Zeilenweise aufgebaut. Die erste Zeile 
      enthält nur das Startsymbol, jede weitere eine Produktion.
    */
    public static void main(String[] args) throws IOException {
	//Datei öffnen
	BufferedReader br = new BufferedReader(
                      new InputStreamReader(new FileInputStream(args[0])));
	Vector rules = new Vector();//Regelliste
	String line = br.readLine();//Startsymbol lesen
	String startsymbol = line.substring(0,1);
	line = br.readLine();//Erste Regel lesen
	while (line!=null) {
	    int l = line.indexOf(" ");//Linke Seite steht vor den Leerzeichen
	    Rule r = new Rule(line.substring(0,l),line.substring(l+1));
	    if (r.left.length()!=1 ||  ( r.right.length()==1 && !Character.isLowerCase(r.right.charAt(0))) || ( r.right.length()==2 && (Character.isLowerCase(r.right.charAt(0)) || Character.isLowerCase(r.right.charAt(1)))) || r.right.length()>2) {
		System.out.println("WARNING: Invalid Rule: "+r);
	    }
	    System.out.println("Added rule: "+r);
	    rules.add(r);
	    line = br.readLine();//Weitere Regeln lesen
	}
	br.close();//Datei schließen
	RuleIndex ri = new RuleIndex(rules);

	String w = args[1];
	int len = w.length();
	//initialize an array to store symbols and derivation trees -> V_{i,j}
	//row: j-i
	//colum: i
	//Note: j = col+row; i = col
	HashMap dp[][] = new HashMap[len][];
	for (int i=0;i<len;++i) {
	    dp[i] = new HashMap[len];
	    for (int j=0;j<len;++j) {
		dp[i][j] = new HashMap();
	    }
	}
	//initialize first row
	for (int i=0;i<len;++i) {
	    int j = i;
	    String c = w.substring(i,j+1);
	    int[] p = ri.findRightSide(c);
	    if (p!=null) {
		for (int t=p[0];t<p[1];++t) {
		    DefaultMutableTreeNode n = new DefaultMutableTreeNode(ri._rightOrdered[t].left);
		    DefaultMutableTreeNode nt =  new DefaultMutableTreeNode(ri._rightOrdered[t].right);
		    n.add(nt);
		    dp[i][j-i].put(ri._rightOrdered[t],n);
		}
	    }
	}
	//dynmaic programming
	for (int d=1;d<len;++d) {//d = diagonal = j-i
	    for (int i=0;i<len-d;++i) {
		int j = d+i;
		//fill: dp[i][d]
		for (int k=i;k<j;++k) {
		    //v_i,k: i, k-i
		    //v_k+1,j : k+1, j-(k+1)
		    int i1 = i;
		    int j1 = k;
		    int i2 = k+1;
		    int j2 = j;
		    Set L = dp[i1][j1-i1].keySet();
		    Set R = dp[i2][j2-i2].keySet();
		    Iterator iterL = L.iterator();
		    while (iterL.hasNext()) {
			Rule lRule = (Rule)iterL.next();
			Iterator iterR = R.iterator();
			while (iterR.hasNext()) {
			    Rule rRule = (Rule)iterR.next();
			    String lhs = lRule.left+rRule.left;
			    int[] p = ri.findRightSide(lhs);
			    if (p!=null) {
				for (int t=p[0];t<p[1];++t) {
				    DefaultMutableTreeNode dnmt = new DefaultMutableTreeNode(ri._rightOrdered[t].left);
				    DefaultMutableTreeNode lNode = (DefaultMutableTreeNode)dp[i1][j1-i1].get(lRule);
				    DefaultMutableTreeNode rNode = (DefaultMutableTreeNode)dp[i2][j2-i2].get(rRule);
				    dnmt.add(Tree.deepClone(lNode));
				    dnmt.add(Tree.deepClone(rNode));
				    dp[i][d].put(ri._rightOrdered[t],dnmt);
				}
			    }
			}
		    }
		}
	    }
	}
	
	//check whether S in V_0(len-1) i=0 j = len-1
	// and display in trees;
	boolean hasTree= false;
	Set S = dp[0][len-1].keySet();
	Iterator iter = S.iterator();
	while (iter.hasNext()) {
	    Rule rule = (Rule)iter.next();
	    if (rule.left.equals(startsymbol)) {
		DefaultMutableTreeNode dnmt = (DefaultMutableTreeNode)dp[0][len-1].get(rule);
		Tree tr = new Tree(dnmt);
		tr.expandAll();
		tr.pack();
		tr.show();
		hasTree = true;
	    }
	}
	if (!hasTree) System.out.println("Not a word of the language.");
    }
}