1<?php
2/*
3    This program is free software: you can redistribute it and/or modify
4    it under the terms of the GNU General Public License as published by
5    the Free Software Foundation, either version 3 of the License, or
6    (at your option) any later version.
7
8    This program is distributed in the hope that it will be useful,
9    but WITHOUT ANY WARRANTY; without even the implied warranty of
10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11    GNU General Public License for more details.
12
13    You should have received a copy of the GNU General Public License
14    along with this program.  If not, see <http://www.gnu.org/licenses/>.
15
16    Vincent Tscherter, tscherter@karmin.ch, Solothurn, 2009-01-18
17
18    2009-01-18 version 0.1 first release
19    2009-01-02 version 0.2
20      - title und comment literal added
21      - ";" als terminator-symbol added
22*/
23error_reporting(E_ALL|E_STRICT);
24
25//
26define('META', 'xis/ebnf v0.2 https://www.dokuwiki.org/plugin:ebnf gpl3');
27
28// parser
29define('EBNF_OPERATOR_TOKEN', 1);
30define('EBNF_LITERAL_TOKEN', 2);
31define('EBNF_WHITESPACE_TOKEN', 3);
32define('EBNF_IDENTIFIER_TOKEN', 4);
33
34// rendering
35define('FONT', 3);
36define('UNIT', 10);
37define('AW', 3);
38
39// lexemes
40$ebnf_lexemes[] = array( 'type' => EBNF_OPERATOR_TOKEN, 'expr' => '[={}()|.;[\]]' );
41$ebnf_lexemes[] = array( 'type' => EBNF_LITERAL_TOKEN,  'expr' => "\"[^\"]*\"" );
42$ebnf_lexemes[] = array( 'type' => EBNF_LITERAL_TOKEN,  'expr' => "'[^']*'" );
43$ebnf_lexemes[] = array( 'type' => EBNF_IDENTIFIER_TOKEN,  'expr' => "[a-zA-Z0-9_-]+" );
44$ebnf_lexemes[] = array( 'type' => EBNF_WHITESPACE_TOKEN,  'expr' => "\\s+" );
45
46// input example
47$input = <<<EOD
48"EBNF defined in itself" {
49  syntax     = [ title ] "{" { rule } "}" [ comment ].
50  rule       = identifier "=" expression ( "." | ";" ) .
51  expression = term { "|" term } .
52  term       = factor { factor } .
53  factor     = identifier
54             | literal
55             | "[" expression "]"
56             | "(" expression ")"
57             | "{" expression "}" .
58  identifier = character { character } .
59  title      = literal .
60  comment    = literal .
61  literal    = "'" character { character } "'"
62             | '"' character { character } '"' .
63}
64EOD;
65
66if (isset($_GET['syntax'])) {
67  $input = $_GET['syntax'];
68  $input = stripslashes($input);
69}
70
71$format = "png";
72if (isset($_GET['format'])) $format = $_GET['format'];
73
74try {
75  $tokens = ebnf_scan($input, true);
76  $dom = ebnf_parse_syntax($tokens);
77  if ($format == 'xml') {
78    header('Content-Type: application/xml');
79    echo $dom->saveXML();
80  } else {
81    render_node($dom->firstChild, true);
82  }
83} catch (Exception $e) {
84    header('Content-Type: text/plain');
85    $dom = new DOMDocument();
86    $syntax = $dom->createElement("syntax");
87    $syntax->setAttribute('title', 'EBNF - Syntax Error');
88    $syntax->setAttribute('meta', $e->getMessage());
89    $dom->appendChild($syntax);
90    render_node($dom->firstChild, true);
91}
92
93function rr($im, $x1, $y1, $x2, $y2, $r, $black){
94  imageline($im, $x1+$r, $y1, $x2-$r, $y1, $black);
95  imageline($im, $x1+$r, $y2, $x2-$r, $y2, $black);
96  imageline($im, $x1, $y1+$r, $x1, $y2-$r, $black);
97  imageline($im, $x2, $y1+$r, $x2, $y2-$r, $black);
98  imagearc($im, $x1+$r, $y1+$r, 2*$r, 2*$r, 180, 270, $black);
99  imagearc($im, $x2-$r, $y1+$r, 2*$r, 2*$r, 270, 360, $black);
100  imagearc($im, $x1+$r, $y2-$r, 2*$r, 2*$r, 90, 180, $black);
101  imagearc($im, $x2-$r, $y2-$r, 2*$r, 2*$r, 0, 90, $black);
102}
103
104function create_image($w, $h) {
105  global $white, $black, $blue, $red, $green, $silver;
106  $im = imagecreatetruecolor($w, $h) or die("no img");
107  imageantialias($im, true);
108  $white = imagecolorallocate ($im, 255, 255, 255);
109  $black = imagecolorallocate ($im, 0, 0, 0);
110  $blue = imagecolorallocate ($im, 0, 0, 255);
111  $red = imagecolorallocate ($im, 255, 0, 0);
112  $green = imagecolorallocate ($im, 0, 200, 0);
113  $silver = imagecolorallocate ($im, 127, 127, 127);
114  imagefilledrectangle($im, 0,0,$w,$h,$white);
115  return $im;
116}
117
118function arrow($image, $x, $y, $lefttoright) {
119  global $white, $black;
120  if (!$lefttoright)
121    imagefilledpolygon($image,
122      array($x, $y-UNIT/3, $x-UNIT, $y, $x, $y+UNIT/3), 3, $black);
123  else
124    imagefilledpolygon($image,
125      array($x-UNIT, $y-UNIT/3, $x, $y, $x-UNIT, $y+UNIT/3), 3, $black);
126}
127
128
129function render_node($node, $lefttoright) {
130  global $white, $black, $blue, $red, $green, $silver;
131  if ($node->nodeName=='identifier' || $node->nodeName=='terminal') {
132    $text = $node->getAttribute('value');
133    $w = imagefontwidth(FONT)*(strlen($text)) + 4*UNIT;
134    $h = 2*UNIT;
135    $im = create_image($w, $h);
136
137    if ($node->nodeName!='terminal') {
138        imagerectangle($im, UNIT, 0, $w-UNIT-1, $h-1, $black);
139      imagestring($im, FONT, 2*UNIT, ($h-imagefontheight(FONT))/2,   $text, $red);
140    } else {
141      if ($text!="...")
142	      rr($im, UNIT, 0, $w-UNIT-1, $h-1, UNIT/2, $black);
143      imagestring($im, FONT, 2*UNIT, ($h-imagefontheight(FONT))/2,
144        $text, $text!="..."?$blue:$black);
145    }
146    imageline($im,0,UNIT, UNIT, UNIT, $black);
147    imageline($im,$w-UNIT,UNIT, $w+1, UNIT, $black);
148    return $im;
149  } else if ($node->nodeName=='option' || $node->nodeName=='loop') {
150    if ($node->nodeName=='loop')
151      $lefttoright = ! $lefttoright;
152    $inner = render_node($node->firstChild, $lefttoright);
153    $w = imagesx($inner)+6*UNIT;
154    $h = imagesy($inner)+2*UNIT;
155    $im = create_image($w, $h);
156    imagecopy($im, $inner, 3*UNIT, 2*UNIT, 0,0, imagesx($inner), imagesy($inner));
157    imageline($im,0,UNIT, $w, UNIT, $black);
158    arrow($im, $w/2+UNIT/2, UNIT, $node->nodeName=='loop'?!$lefttoright:$lefttoright);
159    arrow($im, 3*UNIT, 3*UNIT, $lefttoright);
160    arrow($im, $w-2*UNIT, 3*UNIT, $lefttoright);
161    imageline($im,UNIT,UNIT, UNIT, 3*UNIT, $black);
162    imageline($im,UNIT,3*UNIT, 2*UNIT, 3*UNIT, $black);
163    imageline($im,$w-UNIT,UNIT, $w-UNIT, 3*UNIT, $black);
164	imageline($im,$w-3*UNIT-1,3*UNIT, $w-UNIT, 3*UNIT, $black);
165    return $im;
166  } else if ($node->nodeName=='sequence') {
167    $inner = render_childs($node, $lefttoright);
168    if (!$lefttoright)
169      $inner = array_reverse($inner);
170    $w = count($inner)*UNIT-UNIT; $h = 0;
171    for ($i = 0; $i<count($inner); $i++) {
172      $w += imagesx($inner[$i]);
173      $h = max($h, imagesy($inner[$i]));
174    } $im = create_image($w, $h);
175    imagecopy($im, $inner[0], 0, 0, 0,0, imagesx($inner[0]), imagesy($inner[0]));
176    $x = imagesx($inner[0])+UNIT;
177    for ($i = 1; $i<count($inner); $i++) {
178      imageline($im, $x-UNIT-1, UNIT, $x, UNIT, $black);
179      arrow($im, $x, UNIT, $lefttoright);
180      imagecopy($im, $inner[$i], $x, 0, 0,0, imagesx($inner[$i]), imagesy($inner[$i]));
181      $x += imagesx($inner[$i])+UNIT;
182    } return $im;
183  } else if ($node->nodeName=='choise') {
184    $inner = render_childs($node, $lefttoright);
185    $h = (count($inner)-1)*UNIT; $w = 0;
186    for ($i = 0; $i<count($inner); $i++) {
187      $h += imagesy($inner[$i]);
188      $w = max($w, imagesx($inner[$i]));
189    } $w += 6*UNIT; $im = create_image($w, $h); $y = 0;
190    imageline($im, 0, UNIT, UNIT, UNIT, $black);
191    imageline($im, $w-UNIT, UNIT, $w, UNIT, $black);
192    for ($i = 0; $i<count($inner); $i++) {
193      imageline($im, UNIT, $y+UNIT, $w-UNIT, $y+UNIT, $black);
194      imagecopy($im, $inner[$i], 3*UNIT, $y, 0,0, imagesx($inner[$i]), imagesy($inner[$i]));
195      arrow($im, 3*UNIT, $y+UNIT, $lefttoright);
196      arrow($im, $w-2*UNIT, $y+UNIT, $lefttoright);
197      $top = $y + UNIT;
198      $y += imagesy($inner[$i])+UNIT;
199    }
200    imageline($im, UNIT, UNIT, UNIT, $top, $black);
201    imageline($im, $w-UNIT, UNIT, $w-UNIT, $top, $black);
202    return $im;
203  } else if ($node->nodeName=='syntax') {
204    $title = $node->getAttribute('title');
205    $meta = $node->getAttribute('meta');
206    $node = $node->firstChild;
207    $names = array();
208    $images = array();
209    while ($node!=null) {
210	   $names[] = $node->getAttribute('name');
211	   $im = render_node($node->firstChild, $lefttoright);
212	   $images[] = $im;
213       $node = $node->nextSibling;
214    } $wn  = 0; $wr = 0; $h = 5*UNIT;
215    for ($i = 0; $i<count($images); $i++) {
216      $wn = max($wn, imagefontwidth(FONT)*strlen($names[$i]));
217      $wr = max($wr, imagesx($images[$i]));
218	  $h += imagesy($images[$i])+2*UNIT;
219    }
220    if ($title=='') $h -= 2*UNIT;
221    if ($meta=='') $h -= 2*UNIT;
222    $w = max($wr+$wn+3*UNIT, imagefontwidth(1)*strlen($meta)+2*UNIT);
223    $im = create_image($w, $h);
224    $y = 2*UNIT;
225    if ($title!='') {
226      imagestring($im, FONT, UNIT, (2*UNIT-imagefontheight(FONT))/2,
227      $title, $green);
228      imageline($im, 0, 2*UNIT, $w, 2*UNIT, $green);
229      $y += 2*UNIT;
230    }
231    for ($i = 0; $i<count($images); $i++) {
232      imagestring($im, FONT, UNIT, $y-UNIT+(2*UNIT-imagefontheight(FONT))/2, $names[$i], $red);
233      imagecopy($im, $images[$i], $wn+2*UNIT, $y, 0,0, imagesx($images[$i]) , imagesy($images[$i]));
234      imageline($im, UNIT, $y+UNIT, $wn+2*UNIT, $y+UNIT, $black);
235      imageline($im, $wn+2*UNIT+imagesx($images[$i])-1, $y+UNIT, $w-UNIT, $y+UNIT, $black);
236      imageline($im, $w-UNIT, $y+UNIT/2, $w-UNIT ,$y+1.5*UNIT, $black);
237      $y += 2*UNIT + imagesy($images[$i]);
238    }
239    imagestring($im, 1, UNIT, $h-2*UNIT+(2*UNIT-imagefontheight(1))/2,
240      $meta, $silver);
241    rr($im, 0,0,$w-1, $h-1, UNIT/2, $green);
242    header('Content-Type: image/png');
243    imagepng($im);
244    return $im;
245  }
246}
247
248function render_childs($node, $lefttoright) {
249   $childs = array();
250   $node = $node->firstChild;
251   while ($node!=null) {
252     $childs[] = render_node($node, $lefttoright);
253     $node = $node->nextSibling;
254   } return $childs;
255}
256
257function ebnf_scan(&$input) {
258  global $ebnf_lexemes;
259  $i = 0; $n = strlen($input); $m = count($ebnf_lexemes); $tokens = array();
260  while ($i < $n) {
261    $j = 0;
262    while ($j < $m &&
263      preg_match("/^{$ebnf_lexemes[$j]['expr']}/", substr($input,$i), $matches)==0) $j++;
264    if ($j<$m) {
265      if ($ebnf_lexemes[$j]['type']!=EBNF_WHITESPACE_TOKEN)
266        $tokens[] = array('type' => $ebnf_lexemes[$j]['type'],
267          'value' => $matches[0], 'pos' => $i);
268      $i += strlen($matches[0]);
269	} else
270	  throw new Exception("Invalid token at position: $i");
271  } return $tokens;
272}
273
274
275function ebnf_check_token($token, $type, $value) {
276  return $token['type']==$type && $token['value']==$value;
277}
278
279function ebnf_parse_syntax(&$tokens) {
280  $dom = new DOMDocument();
281  $syntax = $dom->createElement("syntax");
282  $syntax->setAttribute('meta', META);
283  $dom->appendChild($syntax);
284  $i = 0; $token = $tokens[$i++];
285  if ($token['type'] == EBNF_LITERAL_TOKEN) {
286    $syntax->setAttribute('title',
287      stripcslashes(substr($token['value'], 1, strlen($token['value'])-2 )));
288    $token = $tokens[$i++];
289  }
290  if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '{') )
291    throw new Exception("Syntax must start with '{': {$token['pos']}");
292  $token = $tokens[$i];
293  while ($i < count($tokens) && $token['type'] == EBNF_IDENTIFIER_TOKEN) {
294    $syntax->appendChild(ebnf_parse_production($dom, $tokens, $i));
295    if ($i<count($tokens)) $token = $tokens[$i];
296  } $i++; if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '}'))
297    throw new Exception("Syntax must end with '}': ".$tokens[count($tokens)-1]['pos']);
298  if ($i<count($tokens)) {
299    $token = $tokens[$i];
300    if ($token['type'] == EBNF_LITERAL_TOKEN) {
301      $syntax->setAttribute('meta',
302        stripcslashes(substr($token['value'], 1, strlen($token['value'])-2 )));
303    }
304  }
305    return $dom;
306}
307
308function ebnf_parse_production(&$dom, &$tokens, &$i) {
309  $token = $tokens[$i++];
310  if ($token['type']!=EBNF_IDENTIFIER_TOKEN)
311    throw new Exception("Production must start with an identifier'{': {$token['pos']}");
312  $production = $dom->createElement("rule");
313  $production->setAttribute('name', $token['value']);
314  $token = $tokens[$i++];
315  if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, "="))
316    throw new Exception("Identifier must be followed by '=': {$token['pos']}");
317  $production->appendChild( ebnf_parse_expression($dom, $tokens, $i));
318  $token = $tokens[$i++];
319  if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '.')
320    && !ebnf_check_token($token, EBNF_OPERATOR_TOKEN, ';'))
321    throw new Exception("Rule must end with '.' or ';' : {$token['pos']}");
322  return $production;
323}
324
325function ebnf_parse_expression(&$dom, &$tokens, &$i) {
326  $choise = $dom->createElement("choise");
327  $choise->appendChild(ebnf_parse_term($dom, $tokens, $i));
328  $token=$tokens[$i]; $mul = false;
329  while (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '|')) {
330    $i++;
331    $choise->appendChild(ebnf_parse_term($dom, $tokens, $i));
332    $token=$tokens[$i]; $mul = true;
333  } return $mul ? $choise : $choise->removeChild($choise->firstChild);
334}
335
336function ebnf_parse_term(&$dom, &$tokens, &$i) {
337  $sequence = $dom->createElement("sequence");
338  $factor = ebnf_parse_factor($dom, $tokens, $i);
339  $sequence->appendChild($factor);
340  $token=$tokens[$i]; $mul = false;
341  while ($token['value']!='.' && $token['value']!='=' && $token['value']!='|'
342    && $token['value']!=')' && $token['value']!=']' && $token['value']!='}') {
343    $sequence->appendChild(ebnf_parse_factor($dom, $tokens, $i));
344    $token=$tokens[$i]; $mul = true;
345  } return $mul ? $sequence: $sequence->removeChild($sequence->firstChild);
346}
347
348function ebnf_parse_factor(&$dom, &$tokens, &$i) {
349  $token = $tokens[$i++];
350  if ($token['type']==EBNF_IDENTIFIER_TOKEN) {
351    $identifier = $dom->createElement("identifier");
352    $identifier->setAttribute('value', $token['value']);
353    return $identifier;
354  } if ($token['type']==EBNF_LITERAL_TOKEN){
355    $literal = $dom->createElement("terminal");
356    $literal->setAttribute('value', stripcslashes(substr($token['value'], 1, strlen($token['value'])-2 )));
357    return $literal;
358  } if (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '(')) {
359    $expression = ebnf_parse_expression($dom, $tokens, $i);
360    $token = $tokens[$i++];
361    if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, ')'))
362      throw new Exception("Group must end with ')': {$token['pos']}");
363    return $expression;
364  } if (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '[')) {
365    $option = $dom->createElement("option");
366    $option->appendChild(ebnf_parse_expression($dom, $tokens, $i));
367    $token = $tokens[$i++];
368    if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, ']'))
369      throw new Exception("Option must end with ']': {$token['pos']}");
370    return $option;
371  } if (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '{')) {
372    $loop = $dom->createElement("loop");
373    $loop->appendChild(ebnf_parse_expression($dom, $tokens, $i));
374    $token = $tokens[$i++];
375    if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '}'))
376      throw new Exception("Loop must end with '}': {$token['pos']}");
377    return $loop;
378  }
379  throw new Exception("Factor expected: {$token['pos']}");
380}
381
382?>