fri.patterns.interpreter.parsergenerator
Class Parser

java.lang.Object
  |
  +--fri.patterns.interpreter.parsergenerator.Parser
All Implemented Interfaces:
java.io.Serializable

public class Parser
extends java.lang.Object
implements java.io.Serializable

The universal bottom-up parser algorithm. Runs with a Lexer (containing the input), ParserTables (containing the syntax), and a Semantic (optional).

        private static final String [][] syntax =	{
                { "Start", "\"Hello\"", "\"World\"" },
                { Token.IGNORED, "`whitespaces`" },
        };

        SyntaxSeparation separation = new SyntaxSeparation(new Syntax(syntax));
        LexerBuilder builder = new LexerBuilder(separation.getLexerSyntax(), separation.getIgnoredSymbols());
        Lexer lexer = builder.getLexer();
        lexer.setInput("\tHello \r\n\tWorld\n");
        ParserTables parserTables = new SLRParserTables(separation.getParserSyntax());
        Parser parser = new Parser(parserTables);
        parser.parse(lexer, new PrintSemantic());
        
TODO: implement error recovery: method recover()

Author:
(c) 2000, Fritz Ritzberger
See Also:
Serialized Form

Field Summary
protected  java.util.Stack rangeStack
           
protected  java.util.Stack stateStack
           
protected  java.util.Stack valueStack
           
 
Constructor Summary
Parser(ParserTables tables)
          Create a generic bottom-up Parser with passed ParserTables (representing the current syntax to apply).
 
Method Summary
protected  boolean detectError(Token token, java.lang.Integer state, java.lang.Integer action)
          Called after parse loop to determine if everything was OK.
 Lexer getLexer()
          Returns the lexer that was set to this parser, to call setInput() to the lexer.
protected  Token getNextToken()
          Delivers the next token from lexer to parser.
 ParserTables getParserTables()
          Returns current ParserTables.
 java.lang.Object getResult()
          Returns the parsing result built from Semantic call return values.
 Semantic getSemantic()
          Returns the semantic that was set to this parser.
 boolean parse()
          Start parsing after setting Lexer and optionally Semantic.
 boolean parse(Lexer lexer)
          Parse the tokens returned from passed lexer.
 boolean parse(Lexer lexer, Semantic semantic)
          Parse the tokens returned from passed lexer.
 boolean parse(java.lang.Object input)
          Parse the tokens returned from passed input.
 boolean parse(java.lang.Object input, Semantic semantic)
          Parse the tokens returned from passed lexer.
 boolean parse(Semantic semantic)
          Parse the tokens returned from passed lexer.
protected  java.lang.Integer recover(java.lang.Integer action, Token token)
          Recover from error.
protected  void reduce(java.lang.Integer ruleIndex)
          Reduce a rule when input satisfied it.
 void setDebug(boolean debug)
          Set the debug mode.
 void setInput(java.lang.Object input)
          Sets the input to contained lexer, or throws IllegalStateException if no lexer was set.
 void setLexer(Lexer lexer)
          Sets the lexer to be used for parsing.
 void setPassExpectedToLexer(boolean passExpectedToLexer)
          Default is true.
 void setPrintStream(java.io.PrintStream out)
          Debug output will go to passed stream.
 void setSemantic(Semantic semantic)
          Sets the semantic to be applied to parsing results.
protected  Token shift(Token token)
          Push a new state upon state stack, determined by the GOTO table with current state and the received token symbol.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

stateStack

protected java.util.Stack stateStack

valueStack

protected java.util.Stack valueStack

rangeStack

protected java.util.Stack rangeStack
Constructor Detail

Parser

public Parser(ParserTables tables)
Create a generic bottom-up Parser with passed ParserTables (representing the current syntax to apply).

Parameters:
tables - ParserTables representing the syntax.
Method Detail

getResult

public java.lang.Object getResult()
Returns the parsing result built from Semantic call return values. Retrievable after parsing.


setLexer

public void setLexer(Lexer lexer)
Sets the lexer to be used for parsing. The Lexer contains (or will contain) the input to parse. The Parser calls setTerminals() on this call.


getLexer

public Lexer getLexer()
Returns the lexer that was set to this parser, to call setInput() to the lexer.


