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@tscherter.net, 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    2023-09-28 version 0.3 prefixed all constants
23    2025-09-05 version 0.4 PHP 8 compatibility and other fixes
24*/
25
26define('META', 'https://www.dokuwiki.org/plugin:ebnf');
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('EBNF_FONT', 2);
36define('EBNF_U', 10);
37define('EBNF_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 (EbnfException $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',
89        $e->getMessage()
90        . " - '" . substr($input, $e->getPos(), 30) . "...'"
91    );
92    $dom->appendChild($syntax);
93    render_node($dom->firstChild, true);
94}
95
96function rr($im, $x1, $y1, $x2, $y2, $r, $black){
97  imageline($im, $x1+$r, $y1, $x2-$r, $y1, $black);
98  imageline($im, $x1+$r, $y2, $x2-$r, $y2, $black);
99  imageline($im, $x1, $y1+$r, $x1, $y2-$r, $black);
100  imageline($im, $x2, $y1+$r, $x2, $y2-$r, $black);
101  imagearc($im, $x1+$r, $y1+$r, 2*$r, 2*$r, 180, 270, $black);
102  imagearc($im, $x2-$r, $y1+$r, 2*$r, 2*$r, 270, 360, $black);
103  imagearc($im, $x1+$r, $y2-$r, 2*$r, 2*$r, 90, 180, $black);
104  imagearc($im, $x2-$r, $y2-$r, 2*$r, 2*$r, 0, 90, $black);
105}
106
107function create_image($w, $h) {
108  global $white, $black, $blue, $red, $green, $silver;
109  $im = imagecreatetruecolor($w, $h) or die("no img");
110  imageantialias($im, true);
111  $white = imagecolorallocate ($im, 255, 255, 255);
112  $black = imagecolorallocate ($im, 0, 0, 0);
113  $blue = imagecolorallocate ($im, 0, 0, 255);
114  $red = imagecolorallocate ($im, 255, 0, 0);
115  $green = imagecolorallocate ($im, 0, 200, 0);
116  $silver = imagecolorallocate ($im, 127, 127, 127);
117  imagefilledrectangle($im, 0,0,$w,$h,$white);
118  return $im;
119}
120
121function arrow($image, $x, $y, $lefttoright) {
122  global $white, $black;
123    if (!$lefttoright) {
124      $points = array($x, $y - EBNF_U / 3, $x - EBNF_U, $y, $x, $y + EBNF_U / 3);
125  } else {
126      $points = array($x - EBNF_U, $y - EBNF_U / 3, $x, $y, $x - EBNF_U, $y + EBNF_U / 3);
127  }
128  if (PHP_VERSION_ID >= 80000 ) {
129      imagefilledpolygon($image, $points, $black);
130  } else {
131      imagefilledpolygon($image, $points, 3, $black);
132  }
133}
134
135
136function render_node($node, $lefttoright) {
137  global $white, $black, $blue, $red, $green, $silver;
138  if ($node->nodeName=='identifier' || $node->nodeName=='terminal') {
139    $text = html_entity_decode($node->getAttribute('value'));
140    $w = imagefontwidth(EBNF_FONT)*(strlen($text)) + 4*EBNF_U;
141    $h = 2*EBNF_U;
142    $im = create_image($w, $h);
143
144    if ($node->nodeName!='terminal') {
145        imagerectangle($im, EBNF_U, 0, $w-EBNF_U-1, $h-1, $black);
146      imagestring($im, EBNF_FONT, intval(2*EBNF_U), intval(($h-imagefontheight(EBNF_FONT))/2),   $text, $red);
147    } else {
148      if ($text!="...")
149	      rr($im, EBNF_U, 0, $w-EBNF_U-1, $h-1, EBNF_U/2, $black);
150      imagestring($im, EBNF_FONT, intval(2*EBNF_U), intval(($h-imagefontheight(EBNF_FONT))/2),
151        $text, $text!="..."?$blue:$black);
152    }
153    imageline($im,0,EBNF_U, EBNF_U, EBNF_U, $black);
154    imageline($im,$w-EBNF_U,EBNF_U, $w+1, EBNF_U, $black);
155    return $im;
156  } else if ($node->nodeName=='option' || $node->nodeName=='loop') {
157    if ($node->nodeName=='loop')
158      $lefttoright = ! $lefttoright;
159    $inner = render_node($node->firstChild, $lefttoright);
160    $w = imagesx($inner)+6*EBNF_U;
161    $h = imagesy($inner)+2*EBNF_U;
162    $im = create_image($w, $h);
163    imagecopy($im, $inner, 3*EBNF_U, 2*EBNF_U, 0,0, imagesx($inner), imagesy($inner));
164    imageline($im,0,EBNF_U, $w, EBNF_U, $black);
165    arrow($im, $w/2+EBNF_U/2, EBNF_U, $node->nodeName=='loop'?!$lefttoright:$lefttoright);
166    arrow($im, 3*EBNF_U, 3*EBNF_U, $lefttoright);
167    arrow($im, $w-2*EBNF_U, 3*EBNF_U, $lefttoright);
168    imageline($im,EBNF_U,EBNF_U, EBNF_U, 3*EBNF_U, $black);
169    imageline($im,EBNF_U,3*EBNF_U, 2*EBNF_U, 3*EBNF_U, $black);
170    imageline($im,$w-EBNF_U,EBNF_U, $w-EBNF_U, 3*EBNF_U, $black);
171	imageline($im,$w-3*EBNF_U-1,3*EBNF_U, $w-EBNF_U, 3*EBNF_U, $black);
172    return $im;
173  } else if ($node->nodeName=='sequence') {
174    $inner = render_childs($node, $lefttoright);
175    if (!$lefttoright)
176      $inner = array_reverse($inner);
177    $w = count($inner)*EBNF_U-EBNF_U; $h = 0;
178    for ($i = 0; $i<count($inner); $i++) {
179      $w += imagesx($inner[$i]);
180      $h = max($h, imagesy($inner[$i]));
181    } $im = create_image($w, $h);
182    imagecopy($im, $inner[0], 0, 0, 0,0, imagesx($inner[0]), imagesy($inner[0]));
183    $x = imagesx($inner[0])+EBNF_U;
184    for ($i = 1; $i<count($inner); $i++) {
185      imageline($im, $x-EBNF_U-1, EBNF_U, $x, EBNF_U, $black);
186      arrow($im, $x, EBNF_U, $lefttoright);
187      imagecopy($im, $inner[$i], $x, 0, 0,0, imagesx($inner[$i]), imagesy($inner[$i]));
188      $x += imagesx($inner[$i])+EBNF_U;
189    } return $im;
190  } else if ($node->nodeName=='choise') {
191    $inner = render_childs($node, $lefttoright);
192    $h = (count($inner)-1)*EBNF_U; $w = 0;
193    for ($i = 0; $i<count($inner); $i++) {
194      $h += imagesy($inner[$i]);
195      $w = max($w, imagesx($inner[$i]));
196    } $w += 6*EBNF_U; $im = create_image($w, $h); $y = 0;
197    imageline($im, 0, EBNF_U, EBNF_U, EBNF_U, $black);
198    imageline($im, $w-EBNF_U, EBNF_U, $w, EBNF_U, $black);
199    for ($i = 0; $i<count($inner); $i++) {
200      imageline($im, EBNF_U, $y+EBNF_U, $w-EBNF_U, $y+EBNF_U, $black);
201      imagecopy($im, $inner[$i], 3*EBNF_U, $y, 0,0, imagesx($inner[$i]), imagesy($inner[$i]));
202      arrow($im, 3*EBNF_U, $y+EBNF_U, $lefttoright);
203      arrow($im, $w-2*EBNF_U, $y+EBNF_U, $lefttoright);
204      $top = $y + EBNF_U;
205      $y += imagesy($inner[$i])+EBNF_U;
206    }
207    imageline($im, EBNF_U, EBNF_U, EBNF_U, $top, $black);
208    imageline($im, $w-EBNF_U, EBNF_U, $w-EBNF_U, $top, $black);
209    return $im;
210  } else if ($node->nodeName=='syntax') {
211    $title = $node->getAttribute('title');
212    $meta = $node->getAttribute('meta');
213    $node = $node->firstChild;
214    $names = array();
215    $images = array();
216    while ($node!=null) {
217	   $names[] = $node->getAttribute('name');
218	   $im = render_node($node->firstChild, $lefttoright);
219	   $images[] = $im;
220       $node = $node->nextSibling;
221    } $wn  = 0; $wr = 0; $h = 5*EBNF_U;
222    for ($i = 0; $i<count($images); $i++) {
223      $wn = max($wn, imagefontwidth(EBNF_FONT)*strlen($names[$i]));
224      $wr = max($wr, imagesx($images[$i]));
225	  $h += imagesy($images[$i])+2*EBNF_U;
226    }
227    if ($title=='') $h -= 2*EBNF_U;
228    if ($meta=='') $h -= 2*EBNF_U;
229    $w = max($wr+$wn+3*EBNF_U, imagefontwidth(1)*strlen($meta)+2*EBNF_U);
230    $im = create_image($w, $h);
231    $y = 2*EBNF_U;
232    if ($title!='') {
233      imagestring($im, EBNF_FONT, EBNF_U, intval((2*EBNF_U-imagefontheight(EBNF_FONT))/2),
234      $title, $green);
235      imageline($im, 0, 2*EBNF_U, $w, 2*EBNF_U, $green);
236      $y += 2*EBNF_U;
237    }
238    for ($i = 0; $i<count($images); $i++) {
239      imagestring($im, EBNF_FONT, EBNF_U, intval($y-EBNF_U+(2*EBNF_U-imagefontheight(EBNF_FONT))/2), $names[$i], $red);
240      imagecopy($im, $images[$i], $wn+2*EBNF_U, $y, 0,0, imagesx($images[$i]) , imagesy($images[$i]));
241      imageline($im, EBNF_U, $y+EBNF_U, $wn+2*EBNF_U, $y+EBNF_U, $black);
242      imageline($im, $wn+2*EBNF_U+imagesx($images[$i])-1, $y+EBNF_U, $w-EBNF_U, $y+EBNF_U, $black);
243      imageline($im, $w-EBNF_U, $y+EBNF_U/2, $w-EBNF_U ,$y+1.5*EBNF_U, $black);
244      $y += 2*EBNF_U + imagesy($images[$i]);
245    }
246    imagestring($im, 1, EBNF_U, $h-2*EBNF_U+(2*EBNF_U-imagefontheight(1))/2,
247      $meta, $silver);
248    rr($im, 0,0,$w-1, $h-1, EBNF_U/2, $green);
249    header('Content-Type: image/png');
250    imagepng($im);
251    return $im;
252  }
253}
254
255function render_childs($node, $lefttoright) {
256   $childs = array();
257   $node = $node->firstChild;
258   while ($node!=null) {
259     $childs[] = render_node($node, $lefttoright);
260     $node = $node->nextSibling;
261   } return $childs;
262}
263
264function ebnf_scan(&$input) {
265  global $ebnf_lexemes;
266  $i = 0; $n = strlen($input); $m = count($ebnf_lexemes); $tokens = array();
267  while ($i < $n) {
268    $j = 0;
269    while ($j < $m &&
270      preg_match("/^{$ebnf_lexemes[$j]['expr']}/", substr($input,$i), $matches)==0) $j++;
271    if ($j<$m) {
272      if ($ebnf_lexemes[$j]['type']!=EBNF_WHITESPACE_TOKEN)
273        $tokens[] = array('type' => $ebnf_lexemes[$j]['type'],
274          'value' => $matches[0], 'pos' => $i);
275      $i += strlen($matches[0]);
276	} else
277	  throw new EbnfException("Invalid token at position", $i);
278  } return $tokens;
279}
280
281
282function ebnf_check_token($token, $type, $value) {
283  return $token['type']==$type && $token['value']==$value;
284}
285
286function ebnf_parse_syntax(&$tokens) {
287  $dom = new DOMDocument();
288  $syntax = $dom->createElement("syntax");
289  $syntax->setAttribute('meta', META);
290  $dom->appendChild($syntax);
291  $i = 0; $token = $tokens[$i++];
292  if ($token['type'] == EBNF_LITERAL_TOKEN) {
293    $syntax->setAttribute('title',
294      stripcslashes(substr($token['value'], 1, strlen($token['value'])-2 )));
295    $token = $tokens[$i++];
296  }
297  if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '{') )
298    throw new EbnfException("Syntax must start with '{'", $token['pos']);
299  $token = $tokens[$i];
300  while ($i < count($tokens) && $token['type'] == EBNF_IDENTIFIER_TOKEN) {
301    $syntax->appendChild(ebnf_parse_production($dom, $tokens, $i));
302    if ($i<count($tokens)) $token = $tokens[$i];
303  } $i++; if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '}'))
304    throw new EbnfException("Syntax must end with '}'", $tokens[count($tokens)-1]['pos']);
305  if ($i<count($tokens)) {
306    $token = $tokens[$i];
307    if ($token['type'] == EBNF_LITERAL_TOKEN) {
308      $syntax->setAttribute('meta',
309        stripcslashes(substr($token['value'], 1, strlen($token['value'])-2 )));
310    }
311  }
312    return $dom;
313}
314
315function ebnf_parse_production(&$dom, &$tokens, &$i) {
316  $token = $tokens[$i++];
317  if ($token['type']!=EBNF_IDENTIFIER_TOKEN)
318    throw new EbnfException("Production must start with an identifier'{'", $token['pos']);
319  $production = $dom->createElement("rule");
320  $production->setAttribute('name', $token['value']);
321  $token = $tokens[$i++];
322  if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, "="))
323    throw new EbnfException("Identifier must be followed by '='", $token['pos']);
324  $production->appendChild( ebnf_parse_expression($dom, $tokens, $i));
325  $token = $tokens[$i++];
326  if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '.')
327    && !ebnf_check_token($token, EBNF_OPERATOR_TOKEN, ';'))
328    throw new EbnfException("Rule must end with '.' or ';'", $token['pos']);
329  return $production;
330}
331
332function ebnf_parse_expression(&$dom, &$tokens, &$i) {
333  $choise = $dom->createElement("choise");
334  $choise->appendChild(ebnf_parse_term($dom, $tokens, $i));
335  $token=$tokens[$i]; $mul = false;
336  while (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '|')) {
337    $i++;
338    $choise->appendChild(ebnf_parse_term($dom, $tokens, $i));
339    $token=$tokens[$i]; $mul = true;
340  } return $mul ? $choise : $choise->removeChild($choise->firstChild);
341}
342
343function ebnf_parse_term(&$dom, &$tokens, &$i) {
344  $sequence = $dom->createElement("sequence");
345  $factor = ebnf_parse_factor($dom, $tokens, $i);
346  $sequence->appendChild($factor);
347  $token=$tokens[$i]; $mul = false;
348  while ($token['value']!='.' && $token['value']!='=' && $token['value']!='|'
349    && $token['value']!=')' && $token['value']!=']' && $token['value']!='}') {
350    $sequence->appendChild(ebnf_parse_factor($dom, $tokens, $i));
351    $token=$tokens[$i]; $mul = true;
352  } return $mul ? $sequence: $sequence->removeChild($sequence->firstChild);
353}
354
355function ebnf_parse_factor(&$dom, &$tokens, &$i) {
356  $token = $tokens[$i++];
357  if ($token['type']==EBNF_IDENTIFIER_TOKEN) {
358    $identifier = $dom->createElement("identifier");
359    $identifier->setAttribute('value', $token['value']);
360    return $identifier;
361  } if ($token['type']==EBNF_LITERAL_TOKEN){
362    $literal = $dom->createElement("terminal");
363    $literal->setAttribute('value', stripcslashes(substr($token['value'], 1, strlen($token['value'])-2 )));
364    return $literal;
365  } if (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '(')) {
366    $expression = ebnf_parse_expression($dom, $tokens, $i);
367    $token = $tokens[$i++];
368    if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, ')'))
369      throw new EbnfException("Group must end with ')'", $token['pos']);
370    return $expression;
371  } if (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '[')) {
372    $option = $dom->createElement("option");
373    $option->appendChild(ebnf_parse_expression($dom, $tokens, $i));
374    $token = $tokens[$i++];
375    if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, ']'))
376      throw new EbnfException("Option must end with ']'", $token['pos']);
377    return $option;
378  } if (ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '{')) {
379    $loop = $dom->createElement("loop");
380    $loop->appendChild(ebnf_parse_expression($dom, $tokens, $i));
381    $token = $tokens[$i++];
382    if (!ebnf_check_token($token, EBNF_OPERATOR_TOKEN, '}'))
383      throw new EbnfException("Loop must end with '}'", $token['pos']);
384    return $loop;
385  }
386  throw new EbnfException("Factor expected", $token['pos']);
387}
388
389class EbnfException extends Exception {
390    protected int $pos;
391
392    public function __construct($message, $pos) {
393        $this->pos = $pos;
394        parent::__construct($message . ": $pos");
395    }
396
397    public function getPos() {
398        return $this->pos;
399    }
400}
401