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