# Let's try to write a parser for the non-context free language C^nA^nT^n:

terminal C A T
nonterminal S String
nonterminal As String
nonterminal Ts String
nonterminal Cs String
nonterminal AI String
topsym S

S --> Cs AI Ts  { if (cat.ax==0) return "success!"; else throw new Error("wrong number of Ts!"); }

Cs --> C Cs { cat.cx++; return null;}
Cs --> 
As --> A As { cat.ax++; return null;}
As -->      
Ts --> T Ts { cat.ax--; return null;}
Ts -->  

# this extra production is used to insert a semantic action in between reading A's and T's

AI --> As  { if (cat.ax!=cat.cx) throw new Error("wrong number of As!"); return null;}    

EOF


This language is the simplest example of the context free pumping lemma.

Using semantic actions to guide the parser sounds fun but really destroys
the most important theoretical results of parsing theory, namely that
it is decideble whether a grammar is LR(1) or SLR, LALR, LL(1), etc...
(Knuth's result says that it is undecidable if there exists a k such 
that a grammar is LR(k). But it is decidable if we know what k is.)
Semantic actions clearly make parsing undecidable.  In particular, 
two-counter automata (as opposed to full Turing machines) are already
undecidable (by reduction to Halting problem).  A parser generator based 
solely on the grammar can guarantee that a suceessful parser is produced, 
or fail if the grammar is not of the right class that it is designed for.  
The pure grammar only defines the regular expression C*A*T*.  The best
use of semantic actions is to generate a parse tree. Once that's done,
parsing is no longer an issue.  Of course, if you're forced to write 
a parser for a non-CF language, then you will have no choice but to resort 
to such hacks.  The danger of parsing this way is that undisciplined 
programmers (e.g. most undergrads) will use such techniques to parse 
languages that do have deterministic grammars.  Thus in general, you should
avoid semantic actions that do more than build a parse tree.


Contents of cat.java:
/////////////////////////////////////
import java.util.ArrayList;

public class cat
{
    public static int cx=0;  // used by semantic actions of parser
    public static int ax=0;
    
    public static void main(String[] argv) throws Exception
    {
	ArrayList<Gsym> S = new ArrayList<Gsym>();
	for(int i=0;i<argv[0].length();i++) 
	    S.add(new Gsym(argv[0].charAt(i)+""));
	S.add(new Gsym("EOF"));
	catparser parser = new catparser(S);
	String result = parser.parse();
	System.out.println(result);
	ax=cx=0;
    }//main
}
//////////////////////////////////////

Sample runs:
java cat CCCAAATTT
success!
java cat CCCAATTTT
Exception in thread "main" java.lang.Error: wrong number of As!
        at catparser$8.compval(catparser.java:91)
        at reduce.doit(stateaction.java:37)
        at absparser.parse(absparser.java:131)
        at cat.main(cat.java:16)