[antlr-interest] HELP!!!: with left recursion

[jbb at acm.org]

Aaanwar :-

You may have already worked this out for yourself. Anyway FYI here is my 2
cents...

You asked about ambiguity in 
>exp	--> 	let  decs in exp end
>	| 	if exp then exp end
>	| 	if exp then exp else exp end
>	| 	for ID :=  exp to exp do exp end
>	| 	while exp do exp end
>	| 	lvalue
>	| 	lvalue :=exp
>	| 	builtin
>	| 	ID ( arg_seq  )
>	| 	ID ( )
>	| 	exp &  exp 
>	| 	exp |  exp 
>	| 	exp *  exp 
>	| 	exp /  exp  
>	| 	exp +  exp  
>	| 	exp -  exp  
>	| 	exp =  exp 
>	| 	exp > exp 
>	| 	exp >= exp 
>	| 	exp < exp 
>	| 	exp <= exp 
>	| 	exp <> exp 
>	| 	INTEGER_LITERAL
>	| 	STRING_LIT	
>	| 	( exp_seq )
>	| 	( )

...your trial grammar snipped, but is essentially the same as my attached...

You may have already discovered that the above has a problem with the
assignment expression. Consider this expression:

	while i:=j+1<100 do foo() end

in the (sub)expression immediately after the WHILE keyword which operator
should be performed first? which is last? should it be

  ((i:=j)+1)<100   or   (i:=(j+1))<100   or   i:=((j+1)<100)   or ???

all of these interpretations are possible under your original grammar.

Splitting up the expression rules to achieve operator precedence as Loring
suggested - and you posted a message with your attempt to do so - which I
promply deleted and can not comment on - is probably a Good Thing. Altho I do
not agree that you should split the if, for, and while into a set of separate
statement rules - as long as you have well defined sematics for the value each
of these produces. In my experience, functional languages (Scheme, ML, Haskell,
etc.) all have expression syntax similiar to yours and are therefore, I
believe, very much more powerful than current imperative languages.

Anyway here is a grammar, based on your first try, which removes the ambiguity
on the assignment (note I have not actually executed this, but antlr.Tool does
not complain about it in anyway):

-----Begin-----Begin-----Begin-----Cut Here-----Cut Here-----Cut Here-----
class aaanwar_parser extends Parser;

outermost_expression : exp EOF ; 

exp : lvalue ( ASSIGN ( lvalue ASSIGN )* rvalue )? ;

rvalue : expr ( binaryOp expr )* ;

expr :
      LET decs IN exp END 
    | IF exp THEN exp ( ELSE exp )? END 
    | FOR ID ASSIGN exp TO exp DO exp END 
    | WHILE exp DO exp END 
    | builtin 
    | ID LBRACKET ( arg_seq )? RBRACKET 
    | INTEGER_LITERAL 
    | STRING_LIT 
    | LBRACKET ( exp_seq )? RBRACKET 
    ;

binaryOp :
      AMPERSAND
    | OR
    | STAR
    | DIV
    | PLUS
    | MINUS
    | EQUAL
    | GT
    | GTEQ
    | LT
    | LTEQ
    | NOTEQ
    ;

decs    : DUMMY_DECS_TOKEN ;
lvalue  : DUMMY_LVALUE_TOKEN ;
builtin : DUMMY_BUILTIN_TOKEN ;
arg_seq : DUMMY_ARGS_TOKEN ;
exp_seq : DUMMY_EXPRESSIONS_TOKEN ;
-----End-----End-----End-----Cut Here-----Cut Here-----Cut Here-----

observe that I have added dummy tokens as place holders for those rules which
you did not supply. Usually an lvalue begins with an ID so you may have some
more left factoring to do if you choose to use the above in a real language.

Hope this helps...
-- 
	-jbb

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/