// Basic source code implementing a Compiler and Interpreter for
// a Simple Programming Language (SPL)

// The SPL is defined with the following context-free grammar:
// P -> E
// E -> T | T + T | let id=E
// T -> id | num | ( E ) | { B }
// B -> var V ; S | S
// V -> id | id V
// S -> E | E ; S

// The lexical components are defined as follows:
// id  -> letter ( letter | digit )*
// num -> digit digit*
// any -> newline | whitespace | EOF

// for implementation details see: Watt,D.A. and Brown,D.F. (2000)
// "Programming Language Processors in Java", Prentice-Hall, NY.

import java.util.*;
import java.io.*;

// Environment which is a linked list of identifiers
class Env
{
    String key;
    Env next;

    static final Env empty = null;
    Env( String key, Env next )
    {
	  this.key = key;
      this.next = next;
    }

    public String toString()
    {
	String r = "[ ";
	for ( Env env = this; env != null; env = env.next )
	    r +=  env.key + " ";
	r += "]";
	return r;
    }

    static Env find( Env env,String Ktarget )
    {
	for ( ; env != null; env = env.next )
	    if ( env.key.equals( Ktarget ))
	       return env;
	return null;
    }
}

class ValueEnv extends Env
{
    Integer value;

    ValueEnv( String key, Integer value, ValueEnv next )
	{
        super( key,next );
	    this.value = value;
    }

    public String toString()
	{
	   String r = "[ ";
	   for ( ValueEnv env = this; env != null; env = (ValueEnv) env.next )
	       r +=  env.key + "=" + env.value + " ";
	   r += "]";
	   return r;
    }
}

abstract class AST
{
   abstract boolean check( Env env );
   boolean check()
   {
	return this.check( Env.empty );
   }
}

final class VarAST extends AST
{
   private String i;

   VarAST (String ide)
   {
	this.i = ide;
   }

   public String toString()
   {
	return i;
   }

   boolean check( Env env )
   {
	if ( Env.find( env, i ) != null )
	    return true;
	else
      {
	   System.err.println("Check error: undeclared \"" + i + "\" variable");
	   return false;
      }
   }
}

final class ConstAST extends AST
{
   private int c;

   ConstAST( int cons )
   {
	this.c = cons;
   }

   public String toString()
   {
	return Integer.toString(c);
   }

   boolean check( Env env )
   {
	return true;
   }
}
 final class PlusAST extends AST
{
   private AST l;
   private AST r;

   PlusAST( AST left, AST right )
   {
	this.l = left; this.r = right;
   }

   public String toString()
   {
	return "(+ " + l + " " + r + ")";
   }

   boolean check( Env env )
   {
	return l.check( env ) && r.check( env );
   }
}

final class LetAST extends AST
{
   private String i;
   private AST e;

   LetAST( String ide, AST exp )
   {
	this.i = ide; this.e = exp;
   }

   public String toString()
   {
	return "(let " + i + " " + e + ")";
   }

   boolean check( Env env )
   {
	if ( Env.find( env,i ) != null )
	   return e.check( env );
	else
      {
	   System.err.println( "Check error: undeclared \"" + i + "\" variable");
	   return false;
	}
   }
}

final class BlockAST extends AST
{
   private List vs;
   private List es;

   BlockAST( List vars, List exps )
   {
	this.vs = vars; this.es = exps;
   }

   public String toString()
   {
	String r = "(begin ( ";
	for ( Iterator it = vs.iterator(); it.hasNext(); )
	   r += (String) it.next() + " ";
	r += ") ( ";
	for ( Iterator it = es.iterator(); it.hasNext(); )
	   r += ((AST) it.next()) + " ";
	r += "))";

	return r;
   }

   boolean check( Env env )
   {
	for ( Iterator it = vs.iterator(); it.hasNext(); )
      {
	   String ide = (String) it.next();
	   env = new Env( ide, env );
	}
	for ( Iterator it = es.iterator(); it.hasNext(); )
      {
	    AST exp = (AST) it.next();
	    if ( !exp.check( env ) )
		 return false;
	}

	return true;
    }
}


