/**
 * This class consists of a number of methods that "recognize" strings
 * composed of Tokens that follow the indicated grammar rules for each
 * method.
 * <p>Each method may have one of three outcomes:
 * <ul>
 *   <li>The method may succeed, returning <code>true</code> and
 *      consuming the tokens that make up that particular nonterminal.</li>
 *   <li>The method may fail, returning <code>false</code> and not
 *       consuming any tokens.</li>
 *   <li>(Some methods only) The method may determine that an
 *       unrecoverable error has occurred and throw a
 *       <code>LogoException</code>.</li>
 * </ul>
 * @author David Matuszek
 * @version Jan 30, 2006.
 */
public class Recognizer {
    Tokenizer tokenizer = null;

    /**
     * Constructs a Recognizer for the given string.
     * @param text The string to be recognized.
     */
    public Recognizer(String text) {
        tokenizer = new Tokenizer(text);
    }

    /**
     * Tries to recognize an &lt;expression&gt;.
     * <pre>&lt;expression&gt; ::= &lt;term&gt; { &lt;addOperator&gt; &lt;expression&gt; }</pre>
     * A <code>LogoException</code> will be thrown if the &lt;addOperator&gt;
     * is present but not followed by a valid &lt;expression&gt;.
     * @return <code>true</code> if an expression is recognized.
     */
    public boolean expression() {
        if (!term()) return false;
        while (addOperator()) {
            if (!expression()) error("Error in expression after '+' or '-'");
        }
        return true;
    }

    /**
     * Tries to recognize a &lt;term&gt;.
     * <pre>&lt;term&gt; ::= &lt;factor&gt; { &lt;multiplyOperator&gt; &lt;term&gt;}</pre>
     * A <code>LogoException</code> will be thrown if the
     * &lt;multiplyOperator&gt; is present but not followed by a
     * valid &lt;term&gt;.
     * @return <code>true</code> if a term is recognized.
     */
    public boolean term() {
        if (!factor()) return false;
        while (multiplyOperator()) {
            if (!term()) error("No term after '+' or '-'");
        }
        return true;
    }

    /**
     * Tries to recognize a &lt;factor&gt;.
     * <pre>&lt;factor&gt; ::= &lt;name&gt;
     *           | &lt;number&gt;
     *           | "(" &lt;expression&gt; ")"</pre>
     * A <code>LogoException</code> will be thrown if the opening
     * parenthesis is present but not followed by a valid
     * &lt;expression&gt; and a closing parenthesis.
     * @return <code>true</code> if a factor is recognized.
     */
    public boolean factor() {
        if (name()) return true;
        if (number()) return true;
        if (symbol("(")) {
            if (!expression()) error("Error in parenthesized expression");
            if (!symbol(")")) error("Unclosed parenthetical expression");
            return true;
       }
       return false;
    }
    
    /**
     * Tries to recognize a &lt;disjunct&gt;.
     * <pre>&lt;disjunct&gt; ::= &lt;conjunct&gt; { "and" &lt;conjunct&gt; }</pre>
     * A <code>LogoException</code> will be thrown if the word "and"
     * is present but not followed by a valid &lt;conjunct&gt;.
     * @return <code>true</code> if a disjunct is recognized.
     */
    public boolean disjunct() {
        if (!conjunct()) return false;
        while (name("and")) {
            if (!conjunct()) error("Error after \"and\" in  ondition");
        }
        return true;
    }
    
    /**
     * Tries to recognize a &lt;conjunct&gt;.
     * <pre>&lt;conjunct&gt; ::= [ "not" ] &lt;logicalFactor&gt;</pre>
     * @return <code>true</code> if a conjunct is recognized.
     */
    public boolean conjunct() {
        if (name("not")) {
            if (logicalFactor()) return true;
            else {
                error("Error after \"not\" in logical expression");
                return false; // Cannot get here, but required by Java
            }
        }
        else return logicalFactor();
    }
    
