[antlr-interest] Left recursion removal
Johannes Luber
JALuber at gmx.de
Mon Jun 15 05:43:12 PDT 2009
> Hi,
> Below is a fragment from a grammar I've written. I've had to modifiy is so
> that an expression may or may not be enclosed in parenthesis
>
> However, which ever way I try to remove the recursion I either end up by
> reducing teh expressivness or by re-introducing the recursion.
>
> Can anyone help point me in the right direction?
Did you already read <http://www.antlr.org/wiki/display/ANTLR3/Left-Recursion+Removal>?
Johannes
>
>
> grammar SLRR;
>
>
> expression
> : LEFT_PARENTHESIS (predicate|expression) (SPACE_CHAR logicalOperator
> SPACE_CHAR (predicate | expression))* RIGHT_PARENTHESIS
> | (predicate|expression) (SPACE_CHAR logicalOperator SPACE_CHAR
> (predicate | expression))*
> ;
>
>
>
> ///////////////////////////////////////////////////////////////////////
> predicate
> : predicateField SPACE_CHAR searchOperator SPACE_CHAR
> predicateField
> ;
>
>
>
>
> predicateField
> : TEXT
> ;
>
>
> fieldName
> : TEXT
>
> ;
>
> searchOperator
> : TEXT
> | TEXTNOSPACES
>
> //| QUOTATION_MARK urlUnreserved+ (SPACE_CHAR urlUnreserved+)+
> QUOTATION_MARK
> ;
>
> fieldValue
> : TEXT
> //| quotedQueryParamValue
> ;
>
> logicalOperator
> : LOWER_CASE_LETTER_A
> LOWER_CASE_LETTER_N
> LOWER_CASE_LETTER_D
> | LOWER_CASE_LETTER_O
> LOWER_CASE_LETTER_R
> ;
>
> LOWER_CASE_LETTER_A : 'a' ;
> LOWER_CASE_LETTER_B : 'b' ;
> LOWER_CASE_LETTER_C : 'c' ;
> LOWER_CASE_LETTER_D : 'd' ;
> LOWER_CASE_LETTER_E : 'e' ;
> LOWER_CASE_LETTER_F : 'f' ;
> LOWER_CASE_LETTER_G : 'g' ;
> LOWER_CASE_LETTER_H : 'h' ;
> LOWER_CASE_LETTER_I : 'i' ;
> LOWER_CASE_LETTER_J : 'j' ;
> LOWER_CASE_LETTER_K : 'k' ;
> LOWER_CASE_LETTER_L : 'l' ;
> LOWER_CASE_LETTER_M : 'm' ;
> LOWER_CASE_LETTER_N : 'n' ;
> LOWER_CASE_LETTER_O : 'o' ;
> LOWER_CASE_LETTER_P : 'p' ;
> LOWER_CASE_LETTER_Q : 'q' ;
> LOWER_CASE_LETTER_R : 'r' ;
> LOWER_CASE_LETTER_S : 's' ;
> LOWER_CASE_LETTER_T : 't' ;
> LOWER_CASE_LETTER_U : 'u' ;
> LOWER_CASE_LETTER_V : 'v' ;
> LOWER_CASE_LETTER_W : 'w' ;
> LOWER_CASE_LETTER_X : 'x' ;
> LOWER_CASE_LETTER_Y : 'y' ;
> LOWER_CASE_LETTER_Z : 'z' ;
>
> CAPITAL_LETTER_A : 'A' ;
> CAPITAL_LETTER_B : 'B' ;
> CAPITAL_LETTER_C : 'C' ;
> CAPITAL_LETTER_D : 'D' ;
> CAPITAL_LETTER_E : 'E' ;
> CAPITAL_LETTER_F : 'F' ;
> CAPITAL_LETTER_G : 'G' ;
> CAPITAL_LETTER_H : 'H' ;
> CAPITAL_LETTER_I : 'I' ;
> CAPITAL_LETTER_J : 'J' ;
> CAPITAL_LETTER_K : 'K' ;
> CAPITAL_LETTER_L : 'L' ;
> CAPITAL_LETTER_M : 'M' ;
> CAPITAL_LETTER_N : 'N' ;
> CAPITAL_LETTER_O : 'O' ;
> CAPITAL_LETTER_P : 'P' ;
> CAPITAL_LETTER_Q : 'Q' ;
> CAPITAL_LETTER_R : 'R' ;
> CAPITAL_LETTER_S : 'S' ;
> CAPITAL_LETTER_T : 'T' ;
> CAPITAL_LETTER_U : 'U' ;
> CAPITAL_LETTER_V : 'V' ;
> CAPITAL_LETTER_W : 'W' ;
> CAPITAL_LETTER_X : 'X' ;
> CAPITAL_LETTER_Y : 'Y' ;
> CAPITAL_LETTER_Z : 'Z' ;
>
> DIGIT_0 : '0' ;
> DIGIT_1 : '1' ;
> DIGIT_2 : '2' ;
> DIGIT_3 : '3' ;
> DIGIT_4 : '4' ;
> DIGIT_5 : '5' ;
> DIGIT_6 : '6' ;
> DIGIT_7 : '7' ;
> DIGIT_8 : '8' ;
> DIGIT_9 : '9' ;
>
> TEXT
> @init{StringBuilder lBuf = new StringBuilder();}
> :
> QUOTATION_MARK
> ( escaped=ESC {lBuf.append(getText());} |
> normal=~(QUOTATION_MARK|'\\'|'\n'|'\r')
> {lBuf.appendCodePoint(normal);} )*
> QUOTATION_MARK
> {setText("\""+lBuf.toString()+"\"");}
> ;
>
> fragment
> ESC
> : '\\'
> ( 'n' {setText("\n");}
> | 'r' {setText("\r");}
> | 't' {setText("\t");}
> | 'b' {setText("\b");}
> | 'f' {setText("\f");}
> | '"' {setText("\"");}
> | '\'' {setText("\'");}
> | '\\' {setText("\\");}
> | ('u')+ i=HEX_DIGIT j=HEX_DIGIT k=HEX_DIGIT l=HEX_DIGIT
> {setText(this.hextToString(i.getText(),j.getText(),k.getText(),l.getText()));}
>
> )
> ;
>
> fragment
> HEX_DIGIT:
>
> DIGIT_0|DIGIT_1|DIGIT_2|DIGIT_3|DIGIT_4|DIGIT_5|DIGIT_6|DIGIT_7|DIGIT_8|DIGIT_9
>
> |LOWER_CASE_LETTER_A|LOWER_CASE_LETTER_B|LOWER_CASE_LETTER_C|LOWER_CASE_LETTER_D
>
> |LOWER_CASE_LETTER_E|LOWER_CASE_LETTER_F|CAPITAL_LETTER_A|CAPITAL_LETTER_B
> |CAPITAL_LETTER_C|CAPITAL_LETTER_D|CAPITAL_LETTER_E|CAPITAL_LETTER_F
> ;
>
> fragment
> TEXTNOSPACES
> : (HEX_DIGIT|'g'..'z'|'G'..'Z'|'-'|':')+
> ;
>
>
> AMPERSAND : '&' ; // &
> APOSTROPHE : '\'' ;
> ASTERISK : '*' ;
> CIRCUMFLEX_ACCENT : '^' ;
> COLON : ':' ;
> COMMA : ',' ;
> PERCENT_SIGN : '%';
> DOLLAR_SIGN : '$';
> HYPHEN_MINUS : '-';
> LOW_LINE : '_';
> FULL_STOP : '.';
> PLUS_SIGN : '+';
> EXCLAMATION_MARK : '!';
> LEFT_PARENTHESIS : '(';
> RIGHT_PARENTHESIS : ')';
> SEMICOLON : ';';
> SLASH : '/';
> QUESTION_MARK : '?';
> EQUALS_SIGN :'=';
> COMMERCIAL_AT : '@';
> HASH_SIGN : '#';
> TILDE : '~';
> QUOTATION_MARK : '"';
> SPACE_CHAR : ' ';
>
>
> Need a Holiday? Win a $10,000 Holiday of your choice. Enter
> now.http://us.lrd.yahoo.com/_ylc=X3oDMTJxN2x2ZmNpBF9zAzIwMjM2MTY2MTMEdG1fZG1lY2gDVGV4dCBMaW5rBHRtX2xuawNVMTEwMzk3NwR0bV9uZXQDWWFob28hBHRtX3BvcwN0YWdsaW5lBHRtX3BwdHkDYXVueg--/SIG=14600t3ni/**http%3A//au.rd.yahoo.com/mail/tagline/creativeholidays/*http%3A//au.docs.yahoo.com/homepageset/%3Fp1=other%26p2=au%26p3=mailtagline
--
GMX FreeDSL Komplettanschluss mit DSL 6.000 Flatrate und Telefonanschluss
für nur 17,95 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02
More information about the antlr-interest
mailing list