tribble.io
Class Lr1Parser

java.lang.Object
  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