The tables that are generated by this class are transition functions
that correlate with automata theory and can be executed by a finite
state machine, specifically a non-deterministic finite automata.
In English, this class will let you create the necessary LR tools
to parse any context-free grammar (in theory).
NOTE: If you don't know what LR means, don't try to parse any languages
with it. Learn this stuff first.
Providing we have a grammar, like so...
E -> E + E
E -> E - E
E -> ( E )
E -> int
E -> ident
... we can create LR tables that can be executed by an LR parser,
probably something generalized because of the lack of lookahead
symbols.
What this class will do is augment the grammar,
S -> E
create an item set and close (where int and ident, + and -, and "("
and ")" are terminals, S & E are nonterminals, and * are dots),
S -> * E
+ E -> E + E
+ E -> E - E
+ E -> ( E )
+ E -> int
+ E -> ident
and then continue this by rotating right and creating transitions
to each item set, such that:
ITEM SET 0
start -> • e
e -> • e T_PLUS e
e -> • e T_MINUS e
e -> • T_START_PAREN e T_END_PAREN
e -> • T_INT
e -> • T_IDENT
ITEM SET 1
start -> e •
e -> e • T_PLUS e
e -> e • T_MINUS e
ITEM SET 2
e -> T_START_PAREN • e T_END_PAREN
e -> • e T_PLUS e
e -> • e T_MINUS e
e -> • T_START_PAREN e T_END_PAREN
e -> • T_INT
e -> • T_IDENT
ITEM SET 3
e -> T_INT •
ITEM SET 4
e -> T_IDENT •
ITEM SET 5
e -> e T_PLUS • e
e -> • e T_PLUS e
e -> • e T_MINUS e
e -> • T_START_PAREN e T_END_PAREN
e -> • T_INT
e -> • T_IDENT
ITEM SET 6
e -> e T_MINUS • e
e -> • e T_PLUS e
e -> • e T_MINUS e
e -> • T_START_PAREN e T_END_PAREN
e -> • T_INT
e -> • T_IDENT
ITEM SET 7
e -> T_START_PAREN e • T_END_PAREN
e -> e • T_PLUS e
e -> e • T_MINUS e
ITEM SET 8
e -> e T_PLUS e •
e -> e • T_PLUS e
e -> e • T_MINUS e
ITEM SET 9
e -> e T_MINUS e •
e -> e • T_PLUS e
e -> e • T_MINUS e
ITEM SET 10
e -> T_START_PAREN e T_END_PAREN •
These will represent each state. Note, the above is what is outputted
by my class.
Additionally you must provide the class with the correct start symbol
such that
start -> {provided}
and {provided} exists somewhere in your productions. Do not provide
undefined nonterminals.
LR_Parsing_Tables::LR_Parsing_Tables() will accept productions for
first argument and the start symbol for the second.
LR_Parsing_Tables::build() will build the tables and return them.
Use the other functions in the example to display the tables, which is
probably not your intention with these tables anyway.
|
Download
