tribble.io
Class Lr1Parser

java.lang.Object
  extended by tribble.io.Lr1Parser
All Implemented Interfaces:
DiagnosticWriterI, Lr1ParserI, ParserI

public abstract class Lr1Parser
extends java.lang.Object
implements Lr1ParserI, DiagnosticWriterI

Generic LR(1) parser.

This implements an LR(1) parser, as a deterministic finite automaton (DFA) with a push-down stack. It reads tokens from an input source stream (implementing the LexerI interface).

Since:
2001-08-11
Version:
$Revision: 1.7 $ $Date: 2003/02/26 04:42:09 $
Author:
David R. Tribble, david@tribble.com
Copyright 2002-2003 by David R. Tribble, all rights reserved.
Permission is granted to freely use and distribute this source code provided that the original copyright and authorship notices remain intact.
See Also:
LexerI, Lr1Parser

Field Summary
protected static short _A_ACCEPT
          Reserved action number: $accept.
protected static short _A_ERROR
          Reserved action number: $error.
protected  short[] _ACTION
          State transition action table.
protected  short[] _ACTION_LOOKUP
          State transition lookup table.
protected  boolean _debug
          Enable debugging tracing output.
protected  short[] _GOTO
          State reduction goto table.
protected  short[] _GOTO_LOOKUP
          State reduction goto lookup table.
protected  LexerI _lexer
          Lexer input stream.
protected  java.lang.String[] _NONTERM_ID
          Nonterminal symbol names.
protected  java.lang.Object[] _nStack
          Nonterminal stack, of user-defined type '%stacktype'.
protected  DiagnosticOutputI _out
          Output stream.
protected  java.lang.Object _r
          Rule reduction result value ('$$'), of user-defined type '%stacktype'.
protected  short[] _RHS_LEN
          Rule RHS lengths.
protected  java.lang.String[] _RULE_ID
          Rule names.
protected static int _SERIES
          LR(1) parsing table format number.
protected  java.lang.String _sourceName
          Input source (file) name.
protected  int _sp
          Current stack pointer (for all three stacks).
protected  short[] _sStack
          State stack, containing DFS state numbers.
protected  int _state
          Current DFA state number.
protected static short _T_ANY
          Reserved token code: $any.
protected static short _T_EMPTY
          Reserved token code: $empty.
protected static short _T_END
          Reserved token code: $end.
protected static short _T_ERROR
          Reserved token code: error.
protected  java.lang.String[] _TERM_ID
          Terminal symbol names.
protected  TokenI _tok
          Current lookahead token.
protected  int _tokCode
          Current token code (type).
protected  int _tokLine
          Current token line number.
protected  TokenI[] _tStack
          Terminal (token) stack, containing input terminal symbols.
(package private) static java.lang.String REV
          Revision information.
 
Constructor Summary
protected Lr1Parser(int series)
          Constructor.
protected Lr1Parser(int series, LexerI in)
          Constructor.
 
Method Summary
protected abstract  void _action(int n)
          Perform a specific user-defined action for a given grammar rule (production).
protected  int _getToken()
          Read the next token from the lexer input stream.
protected  boolean _resumeParse()
          Parse the token input stream, recognizing valid sentences of an LR(1) grammar.
 void close()
          Close the input stream.
protected  void finalize()
          Finalization.
 boolean parse()
          Parse the token input stream, recognizing valid sentences of an LR(1) grammar.
 void setInput(LexerI in)
          Establish the lexical analyzer (lexer) input stream from which to read tokens during parsing.
 void setOutput(DiagnosticOutputI out)
          Establish the output stream to which diagnostic messages (warning and error messages) are written during parsing.
 void setSourceName(java.lang.String fn)
          Establish the input source filename.
 
Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

REV

static final java.lang.String REV
Revision information.

See Also:
Constant Field Values

_SERIES

protected static final int _SERIES
LR(1) parsing table format number.

See Also:
Constant Field Values

_T_END

protected static final short _T_END
Reserved token code: $end.

See Also:
Constant Field Values

_T_ERROR

protected static final short _T_ERROR
Reserved token code: error.

See Also:
Constant Field Values

_T_ANY

protected static final short _T_ANY
Reserved token code: $any.

See Also:
Constant Field Values

_T_EMPTY

protected static final short _T_EMPTY
Reserved token code: $empty.

See Also:
Constant Field Values

_A_ACCEPT

protected static final short _A_ACCEPT
Reserved action number: $accept.

See Also:
Constant Field Values

_A_ERROR

protected static final short _A_ERROR
Reserved action number: $error.

See Also:
Constant Field Values

_TERM_ID

protected final java.lang.String[] _TERM_ID
Terminal symbol names.


_NONTERM_ID

protected final java.lang.String[] _NONTERM_ID
Nonterminal symbol names.


_RULE_ID

