1 /*********************************************************************
2 Copyright 2012, Ralph Ronnquist.
4 This file is part of GORITE.
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.
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.
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 **********************************************************************/
20 package com.intendico.sdp;
22 import java.io.FileReader;
23 import java.io.IOException;
24 import java.io.StringWriter;
25 import java.io.PrintWriter;
26 import java.text.ParseException;
27 import java.util.Comparator;
28 import java.util.HashSet;
29 import java.util.Hashtable;
30 import java.util.Iterator;
31 import java.util.TreeMap;
32 import java.util.TreeSet;
34 import java.util.Vector;
37 * The Grammar class is used for defining a grammar.
39 public class Grammar {
42 // Support methods for text processing.
46 * Utility method to make a string from a named file.
48 static public String loadFile(String filename)
50 FileReader f = new FileReader( filename );
51 char [] buffer = new char [ 1024 ];
53 StringBuffer s = new StringBuffer();
54 while ( ( length = f.read( buffer ) ) >= 0 ) {
56 s.append( buffer, 0, length );
62 private String strip(String a) {
63 Class [] c = { BNFGrammar.class, getClass() };
64 for ( int i=0; i < c.length; i++ ) {
65 if ( a.startsWith( c[i].getName() + "$" ) )
66 return a.substring( c[i].getName().length() + 1 );
72 * Utility method to map a string index into a line number, by
75 static public int lineNumber(CharSequence s,int index) {
77 for ( int i = 0; i < index; i++ ) {
78 if ( s.charAt( i ) == '\n' ) {
86 * Utility method that forms a string to mark out the indexed
87 * position in the input string.
89 static public String inputPosition(CharSequence input,int index) {
90 return inputPosition( input, index, 0 );
94 * Utility method that forms a string to mark out the indexed
95 * position and span in the input string.
97 static public String inputPosition(CharSequence input,int index,int span) {
101 int from = lastIndexOf( input, "\n", index - 1 ) + 1;
102 int to = indexOf( input, "\n", index );
103 boolean spandots = false;
108 int lineno = lineNumber( input, from );
109 int at = index - from;
114 String line = lineno + ": ";
121 if ( at + span > 60 ) {
122 // Adjust to fit on a line
123 int clip = at + span - 55;
133 if ( to - from > 70 )
137 line += input.subSequence( from, to ).toString();
138 if ( at + span > to )
144 StringBuffer out = new StringBuffer( line );
147 for (int i=0; i<at; i++ ) {
148 if ( Character.isWhitespace( line.charAt( i ) ) ) {
149 out.append( line.charAt( i ) );
155 for (int i=0; i<span; i++ ) {
162 return out.toString();
166 * Utility method to determine if an CharSequence starts with a given
167 * string at a given position.
169 static public boolean startsWith(CharSequence input,int from,String what) {
170 int end = from + what.length();
171 if ( end > input.length() )
173 return what.contentEquals( input.subSequence( from, end ) );
177 * Returns the last occurence of a given string before a given index.
179 static public int lastIndexOf(CharSequence s,String what,int from) {
180 int endw = what.length();
183 int end = s.length();
184 int end1 = end - endw;
185 char first = what.charAt( endw - 1 );
186 for ( from = from - 1; from >= endw; from-- ) {
187 if ( s.charAt( from ) != first )
189 for ( int p = from - 1, k = endw - 2; p >= 0; p--, k-- ) {
192 if ( s.charAt( p ) != what.charAt( k ) )
200 * Returns the first occurence of a given string.
202 static public int indexOf(CharSequence s,String what,int from) {
203 int endw = what.length();
206 int end = s.length();
207 int end1 = end - endw;
208 char first = what.charAt( 0 );
209 for ( ; from < end1; from++ ) {
210 if ( s.charAt( from ) != first )
212 for ( int p = from + 1, k = 1;; p++, k++ ) {
215 if ( s.charAt( p ) != what.charAt( k ) )
223 * Utility method to scan past blank or comment.
225 static public int skipBlanksAndComments(CharSequence s,int from) {
226 int end = s.length();
227 for ( ; from < end; from++ ) {
228 if ( Character.isWhitespace( s.charAt( from ) ) )
230 if ( s.charAt( from ) != '/' )
232 if ( s.length() < 2 )
234 if ( s.charAt( from + 1 ) == '*' ) {
235 int x = indexOf( s, "*/", from );
237 // Unterminated comment
243 if ( s.charAt( from + 1 ) == '/' ) {
244 int x = indexOf( s, "\n", from );
246 // Unterminated comment
258 * The Parse interface represents the result from parsing, prior
259 * to semantic processing.
261 public interface ParseTree {
264 * Returns the first character position spanned by this parse
267 public int getFrom();
270 * Returns the first significant character position within the
271 * region spanned by this parse tree.
273 public int getFirst();
276 * Returns the first character position after the region
277 * spanned by this parse tree.
282 * Returns the grammar rule index for this result.
284 public int getIndex();
287 * Returns the grammar rule for this result, if any.
289 public String getRule();
292 * Returns the 'substance' portion of the span.
294 public String getText();
297 * Returns the parsetree's generic syntax name, which is the
298 * rule name for production syntax, and ":" otherwise.
300 public String getSyntaxName();
303 * Utility method to form a string representation of this
304 * parse tree element, with an indentation argument.
306 public String toString(String head);
309 * Forms a string representation of two lines to indicate the
310 * span of this result on the input line.
312 public String inputSpan();
315 * Forms a string representation of the span region.
317 public String spanString();
320 * Processing method for this parse tree.
322 public Object process() throws Throwable;
325 * Processing method for the children of this parse tree.
327 public Vector processChildren() throws Throwable;
331 * The Result class is for carrying parsing result.
333 public class Result implements ParseTree {
336 * Refers to the input being parsed.
338 public final CharSequence input;
341 * The character position in the input from where this Result
344 public final int from;
347 * The first character position recognised as not whitespace
348 * or comment; the beginning of 'substance'.
350 public final int first;
353 * The character position in the input to where this Result
354 * object spans. Thus, the span is input.substring(from,to).
359 * Flag as to whether or not the text should be preserved upon
360 * semantic processing.
362 public final boolean preserve;
365 * Returns the first character position spanned by this parse
368 public int getFrom() {
373 * Returns the first significant character position within the
374 * region spanned by this parse tree.
376 public int getFirst() {
381 * Returns the first character position after the region
382 * spanned by this parse tree.
391 public Result(CharSequence s,int a,int b,int c) {
392 this( s, a, b, c, false );
398 public Result(CharSequence s,int a,int b,int c,boolean p) {
407 * Returns the 'substance' portion of the span.
409 public String getText() {
410 return input.subSequence( first, to ).toString();
414 * Returns the grammar rule index for this result.
416 public int getIndex() {
421 * Returns the grammar rule for this result.
423 public String getRule() {
428 * Returns the parsetree's generic syntax name, which is the
429 * rule name for production syntax, and ":" otherwise.
431 public String getSyntaxName() {
436 * Returns the canonical token string for this result.
438 public String getToken() {
439 return "'" + getText();
443 * Forms a String representaion of this Result object.
444 * The argument is ignored.
446 public String toString(String head) {
451 * Forms a string representation of the region spanned.
453 public String spanString() {
454 return "[" + from + "," + to + "]";
458 * Presents this result bmo of an input context on one line,
459 * followed by a 'marker' for the span beneath it.
461 public String inputSpan() {
462 return inputPosition( input, first, to - first );
466 * Forms a String representaion of this Result object.
468 public String toString() {
469 return "{" + from + "," + first + "," + to +
470 ( preserve? "=!'" : "='" ) +
475 * Default result processing returns null.
477 public Object process() throws Throwable {
484 * Processing method for the children of this parse tree.
486 public Vector processChildren() throws Throwable {
492 * The ProductionResult class is for carrrying production rule
495 public class ProductionResult extends Result {
498 * Tells the name of the non-terminal produced.
503 * Tells the index for the production used.
508 * Holds the result objects of associated with production rule
511 public ParseTree [] results;
514 * Returns the grammar rule index for this result.
516 public int getIndex() {
521 * Returns the grammar rule for this result.
523 public String getRule() {
528 * Constructor intended for Lexical rules.
530 public ProductionResult(String r,CharSequence s,int a,int b,int c) {
537 * General constructor.
539 public ProductionResult(String r,CharSequence s,int i,ParseTree [] rs) {
541 rs == null? 0 : rs[0].getFrom(),
542 rs == null? 0 : rs[0].getFirst(),
543 rs == null? -1 : rs[ rs.length - 1 ].getTo() );
549 * Returns the parsetree's generic syntax name, which is the
550 * rule name for production syntax, and ":" otherwise.
552 public String getSyntaxName() {
557 * Returns the canonical token string for this result.
559 public String getToken() {
560 return "<" + getRule() + ">";
564 * Forms a string representation of the parse tree.
566 public String toString() {
567 return toString( "" );
571 * Forms a string representation of the parse tree, using the
572 * given string as indentation prefix.
574 public String toString(String head) {
575 StringBuffer s = new StringBuffer();
581 if ( results == null ) {
582 s.append( super.toString() );
584 for ( int i=0; i<results.length; i++ ) {
590 s.append( results[i].toString( head ) );
598 * Default result processing invokes the process method of the
601 public Object process() throws Throwable {
603 return getDefinition( rule ).process( this );
604 } catch (Throwable e) {
605 throw hideParse( e );
610 * Utility method to process the children
612 public Vector processChildren() throws Throwable {
613 Vector v = new Vector();
614 if ( results != null ) {
615 for ( int i=0; i<results.length; i++ ) {
616 Object x = results[i].process();
629 public TreeMap rules = new TreeMap();
632 // Inner interfaces to support concept generalisation.
633 // These are: Rule, Token and ErrorToken.
637 * The Rule interface is for all kinds of syntax definitions.
638 * Presently there are only the two kinds of ProductionList and
641 public interface Rule {
644 * Returns a ParseTree object for successful parse, or
647 public ParseTree parse(CharSequence s,int from) throws ParseException;
650 * Returns the rule name; the non-terminal defined.
652 public String getName();
655 * Performs synthesising operations on a ParseTree
656 * parse tree, and returns a value representing the parse tree
659 public Object process(ParseTree pr) throws Throwable;
663 // The parsing elements.
667 * Bit field for stderr tracing of parser operation.
669 public int trace = 0;
672 * A counter of entries to syntax rules; "attempts"
674 public int trace_count = 0;
676 public static int TRACE_TERMINALS = 1;
677 public static int TRACE_PARSE = 2;
678 public static int TRACE_RECURSION = 4;
679 public static int TRACE_ACTION = 8;
680 public static int TRACE_OPTIONS = 16;
681 public static int TRACE_LINK = 32;
682 public static int TRACE_STACK = 64;
684 public static int REUSE_ALWAYS = 0;
685 public static int REUSE_RECURSIVE = 1;
686 public static int REUSE_RARELY = 2;
687 public int reuse_mode = 0;
691 public int current_from = 0;
694 * Utility method for tracing.
696 public void log(CharSequence input,int from,String rule,String m) {
697 ParseTree last = last( from, rule );
699 String text = "At " + from + ", " + rule + " " +
700 ( last != null? last.spanString() : "[null]" ) + " - " + m ;
702 if ( from != current_from && input != null ) {
703 System.err.println();
704 int span = current_from > from? current_from - from : 0;
705 text = inputPosition( input, from, span ) + "\n" + text;
709 System.err.println( text );
713 * Utility method to test trace mode.
715 public boolean tracing(int mode) {
716 return ( trace & mode ) != 0;
720 * Table of successful parse results.
722 public Hashtable results = null;
725 * Table of known failed parse postions.
727 public HashSet failed = null;
730 * Current parsing level.
732 public int level = 0;
735 * Maps positions to tried lexical rules and terminals
737 public TreeMap errors;
740 * Support method to create a hash key for a rule at a position.
742 public String key(int from,String rule) {
743 return rule + " at " + from ;
747 * Support method to create a hash key for a rule at a position.
749 public String key(int from,String rule,int index) {
750 return rule + ":" + index + " at " + from;
754 * Returns the last parse result for a rule at a position.
756 public ParseTree last(int from,String rule) {
757 if ( results == null )
759 return (ParseTree) results.get( key( from, rule ) );
763 * Support method to set the parse result for a rule at a position.
765 public void saveLast(int from,String rule,ParseTree x) {
768 if ( results == null )
769 results = new Hashtable();
770 results.put( key( from, rule ), x );
774 * Support method to remove the parse result for a rule at a
777 public void clearLast(int from,String rule) {
778 if ( results != null )
779 results.remove( key( from, rule ) );
783 * Tells whether a parse position is known to be failed.
785 public boolean isFailed(int from,String rule) {
786 return failed != null && failed.contains( key( from, rule ) );
790 * Marks a parse position as failed.
792 public void setFailed(int from,String rule) {
793 if ( failed == null )
794 failed = new HashSet();
795 failed.add( key( from, rule ) );
799 * Unmarks a parse position as failed.
801 public void clearFailed(int from,String rule) {
802 if ( failed != null )
803 failed.remove( key( from, rule ) );
807 * Tells whether a parse position is known to be failed.
809 public boolean isFailed(int from,String rule,int index) {
810 return failed != null && failed.contains( key( from, rule, index ) );
814 * Marks a parse option position as failed.
816 public void setFailed(int from,String rule,int index) {
817 if ( failed == null )
818 failed = new HashSet();
819 failed.add( key( from, rule, index ) );
823 * Unmarks a parse position as failed.
825 public void clearFailed(int from,String rule,int index) {
826 if ( failed != null )
827 failed.remove( key( from, rule, index ) );
835 * Support method to log an attempted lexical match.
837 public void tryToken(ErrorToken token,int from) {
838 if ( errors == null )
839 errors = new TreeMap(
841 public int compare(Object a,Object b)
843 return ((Integer) a).compareTo( (Integer) b );
846 Integer i = new Integer( from );
847 TreeSet t = (TreeSet) errors.get( i );
849 t = new TreeSet( new Comparator() {
850 public int compare(Object a,Object b) {
851 return compare( (ErrorToken) a, (ErrorToken) b );
854 public int compare(ErrorToken a,ErrorToken b) {
855 return a.errorName().compareTo( b.errorName() );
864 * Report all error tokens.
866 public String allErrors() {
867 StringBuffer s = new StringBuffer();
868 for ( Iterator i = errors.keySet().iterator(); i.hasNext(); ) {
869 Integer index = (Integer) i.next();
870 TreeSet list = getErrors( index.intValue() );
872 s.append( index.toString() );
874 for ( Iterator e = list.iterator(); e.hasNext(); ) {
876 s.append( (String) e.next() );
884 * Utility method that presents the deepest error in format.
889 public String lastError(CharSequence input) {
890 return errors == null? null : lastError( input, lastErrorPosition() );
893 public int lastErrorPosition() {
894 if ( errors == null )
896 return ((Integer) errors.lastKey()).intValue();
900 * Returns a string of the error names produced by the indicated
903 public TreeSet getErrors(int from) {
904 return (TreeSet) errors.get( new Integer( from ) );
908 * Utility method that presents the deepest error in format.
913 public String lastError(CharSequence input,int from) {
914 StringBuffer out = new StringBuffer();
915 out.append( inputPosition( input, from ) );
916 out.append( " [" + from + "]" );
917 out.append( "\nExpected: " );
919 TreeSet set = getErrors( from );
924 for ( Iterator e = set.iterator(); e.hasNext(); i--) {
927 out.append( " or " );
932 out.append( ((ErrorToken) e.next()).errorName() );
935 return out.toString();
939 * The ErrorToken interface is for producing error token name.
941 public interface ErrorToken {
944 * Returns the token name.
946 public String errorName();
955 * A ProductionList defines a rule by a list of alternative
958 public class ProductionList implements Rule {
961 * The rule defined by the productions.
963 public final String rule;
966 * The list of optional productions for this rule.
968 public final Production [] options;
973 public ProductionList(String r,Production [] list) {
976 if ( list != null ) {
977 for ( int i=0; i<list.length; i++ ) {
978 list[i].setRule( r, i );
984 * Returns the name of the non-terminal defined.
986 public String getName() {
993 * The default parsing of a ProductionList rule is to apply a
994 * modified recursive decent algorithm, which allows
995 * left-recursive as grammars.
997 public ParseTree parse(CharSequence input,int from)
998 throws ParseException {
999 if ( options == null ) {
1000 // Missing syntax definition
1001 throw new ParseException(
1002 "<" + rule + "> is not defined.", from );
1005 boolean recursive = usage == from; // Re-entering this rule
1007 ParseTree last = last( from, rule );
1008 ParseTree result = null;
1010 boolean reuse = reuse_mode < 2 && last != null &&
1011 ( reuse_mode == 0 || recursive );
1014 if ( tracing( TRACE_OPTIONS ) )
1015 log( input, from, rule,
1016 "re-using last (mode=" + reuse_mode + ")" );
1020 int prior_usage = usage;
1023 boolean again = false;
1030 for (int i=0; result == null && i<options.length; i++ ) {
1031 if ( tracing( TRACE_OPTIONS ) )
1032 log( input, from, rule, "check option " + i );
1033 result = options[i].parse( input, from );
1035 if ( result == null ) {
1036 if ( tracing( TRACE_OPTIONS ) )
1037 log( input, from, rule, "all options failed" );
1041 if ( last == null || last.getTo() < result.getTo() ) {
1042 saveLast( from, rule, result );
1043 if ( tracing( TRACE_OPTIONS ) )
1044 log( input, from, rule, "new result" );
1048 if ( tracing( TRACE_OPTIONS ) )
1049 log( input, from, rule, "old result" );
1056 usage = prior_usage;
1063 * Forms a string representation of this rule.
1065 public String toString() {
1066 if ( options == null ) {
1067 // Missing syntax definition
1068 return rule + " IS NOT DEFINED";
1071 StringBuffer s = new StringBuffer();
1074 s.append( " ::= " );
1075 for ( int i=0; i<options.length; i++ ) {
1077 s.append( "\n | " );
1078 s.append( options[i].toString() );
1081 return s.toString();
1085 * Default rule processing applies the option action to the
1086 * processed children.
1088 public Object process(ParseTree pr) throws Throwable {
1090 return options[ pr.getIndex() ].
1091 action( pr, pr.processChildren() );
1092 } catch (Throwable t) {
1093 throw hideParse( t );
1100 * Represents a production alternative.
1102 public class Production {
1105 * The production rule tokens.
1107 public Token [] tokens;
1110 * Set to mark where this rule is attempted
1112 public int usage = -1;
1115 * Set to the non-terminal that this is a production for, if
1118 public String rule = null;
1121 * Help variable used for tracing purposes.
1123 private String rulex;
1126 * Set to be the option index for the rule the Production
1129 public int index = -1;
1134 public Production() {
1138 * Alternative constructor.
1140 public Production(Token [] t) {
1145 * Utility method to set the tokens of the production.
1147 public void setTokens(Token [] t) {
1152 * Utility method to set the rule name.
1154 public void setRule(String r,int i) {
1157 rulex = rule + ":" + i;
1161 * Utility variable to hold the key string.
1163 public String key = null;
1166 * Returns the key string; computes it once first.
1168 public String getKey() {
1175 * Equality method is based on production string.
1177 public boolean equals(Object x) {
1178 return x instanceof Production &&
1179 getKey().equals( ((Production) x).getKey() );
1183 * Hash code method; uses the key string.
1185 public int hashCode() {
1186 return getKey().hashCode();
1190 * Returns the number of tokens.
1192 public int length() {
1193 return tokens == null? -1 : tokens.length;
1199 * The default parsing of a Production is to try the tokens
1200 * from left to right.
1202 public ParseTree parse(CharSequence input,int from)
1203 throws ParseException {
1204 if ( tokens == null ) {
1205 throw new ParseException(
1206 rule + ":" + index + " has no tokens", from );
1209 recursive = usage == from;
1211 if ( usage == from ) {
1212 // Reentering this Production recursively.
1213 if ( tokens.length > 1 ) {
1214 if ( tracing( TRACE_OPTIONS ) )
1215 log( input, from, rulex, "recursive fail");
1218 // Recursive singleton
1219 if ( tracing( TRACE_OPTIONS ) )
1220 log( input, from, rulex, "recursive singleton");
1224 if ( tracing( TRACE_OPTIONS ) )
1225 log( input, from, rulex, "previous usage = " + usage );
1231 ParseTree [] results = new ParseTree [ tokens.length ];
1232 ParseTree result = null;
1233 for ( int i=0; i<tokens.length; i++ ) {
1234 results[i] = tokens[i].parse( input, from );
1235 if ( results[i] == null ) {
1236 if ( tracing( TRACE_OPTIONS ) )
1237 log( input, from, rulex,
1238 "failed at token " + tokens[i] );
1242 from = results[i].getTo() ;
1244 result = new ProductionResult( rule, input, index, results );
1246 if ( tracing( TRACE_OPTIONS ) )
1247 log( input, prior, rulex,
1248 "result = " + result.spanString() );
1257 * Forms a string representation of this Production.
1259 public String toString() {
1260 StringBuffer s = new StringBuffer();
1262 for ( int i=0; i<tokens.length; i++ ) {
1263 s.append( tokens[i].toString() );
1266 String actual = getClass().getName();
1267 if ( ! actual.equals( Production.class.getName() ) ) {
1269 s.append( strip( actual ) );
1272 return s.toString();
1276 * Default option action is to call action(Vector), and
1277 * thereby ignore the source position.
1279 public Object action(ParseTree pr,Vector v) throws Throwable {
1281 if ( tracing( TRACE_ACTION ) )
1283 "action " + pr.getRule() + ":" + pr.getIndex() +
1284 " with " + v.size() + " arguments" );
1286 } catch (Throwable t) {
1288 t + "\n" + pr.inputSpan() + " " + pr.spanString(), t );
1289 t.setStackTrace( new StackTraceElement [0] );
1295 * Default Production action is to return the first argument
1296 * if there is a single one, otherwise the whole argument
1299 public Object action(Vector v) throws Exception {
1300 if ( tracing( TRACE_ACTION ) )
1301 System.err.println( "default Production action with " +
1302 v.size() + " arguments" );
1303 if ( v.size() == 0 )
1305 if ( v.size() == 1 )
1306 return v.elementAt( 0 );
1312 * The Token interface is for production rule tokens.
1314 public interface Token {
1317 * Returns the token name.
1319 public String getName();
1322 * Returns the token's generic syntax name, which is the rule
1323 * name for production syntax, and ":" otherwise.
1325 public String getSyntaxName();
1328 * Returns a parse Result object, or null
1330 public ParseTree parse(CharSequence s,int from) throws ParseException;
1335 * A Terminal is a symbol to find verbatim.
1337 public class Terminal implements Token, ErrorToken {
1340 * The symbol to find.
1342 public final String text;
1345 * The key symbol to use for this token.
1347 public final String ttext;
1350 * Flag to mark whether or not this terminal token is visible
1353 public final boolean preserve;
1356 * Flag to mark whether or not this terminal token is visible
1359 public final boolean optional;
1364 public Terminal(String t) {
1365 this( t, false, false );
1371 public Terminal(String t,boolean p) {
1372 this( t, p, false );
1378 public Terminal(String t,boolean p,boolean opt) {
1384 else if ( preserve )
1391 * Equality for terminals are measured on their name strings.
1393 public boolean equals(Object x) {
1394 return x instanceof Terminal &&
1395 getName().equals( ((Terminal) x).getName() ) ;
1399 * Hash code method; uses the key string.
1401 public int hashCode() {
1402 return getName().hashCode();
1406 * Returns the rule name; the non-terminal defined.
1408 public String getName() {
1413 * Returns the token's generic syntax name, which is the rule
1414 * name for production syntax, and ":" otherwise.
1416 public String getSyntaxName() {
1421 * The default parsing of a terminal token is to match it
1422 * against the current position, after ignoring whitespace and
1425 public ParseTree parse(CharSequence s,int from) throws ParseException {
1426 ParseTree result = last( from, ttext );
1427 if ( result != null )
1429 if ( isFailed( from, ttext ) )
1431 tryToken( this, from );
1432 if ( tracing( TRACE_TERMINALS ) )
1433 System.err.println( "Find " + text + " at pos " + from );
1434 int first = skipBlanksAndComments( s, from );
1435 if ( ! startsWith( s, first, text ) ) {
1437 if ( tracing( TRACE_TERMINALS ) )
1439 "Found omitted optional " + text +
1440 " at pos " + first );
1441 result = new Result(
1442 s, from, first, first, false );
1443 saveLast( from, "", result );
1446 setFailed( from, ttext );
1450 if ( tracing( TRACE_TERMINALS ) )
1451 System.err.println( "Found " + text + " at pos " + first );
1452 result = new Result(
1453 s, from, first, first + text.length(), preserve );
1454 saveLast( from, ttext, result );
1459 * Forms a string representation of this terminal token.
1461 public String toString() {
1466 * The standard error name for a terminal token.
1468 public String errorName() {
1469 return "'" + text + "'" ;
1474 * A NonTerminal is a reference to a syntax rule.
1476 public class NonTerminal implements Token {
1479 * Holds the name of the non-terminal.
1481 public final String rule;
1486 public NonTerminal(String r) {
1491 * Returns the rule name; the non-terminal defined.
1493 public String getName() {
1498 * Returns the token's generic syntax name, which is the rule
1499 * name for production syntax, and ":" otherwise.
1501 public String getSyntaxName() {
1502 return getDefinition( rule ) instanceof ProductionList?
1507 * The default parsing of a non-terminal token is to defer to
1508 * apply its definition to the current input position.
1510 public ParseTree parse(CharSequence input,int from)
1511 throws ParseException {
1513 if ( tracing( TRACE_PARSE ) ) {
1514 log( input, from, rule, ">>-- " + (++level) + " -->>" );
1517 Rule r = getDefinition( rule );
1519 throw new ParseException(
1520 "<" + rule + "> is not defined.", from );
1523 ParseTree result = r.parse( input, from );
1525 if ( result == null ) {
1526 if ( tracing( TRACE_PARSE ) )
1527 log( input, from, rule,
1528 "<<-- " + (level--) + " --<< failed" );
1532 if ( tracing( TRACE_PARSE ) )
1533 log( input, from, rule, "<<-- " + (level--) + " --<< " +
1534 result.spanString() );
1537 } catch (ParseException e) {
1538 throw (ParseException) hideParse( e );
1539 } catch (Throwable e) {
1540 ParseException pe = new ParseException( e.toString(), from );
1547 * Forms a string representation of a non-terminal token.
1549 public String toString() {
1550 return "<" + rule + ">" ;
1555 * The Lexical class is a base class for lexical tokens.
1557 abstract public class Lexical implements Rule, ErrorToken {
1562 final public String rule;
1567 public Lexical(String r) {
1572 * Returns the rule name.
1574 public String getName() {
1579 * Equality for terminals are measured on their error name
1582 public boolean equals(Object x) {
1583 return x instanceof Lexical &&
1584 errorName().equals( ((Lexical) x).errorName() ) ;
1588 * Hash code method; uses the key string.
1590 public int hashCode() {
1591 return errorName().hashCode();
1595 * Handle token ingress, which typically means to skip
1598 public int ingress(CharSequence input,int from) {
1599 return skipBlanksAndComments( input, from );
1603 * The default parsing of a lexical rule: skips blanks and
1604 * comments, and then invokes scan.
1606 public ParseTree parse(CharSequence input,int from)
1607 throws ParseException {
1608 ParseTree last = last( from, rule );
1609 if ( isFailed( from, rule ) ) {
1610 if ( tracing( TRACE_OPTIONS ) )
1611 log( input, from, rule, "lexical known failed" );
1614 if ( last != null ) {
1615 if ( tracing( TRACE_OPTIONS ) )
1616 log( input, from, rule,
1617 "lexical reuse " + last.spanString() );
1620 tryToken( this, from );
1621 int first = ingress( input, from );
1622 int to = scan( input, first );
1624 setFailed( from, rule );
1625 if ( tracing( TRACE_OPTIONS ) )
1626 log( input, from, rule, "lexical failed" );
1629 last = new ProductionResult( rule, input, from, first, to );
1630 saveLast( from, rule, last );
1631 if ( tracing( TRACE_OPTIONS ) )
1632 log( input, from, rule, "lexical success" );
1637 * The lexical function, which returns the end of the span
1638 * covered by the lexical rule, or -1. The method is given the
1639 * input string and the position to scan, which is neither
1640 * whitespace nor in a comment.
1642 abstract public int scan(CharSequence s,int from);
1645 * Forms a string representation of this lexical rule.
1647 public String toString() {
1649 rule + " is lexical " + strip( getClass().getName() ) + "\n" ;
1653 * The standard error name for a lexical rule.
1655 public String errorName() {
1656 return "<" + rule + ">";
1660 * Semantic processing for a lexical will return the matched
1661 * string unless it's an empty string.
1663 public Object process(ParseTree pr) {
1664 return pr.getFirst() == pr.getTo()? null : pr.getText();
1669 * The Link class is a base class for rules that link to
1672 public class Link implements Rule {
1675 * The grammar linked to.
1677 public final Grammar grammar;
1680 * The name of the non-terminal in this grammar.
1682 public final String rule;
1685 * The corresponding name in the linked grammar.
1687 public final String goal;
1692 public Link(String r,String g,Grammar gr) {
1699 * Constructor. Alternative constructor using the same rule
1700 * name in both grammars.
1702 public Link(String r,Grammar gr) {
1707 * Returns the 'local' rule name
1709 public String getName() {
1714 * Parse input, save result, and return true if successful.
1716 public ParseTree parse(CharSequence input,int from)
1717 throws ParseException {
1718 if ( grammar.tracing( TRACE_LINK ) )
1719 grammar.log( input, from, rule, "link: " + goal );
1720 int trace_start = grammar.trace_count;
1722 ParseTree p = grammar.parse( goal, input, from );
1724 trace_count += grammar.trace_count - trace_start;
1725 int index = grammar.lastErrorPosition();
1726 TreeSet t = grammar.getErrors( index );
1727 for ( Iterator i = t.iterator(); i.hasNext(); )
1728 tryToken( (ErrorToken) i.next(), index );
1731 if ( tracing( TRACE_LINK ) )
1733 input, from, rule, "link return: " + goal + " = " +
1734 p.spanString() + " with last error at " + index );
1736 if ( tracing( TRACE_LINK ) )
1739 "link return: " + goal + " failed" );
1745 * Semantic processing for a Link
1747 public Object process(ParseTree pr) throws Throwable {
1748 // The parse tree is contained in the other grammar.
1749 return grammar.process( pr );
1752 public String toString() {
1753 String pkg = Grammar.this.getClass().getName();
1754 pkg = pkg.substring( 0, pkg.lastIndexOf( "." ) + 1 );
1755 String name = grammar.getClass().getName();
1756 if ( name.startsWith( pkg ) )
1757 name = name.substring( pkg.length() );
1759 rule + " is linked to <" + goal + "> in " + name + "\n";
1764 // Additional Grammar methods
1768 * Constructor. Invokes the initialisation() method.
1775 * Overridable method to perform grammar initialisation.
1777 public void initialisation() {
1781 * Utility method to add a syntax rule.
1783 public void addRule(Rule rule) {
1784 rules.put( rule.getName(), rule );
1788 * Applies a syntax rule to a string.
1790 public ParseTree parse(String rule,CharSequence input)
1791 throws ParseException {
1792 for ( Iterator i = getGrammars().iterator(); i.hasNext(); ) {
1793 Grammar g = (Grammar) i.next();
1796 return parse( rule, input, 0 );
1800 * Resets the parsing machinery.
1802 public void reset() {
1810 * Applies a syntax rule to a string.
1812 public ParseTree parse(String rule,CharSequence input,int from)
1813 throws ParseException {
1814 Rule r = getDefinition( rule );
1816 throw new ParseException(
1817 "<" + rule + "> is not defined.", from );
1818 return r.parse( input, from );
1822 * Utility method to change the stack trace of an exception by
1823 * removing all Grammar elements.
1825 public Throwable hideParse(Throwable e) {
1826 return hideParse( e, Grammar.class.getName() );
1830 * Utility method to change the stack trace of an exception by
1831 * removing all elements with agiven class name prefix.
1833 public Throwable hideParse(Throwable e,String prefix) {
1834 if ( tracing( TRACE_STACK ) )
1837 for ( Throwable t = e; t != null; t = t.getCause() ) {
1838 StackTraceElement[] stack = t.getStackTrace();
1839 Vector v = new Vector();
1840 for ( int i=0; i<stack.length; i++ ) {
1841 String s = stack[i].getClassName();
1842 if ( ! ( s.startsWith( prefix ) ||
1843 s.startsWith( "java." ) ||
1844 s.startsWith( "sun." ) ) )
1847 t.setStackTrace( (StackTraceElement[]) v.toArray(
1848 new StackTraceElement [ v.size() ] ) );
1853 public Rule getDefinition(String rule) {
1854 return (Rule) rules.get( rule );
1858 * Utility method to process a parse, and catch exception
1860 public Object process(ParseTree pr) throws Throwable {
1861 return pr.process();
1865 * Applies a syntax rule to a string and performs its semantics.
1867 public Object parseAndProcess(String rule,String input)
1869 ParseTree p = parse( rule, input );
1871 return process( p );
1872 System.err.println( lastError( input ) );
1877 * Returns a TreeSet of all included grammars, sorted by class
1880 public Vector getGrammars() {
1881 return getGrammars( null );
1885 * Collect all grammars involved, by linking.
1887 private Vector getGrammars(Vector v) {
1888 Vector links = v != null? v : new Vector();
1892 for ( Iterator i = rules.keySet().iterator(); i.hasNext(); ) {
1893 Rule r = getDefinition( (String) i.next() );
1894 if ( r instanceof Link ) {
1895 Link link = (Link) r;
1896 if ( ! links.contains( link.grammar ) )
1897 link.grammar.getGrammars( links );
1904 * Utility method for text representation.
1906 public String toStringAlone() {
1907 StringBuffer s = new StringBuffer();
1908 for ( Iterator i = rules.keySet().iterator(); i.hasNext(); ) {
1909 Rule r = getDefinition( (String) i.next() );
1910 s.append( r.toString() );
1912 return s.toString();
1916 * Textual representation of a grammar.
1918 public String toString() {
1919 Vector t = getGrammars( null );
1920 StringBuffer s = new StringBuffer();
1921 boolean rest = false;
1922 for ( Iterator i = t.iterator(); i.hasNext(); ) {
1923 Grammar g = (Grammar) i.next();
1927 s.append( "/*** Definitions of grammar " );
1928 s.append( g.getClass().getName() );
1929 s.append( " follow ***/\n" );
1930 s.append( g.toStringAlone() );
1932 return s.toString();
1936 // Auxillary support for 'remoteHCyl2 semantics'. These are used by the
1937 // action tagging of LLBNF.
1941 * An interface for production rule actions.
1943 public interface RuleAction {
1944 public Object action(Vector v)
1949 * A table of tagged rule actions.
1951 Hashtable rule_actions = new Hashtable();
1954 * Utility method for defining rule actions.
1956 public void setAction(String tag,RuleAction r) {
1957 rule_actions.put( tag, r );
1961 * Utility method for defining rule actions.
1963 public void setAction(Class c,String tag,RuleAction r) {
1964 for ( Iterator i = getGrammars().iterator(); i.hasNext(); ) {
1965 Grammar g = (Grammar) i.next();
1966 if ( c.isInstance( g ) )
1967 g.rule_actions.put( tag, r );