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