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