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