com/intendico/sdp/BNFGrammar.java

   1 /*********************************************************************
   2 Copyright 2012, Ralph Ronnquist.
   3
   4 This file is part of GORITE.
   5
   6 GORITE is free software: you can redistribute it and/or modify it
   7 under the terms of the Lesser GNU General Public License as published
   8 by the Free Software Foundation, either version 3 of the License, or
   9 (at your option) any later version.
  10
  11 GORITE is distributed in the hope that it will be useful, but WITHOUT
  12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  14 License for more details.
  15
  16 You should have received a copy of the Lesser GNU General Public
  17 License along with GORITE.  If not, see <http://www.gnu.org/licenses/>.
  18 **********************************************************************/
  19
  20 package com.intendico.sdp;
  21
  22 import java.util.Vector;
  23 import java.util.Hashtable;
  24 import java.util.Iterator;
  25 import java.util.TreeSet;
  26
  27 /**
  28  * The BNFGrammar class is a base class for grammars that make use of
  29  * the LLBNF translator for defining their syntax.
  30  */
  31 public class BNFGrammar extends Grammar {
  32
  33     /**
  34      * Utility method to scan for blank or comment.
  35      */
  36     public int findBlankOrComment(CharSequence s,int from) {
  37         int end = s.length();
  38         for ( ; from < end; from++ ) {
  39             if ( Character.isWhitespace( s.charAt( from ) ) )
  40                 return from;
  41             if ( s.charAt( from ) != '/' )
  42                 continue;
  43             if ( from + 1 >= end )
  44                 return end;
  45             if ( s.charAt( from + 1 ) == '*' )
  46                 return from;
  47             if ( s.charAt( from + 1 ) == '/' )
  48                 return from;
  49         }
  50         return end;
  51     }
  52
  53     //
  54     // Predefined lexical scanners.
  55     //
  56
  57     /**
  58      * A Nothing is a lexical token that accepts.
  59      */
  60     public class Nothing extends Lexical {
  61
  62         /**
  63          * Constructor.
  64          */
  65         public Nothing(String r) {
  66             super( r );
  67         }
  68
  69         /**
  70          * Scanning nothing.
  71          * Requires nothing.
  72          */
  73         public int scan(CharSequence s,int from) {
  74             return from;
  75         }
  76     }
  77
  78     /**
  79      * An AnySymbol is a lexical token between blanks or comments.
  80      */
  81     public class AnySymbol extends Lexical {
  82
  83         /**
  84          * Constructor.
  85          */
  86         public AnySymbol(String r) {
  87             super( r );
  88         }
  89
  90         /**
  91          * Scanning anything unto next blank or comment or end.
  92          * Requires something.
  93          */
  94         public int scan(CharSequence s,int from) {
  95             int to = findBlankOrComment( s, from );
  96             return from == to? -1 : to ;
  97         }
  98     }
  99
 100     /**
 101      * An End is a lexical token for nothing after blanks or comments.
 102      */
 103     public class End extends Lexical {
 104
 105         /**
 106          * Constructor.
 107          */
 108         public End(String r) {
 109             super( r );
 110         }
 111
 112         /**
 113          * Requires there to remain nothing.
 114          */
 115         public int scan(CharSequence s,int from) {
 116             return from == s.length()? from : -1 ;
 117         }
 118     }
 119
 120     /**
 121      * An Identifier is a lexical token of Java identifier characters.
 122      */
 123     public class Identifier extends Lexical {
 124
 125         /**
 126          * Constructor.
 127          */
 128         public Identifier(String r) {
 129             super( r );
 130         }
 131
 132         /**
 133          * Scanning a Java identifier.
 134          */
 135         public int scan(CharSequence s,int from) {
 136             int end = s.length();
 137             if ( from == end )
 138                 return -1;
 139
 140             if ( ! Character.isJavaIdentifierStart( s.charAt( from++ ) ) )
 141                 return -1;
 142
 143             for ( ; from < end; from++ ) {
 144                 if ( ! Character.isJavaIdentifierPart( s.charAt( from ) ) )
 145                     return from;
 146             }
 147             return end;
 148         }
 149     }
 150
 151     /**
 152      * A PackedChars is a lexical token consisting of a string of
 153      * characters of a given collection, in any order.
 154      */
 155     public class PackedChars extends Lexical {
 156
 157         /**
 158          * The accepted characters.
 159          */
 160         public String characters;
 161
 162         /**
 163          * Constructor.
 164          */
 165         public PackedChars(String r,String set) {
 166             super( r );
 167             characters = set;
 168         }
 169
 170         /**
 171          * Scanning a PackedChars.
 172          */
 173         public int scan(CharSequence s,int from) {
 174             int end = s.length();
 175             if ( from == end )
 176                 return -1;
 177
 178             if ( characters.indexOf( s.charAt( from++ ) ) < 0 )
 179                 return -1;
 180
 181             for ( ; from < end; from++ ) {
 182                 if ( characters.indexOf( s.charAt( from ) ) < 0 )
 183                     return from;
 184             }
 185             return end;
 186         }
 187     }
 188
 189     /**
 190      * A Number is a lexical token of digits. Optionally preceded by a
 191      * single "-".
 192      */
 193     public class Number extends Lexical {
 194
 195         /**
 196          * Constructor.
 197          */
 198         public Number(String r) {
 199             super( r );
 200         }
 201
 202         /**
 203          * Scanning an integer, with an optional preceding "-".
 204          */
 205         public int scan(CharSequence s,int from) {
 206             int end = s.length();
 207
 208             if ( from == end )
 209                 return -1;
 210
 211             if ( inSet( s, from, end, "+-" ) )
 212                 from++;
 213
 214             int h = scanSet( s, from, end, "0123456789" );
 215             return h == 0? -1 : from + h;
 216         }
 217     }
 218
 219     /**
 220      * A Number is a lexical token of digits. Optionally preceded by a
 221      * single "-".
 222      */
 223     public class RealNumber extends Lexical {
 224
 225         /**
 226          * Constructor.
 227          */
 228         public RealNumber(String r) {
 229             super( r );
 230         }
 231
 232         /**
 233          * Scanning a real number, with an optional preceding "-" or '+'.
 234          */
 235         public int scan(CharSequence s,int from) {
 236             int end = s.length();
 237             int h = 0;
 238             int f = 0;
 239
 240             if ( from == end )
 241                 return -1;
 242
 243             if ( inSet( s, from, end, "+-" ) ) {
 244                 from++;
 245                 if ( from == end )
 246                     return -1;
 247                 h = scanSet( s, from, end, "0123456789" );
 248             } else {
 249                 if ( s.charAt( from++ ) == '0' ) {
 250                     // possible lead-in  for 0xh* or otherwise octal?
 251                     if ( from == end )
 252                         return end;
 253                     if ( s.charAt( from++ ) == 'x' ) {
 254                         // found 0x lead-in
 255                         h = scanSet( s, from+2, end, "01234567abcdefABCDEF" );
 256                         if ( h == 0 )
 257                             return -1;
 258                         return from + h;
 259                     }
 260                     from--;
 261                     return from + scanSet( s, from, end, "01234567" );
 262                 }
 263                 from--; //
 264                 h = scanSet( s, from, end, "0123456789" );
 265                 if ( h == 0 )
 266                     return -1;
 267             }
 268
 269             from += h;
 270             if ( from == end )
 271                 return h == 0? -1 : end;
 272
 273             if ( s.charAt( from++ ) == '.' ) {
 274                 // there's a fraction part
 275                 f = scanSet( s, from, end, "0123456789" );
 276                 if ( h == 0 && f == 0 )
 277                     return -1;
 278                 from += f;
 279                 if ( from >= end )
 280                     return end;
 281                 if ( inSet( s, from, end, "fF" ) )
 282                     return from + 1;
 283             } else {
 284                 // There's no fractional part
 285                 from--;
 286                 if ( h == 0 )
 287                     return -1;
 288                 if ( inSet( s, from, end, "lL" ) )
 289                     return from + 1;
 290             }
 291
 292             if ( ! inSet( s, from++, end, "eE" ) )
 293                 return from - 1;
 294
 295             // scan exponent
 296             if ( inSet( s, from, end, "+-" ) )
 297                 from++;
 298             f = scanSet( s, from, end, "0123456789" );
 299             return f == 0? -1 : from + f;
 300         }
 301     }
 302
 303     /**
 304      * Scans past the given set of characters, and tells how far it
 305      * has scanned.
 306      */
 307     static public int scanSet(CharSequence s,int from,int end,String set) {
 308         int start = from;
 309         for ( ; from < end; from++ )
 310             if ( set.indexOf( s.charAt( from ) ) < 0 )
 311                 return from - start ;
 312         return from - start;
 313     }
 314
 315     /**
 316      * Tells if the character in s at from is one of those in the set.
 317      */
 318     static public boolean inSet(CharSequence s,int from,int end,String set) {
 319         return from < end? set.indexOf( s.charAt( from ) ) >= 0 : false;
 320     }
 321
 322     /**
 323      * Scan a compound character after the '\':
 324      * \ a    - letter or any non-digit
 325      * \ ooo   - octal
 326      * \ x hh   - hexadecimal
 327      * \ u nnnn - digits
 328      */
 329     static public int compound(CharSequence s,int from,int end) {
 330         if ( from >= end )
 331             return 0;
 332         switch ( s.charAt( from ) ) {
 333         case 'x':
 334             return 3;
 335         case 'u':
 336             return 5;
 337         case '0': case '1': case '2': case '3':
 338         case '4': case '5': case '6': case '7':
 339             return 3;
 340         default:
 341             return 1;
 342         }
 343     }
 344
 345     /**
 346      * A String is a lexical token between a mark characters
 347      * (double-quotes by default), but without a new-line in it.
 348      */
 349     public class QuotedString extends Lexical {
 350
 351         public char mark;
 352
 353         /**
 354          * Constructor.
 355          */
 356         public QuotedString(String r,char m) {
 357             super( r );
 358             mark = m;
 359         }
 360
 361         /**
 362          * Utility constructor to use double-quote as mark character.
 363          */
 364         public QuotedString(String r) {
 365             this( r, '"' );
 366         }
 367
 368         /**
 369          * Scanning a String
 370          */
 371         public int scan(CharSequence s,int from) {
 372             int end = s.length();
 373
 374             if ( from == end || s.charAt( from++ ) != mark )
 375                 return -1;
 376
 377             tryToken( this, from ); // Special marker
 378
 379             for ( ; from < end; ) {
 380                 char c = s.charAt( from++ );
 381                 if ( c == mark )
 382                     return from;
 383                 if ( c == '\n' )
 384                     return -1; // bad string
 385                 if ( c == '\\' ) {
 386                     // lead-in for compound characters.
 387                     from += compound( s, from, end );
 388                     if ( from > end )
 389                         return -1;
 390                 }
 391             }
 392             // Bad string 2
 393             return -1;
 394         }
 395
 396         /**
 397          * The error name for a buggy string.
 398          */
 399         public String errorName() {
 400             return "terminated and well-formed <" + rule + ">" ;
 401         }
 402     }
 403
 404     /**
 405      * A QuotedCharacter is a lexical token between a pair of
 406      * single-quotes, with restrictions.
 407      */
 408     public class QuotedCharacter extends Lexical {
 409
 410         /**
 411          * Constructor.
 412          */
 413         public QuotedCharacter(String r) {
 414             super( r );
 415         }
 416
 417         /**
 418          * Scanning a String
 419          */
 420         public int scan(CharSequence s,int from) {
 421             int end = s.length();
 422
 423             if ( from == end || s.charAt( from++ ) != '\'' )
 424                 return -1;
 425
 426             tryToken( this, from ); // Special marker
 427
 428             if ( from == end )
 429                 return -1;
 430
 431             switch ( s.charAt( from++ ) ) {
 432             case '\'':
 433                 return -1;
 434             case '\\':
 435                 from += compound( s, from, end );
 436                 break;
 437             default:
 438                 from += 1;
 439                 break;
 440             }
 441             if ( from >= end )
 442                 return -1;
 443             if ( s.charAt( from++ ) != '\'' )
 444                 return -1;
 445             return from;
 446         }
 447
 448         /**
 449          * The error name for a buggy string.
 450          */
 451         public String errorName() {
 452             return "terminated and well-formed <" + rule + ">" ;
 453         }
 454     }
 455
 456
 457     /**
 458      * A lexical scanner to match multi-word phrases from a given
 459      * collection. It greedily consumes its longest match.
 460      */
 461     public class PhraseSet extends Lexical {
 462
 463         /**
 464          * Matching phrases. This contains the successive heads of the
 465          * matching phrases, mapped to 0, 1, or 2. 0 means that the
 466          * phrase ends there, 1 means it must continue, and 2 means it
 467          * may end or continue. The scanner always consumes as much as
 468          * possible.
 469          */
 470         public TreeSet/*<String>*/ phrases = new TreeSet/*<String>*/();
 471
 472         /**
 473          * Cache of defining phrases.
 474          */
 475         public Vector/*<String>*/ definition = new Vector/*<String>*/();
 476
 477         /**
 478          * Constructor for a given name and collection of phrases.
 479          */
 480         public PhraseSet(String name,Vector/*<String>*/ set) {
 481             super( name );
 482             addSet( set );
 483         }
 484
 485         /**
 486          * Utility method to add a collection of phrases.
 487          */
 488         public void addSet(Vector/*<String>*/ set) {
 489             for ( Iterator si = set.iterator(); si.hasNext(); ) {
 490                 String phrase = (String) si.next();
 491                 definition.add( phrase );
 492                 phrases.add( phrase.toLowerCase() );
 493             }
 494         }
 495
 496         /**
 497          * Returns index to first character following a matching
 498          * token.
 499          */
 500         public int scan(CharSequence input,int from) {
 501             CharSequence phrase = input.subSequence( from, input.length() );
 502             if ( from >= input.length() )
 503                 return -1;
 504             char first = phrase.charAt( 0 );
 505             for ( Iterator/*<String>*/ pi =
 506                       phrases.headSet( phrase, true ).descendingIterator();
 507                   pi.hasNext(); ) {
 508                 String key = (String) pi.next();
 509                 if ( key.charAt( 0 ) != first ) {
 510                     System.err.println( "failed: " + key );
 511                     return -1;
 512                 }
 513                 if ( startsWith( phrase, 0, key ) ) {
 514                     return from + key.length();
 515                 }
 516             }
 517             return -1;
 518         }
 519
 520         /**
 521          * Returns this collection as a defintion clause:
 522          * name = { .... }
 523          */
 524         public String toString() {
 525             StringBuilder s = new StringBuilder();
 526             s.append( rule );
 527             s.append( " = {" );
 528             String separator = "\n  ";
 529             //for ( String phrase : definition ) {
 530             for ( Iterator pi = phrases.iterator(); pi.hasNext(); ) {
 531                 String phrase = (String) pi.next();
 532                 s.append( separator );
 533                 s.append( phrase );
 534                 separator = ",\n  ";
 535             }
 536             s.append( "\n}\n" );
 537             return s.toString();
 538         }
 539     }
 540
 541     //
 542     // Predefined utility actions
 543     //
 544
 545     /**
 546      * Utility method to add elements individually from a Vector
 547      * operand, if it begins with the operator.
 548      */
 549     static public void addArguments(Vector args,Object op,Object opnd) {
 550         if ( opnd instanceof Vector ) {
 551             Vector v = (Vector) opnd;
 552             if ( v.size() > 0 && op.equals( v.get( 0 ) ) ) {
 553                 v.remove( 0 );
 554                 args.addAll( v );
 555                 return;
 556             }
 557         }
 558         args.add( opnd );
 559     }
 560
 561     /**
 562      * Helper class for infix syntax
 563      */
 564     public class Infix extends Production {
 565
 566         /**
 567          * Default Infix action is to move the middle element to
 568          * beginning, if there are three arguments, and otherwise
 569          * re-use the Grammar.Production action.
 570          */
 571         public Object action(Vector v) throws Exception {
 572             if ( v.size() != 3 )
 573                 return super.action( v );
 574
 575             v.add( 0, v.remove( 1 ) );
 576             return v;
 577         }
 578     }
 579
 580     /**
 581      * Helper class for postfix syntax
 582      */
 583     public class Postfix extends Production {
 584
 585         /**
 586          * Default Postfix action is to move the last element to
 587          * beginning, if there are more than one argument, and otherwise
 588          * re-use the Grammar.Production action.
 589          */
 590         public Object action(Vector v) throws Exception {
 591             if ( v.size() <= 1 )
 592                 return super.action( v );
 593
 594             v.add( 0, v.remove( v.size() - 1 ) );
 595             return v;
 596         }
 597     }
 598
 599     /**
 600      * Helper class for associative infix syntax
 601      */
 602     public class Associative extends Production {
 603
 604         /**
 605          * Default Associative action is to move the middle element to
 606          * beginning, if there are three arguments, and then flatten
 607          * out the first and last argument of they are vectors with
 608          * the same operator. If there are not three arguments, then
 609          * re-use the Grammar.Production action.
 610          */
 611         public Object action(Vector v) throws Exception {
 612             if ( v.size() != 3 )
 613                 return super.action( v );
 614
 615             Object op = v.get( 1 );
 616             Vector args = new Vector();
 617             args.add( op );
 618             addArguments( args, op, v.get( 0 ) );
 619             addArguments( args, op, v.get( 2 ) );
 620             return args;
 621         }
 622     }
 623
 624     /**
 625      * Helper class for lists
 626      */
 627     public class Enlist extends Production {
 628
 629         /**
 630          * Default Enlist action is coalesc arguments into a Vector.
 631          */
 632         public Object action(Vector v) {
 633             if ( v.size() <= 1 )
 634                 return v;
 635
 636             Object last = v.remove( v.size() - 1 );
 637             if ( last instanceof Vector ) {
 638                 v.addAll( (Vector) last );
 639             } else {
 640                 v.add( last );
 641             }
 642             return v;
 643         }
 644     }
 645
 646     /**
 647      * Helper class for left-associative lists
 648      */
 649     public class Leftlist extends Production {
 650
 651         /**
 652          * Default Enlist action is coalesc arguments into a ".."
 653          * headed Vector.
 654          */
 655         public Object action(Vector v) {
 656             if ( v.size() <= 1 )
 657                 return v;
 658
 659             Object first = v.remove( 0 );
 660
 661             if ( first instanceof Vector ) {
 662                 ((Vector) first).addAll( v );
 663                 return first;
 664             }
 665
 666             v.add( 0, first );
 667             return v;
 668         }
 669     }
 670
 671     /**
 672      * Installs a grammar from string rules using LLBNF.
 673      */
 674     public void install(String rules) {
 675         try {
 676             new LLBNF().addRules( this, rules );
 677         } catch (Throwable t) {
 678             t.printStackTrace();
 679             throw new Error( "Grammar failure" );
 680         }
 681     }
 682
 683     /**
 684      * Utility method to clip a string after some length
 685      */
 686     public String clip(String input,int clip) {
 687         int x = input.indexOf( "\n", 0 );
 688         if ( x > 0 && x < clip )
 689             return input.substring( 0, x ) + " ..." ;
 690         if ( clip < input.length() )
 691             return input.substring( 0, clip ) + "...";
 692         return input;
 693     }
 694
 695     /**
 696      * Utility method to time parse and process.
 697      */
 698     public boolean timedProcess(int i,String goal,String input) {
 699         try {
 700             System.out.println(
 701                 "(" + i + ") " + goal + ": " + clip( input, 65 ) );
 702             long time = System.currentTimeMillis();
 703             ParseTree pr = parse( goal, input );
 704             long snap = System.currentTimeMillis() - time;
 705             if ( pr != null ) {
 706                 //System.out.println( "--> " + pr );
 707                 time = System.currentTimeMillis();
 708                 Object result = process( pr );
 709                 time = System.currentTimeMillis() - time;
 710                 System.out.println( "==> " + result );
 711                 System.out.println(
 712                     "--------- time = " + snap + "/" + time + " ms" );
 713                 return true;
 714             } else {
 715                 System.out.println( lastError( input ) );
 716                 System.out.println(
 717                     "--------- time = " + snap + "/-- ms" );
 718                 return false;
 719             }
 720         } catch (Throwable t) {
 721             t.printStackTrace();
 722         }
 723         return false;
 724     }
 725
 726     /**
 727      * Utility method to parse and process several tests.
 728      */
 729     public boolean processAll(String [][] args) {
 730
 731         for ( int i=0; i<args.length; i++ ) {
 732             if ( ! timedProcess( i, args[i][0], args[i][1] ) )
 733                 return false;
 734         }
 735         return true;
 736     }
 737
 738 }