PHP Classes

File: lr_parser_tables.class.php

Recommend this page to a friend!
  Classes of Debug   LR Parsing Tables   lr_parser_tables.class.php   Download  
File: lr_parser_tables.class.php
Role: Class source
Content type: text/plain
Description: The LR Parsing Tables class.
Class: LR Parsing Tables
Generate parsing tables for context free grammars
Author: By
Last change:
Date: 15 years ago
Size: 8,374 bytes
 

Contents

Class file image Download
<?php
/**
 * This class will create LR parsing tables (action and goto tables)
 * It runs through the naturally overcomplicated algorithm of generating
 * item sets, finding closure, and creating transition tables. Then it
 * runs through the transition tables, assigns shift-reduce-accept actions
 * to the tables. The end result has non-deterministic cells that may contain
 * one or more actions. It's up to the algorithm (I recommend GLR) that parses
 * these tables to determine which actions should be taken etc.
 *
 * This can print the productions and result tables too.
 *
 * These are LR(0) tables. There are no lookaheads.
 *
 * ENJOY!
 */

Class LR_Parsing_Tables
   
{
        var
$productions = array();
        var
$production_sets = array();
        var
$production_index = array();
        var
$start_symbol = "";
        var
$item_sets = array();
        var
$transition_table = array();
       
        function
print_productions()
            {
                foreach (
$this->productions as $id => $production)
                    {
                       
$production[1] = implode(" ", $production[1]);
                        echo
$id . ") <b>$production[0]</b> -> $production[1]<br>";
                    }
            }
       
        function
print_tables($tables)
            {
               
$goto_index = $tables[0][0];
               
$goto = $tables[0][1];
               
$action_index = $tables[1][0];
               
$action = $tables[1][1];
                echo
"<table width=100% cellpadding=\"0\" cellspacing=\"0\" border><tr><td><b>ACTION TABLE</b></td><td><b>GOTO TABLE</b></td></tr>";
                echo
"<tr><td>";
                echo
"<table width=100% cellpadding=\"0\" cellspacing=\"0\" border><tr><td>State</td>";
                foreach (
$action_index as $terminal)
                    {
                        echo
"<td><b>$terminal</b></td>";
                    }
                echo
"</tr>";
                foreach (
$action as $state => $cells)
                    {
                        echo
"<tr><td><b>$state</b></td>";
                        foreach (
$action_index as $num => $terminal)
                            {
                                echo
"<td>" . @implode("/", $cells[$num]) . "</td>";
                            }
                        echo
"</tr>";
                    }
                echo
"</table>";
                echo
"</td><td>";
                echo
"<table width=100% cellpadding=\"0\" cellspacing=\"0\" border><tr><td>State</td>";
                foreach (
$goto_index as $nonterminal)
                    {
                        echo
"<td><b>$nonterminal</b></td>";
                    }
                echo
"</tr>";
                foreach (
$goto as $state => $cells)
                    {
                        echo
"<tr><td><b>$state</b></td>";
                        foreach (
$goto_index as $num => $nonterminal)
                            {
                                echo
"<td>" . $cells[$num] . "</td>";
                            }
                        echo
"</tr>";
                    }
                echo
"</table>";
                echo
"</td></table>";
            }
       
        function
build()
            {
               
$transition_index = array();
               
$first = $this->close_set(array($this->production_sets[0][0]));
               
$next_round = array($first);
               
$reserved = 2;
                while (!empty(
$next_round))
                    {
                       
$new_round = array();
                        foreach (
$next_round as $item_set)
                            {
                               
$this->item_sets[] = $item_set;
                               
$next_item_set++; $reserved--;
                               
$transition_sets = $this->generate_transition_sets($item_set);
                                foreach (
$transition_sets as $leading_symbol => $transition_set)
                                    {
                                       
$serialized_transition_set = serialize($transition_set);
                                        if (isset(
$transition_index[$serialized_transition_set]))
                                            {
                                               
$this->transition_table[count($this->item_sets) - 1][$leading_symbol] = $transition_index[$serialized_transition_set];
                                            }
                                        else
                                            {
                                               
$transition_index[$serialized_transition_set] = count($this->item_sets) - 1 + $reserved;
                                               
$this->transition_table[count($this->item_sets) - 1][$leading_symbol] = count($this->item_sets) - 1 + $reserved;
                                               
$new_round[] = $transition_set;
                                               
$reserved++;
                                            }
                                    }
                            }
                       
$next_round = $new_round;
                    }
                return
$this->create_action_and_goto();
            }
       
        function
create_action_and_goto()
            {
               
$action_index = $goto_index = array();
                foreach (
$this->item_sets as $num => $item_set)
                    {
                       
$goto[$num] = array();
                    }
               
$action = $goto;
               
                foreach (
$this->transition_table as $item_set => $transition)
                    {
                        foreach (
$transition as $leading_symbol => $set)
                            {
                                if (
strtolower($leading_symbol) == $leading_symbol)
                                    {
                                        if (!
in_array($leading_symbol, $goto_index))
                                            {
                                               
$goto_index[] = $leading_symbol;
                                               
$pos = count($goto_index) -1;
                                            }
                                        else
                                            {
                                               
$pos = array_search($leading_symbol, $goto_index);
                                            }
                                       
$goto[$item_set][$pos] = $set;
                                    }
                                else
                                    {
                                        if (!
in_array($leading_symbol, $action_index))
                                            {
                                               
$action_index[] = $leading_symbol;
                                               
$pos = count($action_index) - 1;
                                            }
                                        else
                                            {
                                               
$pos = array_search($leading_symbol, $action_index);
                                            }
                                       
$action[$item_set][$pos][] = "s$set";
                                    }
                            }
                    }
               
               
$action_index[] = "$";
                foreach (
$this->item_sets as $state => $item_set)
                    {
                        foreach (
$item_set as $item)
                            {
                                if (
$item == array("start", array(array($this->start_symbol), "*", array())))
                                    {
                                       
$action[$state][count($action_index) - 1][] = "acc";
                                    }
                                elseif (empty(
$item[1][2]))
                                    {
                                       
$production = array($item[0], array_merge($item[1][0], $item[1][2]));
                                       
$reduce = array_search($production, $this->productions);
                                       
$i = 0;
                                        for (
$x=count($action_index);$x > 0;$x--)
                                            {
                                               
$action[$state][$i][] = "r$reduce";
                                               
$i++;
                                            }
                                    }
                            }
                    }

                return array(array(
$goto_index, $goto),array($action_index, $action));
            }
       
        function
generate_transition_sets($item_set)
            {
               
$leading_symbols = array();
                foreach (
$item_set as $item)
                    {
                        if (!empty(
$item[1][2]))
                            {
                               
$shift = $this->shift_item_set(array($item));
                               
$leading_symbols[$item[1][2][0]][] = $shift[0];
                            }
                    }
                foreach (
$leading_symbols as $lead => $item_set)
                    {
                       
$leading_symbols[$lead] = $this->close_set($item_set);
                    }
                return
$leading_symbols;
            }
       
        function
shift_item_set($item_set)
            {
                foreach (
$item_set as $lol => $item)
                    {
                       
array_push($item_set[$lol][1][0], array_shift($item_set[$lol][1][2]));
                    }
                return
$item_set;
            }
       
        function
LR_Parsing_Tables($productions, $start)
            {
               
array_unshift($productions, array("start", array($start)));
               
$this->productions = $productions;
                foreach (
$productions as $num => $production)
                    {
                       
$this->production_sets[serialize($production)] &= $this->production_sets[$num] = $this->item_set($production);
                       
$this->production_index[$production[0]][] = $num;
                    }
               
$this->start_symbol = $start;
            }
       
        function
close_set($item_set)
            {
               
$new_set = $item_set;
               
$nonterminals = array();
                do
                    {
                       
$item_set = $new_set;
                        foreach (
$item_set as $item)
                            {
                               
$nonterminal = $item[1][2];
                                if (isset(
$nonterminal[0]) && (strtolower($nonterminal[0]) == $nonterminal[0]) && !in_array($nonterminal[0], $nonterminals))
                                    {
                                        foreach (
$this->production_index[$nonterminal[0]] as $production_id)
                                            {
                                                if (!
in_array($this->production_sets[$production_id][0], $item_set))
                                                   
$new_set = array_merge($new_set, array($this->production_sets[$production_id][0]));
                                            }
                                       
$nonterminals[] = $item[1][2][0];
                                    }
                            }
                    } while (
$item_set != $new_set);
                return
$this->unique_items($new_set);
            }
       
        function
unique_items($item_set)
            {
                foreach (
$item_set as $num => $set)
                    {
                       
$item_set[$num] = serialize($set);
                    }
               
$item_set = array_keys(array_flip($item_set));
                foreach (
$item_set as $num => $set)
                    {
                       
$item_set[$num] = unserialize($set);
                    }
                return
$item_set;
            }
       
        function
item_set($production)
            {
               
$item_set = array();
               
$left = array();
               
$right = $production[1];
                while(
true)
                    {
                       
$item_set[] = array($production[0], array($left, "*", $right));
                        if (empty(
$right)) break;
                       
array_push($left, array_shift($right));
                    }
                return
$item_set;
            }
    }

?>