<?php

/* BNF to graph converter by Bisqwit.
 * Copyright (C) 1992,2007 Joel Yliluoma - http://iki.fi/bisqwit/
 * License: http://bisqwit.iki.fi/TINYFREELICENSE
 */
  
  $input = <<<EOF
   request =
     [ (DESC|DESCRIBE|EXPLAIN) [EXTENDED] ] query.
   
   query =
    (SELECT
       [DISTINCT]
       ( '*'
       | (expression [ [ AS ] name ]) % ','
       )
    [ FROM table_refs
      [ WHERE    expression ]
      [ GROUP BY (expression [ASC | DESC]) % ',' ]
      [ HAVING   expression ] ]
    [ ORDER BY (expression [ASC | DESC]) % ',' ]
    [ LIMIT integer
       ( OFFSET integer
       | [ ',' integer ]
       ) ]
    ) % (UNION [ DISTINCT | ALL ])
     .

   table_refs =
       ( table_name [ [ AS ] table_alias ]
       | '(' table_refs ')'
       | LEFT JOIN table_refs ( ON expression
                              | USING '(' (name % ',') ')'
                              )
       ) % ','.

   name = field_name_or_alias.

   expression =
    ( (NOT | '!' | '-' | '+')*
      ( [table_name_or_alias '.'] name
     | TRUE
     | FALSE
     | numeric_constant
     | string_constant
     | expression
     | [ EXISTS ] '(' query ')'
     | COUNT '(' [ DISTINCT ] ( '*' | expression ) ')'
     | [ SUM | LENGTH | AVG | FLOOR ] '(' expression ')'
      )
      (
        IS [ NOT ] NULL
      | [ NOT ] IN '(' ( query
                      | ( expression % ',' )
                        ) ')'
      | BETWEEN expression AND expression
      | LIKE string_constant      )*
     ) %
     (
           '+' | '-' | '/' | '*' | '^'
         | '=' | '<' | '>' | '<=' | '>=' | '!=' | '<>'
         | AND | OR | XOR | MOD
     ).
EOF;

#$input = 'x = [a [ASC | DESC]].';
#$input = 'x = (a) % (u [ d | a ]).';

#$input = 'x = (a|b|c|d)*.';

  $tokens=Array();
  $id ='[a-z][a-zA-Z0-9-_]*';
  $op  ='[?*+=%.|()\[\]]';
  $tok='(?:[A-Z][a-zA-Z0-9-_]*|\'(?:[^\']|\\\\.)*\')';
  preg_match_all(
    '@('.$id.')|('.$op.')|('.$tok.')@', $input, $tokens);
  #print_r($tokens);
  define('ID',  1);
  define('OP',  2);
  define('TOK', 3);

  $pos = 0;
  $end = count($tokens[0]);

  print "digraph syntax {\n";
  print "  graph [ clusterrank=local ]; rankdir=TB; compound=true;\n";
  
  while($pos < $end)
  {
    $definition = new Definition;
    print "/** NEW RULE **/\n";
    ParseDefinition();
  }
  
  print "\n}\n";


class Definition
{
  var $toknodes_ell;  // nonterminal nodes
  var $toknodes_cir;  // token type: character constant
  var $idnodes;       // token type: reserved identifier
  var $hidnodes;      // Nodes that exist for the purpose of tidying the graph
  var $connections;   // edges
  var $name;

  function SetName($name)
  {
    $this->name = $name;
    $this->toknodes_ell = Array();
    $this->toknodes_cir = Array();
    $this->idnodes  = Array();
    $this->connections = Array();
    $this->hidnodes = Array();
    
    print "subgraph cluster_{$name} {\n";
    print "  label=\"$name\";\n";
    print "  node [ fontsize=12 ];\n";
    print "  edge [ length=0.1, style=\"setlinewidth(3)\" ];\n";
    print "  graph [ fontsize=12, clusterrank=local, nodesep=0.03 ];\n";
  }
  
  function Finish()
  {
    $this->RemoveUnnecessaryHidNodes();
    $this->RepointArrows();
    
    print "  node [ shape=box,style=filled,color=darkolivegreen1];\n";
    foreach($this->idnodes as $node)
      print "    {$node['name']} [ label=\"{$node['token']}\" ];\n";

    print "  node [ shape=circle,style=filled,color=darkolivegreen2 ];\n";
    foreach($this->toknodes_cir as $node)
      print "    {$node['name']} [ label=\"{$node['token']}\" ];\n";

    print "  node [ shape=ellipse,style=filled,color=darkolivegreen2 ];\n";
    foreach($this->toknodes_ell as $node)
      print "    {$node['name']} [ label=\"{$node['token']}\" ];\n";
    
    foreach($this->hidnodes as $node)
      print "    {$node['name']} [ shape=point, label=\"\" ];\n";
    
    print "}\n";
    
    foreach($this->connections as $s => $dlist)
      if(!empty($dlist))
        foreach($dlist as $d => $attrs)
          print "$s -> $d [ $attrs ] ;\n";
  }
  