    /**
     * Tries to recognize a &lt;logicalFactor&gt;, which is now
     * just the same as a &lt;comparison&gt;.
     * <pre>&lt;logicalFactor&gt; ::= &lt;comparison&gt;</pre>
     * @return <code>true</code> if a logical factor is recognized.
     */
    public boolean logicalFactor() {
        return comparison();
    }

    /**
     * Tries to recognize an &lt;addOperator&gt;.
     * <pre>&lt;addOperator&gt; ::= "+" | "-"</pre>
     * @return <code>true</code> if a "+" or "-" is recognized.
     */
    public boolean addOperator() {
        return symbol("+") || symbol("-");
    }

    /**
     * Tries to recognize a &lt;multiplyOperator&gt;.
     * <pre>&lt;multiplyOperator&gt; ::= "*" | "/"</pre>
     * @return <code>true</code> if a "*" or "/" is recognized.
     */
    public boolean multiplyOperator() {
        return symbol("*") || symbol("/");
    }

    /**
     * Tries to recognize a &lt;variable&gt;, which is
     * just a &lt;name&gt;.
     * <pre>&lt;variable&gt; ::= &lt;name&gt;</pre>
     * @return <code>true</code> if a variable is recognized.
     */
    public boolean variable() {
//        if (name("end")) {
//            tokenizer.putBack(1);
//            return false;
//        }
        return name();
    }
    
    /**
     * Tries to recognize a &lt;command&gt;.
     * <pre>&lt;command&gt; ::= "move" &lt;expression&gt; &lt;eol&gt;
     *            | "turn" &lt;direction&gt; &lt;eol&gt;
     *            | "penup" &lt;eol&gt;
     *            | "pendown" &lt;eol&gt;
     *            | "color" &lt;colorName&gt; &lt;eol&gt;
     *            | "home" &lt;eol&gt;
     *            | &lt;variable&gt; "=" &lt;expression&gt; &lt;eol&gt;
     *            | "repeat" &lt;expression&gt; &lt;block&gt;
     *            | "while" &lt;condition&gt; &lt;block&gt; 
     *            | "if" &lt;condition&gt; &lt;block&gt; [ "else" &lt;block&gt; ]
     *            | "call" &lt;NAME&gt; { &lt;expression&gt; } &lt;eol&gt;</pre>
     * @return <code>true</code> if a command is recognized.
     */
     public boolean command() {
         if (name("move")) {
             if (!expression()) error("No expression after \"move\"");
             if (eol()) return true;
             else error("Unexpected characters after \"move\"");
         }
         if (name("turn")) {
            if (!direction()) error("Incorrect amount for \"turn\"");
            if (eol()) return true;
            else error("Unexpected characters after \"turn\"");
        }
        if (name("penup"))  {
            if (eol()) return true;
            else error("Unexpected characters after \"penup\"");
        }
        if (name("pendown"))  {
            if (eol()) return true;
            else error("Unexpected characters after \"penup\"");
        }
        if (name("color"))  {
            if (!colorName()) error("Unexpected characters after \"color\"");
            if (!eol()) error("Garbage after color command");
            return true;
        }
        if (name("home"))  {
            if (eol()) return true;
            else error("Unexpected characters after \"penup\"");
        }
        if (name())  {
            if (symbol("=")) {
                if (!expression()) error("\"variable =\" must be followed by an expression");
                if (!eol()) error("Garbage after \"=\" in assignment command");
                return true;
            }
            else {
                tokenizer.putBack(1);
            }
        }
        if (name("repeat"))  {
            if (!expression()) error("\"repeat\" must be followed by an expression");
            if (!block()) error("\"repeat <expression>\" must be followed by a \"[\"");
            return true;
        }
        if (name("while"))  {
            if (!condition()) error("\"while\" must be followed by a condition");
            if (!block()) error("\"while <condition>\" must be followed by a \"[\"");
            return true;
        }
        if (name("if"))  {
            if (!condition()) error("\"if\" must be followed by a condition");
            if (!block()) error("\"if <condition>\" must be followed by a \"[\"");
            return true;
        }
        if (name("call"))  {
            if (!variable()) error("\"call\" must be followed by a name");
            while (expression()) {}
            if (!eol()) error("Garbage after color command");
            return true;
        }     
        return false;
    }

