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