// Tokens for the SPL
class Token
{
    private Token() {}

    final static byte // keywords and special symbols
	VAR = 0,    // 'var'
	LET = 1,    // 'let'
	ID = 2,     // identifier
	NUM = 3,    // number
	EQ = 4,     // =
	LBRA = 5,   // {
	RBRA = 6,   // }
	LPAR = 7,   // (
	RPAR = 8,   // )
	PLUS = 9,   // +
	MINUS = 10, // -
	SEMI = 11,  // ;
	EOF = 12;   // end of file

   final static String[] stringOf =
   {
	"'var'","'let'","id","num","'='","'{'","'}'","'('","')'","'+'","'-'","';'","eofile"
   };

   final static String[] keywords =
   {
	"var","let",
   };

   final static char[] symbols =
   {
	'=','{','}','(',')','+','-',';'
   };

   final static byte fkwrd = VAR;

   final static byte fsmbl = EQ;
}

// Lexical analyzer for the SPL
class Scanner
{
   int lineno;
   Object attrib = null;
   private PushbackReader brd;
   static final char newline = System.getProperty( "line.separator" ).charAt( 0 );

   Scanner( Reader file )
   {
	brd = new PushbackReader( file );
	lineno = 1;
   }

   byte lex() throws CompError
   {
	try
      {
	    attrib = null;
	    while ( true )
          { // get next input symbol
		char c = (char) brd.read();
		if ( c == (char) (-1) )
		    return Token.EOF;
		else
               if ( c == newline )
               {
		      lineno++;
		      continue;
		   }
               else
                  if ( Character.isWhitespace( c ))
		         continue;
  		      else
                     if ( Character.isLetter( c ))
                     { // scan identifier starting with a letter
		            StringBuffer lexeme = new StringBuffer();
		            lexeme.append( c );
		            c = (char) brd.read();
		            while ( Character.isLetterOrDigit( c ))
                        { // scan identifier of letters and digits
			         lexeme.append( c );
			         c = (char) brd.read();
		            };
		            brd.unread( c );
		            for ( byte i = 0; i< Token.keywords.length; i++ )
			         if ( Token.keywords[ i ].contentEquals( lexeme ))
			            return (byte)( Token.fkwrd + i );
		            attrib = lexeme.toString();
		            return Token.ID;
		         }
                      else
                        if ( Character.isDigit( c ))
                        { // scan numeric literal
		               StringBuffer lexeme = new StringBuffer();
		               lexeme.append( c );
		               c = (char) brd.read();
		               while ( Character.isDigit( c ))
                           { // scan sequence of digits
			            lexeme.append( c );
			            c = (char) brd.read();
		               }
		               brd.unread( c );
		               attrib = Integer.valueOf( lexeme.toString() );

                           return Token.NUM;
		            }
                        else
                        {
		               for ( byte i = 0; i < Token.symbols.length; i++ )
			             if ( Token.symbols[ i ] == c )
			                return (byte)( Token.fsmbl + i );
		               throw new CompError( "Invalid \'" +c+ "\'", lineno );
		            }
	              }
	          }
                catch( IOException exn )
                {
                   throw new CompError("I/O error:" + exn.getMessage(),lineno );
	          }
         }
}

class CompError extends Exception
{
    CompError( String message, int lineno )
	{
	    super("Line " + lineno + ": " + message);
    }
}

// Syntactic analyzer for the SPL
final class Parser
{
   private Parser() {}
   static Scanner scaner;
   static byte tokn;

   static void EvError( String Ev ) throws CompError
   {
	throw new CompError("Eventual: " + Ev + " Found: " + Token.stringOf[tokn], scaner.lineno );
   }

   static void takeIt() throws CompError
   {
	tokn = scaner.lex();
   }