    /**
     * Tries to recognize a &lt;direction&gt;.<br>
     * <pre>&lt;direction&gt; ::= "north"
               | "east"
               | "south"
               | "west"
               | "left" [ &lt;expression&gt; ]
               | "right" [ &lt;expression&gt; ]</pre><br>
                        
     * @return <code>true</code> if a direction is recognized.
     */
    private boolean direction() {
        if (name("north")) return true;
        if (name("south")) return true;
        if (name("east"))  return true;
        if (name("west"))  return true;
        if (name("left") || name("right")) {
            if (peekAhead(Type.EOL, "\n")) return true;
            if (expression()) return true;
            else error("Unexpected characters after  \"left\" or \"right\" command");
        }
        return false;
    }

    /**
     * Tries to recognize the name of a color. Recognized names are:
     * magenta, red, orange, yellow, green, aqua, blue, purple, violet,
     * brown, black, charcoal, gray, grey, white, pink.
     * 
     * @return <code>true</code> if the next Token corresponds to a
     *         known color name.
     */
    public boolean colorName() {
        if (name("magenta"))  return true;
        if (name("red"))      return true;
        if (name("orange"))   return true;
        if (name("yellow"))   return true;
        if (name("green"))    return true;
        if (name("aqua"))     return true;
        if (name("blue"))     return true;
        if (name("purple"))   return true;
        if (name("violet"))   return true;
        if (name("brown"))    return true;
        if (name("black"))    return true;
        if (name("charcoal")) return true;
        if (name("gray"))     return true;
        if (name("grey"))     return true;
        if (name("white"))    return true;
        if (name("pink"))     return true;
        return false;
    }

    /**
     * Tries to recognize a block.<br>
     * &lt;block&gt; ::= "[" &lt;eol&gt; { &lt;command&gt; } "]" &lt;eol&gt;
     * @return <code>true</code> if a block is recognized.
     */
    public boolean block() {
        if (!symbol("[")) return false;
        if (!eol()) error("\"[\" must be last thing on the line");
        while (command()) {}
        if (symbol("]") && eol()) return true;
        error("Illegal block contents");
        return false;
    }
    
    /**
     * Tries to recognize a &lt;condition&gt;.<br>
     * <pre>&lt;condition&gt; ::= &lt;disjunct&gt; { "or" &lt;disjunct&gt;}</pre>
     * 
     * @return <code>true</code> if a condition is recognized.
     */
    public boolean condition() {
        if (!disjunct()) return false;
        while (name("or")) {
            if (!disjunct()) error("Error after \"or\" in condition");
        }
        return true;
    }

    
    /**
     * Tries to recognize a &lt;comparison&gt;.<br>
     * <pre>&lt;comparison&gt; ::=
     *  &lt;expression&gt; &lt;comparator&gt; &lt;expression&gt;</pre>
     *  
     * @return <code>true</code> if a condition is recognized.
     */
    public boolean comparison() {
        if (!expression())
            return false;
        if (!comparator()) {
            error("Expected a condition but just found an expression");
        }
        if (expression()) return true;
        error("Illegal expression after '<', '=', or '>'");
        return false;
    }
    
    /**
     * Tries to recognize a &lt;comparator&gt;.<br>
     * <pre>&lt;comparator&gt; ::= "&lt;" | "=" | "&gt;"</pre>
     * 
     * @return <code>true</code> if a condition is recognized.
     */
    public boolean comparator() {
        if (symbol("<")) return true;
        if (symbol("=")) return true;
        if (symbol(">")) return true;
        return false;
    }
    
    /**
     * Tries to recognize an end-of-line character.
     * 
     * @return <code>true</code> if an end-of-line character is recognized.
     */
    public boolean eol() {
        return nextTokenMatches(Type.EOL);
    }
    
