// ParserDS.java

// ParserDS is a class to represent a recursive descent parser for the PL/0 
// programming language, described in Algorithms + Data Structures = Programs 
// by Niklaus Wirth, Prentice-Hall, 1976. The parser also constructs a symbol
// table as it processes declarations and a syntax tree representation of
// all executable constructions, according to the denotational semantics
// specification of these. At the end of each block, these are output.
// Type checking is also performed according to the denotational semantics
// specification.

public class ParserDS {

  protected PL0Lexer lexer;     // lexical analyzer
  protected Token token;        // current token

  public ParserDS () throws java.io.IOException {
    lexer = new PL0Lexer (System . in);
    getToken ();
  }

  private void getToken () throws java.io.IOException {
    token = lexer . nextToken ();
  }

  // program parses PL/0 programs.

  public SyntaxTree program (Environment env) throws java.io.IOException {
    SyntaxTree programTree = block (env);
    if (token . symbol () != TokenClass . PERIOD) 
      ErrorMessage . print (lexer . position (), ". expected");
    return programTree;
  }

  // block parses blocks. Both a local symbol table and syntax tree will be
  // created for the block. 

  public SyntaxTree block (Environment env) throws java.io.IOException {
    if (token . symbol () == TokenClass . CONST) {
      getToken ();
      constDeclaration (env);
      while (token . symbol () == TokenClass . COMMA) { 
        getToken (); 
        constDeclaration (env); 
      }
      if (token . symbol () == TokenClass . SEMICOLON) 
        getToken (); 
      else 
        ErrorMessage . print (lexer . position (), ", or ; expected");
    }
    if (token . symbol () == TokenClass . VAR) {
      getToken ();
      varDeclaration (env);
      while (token . symbol () == TokenClass . COMMA) {
        getToken (); 
        varDeclaration (env); 
      }
      if (token . symbol () == TokenClass . SEMICOLON) 
        getToken (); 
      else 
        ErrorMessage . print (lexer . position (), ", or ; expected");
    }
    while (token . symbol () == TokenClass . PROC) {
      getToken ();
      String procId = null;
      if (token . symbol () == TokenClass . ID) { 
        procId = token . lexeme ();
        getToken ();
      }
      else 
        ErrorMessage . print (lexer . position (), "Id expected");
      env . updateEnvProc (procId); // enter proc id for recursive calls
      if (token . symbol () == TokenClass . SEMICOLON) 
        getToken (); 
      else 
        ErrorMessage . print (lexer . position (), "; expected");
      Environment blockEnv = env . newBlock ();
      SyntaxTree blockTree = block (blockEnv);
      if (token . symbol () == TokenClass . SEMICOLON) 
        getToken (); 
      else 
        ErrorMessage . print (lexer . position (), "; expected");
      env . updateEnvProc (procId, blockTree, blockEnv);
    }
    SyntaxTree statementTree = statement (env);
    return statementTree;
  }

  // constDeclaration parses constant declarations, entering the identifiers
  // into the symbol table as constants.

  public void constDeclaration (Environment env) throws java.io.IOException {
    String id;
    if (token . symbol () == TokenClass . ID) {
      id = token . lexeme ();
      getToken ();
      if (token . symbol () == TokenClass . EQ) {
        getToken ();
        if (token . symbol () == TokenClass . INTEGER) { 
          env . updateEnvConst (id, new Integer (token . lexeme ())); 
          getToken (); 
        }
        else 
          ErrorMessage . print (lexer . position (), "Integer expected");
      }
      else ErrorMessage . print (lexer . position (), "= expected");
    }
    else ErrorMessage . print (lexer . position (), "Id expected");
  }

  // varDeclaration parses variable declarations, entering the identifiers
  // into the symbol table as variables.

  public void varDeclaration (Environment env) throws java.io.IOException {
    if (token . symbol () == TokenClass . ID) {
      env . updateEnvVar (token . lexeme ()); 
      getToken (); 
    }
    else 
      ErrorMessage . print (lexer . position (), "Id expected");
  }

  // statement parses and constructs a syntax tree for statements.

