header
{
/*
 * $Id$
 *
 * Copyright (c) 2001-2004, RIACA, Technische Universiteit Eindhoven (TU/e).
 * All Rights Reserved.
 *
 * ---------------------------------------------------------------------------
 *
 *  The contents of this file are subject to the RIACA Public License
 *  Version 1.0 (the "License"). You may not use this file except in
 *  compliance with the License. A copy of the License is available at
 *  http://www.riaca.win.tue.nl/
 *
 * ---------------------------------------------------------------------------
 */

package nl.tue.win.riaca.gap.parser;

import antlr.collections.*;
import java.util.*;
}

class GapOMParser extends Parser;

options
{
	k = 2; //two token lookahead
        codeGenMakeSwitchThreshold = 5;
        codeGenBitsetTestThreshold = 6;
        buildAST=true;
        ASTLabelType = "antlr.CommonAST"; // change default of "AST"
}

tokens
{
	AST_TOP;		/* imaginary token */
	AST_LIST;		/* imaginary token */
	AST_FUNCTION;		/* imaginary token */
	AST_CYCLE;		/* imaginary token */
    AST_PERM;
    AST_STRING;
	UNARY_MINUS;		/* helper token to match unary minus. */
	UNARY_PLUS;		/* helper token to match unary plus.  */
}

expr : assignExpr SEMI!
       {
		#expr = #([AST_TOP, "AST_TOP"], expr);
       }
     ;


assignExpr
        :       
		equalityExpression
                (
                        ASSIGN^
                        assignExpr 
                )?
        ;


/**
 * Matches equality expressions. <p>
 *
 * @since 1.0
 */

equalityExpression
	: relationalExpression ( ( EQ^ | NEQ^ ) relationalExpression )*
	;


/**
 * Matches relational expressions. <p>
 *
 * @since 1.0
 */

relationalExpression
	: additiveExpression ( ( LT^ | GT^ | LE^ | GE^ ) additiveExpression )*
	;


/**
 * Matches additive expressions. <p>
 *
 * @since 1.0
 */

additiveExpression
	: multiplicativeExpression 
   	  ( ( PLUS^ | MINUS^ ) multiplicativeExpression )*
        ;


/**
 * Matches multiplicative expressions. <p>
 *
 * @since 1.0
 */
 
multiplicativeExpression 
	: powerExpression ( ( STAR^ | DIV^ ) powerExpression )*
	;


/**
 * Matches power expressions. <p>
 *
 * @since 1.0
 */

powerExpression
	: unaryExpression ( POWER^  unaryExpression )*
	;



/**
 * Matches the unary expressions. <p>
 *
 * @since 1.0
 */

