<?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;
}
}
?>
|
Stumble It!
Bookmark in del.icio.us