setInput

public void setInput(java.lang.Object input)
              throws java.io.IOException
Sets the input to contained lexer, or throws IllegalStateException if no lexer was set.

java.io.IOException

setSemantic

public void setSemantic(Semantic semantic)
Sets the semantic to be applied to parsing results.


getSemantic

public Semantic getSemantic()
Returns the semantic that was set to this parser.


getParserTables

public ParserTables getParserTables()
Returns current ParserTables.


setPassExpectedToLexer

public void setPassExpectedToLexer(boolean passExpectedToLexer)
Default is true. When true, the Parser will pass a Map of expected symbols to Lexer at every token request.


reduce

protected void reduce(java.lang.Integer ruleIndex)
Reduce a rule when input satisfied it. Pop the stack n times, n is the number of right symbols of the rule. Semantic gets called with all input tokens corresponding to the rule, if not null. A new state gets pushed, determined by the new state (after pops) and the nonterminal of the rule (left side).


shift

protected Token shift(Token token)
               throws java.io.IOException
Push a new state upon state stack, determined by the GOTO table with current state and the received token symbol. Then read a new token from Lexer, trying to evaluate a rule.

java.io.IOException

getNextToken

protected Token getNextToken()
                      throws java.io.IOException
Delivers the next token from lexer to parser. Override to convert the Token value.

java.io.IOException

parse

public boolean parse(Lexer lexer)
              throws java.io.IOException
Parse the tokens returned from passed lexer. This call is for checking correctness without semantics.

Parameters:
lexer - the Lexer, loaded with input to scan.
Returns:
true when input was syntactically correct.
java.io.IOException

parse

public boolean parse(Semantic semantic)
              throws java.io.IOException
Parse the tokens returned from passed lexer. This call is for processing input with semantics. At least setLexer() must have been called before.

Parameters:
semantic - the semantic to apply to parser results.
Returns:
true when input was syntactically correct.
java.io.IOException

parse

public boolean parse(java.lang.Object input)
              throws java.io.IOException
Parse the tokens returned from passed input. At least setLexer() must have been called before.

Parameters:
input - the input to parse, as File, InputStream, String, ....
Returns:
true when input was syntactically correct.
java.io.IOException

parse

public boolean parse(Lexer lexer,
                     Semantic semantic)
              throws java.io.IOException
Parse the tokens returned from passed lexer. This call is for integrating a semantic.

Parameters:
lexer - Lexer containing the input to parse
semantic - the semantic to apply to parser results.
Returns:
true when input was syntactically correct.
java.io.IOException

parse

public boolean parse(java.lang.Object input,
                     Semantic semantic)
              throws java.io.IOException
Parse the tokens returned from passed lexer. This call is for integrating a semantic.

Parameters:
input - the input to parse, as File, InputStream, String, ....
semantic - the semantic to apply to parser results.
Returns:
true when input was syntactically correct.
java.io.IOException

parse

public boolean parse()
              throws java.io.IOException
Start parsing after setting Lexer and optionally Semantic. At least setLexer() must have been called before.

Init the parser, read first token, push state 0 and set action to SHIFT. Loop while action is not ERROR or ACCEPT, and token symbol is not ERROR, and top of stack is not ERROR. Within loop, get next action from PARSE-ACTION table using current state and token symbol. When action greater than zero, call reduce(), else when action is SHIFT, call shift().

Returns:
true when input was syntactically correct.
java.io.IOException

recover

protected java.lang.Integer recover(java.lang.Integer action,
                                    Token token)
Recover from error. Not implemented.

Parameters:
action - current action from PARSE-ACTION table.
token - recently received Token.
Returns:
action to proceed with. Token.symbol may not be null and current state may not be ERROR after this call.

detectError

protected boolean detectError(Token token,
                              java.lang.Integer state,
                              java.lang.Integer action)
Called after parse loop to determine if everything was OK.

Returns:
true when action is ACCEPT, token.symbol is EPSILON, and state is not ERROR.

setPrintStream

public void setPrintStream(java.io.PrintStream out)
Debug output will go to passed stream.


setDebug

public void setDebug(boolean debug)
Set the debug mode.