unaryExpression
	: MINUS^ { #MINUS.setType( UNARY_MINUS ); } unaryExpression
	| PLUS^  { #PLUS.setType( UNARY_PLUS );   } unaryExpression
	| unaryExpressionRest
	;

/**
 * Matches the rest of the unary expressions. <p>
 *
 * @since 1.0
 */

unaryExpressionRest	:
        ( (LPAREN RPAREN) | ( LPAREN INT COMMA ) ) =>  permutation
    |   ( ID LPAREN ) => gapFunction
    |   parenthesizedExpression
	|   gapList
    |   string
    |   atom
	;

/**
*  Matches one cycle in a permutation (cycles in gap have length > 1).
*/
cycle : LPAREN! INT COMMA! INT (COMMA! INT)* RPAREN!
        {
            #cycle = #([AST_CYCLE, "AST_CYCLE"], cycle);
        }
    ;

/**
*  Matches a permutation in cycle notation: either () or a nonempty sequence
*  of cycles of length at least 2.
*/
permutation : ( LPAREN! RPAREN! | ( cycle )+ )
        {
            #permutation = #([AST_PERM, "AST_PERM"], permutation);
        }
	;

gapFunction :
        ID^
        LPAREN!
        (
            assignExpr
            (
                COMMA!
                assignExpr
            )*
        )?
        RPAREN!
		{
                #gapFunction = 
			    #([AST_FUNCTION, "AST_FUNCTION"], gapFunction);
		}
        ;

parenthesizedExpression : LPAREN! assignExpr RPAREN!
        ;

gapList :
        LBRACK! ( additiveExpression ( COMMA! additiveExpression )* )? RBRACK!
        {
        #gapList = #([AST_LIST, "AST_LIST"], gapList);
        }
        ;


string : STRING_LITERAL
        {
            #string = #([AST_STRING, "AST_STRING"], string);
        }
    ;

atom :
        ID
    |   INT
    |   CHAR_LITERAL 
    ;

/**
 * The Gap Lexer. <p>
 *
 * It reads in the input that is said to be GAP input. It tries
 * to read the tokens that valid GAP input should have. If it
 * succeeds it generates a sequence of tokens, which in turn can
 * be read by the Gap parser. <p>
 *
 * @author Manfred Riem (mriem@win.tue.nl).
 * @version 1.0
 */

class GapOMLexer 
      extends Lexer;

options 
{
	k = 2;
    charVocabulary = '\u0000'..'\u00FF';
}

/**
 * Reads whitespace and throws it away. <p>
 *
 * @since 1.0
 */

WS      :       (' '
        |       '\t'
        |       '\n'
        |       '\r')
                { _ttype = Token.SKIP; }
        ;


/**
 * Reads the last semi-colon. <p>
 *
 * @since 1.0 
 */

SEMI		:	';' ;


/**
 * Reads the left parenthesis. <p>
 *
 * @since 1.0
 */

LPAREN		:	'(' ;


/**
 * Reads the right parenthesis. <p>
 *
 * @since 1.0
 */

RPAREN		:	')' ;


/**
 * Reads the left bracket. <p>
 *
 * @since 1.0
 */

LBRACK		:	'[' ;


/**
 * Reads the right bracket. <p>
 *
 * @since 1.0
 */

RBRACK		:	']' ;


/**
 * Reads the plus operator. <p>
 *
 * @since 1.0
 */

PLUS : '+';


/**
 * Reads the minus operator. <p>
 *
 * @since 1.0
 */

MINUS : '-';


/**
 * Reads the star operator. <p>
 *
 * @since 1.0
 */

STAR :	'*';


/**
 * Reads the divide operator. <p>
 *
 * @since 1.0
 */

DIV : '/';


/*
 * Reads the power operator. <p>
 *
 * @since 1.0
 */

POWER : '^';


/**
 * Reads the assignment operator. <p>
 *
 * @since 1.0
 */

ASSIGN		:	":=" ;


/**
 * Reads the comma operator. <p>
 *
 * @since 1.0
 */

COMMA		:	',' ;


/**
 * Reads the '<' operator. <p>
 *
 * @since 1.0
 */

LT : '<';


/**
 * Reads the '>' operator. <p>
 *
 * @since 1.0
 */

GT : '>';


/**
 * Reads the "<=" operator. <p>
 *
 * @since 1.0
 */

LE : "<=";


/**
 * Reads the ">=" operator. <p>
 *
 * @since 1.0
 */

GE : ">=";


/**
 * Reads the '=' operator. <p>
 *
 * @since 1.0
 */

EQ : '=';


/**
 * Reads the "<>" operator. <p>
 *
 * @since 1.0
 */

NEQ : "<>";


/**
 * Reads a simple character-literal. <p>
 *
 * @since 1.0
 */

CHAR_LITERAL	:	'\'' (ESC|~'\'') '\'' ;


/**
 * Reads a string literal. <p>
 *
 * @since 1.0
 */

//STRING_LITERAL	:	'"'! (ESC|~'"')* '"'! ;
STRING_LITERAL	:	'"'! (~'"')* '"'! ;

/**
 * Reads an escape-sequence. <p>
 *
 * @since 1.0
 */

protected
ESC     :       '\\'
                (       'n'
                |       'r'
                |       't'
                |       'b'
                |       'f'
                |       '"'
                |       '\''
                |       '\\'
                |       ('0'..'3')
                        (
                                options {
                                        warnWhenFollowAmbig = false;
                                }
                        :       ('0'..'9')
                                (
                                        options {
                                                warnWhenFollowAmbig = false;
                                        }
                                :       '0'..'9'
                                )?
                        )?
                |       ('4'..'7')
                        (
                                options {
                                        warnWhenFollowAmbig = false;
                                }
                        :       ('0'..'9')
                        )?
                )
        ;

protected
DIGIT
        :       '0'..'9'
        ;

INT 
        : (DIGIT)+
        ;

ID
options 
{
	testLiterals = true;
}
        :       ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*
        ;


/**
 * Tree walker. <p>
 *
 * Transform the AST-tree to an XML-encoded OpenMath object. It does
 * NOT use any of the libraries for OpenMath to make it possible to
 * run without any of those libraries. <p>
 *
 * @author Manfred Riem (mriem@win.tue.nl)
 * @version 1.0
 */

class GapOMTreeWalker extends TreeParser;

{
    /**
     * Parse a GRAPE graph into an OpenMath graph. The method only works 
     * if the graph uses the trivial group as its automorphism group; it 
     * may have a bigger automorphism group, but gamma.group must be the 
     * trivial group. Otherwise, it is relatively difficult to obtain the
     * adjacency information from the GRAPE syntax. Any graph can be put 
     * into this form by applying the GAP function
     *    (gamma -> NewGroupGraph (Group (()), gamma))
     * to it.
     * @author Erik Postma
     * @since  1.7
     * @param  theRecord the Map as returned by {@see GapOMTreeWalker#mapify}.
     * @return a String with the XML-encoded OpenMath representation for this graph.
     * @throws RecognitionException if the graph cannot be parsed.
     */
    private String parse_graph (Map theRecord)
      throws RecognitionException
    {
      int       i;          // Multi-purpose counter.
      int       order;
      String [] names;
      boolean   isDirected;
      String    tResult     = "<OMA>\n";
      String    setStartTag = "<OMA>\n<OMS cd=\"set1\" name=\"set\"/>\n";
      String    listStartTag = "<OMA>\n<OMS cd=\"list1\" name=\"list\"/>\n";

      if (theRecord.containsKey ("isSimple") && 
	  ((AST) theRecord.get ("isSimple")).getText ().equals ("true"))
      {
	tResult += "<OMS cd=\"graph1\" name=\"graph\"/>\n";
	isDirected = false;
      }
      else
      {
	tResult += "<OMS cd=\"graph1\" name=\"digraph\"/>\n";
	isDirected = true;
      }
      
      // Generate the vertex names.
      try 
      {
	order = Integer.parseInt 
	  (((AST) theRecord.get ("order")).getText ());
	names = new String [order];
	if (theRecord.containsKey ("names"))
	{
	  AST currentName  = ((AST) theRecord.get ("names")).getFirstChild ();
	  for (i = 0; i < order; i++)
	  {
	    names [i] = this.expr (currentName);
	    currentName = currentName.getNextSibling ();
	  }
	}
	else
	  for (i = 0; i < order; i++)
	    names [i] = "<OMI> " + Integer.toString (i + 1) + " </OMI>\n";
      }
      catch (NumberFormatException e)
      {throw new RecognitionException ("Malformed graph -- order is not a number.");}
      catch (NullPointerException e)
      {throw new RecognitionException 
	("Malformed graph -- maybe order doesn't fit " + 
	 "the number of names, or order not present.");}
      
      tResult += setStartTag;
      for (i = 0; i < order; i++)
	tResult += names [i];
      tResult += "</OMA>\n";

      tResult += setStartTag;
      try
      {
	AST currentNeighbourSet = 
	  ((AST) theRecord.get ("adjacencies")).getFirstChild ();
	for (i = 0; i < order; i++)
	  // Now currentNeighbourSet is a list of vertex numbers adjacent to vertex i.
	{
	  AST currentNeighbour = currentNeighbourSet.getFirstChild ();
	  while (currentNeighbour != null)
	  {
	    int j = Integer.parseInt (currentNeighbour.getText ());
	    // This represents an edge from i to j. If it's undirected, we will 
            // find it twice. Count it only once.
            if (isDirected)
	      tResult += listStartTag + names [i] + names [j - 1] + "</OMA>\n";
	    else if (j > i)
	      tResult += setStartTag + names [i] + names [j - 1] + "</OMA>\n";
	    currentNeighbour = currentNeighbour.getNextSibling ();
	  }
	  currentNeighbourSet = currentNeighbourSet.getNextSibling ();
	}
      }
      catch (NumberFormatException e)
      {throw new RecognitionException 
	("Malformed graph -- non-numerical adjacency");}
      catch (NullPointerException e)
      {throw new RecognitionException
	("Malformed graph -- probably the \"group\" field is not set to " + 
	 "the trivial group.");}
      
      tResult += "</OMA>\n" /* End edge set */ + "</OMA>\n"; /* End graph */

      return tResult;
    }

    /**
     * Build a java.util.Map with the key-value pairs in the record.
     * @author Erik Postma
     * @since  1.7
     * @param  record same as in {@see GapOMTreeWalker#parse_record}
     * @return a java.util.TreeMap with the key-value pairs in the record.
     * @throws RecognitionException if it is not a well-formed record.
     */
    private Map mapify (AST record)
	throws RecognitionException
    {
	Map tResult = new TreeMap ();
	
	AST child   = record.getFirstChild ();
	while (child != null)
	{
	    if (! child.getText ().equals (":="))
		throw new RecognitionException 
		    ("Record containing non-assignment.");

	    AST key = child.getFirstChild ();
	    if (key == null)
		throw new RecognitionException 
		    ("Record contains assignment without key.");
	    
	    AST value = key.getNextSibling ();
	    if (value == null)
		throw new RecognitionException 
		    ("Record contains assignment without value for key " +
		     key.getText () + ".");
	    
	    tResult.put (key.getText (), value);
	    child = child.getNextSibling ();
	}
	
	return tResult;
    }

    /**
     * Parse a record. Not all records can be parsed; there is no structure
     * in OpenMath corresponding to a record. But some classes of records have 
     * a special meaning; like GRAPE graphs, recognizable by having a field 
     * "isGraph" with value true. If you'd like to extend this to some other 
     * class, please put only a simple check here and do the actual parsing in
     * another method.
     * @author Erik Postma
     * @since  1.7
     * @param  record the AST representing the record (excluding the AST_FUNCTION).
     * @return a String with an XML-encoded OpenMath representation of the record.
     * @throws RecognitionException if the record is not recognized or malformed.
     */
    private String parse_record( AST record )
	throws RecognitionException
    {
	Map theRecord = mapify (record);

	if (theRecord.containsKey ("isGraph") && 
	    ((AST) theRecord.get ("isGraph")).getText ().equals ("true"))
	    return parse_graph (theRecord);
	
	throw new RecognitionException 
	    ("Record of a class that is not understood.");
    }

/**
*  Transform a string into a valid XML string (i.e., no "&", "<", ">").
*/
    private String xmlify(String s) {
        StringBuffer sb = new StringBuffer(s);

        replaceChar(sb, '&', "&amp;");
        replaceChar(sb, '<', "&lt;");
        replaceChar(sb, '>', "&gt;");
        return sb.toString();
    }

    private void replaceChar(StringBuffer buf, char c, String s) {
        // Replace all c in buf by s.
        int i = buf.toString().lastIndexOf(c);
        while (i != -1) {
            buf.replace(i, i + 1, s);
            i = buf.toString().lastIndexOf(c, i-1);
        }
    }
}


expr returns [String tResult]
{
	String tLeft,tRight;
	tResult  = "";
}
	: tTop : AST_TOP
        {
            AST tChild = tTop.getFirstChild();
	
            tResult = "<OMOBJ>\n";

            if ( tChild != null )
            {
                tResult += this.expr( tChild );
            }
            tResult += "</OMOBJ>\n";
        }

	| #( tMinus:MINUS tLeft=expr tRight=expr )	
	  {
 		tResult = "<OMA>\n" +
			  "<OMS cd=\"arith1\" name=\"minus\"/>\n" + 
			  tLeft   +
			  tRight  +
			  "</OMA>\n" ;
	  }

	| tUnaryMinus:UNARY_MINUS
	  {
		AST tAST = tUnaryMinus.getFirstChild();

		if ( tAST.getType() == INT )
		   tResult = "<OMI>-" + tAST + "</OMI>\n";
		else
		   tResult = "<OMA>\n" +
		             "<OMS cd=\"arith1\" name=\"unary_minus\"/>\n" +
			     this.expr( tAST )  +
			     "</OMA>";
	  }

	| #( tPlus:PLUS tLeft=expr tRight=expr  )
	  {
 		tResult = "<OMA>\n" +
			  "<OMS cd=\"arith1\" name=\"plus\"/>\n" + 
			  tLeft   +
			  tRight  +
			  "</OMA>\n" ;
	  }

	| #( tLess:LT tLeft=expr tRight=expr )
	  {
		tResult = "<OMA>\n" +
			  "<OMS cd=\"relation1\" name=\"lt\"/>\n" +
			  tLeft +
			  tRight +
			  "</OMA>\n";
	  }

	| #( tGreater:GT tLeft=expr tRight=expr )
	  {
		tResult = "<OMA>\n" +
			  "<OMS cd=\"relation1\" name=\"gt\"/>\n" +
			  tLeft +
			  tRight +
			  "</OMA>\n";
	  }

	| #( tLessEqual:LE tLeft=expr tRight=expr )
	  {
		tResult = "<OMA>\n" +
			  "<OMS cd=\"relation1\" name=\"le\"/>\n" +
			  tLeft +
			  tRight +
			  "</OMA>\n";
	  }

	| #( tGreaterEqual:GE tLeft=expr tRight=expr )
	  {
		tResult = "<OMA>\n" +
			  "<OMS cd=\"relation1\" name=\"ge\"/>\n" +
			  tLeft +
			  tRight +
			  "</OMA>\n";
	  }

	| tUnaryPlus:UNARY_PLUS
	  {
		AST tAST = tUnaryPlus.getFirstChild();

		if ( tAST.getType() == INT )
		   tResult = "<OMI>" + tAST + "</OMI>\n";
		else
		   tResult = this.expr( tAST );
	  }

	| #( tStar:STAR tLeft=expr tRight=expr )	
	  { 
		tResult = "<OMA>\n" +
		  	  "<OMS cd=\"arith1\" name=\"times\"/>\n" +
			  tLeft   +
			  tRight  +
			  "</OMA>\n";
	  }

	| tDiv:DIV
	  {
            tResult = "<OMA>\n";

            AST tAST1 = tDiv.getFirstChild();
            AST tAST2 = tAST1.getNextSibling();
            if ( tAST1.getType() == INT && tAST2.getType() == INT )
            {
                tResult += "<OMS cd=\"nums1\" name=\"rational\"/>\n";
            }
            else
            {
                tResult += "<OMS cd=\"arith1\" name=\"divide\"/>\n";
            }

            tResult += this.expr( tAST1 ) + this.expr( tAST2 ) + "</OMA>\n";
	  }

	| #( tPower:POWER tLeft=expr tRight=expr )
	  {
		tResult = "<OMA>\n" +
			  "<OMS cd=\"arith1\" name=\"power\"/>\n" +
			  tLeft +
			  tRight +
			  "</OMA>\n";
	  }

	| #( tEqual:EQ tLeft=expr tRight=expr )
	  {
		tResult = "<OMA>\n" +
			  "<OMS cd=\"relation1\" name=\"eq\"/>\n" +
			  tLeft +
			  tRight +
			  "</OMA>\n";
	  }

	| #( tNotEqual:NEQ tLeft=expr tRight=expr )
	  {
	      tResult = "<OMA>\n" +
		  "<OMS cd=\"relation1\" name=\"neq\"/>\n" +
		  tLeft +
		  tRight +
		  "</OMA>\n";
	  }

	| tInteger : INT
	  {
	      tResult = "<OMI>" + tInteger.getText() + "</OMI>\n";
	  }
        
	| tCycle : AST_CYCLE
        {
            tResult = "<OMA>\n<OMS cd=\"permutation1\" name=\"cycle\"/>\n";

            AST tChild = tCycle.getFirstChild();
            while ( tChild != null )
            {
                tResult += this.expr( tChild );		
                tChild = tChild.getNextSibling();		  
            }

            tResult += "</OMA>\n";
        }

	| tPerm : AST_PERM
        {
            tResult = "<OMA>\n<OMS cd=\"permutation1\" name=\"permutation\"/>\n";

            AST tChild = tPerm.getFirstChild();
            while ( tChild != null )
            {
                tResult += this.expr( tChild );		
                tChild = tChild.getNextSibling();		  
            }

            tResult += "</OMA>\n";	
        }
        
	| tList : AST_LIST
	  {
	      /*
	       * Add each child to the list. <p>
	       */
	      
	      AST tChild = tList.getFirstChild();
	      
	      tResult = "<OMA>\n" +
		  "<OMS cd=\"list1\" name=\"list\"/>\n";
	      
	      if ( tChild != null )
	      {
		  tResult += this.expr( tChild );
		  
		  tChild = tChild.getNextSibling();
		  
		  while( tChild != null )
		  {
		      tResult += this.expr( tChild );
		      tChild = tChild.getNextSibling();
		  }
	      }
	      
	      tResult +=  "</OMA>\n";
	  }

	| tFunction : AST_FUNCTION
        {
		/*
		 * A function call or a record.
		 */

            AST tChild = tFunction.getFirstChild();

            if ( tChild.getText().equals( "rec" ))
            tResult = parse_record (tChild);
            else if (tChild.getText().equals("E"))
            { // parse "E(5)"
                tResult =
                "<OMA>\n" +
                "<OMS cd=\"transc1\" name=\"exp\"/>\n" +
                "<OMA>\n" +
                "<OMS cd=\"arith1\" name=\"divide\"/>\n" +
                "<OMA>\n" +
                "<OMS cd=\"arith1\" name=\"times\"/>\n" +
                "<OMI>2</OMI>\n" +
                "<OMS cd=\"nums1\" name=\"pi\"/>\n" +
                "<OMS cd=\"nums1\" name=\"i\"/>\n" +
                "</OMA>\n" +
                "<OMI>" + tChild.getFirstChild().getText() + "</OMI>\n" +
                "</OMA>\n" +
                "</OMA>\n"; 

            }
            else if (tChild.getText().equals("Group"))
            { // E.g.: Group([(1,2)(3,4),(1,2,3)]) or Group(())
                tResult =
                "<OMA>\n" +
                "<OMS cd=\"permgrp1\" name=\"group\"/>\n" +
                "<OMS cd=\"permutation1\" name=\"rightcompose\"/>\n";
                tChild = tChild.getFirstChild();
                if ( tChild.getType() == AST_LIST )
                {
                    // "delistify" the list of generators
                    tChild = tChild.getFirstChild();
                }

                while( tChild != null )
                {
                    tResult += this.expr( tChild );
                    tChild = tChild.getNextSibling();
                }
                tResult +=  "</OMA>\n"; 
            }
            else if (tChild.getText().equals("Z"))
            {
                tResult =
                "<OMA>\n" +
                "<OMS cd=\"gap\" name=\"primitive_elt\"/>\n" +
                this.expr(tChild.getFirstChild()) +  
                "</OMA>\n"; 
            }
            else
            {
                tResult = "<OMA>\n" +
                "<OMS cd=\"gap\" name=\"" + tChild.getText() + "\"/>\n"; 

                tChild = tChild.getFirstChild();

                while( tChild != null )
                {
                    tResult += this.expr( tChild );
                    tChild = tChild.getNextSibling();
                }
                
                tResult +=  "</OMA>\n";
            }
	  }

	| tIdentifier : ID
        {
            if ( tIdentifier.getText().equals( "true" ) ||
                tIdentifier.getText().equals( "false" ) )
            {
                tResult = 
				"<OMS cd=\"logic1\" name=\"" +
				tIdentifier.getText() +
				"\"/>\n";
            }
            else if ( tIdentifier.getText().equalsIgnoreCase( "infinity" ) )
            {
                tResult = "<OMS cd=\"nums1\" name=\"infinity\"/>\n";
            }
            else if ( tIdentifier.getText().equals( "fail" ) )
            {
                tResult = "<OMS cd=\"gap\" name=\"fail\"/>\n";
            }
			else
            tResult = "<OMV name=\"" + tIdentifier.getText() + "\"/>\n";
		}
    | tString : AST_STRING
        {
            tResult = "<OMSTR>" +
                      xmlify( tString.getFirstChild().getText() ) +
                      "</OMSTR>\n";
        }
	;