  function CreateBeginRule()
  {
    $name = $this->CreateNodeName();

    print "  {$name} [ shape=octagon,style=filled,color=lightgray,label=\"<begin>\" ]\n";
    
    return $name;
  }
  function CreateEndRule()
  {
    $name = $this->CreateNodeName();
    
    print "  {$name} [ shape=octagon,style=filled,color=lightgray,label=\"<end>\" ]\n";
    
    return $name;
  }
  function CreateTokenRule($token)
  {
    $node = Array('token' => $token, 'name' => $this->CreateNodeName());
    if($token[0]=="'")
    {
      $node['token'] = stripslashes(preg_replace("@^'(.*)'\$@", '\1', $token));
      $this->toknodes_cir[] = $node;
    }
    else
      $this->toknodes_ell[] = $node;
    return $node['name'];
  }
  function CreateIDRule($token)
  {
    $node = Array('token' => $token, 'name' => $this->CreateNodeName());
    $this->idnodes[] = $node;
    return $node['name'];
  }
  function ReduceGroup($group)
  {
    if(!is_array($group))  $group = Array($group);
    if(true||count($group) != 1)
    {
      $n = $this->CreateNodeName();
      $this->hidnodes[$n] = Array('name' => $n);
      $this->JoinRules($group, $n);
      $group = Array($n);
    }
    return $group;
  }

  function JoinRules($src, $dest, $attrs='')
  {
    if(!is_array($src))  $src = Array($src);
    if(!is_array($dest)) $dest = Array($dest);
    
   # echo join(', ', $src), ' -> ', join(', ', $dest), ";\n";
    foreach($src as $s)
      foreach($dest as $d)
        $this->connections[$s][$d] = $attrs;
  }
  
  function CreateNodeName()
  {
    static $n; ++$n;
    return sprintf('n%04d',$n);
  }
  
  function RepointArrows()
  {
    return; // doesn't work properly yet. FIXME.
    
    // For all arrows that point from a hidnode into a hidnode,
    // Replace them by the target hidnode's arrows, but only
    // if all of those arrows point forward.
    foreach($this->connections as $s => &$dlist)
    {
      if(!isset($this->hidnodes[$s])) continue;
      foreach($dlist as $d => $ddesc)
      {
        if($d <= $s) continue;
        if(!isset($this->hidnodes[$d])) continue;
        
        $hid_connections = &$this->connections[$d];
        if(!$hid_connections || empty($hid_connections)) continue;
        
        $ok = true;
        foreach($hid_connections as $hd => $hddesc)
          if($hd <= $d) { $ok=false; break; }
        
        print "// $s points to $d, adopting\n";
        
        if($ok)
        {
         #return;
         
          unset($dlist[$d]); // remove target from the list
          foreach($hid_connections as $hd => $hddesc)
            $dlist[$hd] = $hddesc; // adopt target's targets
          #$hid_connections = Array(); // make target point nowhere
          
          $this->RemoveUnnecessaryHidNodes();
          #$this->RepointArrows();
          return;
        }
      }
    }
  }
  
  function RemoveUnnecessaryHidNodes()
  {
    $redo = true;
    while($redo)
    {
      $redo=false;
      // Remove all hidnodes that have exactly one source and one destination.
      foreach($this->hidnodes as $hidname => $node)
      {
        // Find how many connections point here
        $incoming = Array();
        foreach($this->connections as $s => $dlist)
          if(!empty($dlist))
            foreach($dlist as $d => $desc)
             if($d == $hidname)
               $incoming[] = $s;

        if(empty($incoming))
        {
          unset($this->hidnodes[$hidname]);
          unset($this->connections[$hidname]);
          $redo=true;
          break;
        }

        $outconn = @$this->connections[$hidname];
        if(empty($outconn)) $outconn = Array();
        if(count($outconn) > 1) continue;
        
        $outlist = Array();
        foreach($outconn as $d => $ddesc)
          $outlist[] = $d;
        
        if(#$incoming[0] < $hidname &&
         (count($incoming) == 1
         || (empty($outlist) || $outlist[0] > $hidname)
          ))
        {
          echo "// ";
          echo "$hidname is unnecessary: it is only pointed by ".join(' ', $incoming),
               " and it only goes to ", join(' ', $outlist),
               "\n";
          #continue;

          // This node is unnecessary.
          foreach($incoming as $s)
          {
            $c = &$this->connections[$s];
            unset($c[$hidname]);
            foreach($outconn as $d => $ddesc)
              $c[$d] = $ddesc;
          }
          
          unset($this->hidnodes[$hidname]);
          unset($this->connections[$hidname]);
          
          $redo=true;
          break;
        }
      }
    }
  }
};