   static void take( byte evKind ) throws CompError
   {
	if ( tokn == evKind )
	   tokn = scaner.lex();
	else
	   EvError( Token.stringOf[ evKind ] );
   }

   // Parse the program
   static AST parse( Reader file ) throws CompError
   {
	scaner = new Scanner( file );
	tokn = scaner.lex();
	AST exp = parseAST();
	take( Token.EOF );
	return exp;
    }

    // Parse identifier
    static String parseId() throws CompError
    {
	 if ( tokn == Token.ID )
       {
	    String ide = (String) scaner.attrib;
	    takeIt();
	    return ide;
	 }
       else
       {
	    EvError( Token.stringOf[ Token.ID ] );
	    return "";
	}
    }

	 // Parse expression
     static AST parseAST() throws CompError
    {
	 if ( tokn == Token.LET )
       { // Parse let expression
	    takeIt();
	    String ide = parseId();
	    take( Token.EQ );
	    AST exp = parseAST();
	    return new LetAST( ide,exp );
	 }
       else
       { // Parse plus expression
	    AST el = parseTerm();
	    if ( tokn == Token.PLUS )
          {
		 takeIt();
		 AST er = parseTerm();
		 return new PlusAST( el,er );
	    }
          else return el;
	}
    }

     // Parse term
    static AST parseTerm() throws CompError
    {
	 if ( tokn == Token.NUM )
       { // Parse number
	    int num = ((Integer) scaner.attrib).intValue();
	    takeIt();
	    return new ConstAST( num );
	 }
       else
          if ( tokn == Token.LBRA )
          { // Parse block
	       takeIt();
	       ArrayList is = new ArrayList();
	       if ( tokn == Token.VAR )
             { // Parse variables
		    takeIt();
		    String ide = parseId();
		    is.add( ide );
		    while ( tokn != Token.SEMI )
                { // Parse list of variables
		       ide = parseId();
		       is.add( ide );
		    }
		    takeIt();
	    }
	    ArrayList es = new ArrayList();
	    AST exp = parseAST();
	    es.add( exp );
	    while ( tokn != Token.RBRA )
          { // Parse list of expressions
		 take( Token.SEMI );
		 exp = parseAST();
		 es.add( exp );
	    }
	    takeIt();
	    return new BlockAST(is,es);
	}
      else
          if ( tokn == Token.LPAR )
          { // Parse parenthesised expression
	       takeIt();
	       AST exp = parseAST();
	       take( Token.RPAR );
	       return exp;
     	    }
          else
          {
	       String ide = parseId();
	       return new VarAST( ide );
	    }
      }
}

class SPL
{
    public static void main( String argv[] )
    //public static void main()
    {
	   System.out.println();
	   System.out.println("-----------------------------------------------");
	   System.out.println(" SPL Compiler (Java version 1.0), Fall 2010. ");
	   System.out.println("-----------------------------------------------");

  	  try
      {
	    //Reader file = new FileReader( argv[ 0 ] );
	    Reader file = new FileReader( "prg.spl" );

        System.out.println();
		System.out.println (" Lexical and Syntax Analysis ( 1st pass )  ... " );
	    AST theAST = Parser.parse( file );
/*
        System.out.println();
		System.out.println (" Contextual Analysis         ( 2nd pass )  ... " );
		//boolean compiledOK = Checker.check( theAST );
		//if ( compiledOK )
		{
		      System.out.println();
		      System.out.println (" AST traversal and Interpretation ... " );
	          //int res = Interpreter.interpet( theAST );
	          //System.out.println( " Result = " + res );
		}*/
	  }
	  catch( FileNotFoundException ferr )
	  {
	     //System.err.println("File not found: " + argv[ 0 ]);
	     System.err.println("File not found ! ");
	  }
	  catch( CompError cerr )
	  {
	     System.err.println("Compiler error: " + cerr.getMessage());
	  }
      System.out.println();
   }
}