Generic Interpreter 0.9
Private API

gi
Class LL1_Grammar

java.lang.Object
  |
  +--gi.Lexicon
        |
        +--gi.Grammar
              |
              +--gi.LL1_Grammar

public class LL1_Grammar
extends Grammar

This class implements an LL(1) parser around a Grammar. The parser adapts to changes in the underlying Grammar. Semantics in a phrase are evaluated during a top-down left-to-right recursive descent parse, when they are first visited. Attributes above or to the left of the Semantics are available during evaluation. A Grammar with left-recursive productions can cause infinite recursion, unless productions that terminate recursion have priority over productions that recurse.

Version:
0.9
Author:
© 1999-2000 Craig A. Rich <carich@acm.org>
See Also:
Source code

Inner classes inherited from class gi.Grammar
Grammar.ParseTree, Grammar.Production, Grammar.Semantics
 
Inner classes inherited from class gi.Lexicon
Lexicon.Alphabet, Lexicon.Concatenation, Lexicon.Exception, Lexicon.Expression, Lexicon.Match, Lexicon.NonMatch, Lexicon.PosixClass, Lexicon.Range, Lexicon.Repetition, Lexicon.Set, Lexicon.Singleton, Lexicon.UnicodeCategory, Lexicon.Union
 
Field Summary
private  Object lookahead
          The lookahead terminal.
 
Fields inherited from class gi.Grammar
first, firsts, follows, productions, size, start, terminals
 
Fields inherited from class gi.Lexicon
accepts, END_OF_SOURCE, END_OF_SOURCE_EXPRESSION, initial, states, transitions, word
 
Constructor Summary
protected LL1_Grammar()
          Constructs an LL(1) parser around a new empty Grammar.
protected LL1_Grammar(Grammar grammar)
          Constructs an LL(1) parser around an existing Grammar.
 
Method Summary
private  void descend(BufferedReader source, Grammar.ParseTree root)
          Completes a seed ParseTree by LL(1) recursive descent.
private  Lexicon.Set expected(Object nonterminal)
          Computes the terminals matching a nonterminal.
(package private)  Grammar.ParseTree interpret(LineNumberReader source)
          Interprets a source character stream by LL(1) recursive descent.
private  Grammar.Production parse(Object nonterminal, Object lookahead)
          Computes a Production to use in a leftmost derivation.
 
Methods inherited from class gi.Grammar
first, first, follow, grab, interpret, interpret, interpret, interpret, interpret, interpret, interpret, nonterminal, put, put, terminal
 
Methods inherited from class gi.Lexicon
closure, expression, initial, put, put, recognize, state, transition, word
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

lookahead

private Object lookahead

The lookahead terminal.

Constructor Detail

LL1_Grammar

protected LL1_Grammar()

Constructs an LL(1) parser around a new empty Grammar.


LL1_Grammar

protected LL1_Grammar(Grammar grammar)

Constructs an LL(1) parser around an existing Grammar.

Parameters:
grammar - the Grammar around which the parser is constructed.
Method Detail

descend

private void descend(BufferedReader source,
                     Grammar.ParseTree root)
              throws Lexicon.Exception

Completes a seed ParseTree by LL(1) recursive descent.

Parameters:
source - the source character stream.
root - a seed ParseTree to be completed by interpreting source.
Throws:
Lexicon.Exception - if an I/O, lexical, syntax or semantic error occurs.

expected

private Lexicon.Set expected(Object nonterminal)

Computes the terminals matching a nonterminal.

Parameters:
nonterminal - the expected nonterminal.
Returns:
the terminals matching the expected nonterminal.

interpret

Grammar.ParseTree interpret(LineNumberReader source)
                      throws Lexicon.Exception

Interprets a source character stream by LL(1) recursive descent.

Overrides:
interpret in class Grammar
Parameters:
source - the source character stream.
Returns:
the ParseTree constructed by interpreting source.
Throws:
Lexicon.Exception - if an I/O, lexical, syntax or semantic error occurs.

parse

private Grammar.Production parse(Object nonterminal,
                                 Object lookahead)

Computes a Production to use in a leftmost derivation.

Parameters:
nonterminal - the expected nonterminal.
lookahead - the lookahead terminal.
Returns:
the highest priority Production with which to replace the expected nonterminal and eventually match the lookahead terminal; returns null if none.

 

© 1999-2000 Craig A. Rich <carich@acm.org>