File: documentation.txt

Recommend this page to a friend!
  Classes of Debug  >  LR Parsing Tables  >  documentation.txt  >  Download  
File: documentation.txt
Role: Documentation
Content type: text/plain
Description: Documentation
Class: LR Parsing Tables
Generate parsing tables for context free grammars
Author: By
Last change:
Date: 11 years ago
Size: 2,652 bytes
 

 

Contents

Class file image Download
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.

For more information send a message to info at phpclasses dot org.