function ParseDefinition()
{
  global $tokens, $pos, $end, $definition;
  $name = Expect(ID);
  $definition->SetName($name);
  
  ExpectOp('=');
  
  $rule = $definition->CreateBeginRule();
  $previous = Array($rule);
  
  $previous = CompileRule($previous);
  ExpectOp('.');
  
  $rule = $definition->CreateEndRule();
  $definition->JoinRules($previous, $rule);
  
  $definition->Finish();
}


function Classify()
{
  global $tokens, $pos, $end;
  for($c=1; $c<=3; ++$c)
  {
    #print "classify @ $pos: $c={$tokens[$c][$pos]}\n";
    if(!empty($tokens[$c][$pos]))
      return $c;
  }
  return 0;
}

function Expect($n)
{
  global $tokens, $pos, $end;
  #print "Expecting $n\n";
  $class = Classify();
  if($class != $n) die("Expectation failure @ $pos, got $class");
  return $tokens[$n][$pos++];
}

function ExpectOp($op)
{
  if(Expect(OP) != $op) die('Expected "'.$op.'", did not get it');
}

function PeekOp()
{
  global $tokens, $pos, $end;
  return $tokens[OP][$pos];
}
function PeekID()
{
  global $tokens, $pos, $end;
  return $tokens[ID][$pos];
}
function PeekTok()
{
  global $tokens, $pos, $end;
  return $tokens[TOK][$pos];
}
function SkipOne()
{
  global $pos;
  ++$pos;
}

function InjectOp($op)
{
  global $tokens, $pos, $end;
  --$pos;
  $tokens[ID][$pos] = null;
  $tokens[OP][$pos] = $op;
  $tokens[TOK][$pos] = null;
}

/*
  Syntax elements:
     a | b
     
     a % b
     
     a ?
     a *
     a +
     
     [ a ]

     ( a )
     
     a b
     
*/

function CompileRule($previous)
{
  #global $pos; print "cr $pos\n";
  $result = Array();
  for(;;)
  {
    $result = array_merge($result, CompileSequence($previous));
    if(PeekOp() != '|') break;
    SkipOne();
  }
  return $result;
}
function CompileSequence($previous)
{
  global $definition;

  for(;;)
  {
    $entry = $definition->ReduceGroup($previous);
    
    $result = CompileElement($entry);
    if(!$result) return $entry;
    
    $repeat_ok = false;
    $skip_ok   = false;
    
    /**/if(PeekOp() == '*') { SkipOne(); $repeat_ok = true; $skip_ok = true; }
    elseif(PeekOp() == '?') { SkipOne(); $repeat_ok =false; $skip_ok = true; }
    elseif(PeekOp() == '+') { SkipOne(); $repeat_ok = true; $skip_ok =false; }
    else /****************/ { /********/ $repeat_ok =false; $skip_ok =false; }
    
    $exit = $definition->ReduceGroup($result);
    $simpler_result = $result;
    if(count($result) > 1) $simpler_result = $exit;

    if($repeat_ok)
      $definition->JoinRules($simpler_result, $entry);

    if($skip_ok)
      $definition->JoinRules($previous, $exit);

    if(PeekOp() == '%')
    {
      SkipOne();

      $result2 = CompileSequence($exit);
      $definition->JoinRules($result2, $entry);
      return $exit;
    }
  
    $previous = $exit;
  }

/*
    if(!$first)
    {
      $definition->JoinRules($prev_prev, $previous, 'weight=10');
    }
*/

}

function CompileElement($previous)
{
  global $definition;
  #global $pos; print "ce $pos\n";
  switch(Classify())
  {
    case TOK:
    {
      $result = Array($definition->CreateTokenRule(Expect(TOK)));

      global $definition;
      $definition->JoinRules($previous, $result);
      
      return $result;
    }
    case ID:
    {
      $result = Array($definition->CreateIDRule(Expect(ID)));

      global $definition;
      $definition->JoinRules($previous, $result);
      
      return $result;
    }
  }
  
  if(PeekOp() == '(')
  {
    SkipOne();
    $result = CompileRule($previous);
    ExpectOp(')');
    
    #global $definition;
    #$definition->JoinRules($previous, $result);
    
    return $result;
  }
  
  if(PeekOp() == '[')
  {
    SkipOne();
    $result = CompileRule($previous);
    ExpectOp(']');
    InjectOp('?');

    #global $definition;
    #$definition->JoinRules($previous, $result);
    
    return $result;
  }
  return false;
}