Go to the first, previous, next, last section, table of contents.


Processing Model

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

Translation Components

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).

Input

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.

Lexer

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 (DFAs). 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.

LexerInterpreter

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.

Parser

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.

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.

LRTranslatorInterpreter

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.

Translator

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.

components-scheme

(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.