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