    /**
     * Tries to recognize a &lt;procedure&gt;.<br>
     * 
     * <pre>&lt;procedure&gt; ::= &quot;define&quot; &lt;NAME&gt; { &lt;variable&gt; } &lt;eol&gt;
     *               { &lt;command&gt; } &quot;end&quot; &lt;eol&gt;</pre>
     * @return <code>true</code> if a procedure is recognized.
     */
    public boolean procedure() {
        if (!name("define")) return false;
        if (!name()) {
            error("Error in procedure--\"define\" must be followed by a name");
        }
        while (name()) {}
        if (!eol()) {
            error("Error in parameter list of procedure");
        }
        while (command()) {}
        if (!name("end")) {
            error("Error in some command of a procedure");
        }
        if (!eol()) {
            error("Procedure \"end\" not followed by end of line");
        }
        return true;
    }
    
    /**
     * Tries to recognize a &lt;program&gt;.<br>
     * <pre>&lt;program&gt; ::= &lt;command&gt; { &lt;command&gt; } { &lt;procedure&gt; }</pre>
     * 
     * @return <code>true</code> if a program is recognized.
     */
    
    public boolean program() {
        if (!command()) return false;
        while (command()) {}
        if (nextTokenMatches(Type.END_OF_INPUT)) return true;
        while (procedure()) {}
        return nextTokenMatches(Type.END_OF_INPUT);
    }


//----- Private "helper" methods

  /**
   * Tests whether the next token is a number. If it is, the token
   * is consumed, otherwise it is not.
   *
   * @return <code>true</code> if the next token is a number.
   */
      private boolean number() {
        return nextTokenMatches(Type.NUMBER);
    }

    /**
     * Tests whether the next token is a name. If it is, the token
     * is consumed, otherwise it is not.
     *
     * @return <code>true</code> if the next token is a name.
     */
    private boolean name() {
        return nextTokenMatches(Type.NAME);
    }

    /**
     * Tests whether the next token is the expected name. If it is, the token
     * is consumed, otherwise it is not.
     *
     * @param expectedName The String value of the expected next token.
     * @return <code>true</code> if the next token is a name with the expected value.
     */
    private boolean name(String expectedName) {
        return nextTokenMatches(Type.NAME, expectedName);
    }

    /**
     * Tests whether the next token is the expected symbol. If it is,
     * the token is consumed, otherwise it is not.
     *
     * @param expectedSymbol The String value of the token we expect
     *    to encounter next.
     * @return <code>true</code> if the next token is the expected symbol.
     */
    private boolean symbol(String expectedSymbol) {
        return nextTokenMatches(Type.SYMBOL, expectedSymbol);
    }

    /**
     * Tests whether the next token has the expected type. If it does,
     * the token is consumed, otherwise it is not. This method would
     * normally be used only when the token's value is not relevant.
     *
     * @param type The expected type of the next token.
     * @return <code>true</code> if the next token has the expected type.
     */
    private boolean nextTokenMatches(Type type) {
        Token t = (Token)tokenizer.next();
        if (t.type == type) return true;
        else tokenizer.putBack(1);
        return false;
    }

    /**
     * Tests whether the next token has the expected type and value.
     * If it does, the token is consumed, otherwise it is not. This
     * method would normally be used when the token's value is
     * important.
     *
     * @param type The expected type of the next token.
     * @param value The expected value of the next token; must
     *              not be <code>null</code>.
     * @return <code>true</code> if the next token has the expected type.
     */
    private boolean nextTokenMatches(Type type, String value) {
        Token t = (Token)tokenizer.next();
        if (type == t.type && value.equals(t.value)) return true;
        else tokenizer.putBack(1);
        return false;
    }
    
    /**
     * Peeks at the next token to see whether it has the expected
     * type and value, but (in either case) does not consume that
     * token.
     * 
     * @param type The type of the expected Token.
     * @param value The value of the expected Token.
     * @return <code>true</code> if the next Token is as expected.
     */
    private boolean peekAhead(Type type, String value) {
        if (!tokenizer.hasNext()) return false;
        Token t = (Token)tokenizer.next();
        tokenizer.putBack(1);
        return (type == t.type && value.equals(t.value));
    }

    /**
     * Utility routine to throw a <code>LogoException</code> with the
     * given message.
     * @param message The text to put in the <code>LogoException</code>.
     */
    private void error(String message) {
        throw new LogoException(message);
    }
}