package G4ip;
import java.util.*;
import pizza.lang.Pair;
import G4ip.Form.*;
import G4ip.Token.*;
public class Token {
public static final int AND = 0;
public static final int OR = 1;
public static final int IMP = 2;
public static final int EQU = 3;
/** End-of-Input */
public case EOI(); // end-of-input
public case LPAREN();
public case RPAREN();
public case ID(String id);
public case FALSE();
public case BINOP(int op); // binary operation
public case COMMA();
}
/** A left-to-right, rightmost-derivation parser.
* The following grammar is implemented:
*
* - Formula ::= Id
* | false
* |
( Formula )
* |
Formula Binop Formula
*
*
* - Id is a string of lower case letters
*
*
* - Binop is either
&, v, ->
or <->
*
*
* - FormulaList ::= empty
* |
[ FormulaList ,]* Formula
*
* The parser uses a stack where two actions are performed:
*
* - shift moves the next token to the top of the stack (getNextToken)
* - reduce chooses a grammar rule, X -> A B C; pops A, B, C from the
* top of the stack and pushes X onto the stack
*
* @author Christian Urban
*/
public class Parser {
final Pair keywords[] =
{ new Pair("(", LPAREN()),
new Pair(")", RPAREN()),
new Pair(",", COMMA()),
new Pair("&", BINOP(Token.AND)),
new Pair("v ", BINOP(Token.OR)),
new Pair("->", BINOP(Token.IMP)),
new Pair("<->", BINOP(Token.EQU)),
new Pair("false",FALSE()) };
String in; // string to be parsed
int index; // position of the current input
Stack stack; // stack for the left-to-right parser 'LR(0)'
public Parser(String init_in){
index = 0;
in = init_in;
stack = new Stack();
}
/** tokens are: identifiers( ) , & v -> <-> false
* and EOI
(end of input)
*/
public Token getNextToken() throws Exception {
while ( index < in.length() && Character.isSpace(in.charAt(index)) )
{ index++; } //delete white-spaces
if (index == in.length()) { return EOI(); } //end-of-string
for (int i=0;i Atm(string) */
if (stack.size() > 0 &&
(stack.elementAt(stack.size()-1) instanceof ID))
{ ID id = (ID)stack.pop();
stack.push(Atm(id.id));
again = true;
}
/* FALSE -> False() */
if (stack.size() > 0 &&
(stack.elementAt(stack.size()-1) instanceof FALSE))
{ stack.pop();
stack.push(False());
again = true;
}
/* ( Formula ) -> Formula */
if (stack.size() > 2 &&
(stack.elementAt(stack.size()-3) instanceof LPAREN) &&
(stack.elementAt(stack.size()-2) instanceof Form) &&
(stack.elementAt(stack.size()-1) instanceof RPAREN))
{ stack.pop();
Form form = (Form)stack.pop();
stack.pop();
stack.push(form);
again = true;
}
/* Formula BINOP Formula -> Formula */
if (stack.size() > 2 &&
(stack.elementAt(stack.size()-3) instanceof Form) &&
(stack.elementAt(stack.size()-2) instanceof BINOP) &&
(stack.elementAt(stack.size()-1) instanceof Form))
{ Form c2 = (Form)stack.pop();
BINOP op = (BINOP)stack.pop();
Form c1 = (Form)stack.pop();
switch(op.op) {
case Token.AND: stack.push(new And(c1,c2)); again = true;break;
case Token.OR: stack.push(new Or(c1,c2)); again = true;break;
case Token.IMP: stack.push(new Imp(c1,c2)); again = true;break;
case Token.EQU: stack.push(new And(Imp(c1,c2),Imp(c2,c1))); again = true;break;
}
}
if (again == true) { reduce(); } // do as many "reduces" as possible
}
/** parses a single formula
*/
public Form parseFormula() throws Exception {
Token tok;
while (!((tok = getNextToken()) instanceof EOI)) {
stack.push(tok);
reduce();
}
if (stack.size() == 1 &&
(stack.elementAt(stack.size()-1) instanceof Form))
{ return (Form)stack.pop(); }
else throw new Exception("Grammar error");
return null;
}
/** parses a list of formulae separated by commas
*/
public Context parseFormulae() throws Exception {
Token tok;
Context erg = new Context();
while (!((tok = getNextToken()) instanceof EOI)) {
stack.push(tok);
reduce();
}
if (stack.empty()) return erg; // LHS can be empty !!
stack.push(new COMMA());
for(int i=0;i