PHP Classes

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: 13 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.