  public SyntaxTree statement (Environment env) throws java.io.IOException {
    DenotableValue denotVal;
    String id;
    SyntaxTree conditionTree, expressionTree, idTree;
    SyntaxTree statementTree, statement2Tree;

    switch (token . symbol ()) {

      case ID :
        id = token . lexeme ();
        denotVal = env . accessEnv (id);
        if (denotVal . category () != Category . VARIABLE)
          ErrorMessage . print ("Assignment to non variable " + id);
        idTree = 
          new SyntaxTree ("id", 
            new SyntaxTree (id,
              new SyntaxTree (denotVal . value ())));
        getToken ();
        if (token . symbol () == TokenClass . ASSIGN) 
          getToken (); 
        else 
          ErrorMessage . print (lexer . position (), ":= expected");
        expressionTree = expression (env);
        statementTree = new SyntaxTree (":=", idTree, expressionTree);
        break;

      case CALL :
        getToken ();
        if (token . symbol () != TokenClass . ID) 
	  ErrorMessage . print (lexer . position (), "Id expected");
        id = token . lexeme ();
        denotVal = env . accessEnv (id);
        if (denotVal . category () != Category . PROCEDURE)
          ErrorMessage . print ("Call to non procedure " + id);
        idTree = 
          new SyntaxTree ("id", 
            new SyntaxTree (id, 
              new SyntaxTree (env . location (), // storage info for caller
                ((Procedure) denotVal . value ()) . syntaxTree ())));
        statementTree = new SyntaxTree ("call", idTree);
        getToken ();
        break;

      case IF :
        getToken ();
        conditionTree = condition (env);
        if (token . symbol () == TokenClass . THEN) 
          getToken (); 
        else 
          ErrorMessage . print (lexer . position (), "then expected");
        statementTree = statement (env);
        statementTree = 
	  new SyntaxTree ("if-then", conditionTree, statementTree);
        break;

      case BEGIN :
        getToken ();
        statementTree = statement (env);
        while (token . symbol () == TokenClass . SEMICOLON) {
	  getToken (); 
	  statement2Tree = statement (env); 
          statementTree = new SyntaxTree (";", statementTree, statement2Tree);
        }
        if (token . symbol () == TokenClass . END) 
          getToken (); 
        else 
          ErrorMessage . print (lexer . position (), "end or ; expected");
        break;

      case WHILE :
        getToken ();
        conditionTree = condition (env);
        if (token . symbol () == TokenClass . DO) 
          getToken (); 
        else 
          ErrorMessage . print (lexer . position (), "do expected");
        statementTree = statement (env);
        statementTree =
          new SyntaxTree ("while-do", conditionTree, statementTree);
        break;

      default : statementTree = new SyntaxTree ("nil");
    }
    return statementTree;
  }

  // condition parses and constructs a syntax tree for conditions.

  public SyntaxTree condition (Environment env) 
      throws java.io.IOException {
    String op = null;
    SyntaxTree conditionTree, expression1Tree, expression2Tree;
    if (token . symbol () == TokenClass . ODD) { 
      getToken (); 
      expression1Tree = expression (env); 
      conditionTree = new SyntaxTree ("odd", expression1Tree);
    }
    else {
      expression1Tree = expression (env);
      switch (token . symbol ()) {
        case EQ : op = "=";  break;
        case LT : op = "<";  break;
        case GT : op = ">";  break;
        case NE : op = "<>"; break;
        case LE : op = "<="; break;
        case GE : op = ">="; break;
        default : 
	  ErrorMessage . print (lexer . position (), "Relational operator expected");
      }
      getToken (); 
      expression2Tree = expression (env); 
      conditionTree = new SyntaxTree (op, expression1Tree, expression2Tree);
    }
    return conditionTree;
  }

  // expression parses and constructs a syntax tree for expressions.

  public SyntaxTree expression (Environment env) 
      throws java.io.IOException {
    String op;
    SyntaxTree expressionTree, termTree;
    if (token . symbol () == TokenClass . PLUS || 
	token . symbol () == TokenClass . MINUS) { 
      if (token . symbol () == TokenClass . PLUS) op = "+"; else op = "-";
      getToken (); 
      termTree = term (env); 
      expressionTree = new SyntaxTree (op, termTree);
    } 
    else 
      expressionTree = term (env);
    while (token . symbol () == TokenClass . PLUS || 
	token . symbol () == TokenClass . MINUS) {
      if (token . symbol () == TokenClass . PLUS) op = "+"; else op = "-";
      getToken (); 
      termTree = term (env); 
      expressionTree = new SyntaxTree (op, expressionTree, termTree);
    }
    return expressionTree;
  }

  // term parses and constructs a syntax tree for terms.

  public SyntaxTree term (Environment env) throws java.io.IOException {
    String op;
    SyntaxTree factorTree, termTree;
    termTree = factor (env);
    while (token . symbol () == TokenClass . TIMES || 
	token . symbol () == TokenClass . SLASH) { 
      if (token . symbol () == TokenClass . TIMES) op = "*"; else op = "/";
      getToken (); 
      factorTree = factor (env); 
      termTree = new SyntaxTree (op, termTree, factorTree);
    }
    return termTree;
  }

  // factor parses and constructs a syntax tree for factors.

  public SyntaxTree factor (Environment env) throws java.io.IOException {
    SyntaxTree factorTree = null, idTree, intTree;
    if (token . symbol () == TokenClass . ID) {
      String id = token . lexeme ();
      DenotableValue denotVal = env . accessEnv (id);
      if (denotVal . category () == Category . CONSTANT)
        factorTree = 
          new SyntaxTree ("int", 
            new SyntaxTree (denotVal . value (),
              new SyntaxTree (id)));
      else if (denotVal . category () == Category . VARIABLE)
        factorTree = 
          new SyntaxTree ("id", 
            new SyntaxTree (id,
              new SyntaxTree (denotVal . value ())));
      else
        ErrorMessage . print ("Id " + id + " not constant or variable");
      getToken ();
    }
    else if (token . symbol () == TokenClass . INTEGER) {
      factorTree = 
        new SyntaxTree ("int", 
          new SyntaxTree (new Integer (token . lexeme ())));
      getToken ();
    }
    else if (token . symbol () == TokenClass . LPAREN) {
      getToken ();
      factorTree = expression (env);
      if (token . symbol () == TokenClass . RPAREN) 
        getToken (); 
      else 
        ErrorMessage . print (lexer . position (), "Missing )");
    }
    else 
      ErrorMessage . print (lexer . position (), "Unrecognizable symbol");
    return factorTree;
  }

}