This section describes the sequence of events that occur during a translation run and the components that are involved. Below is a graphical summary of how these components interact, refer to it as necessary.
SUMMARY OF PROCESSING MODEL (1) user invokes `trnsltr.translate(in)'. +-----------+ (2) trnsltr initializes Input with `in' argument. | | (3) trnsltr initializes Auditor (the error repository). | The User | (4) trnsltr invokes `lexer.start()', begins parse loop. | | (5) lexer returns, parse is complete. +-----------+ (6) trnsltr requests result Object from ParserInterpreter. || /\ (7) ParserInterpreter returns result. || (1) || (8) (8) trnsltr returns result to user, translation is complete. \/ || +------------------------------------------+ | Translator | +------------------------------------------+ || /\ /\ || || || (4) || (5) || (6,7) || (2) || >> \/ || || \/ || __ +---------------------+ +---+ || ' ` | Lexer | <---> |I | || (3) |M | +---------------------+ |N | \/ |A | || || | |P | +---+ |I | || (a) || `---------|U |--> |A | |N | \/ || |T | |U | | | +=====================+ | | |D t| |P | | LexerInterpreter | <---> | | |I h| |A | +=====================+ | | |T e| |R | || || | | | |O | |S | || (b) || `---------| |--> |R e| |E | \/ || | | | r| | | +---------------------+ | | | r| |L | | Parser | <---> | | | o| |O | +---------------------+ | | | r| |O | || /\ || | | | | | |P | || (c) || (d) || `---------| |--> | m| | | \/ || \/ | | | a| | | +=====================+ | | | n| | | | ParserInterpreter | <---> | | | a| `__' +=====================+ +---+ | g| | | e| << `----------------> | r| +---+ PARSE LOOP SUMMARY -------------------- (a) Lexer uses Input & DFA[] recognizes terminal character sequence (match event) calls `interpreter.match(int terminal_type, int offset, int length)' (b) LexerInterpreter interprets match event packages terminal as a Symbol calls `parser.notify(Symbol terminal)' (c) Parser uses Symbol & DPA recognizes nonterminal symbol sequence (reduction event) calls `interpreter.reduce(int production_type, Sentence stack)' (d) ParserInterpreter interprets reduction packages nonterminal as a Symbol returns nonterminal to Parser for inclusion on parse stack * All components may interact with Input and Auditor as necessary * LexerInterpreter and ParserInterpreter (double-lined boxes) are generally a single object that implements LRTranslatorInterpreter
There are several components that make up a translator. They are listed
here as interfaces, which is how they are exist in the API, but a
translator that has been generated by the STT
may or may not
retain these abstractions (for performance reasons).
Responsible for directly managing the input character sequence; it tracks position and line status. When the input has been exhausted, it will trigger an end-of-file signal.
Responsible for transforming the fine-grained sequence of
characters into a larger-grained sequence of tokens. It uses an
Input
object and a set of finite automatons (DFA
s). When
a token is recognized, it notifies the LexerInterpreter
that a token
recognition event has occurred; this event describes what token was
matched, where in the input the token starts, and how long the token is.
Context switching also occurs within the Lexer
.
Responsible for listening for lexer events, packaging tokens
as terminal symbols, and notifying the Parser
of these
terminals. It is therefore the intermediary between the Lexer and
the Parser that interprets lexer events.
Code within the LexerInterpreter
is typically a large switch
statement with a case for each token type. The user is
responsible for writing this code.
One of the advantages of using this type of event model is that
String
creation is minimized. No since most tokens are either
ignored (comments and whitespace) or syntactic placeholders (which carry
all their meaning in their name, such as a parenthesis), no
String
or array copying needs to occur in these instances. It
gives the user complete control of what is passed to the parser. For
example, if the LexerInterpreter
recieves an Identifier
event, it could do a keyword symbol table lookup and then pass the
correct keyword terminal to the parser.
This also gives a chance to instantiate terminals that may form part of the final syntax tree, minimizing transformations later in the processing cycle.
Responsible for transforming a serial stream of tokens into a syntax
tree; it employs an augmented finite automaton (DPA
) as the
recognition engine and maintains a parse stack of the symbols.
When the parser is notified of a terminal Symbol
, it consults the
DPA to see what to do. If the action is reduce, the parser will
delegate nonterminal construction to the ParserInterpreter
. This
delegation of Symbol
construction responsibility to the
ParserInterpreter
is analogous to the relationship between the
Lexer
and the LexerInterpreter
. When the
ParserInterpreter
returns, it passes back a nonterminal symbol to
be placed on the top of the parse stack as per normal shift-reduce
parsing.
When the DPA says accept, the accept()
method is called on
the ParserInterpreter
.
Responsible for listening for parse events and packaging
nonterminal symbols to the parser. When the parser sees that a
reduction is necessary, it sends the ParserInterpreter
a number
identifying what production needs to be reduced as well as another
object (called a Sentence
), which is the exposed top of the parse
stack. The ParserInterpreter
then decides what symbols in the
Sentence
(i.e. stack) to keep, packages them as a [new]
nonterminal, and returns that to the Parser
. The Parser
then places this symbol on the top of the (now reduced) parse stack.
Code within the ParserInterpreter
is typically a large switch
statement with a case for each production type. The user is
responsible for writing this code.
When the parser discovers a syntactic error, it consults the
ParserListener
for instruction on how to recover from the
error. The ParserListener formulates a list of corrections and
returns this to the parser for execution. When these corrections are
satisfied, normal parsing resumes.
Typically, the LexerInterpreter
and ParserInterpreter
are
a single object that implements LRTranslatorInterpreter
, which is
formed by the union of these interfaces. For examples, consult the
RegexpInterpreter
and the SyntacsInterpreter
classes.
The LRTranslatorInterpreter
has the additional responsibility of
packaging the final result for the Translator
. The translator
instance will retrieve this object through the getResult()
method. The interpreter only need return a meaningful result if the
input is accepted.
A Translator
is an object that abstracts the lower-level
structural analysis; it is the thing the user interacts with.
Internally, a Translator
may or may not use all of the other
components listed above. It manages initialization of the parse, runs
it, and then returns the result Object
to the user.
If the translation is not error-free, a TranslationException
is
thrown. This exception carries out the Auditor
(the repository
for errors and warnings) to the user.
In summary, a simplified schematic for the translation is given below.
(1) User invokes translate()
(2) Translator runs the internal parse loop
(3) Translator fetches the result from the Interpreter
(4) Result is returned to the User
Fig 2: Simplified Processing Model
Go to the first, previous, next, last section, table of contents.