protected final java.lang.String[] _RULE_ID
Rule names.


_RHS_LEN

protected final short[] _RHS_LEN
Rule RHS lengths.


_ACTION_LOOKUP

protected final short[] _ACTION_LOOKUP
State transition lookup table.


_ACTION

protected final short[] _ACTION
State transition action table.


_GOTO_LOOKUP

protected final short[] _GOTO_LOOKUP
State reduction goto lookup table.


_GOTO

protected final short[] _GOTO
State reduction goto table.


_sStack

protected short[] _sStack
State stack, containing DFS state numbers.


_tStack

protected TokenI[] _tStack
Terminal (token) stack, containing input terminal symbols.


_nStack

protected java.lang.Object[] _nStack
Nonterminal stack, of user-defined type '%stacktype'. This is supplied by derived subclasses.


_sp

protected int _sp
Current stack pointer (for all three stacks).


_state

protected int _state
Current DFA state number.


_r

protected java.lang.Object _r
Rule reduction result value ('$$'), of user-defined type '%stacktype'. This is supplied by derived subclasses.


_tok

protected TokenI _tok
Current lookahead token.


_tokCode

protected int _tokCode
Current token code (type).


_tokLine

protected int _tokLine
Current token line number.


_lexer

protected LexerI _lexer
Lexer input stream.


_sourceName

protected java.lang.String _sourceName
Input source (file) name.


_out

protected DiagnosticOutputI _out
Output stream.


_debug

protected boolean _debug
Enable debugging tracing output.

Constructor Detail

Lr1Parser

protected Lr1Parser(int series)
Constructor.

Parameters:
series - LR(1) parser table format number. This must be compatible with _SERIES.
Since:
1.1, 2002-09-30

Lr1Parser

protected Lr1Parser(int series,
                    LexerI in)
Constructor.

Parameters:
series - LR(1) parser table format number. This must be compatible with _SERIES.
in - The lexer input stream from which to read tokens.
Since:
1.1, 2002-09-30
Method Detail

setOutput

public void setOutput(DiagnosticOutputI out)
Establish the output stream to which diagnostic messages (warning and error messages) are written during parsing.

Specified by:
setOutput in interface DiagnosticWriterI
Parameters:
out - The error output stream.
Since:
1.1, 2001-08-11

setInput

public void setInput(LexerI in)
Establish the lexical analyzer (lexer) input stream from which to read tokens during parsing.

Specified by:
setInput in interface ParserI
Parameters:
in - The lexer input stream from which to read tokens.
Since:
1.1, 2001-08-11

setSourceName

public void setSourceName(java.lang.String fn)
Establish the input source filename.

Specified by:
setSourceName in interface ParserI
Parameters:
fname - The source filename.
Since:
1.1, 2001-08-11

close

public void close()
Close the input stream.

It is typically not necessary to invoke this method since the input stream is usually closed automatically once parsing has completed, unless it is necessary to close the input stream deliberately or prematurely.

Note that this method does not throw any exceptions.

Specified by:
close in interface ParserI
Since:
1.1, 2001-08-11

parse

public boolean parse()
              throws java.lang.Exception
Parse the token input stream, recognizing valid sentences of an LR(1) grammar.

...

Specified by:
parse in interface ParserI
Returns:
True if the parse was successful (i.e., the sequence of tokens read from the input stream constitutes a valid sentence of the grammar), otherwise false.
Throws:
java.lang.Exception - Thrown if an I/O error or parsing error occurs.
Since:
1.1, 2001-08-11

_resumeParse

protected boolean _resumeParse()
                        throws java.lang.Exception
Parse the token input stream, recognizing valid sentences of an LR(1) grammar.

Returns:
True if the parse was successful (i.e., the sequence of tokens read from the input stream constitutes a valid sentence of the grammar), otherwise false.
Throws:
java.lang.Exception - Thrown if an I/O error or parsing error occurs.
Since:
1.1, 2002-10-07

_getToken

protected int _getToken()
                 throws java.io.IOException
Read the next token from the lexer input stream.

Returns:
A token code. Also sets _tokCode to the same token code, and sets _tok to the token object just read.
Throws:
java.io.IOException
Since:
1.1, 2001-08-28

_action

protected abstract void _action(int n)
                         throws java.lang.Exception
Perform a specific user-defined action for a given grammar rule (production).

Parameters:
n - The rule (production) number of the associated code block.
Throws:
java.lang.Exception - Thrown if an error (i.e., a semantic error) occurs.
Since:
1.2, 2002-10-29

finalize

protected void finalize()
                 throws java.lang.Throwable
Finalization. Closes and disassociates the lexer input stream and the diagnostic output stream from this parser.

Overrides:
finalize in class java.lang.Object
Throws:
java.lang.Throwable
Since:
1.6, 2003-02-24