[antlr-interest] Grammar nondeterminism on recursion
beginner'squestion
Stritzel.Nils at infineon.com
Stritzel.Nils at infineon.com
Fri Apr 28 02:16:01 PDT 2006
Thanks, I got your idea. Since you asked (or rather explicitly did not
ask) why DOUBLEs can occur in batchExprs and not runExprs, the answer is
rather simple, because runExpr is a variable standing for a value or
array (to be read from a Database or wherever), but don't ask me why
it's legacy.
Nils
-----Original Message-----
From: Loring Craymer [mailto:craymer at warpiv.com]
Sent: Friday, April 28, 2006 5:04 PM
To: Nils Stritzel (IFIS DC); antlr-interest at antlr.org
Subject: RE: [antlr-interest] Grammar nondeterminism on recursion
beginner'squestion
The most reasonable way is to combine the rules called by runExpr and
batchExpr, and return a three-valued integer as to whether a RUNVARIABLE
or BATCHVARIABLE (or DOUBLE) has been encountered or not:
primaryExpr
returns [int flag = 0]
:
DOUBLE { flag = -1; }
|
BATCHVARIABLE { flag = -1; }
|
RUNVARIABLE { flag = 1; }
|
(LPAREN^ flag = batchExpr RPAREN! )
|
flag = functionCall
;
signedExpr
returns [int flag]
:
(m: MINUS^ {#m.setType(SIGN_MINUS);} | p: PLUS^
{#p.setType(SIGN_PLUS);})
flag = baseExpr
;
and so forth. (sumExpr will require two flags; an error condition
exists if
flag1 * flag2 == -1.) I won't ask why DOUBLEs can occur in batchExprs
and not runExprs--or even why there is a difference, since the RUNCSID
and BATCHCSID distinguish the result--although that seems very odd.
Basically, the idea is to distinguish runExprs from batchExprs
semantically, not syntactically. Build trees according to recognized
semantics (e. g., have a BATCH_SEP and a RUN_SEP for lists) so that they
are differentiated syntactically during tree walks.
--Loring
> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Stritzel.Nils at infineon.com
> Sent: Friday, April 28, 2006 12:38 AM
> To: antlr-interest at antlr.org
> Subject: [antlr-interest] Grammar nondeterminism on recursion
> beginner'squestion
>
> Hi all,
>
> I am still working my fomrula parser and after solving an earlier
> issue (thanks to Martin Probst).
> But now I have got a new problem.
>
> My grammar includes a list that contains to different types of
> elements runExpr and batchExpr. This is supposed to contains and list
> one runExpr and one batchExpr.
>
> runBatchExprList
> :
> (runExpr SEP!) =>
> runExpr SEP! runBatchExprList
> |
> runExpr SEP! batchExpr
> |
> (batchExpr SEP!) =>
> batchExpr SEP! runBatchExprList
> |
> batchExpr SEP! runExpr
> ;
>
> But the matter is that runExpr and batchExpr can start with the same
> Tokens so this seemingly causes some problem.
> Is there a way to make the parser know which is the right alternative?
> Can I get this to work without rewriting everything?
> Below is my (for this posting somewhat simplified) grammar.
> Maybe the question boils down to the question, how to choose correctly
> from a a rule like this:
> Rule1 : batchExpr | runExpr ;
>
>
> Thanks,
>
> Nils
>
>
>
>
> class ExpressionParser extends Parser; options {
> buildAST = true; // uses CommonAST by default
> k = 1;
> }
>
> imaginaryTokenDefinitions
> :
> SIGN_MINUS
> SIGN_PLUS
> ;
>
> expr :
> (formula)* EOF!
> ;
>
> formula
> :
> BATCHCSID ASSIGN^ batchExpr
> |
> RUNCSID ASSIGN^ runExpr
> ;
>
> batchExpr
> :
> sumExpr
> ;
>
> sumExpr :
> baseExpr ((PLUS^|MINUS^) baseExpr)*
> ;
>
> baseExpr
> :
> primaryExpr
> |
> signedExpr
> ;
>
> signedExpr
> :
> (m: MINUS^ {#m.setType(SIGN_MINUS);} | p: PLUS^
> {#p.setType(SIGN_PLUS);})
> baseExpr
> ;
>
> primaryExpr
> :
> DOUBLE
> |
> BATCHVARIABLE
> |
> (LPAREN^ batchExpr RPAREN! )
> |
> functionCall
> ;
>
>
> functionCall
> :
> (CABS^ | CSIGN^) LPAREN! batchExpr RPAREN!
> |
> ((CAVG LPAREN^) => CAVG LPAREN! batchExprList RPAREN!
> | CAVG LPAREN! batchExpr RPAREN!)
> |
> (CMAX^ | CMIN^) LPAREN! batchExprList RPAREN!
> ;
>
>
> batchExprList
> :
> batchExpr (SEP! batchExpr)+ {## = #(#[SEP], ##); }
> ;
>
> runExpr :
> runSumExpr
> ;
>
> runSumExpr
> :
> runBaseExpr ((PLUS^|MINUS^) runBaseExpr)*
> ;
>
>
> runBaseExpr
> :
> runPrimaryExpr
> |
> runSignedExpr
> ;
>
>
> runSignedExpr
> :
> (m: MINUS^ {#m.setType(SIGN_MINUS);} | p: PLUS^
> {#p.setType(SIGN_PLUS);})
> runBaseExpr
> ;
>
> runPrimaryExpr
> :
> RUNVARIABLE
> |
> (LPAREN^ runExpr RPAREN! )
> |
> runFunctionCall
> ;
>
>
> runFunctionCall
> :
> (CABS^ | CSIGN^) LPAREN! runExprList RPAREN!
> |
> (CMAX^) => (CMAX^ LPAREN! runBatchExprList RPAREN!)
> |
> (CMAX^ LPAREN! runExprList RPAREN!)
> |
> (CMIN^) => (CMIN^ LPAREN! runBatchExprList RPAREN!)
> | (CMIN^ LPAREN! runExprList RPAREN!)
> |
> (CAVG^) => (CAVG^ LPAREN! runExprList RPAREN!)
> |
> (CAVG^ LPAREN! runExpr RPAREN!)
> ;
>
> runExprList
> :
> runExpr (SEP! runExpr)+ {## = #(#[SEP], ##); }
> ;
>
>
>
> runBatchExprList
> :
> (runExpr SEP!) =>
> runExpr SEP! runBatchExprList
> |
> runExpr SEP! batchExpr
> |
> (batchExpr SEP!) =>
> batchExpr SEP! runBatchExprList
> |
> batchExpr SEP! runExpr
> ;
>
>
>
>
> class ExpressionLexer extends Lexer;
>
> options {
> caseSensitive = false;
> k = 8;
> }
>
> PLUS :
> '+'
> ;
>
> MINUS :
> '-'
> ;
>
> MULT :
> '*'
> ;
>
> DIV :
> '/'
> ;
>
> LPAREN :
> '('
> ;
>
> RPAREN :
> ')'
> ;
>
> protected DIGIT
> :
> '0'..'9'
> ;
>
> WS :
> (' '
> |
> '\t'
> |
> '\r' '\n' {newline(); }
> |
> '\n' {newline(); }
> )
> { $setType(Token.SKIP); }
> ;
>
> DOUBLE :
> (DIGIT)+ ('.' (DIGIT)+)? ('e' (MINUS|PLUS)? (DIGIT)+ )?
> ;
>
> ASSIGN :
> '='
> ;
>
> SEP :
> '\\'
> ;
>
>
> RUNCSID
> :
> "rsc."
> ;
>
> RUNVARIABLE
> :
> "r."
> ;
>
> BATCHCSID
> :
> "bsc."
> ;
>
> BATCHVARIABLE
> :
> "b."
> ;
>
> CMAX :
> "c_max"
> ;
>
> CMIN :
> "c_min"
> ;
>
> CABS :
> "c_abs"
> ;
>
> CAVG :
> "c_avg"
> ;
>
> CSIGN :
> "c_sign"
> ;
More information about the antlr-interest
mailing list