🔒 Locked

Operator Associativity

Started by swiftcoder Jul 29, 2007 at 9:49 AM 8 replies 1.6k views

Original Post

swiftcoder

Mod

2,296

swiftcoder

Jul 29, 2007 at 9:49 AM

Just a quick question, as I am writing an ANTLR grammar for a scripting language (purely as an exercise), and I am feeling some gaps in my knowledge :) I took a course on programming languages last semester, and while very useful, it was taught in Scheme, which has no operators. Now I am implementing a C-like language, and I ran into the problem of operators. I know what associativity is, but some help on implementing would be welcome... Here is the complete grammar for statements so far (the tokens I hope are self-explanatory):


statement:   expr ';'
    |	'{' statement* '}'
    |   ';'
    ;

listExpr:	expr (',' expr)*;

selectExpr
	:	atom ( '(' listExpr? ')' | '[' expr ']' | '.' expr )*;

unaryOp	:	('!'|'~'|'+'|'-'|'*'|'&'|'++'|'--')* selectExpr;

binaryMul:	unaryOp (('*'|'/'|'%') unaryOp)*;

binaryAdd:	binaryMul (('+'|'-') binaryMul)*;

shiftOp	:	binaryAdd (('<<'|'>>') binaryAdd)*;

compare :	shiftOp (('<'|'<='|'>'|'>=') shiftOp)*;

equality:	compare (('=='|'!=') compare)*;

bitAnd	:	equality ('&' equality)*;
bitXor	:	bitAnd ('^' bitAnd)*;
bitOr	:	bitXor ('|' bitXor)*;

logAnd	:	bitOr ('&&' bitOr)*;
logOr	:	logAnd ('||' logAnd)*;

assign	:	logOr (('='|'+='|'-='|'*='|'/='|'%='|'&='|'|='|'^='|'<<='|'>>=') logOr)*;

expr
	:	assign;
atom
    :   LITERAL
    |   ID
    |   '(' expr ')'
    ;

This is an early experiment, and my first ANTLR parser, so please don't be too harsh [smile] It parses everything it should (it is close to being a subset of D's statements, I guess), but it doesn't take associativity into account for the operators. This will be generating an AST soon, and I would like to generate the correct associativity directly, rather than having to manipulate the tree to fix this. Would someone be able to explain how I would go about rewriting to handle this? Thanks, - Tristam

ToohrVyk

238

ToohrVyk

Jul 29, 2007 at 10:13 AM

I would suggest a rewriting of the form:

binaryAdd:	  | binaryMul  | binaryAdd ('+'|'-') binaryMul;

swiftcoder

Author Mod

2,296

swiftcoder

Jul 29, 2007 at 10:48 AM

Quote:
Original post by ToohrVyk
I would suggest a rewriting of the form:
binaryAdd:	  | binaryMul  | binaryAdd ('+'|'-') binaryMul;

I s it reasonable to reverse that to remove the left recursion?

binaryAdd:	  | binaryMul  | binaryMul ('+'|'-') binaryAdd;

ToohrVyk

238

ToohrVyk

Jul 29, 2007 at 10:52 AM

Quote:
Original post by swiftcoder
Is it reasonable to reverse that to remove the left recursion?
binaryAdd:	  | binaryMul  | binaryMul ('+'|'-') binaryAdd;

This would result in right-associativeness, which is bad because it would parse 2-2+1 as 2-(2+1).

swiftcoder

Author Mod

2,296

swiftcoder

Jul 29, 2007 at 10:54 AM

Quote:
Original post by ToohrVyk
Quote:
Original post by swiftcoder
Is it reasonable to reverse that to remove the left recursion?
binaryAdd:	  | binaryMul  | binaryMul ('+'|'-') binaryAdd;
This would result in right-associativeness, which is bad because it would parse 2-2+1 as 2-(2+1).

OK, that is roughly the problem I had. So is there a longer way to refactor an expression of this type, since ANTLR doesn't like/support(?) left-recursion?

Edit: I see on further googling that there is no simple way to fix this. Wikipedia does mention adding extra non-terminals to coerce the right recursion into left-associativity though. Any knowledge/links to stuff on this technique?

Your method of recursive expansion gives a much nicer tree than my kleene-star iteration, so I switched the whole thing over (I should have remembered that from class [smile]):

statement:   expr ';'    |	'{' statement* '}'    |   ';'    ;listExpr:	expr (',' expr)*;selectExpr	:	atom ( '(' listExpr? ')' | '[' expr ']' | '.' expr )?;unaryOp	:	('!'|'~'|'+'|'-'|'*'|'&'|'++'|'--')? selectExpr;binaryMul	:	unaryOp (('*'|'/'|'%') binaryMul)?;binaryAdd	:	binaryMul (('+'|'-') binaryAdd)?;shiftOp	:	binaryAdd (('<<'|'>>') shiftOp)?;compare	:	shiftOp (('<'|'<='|'>'|'>=') compare)?;equality:	compare (('=='|'!=') equality)?;bitAnd	:	equality ('&' bitAnd)?;bitXor	:	bitAnd ('^' bitXor)?;bitOr	:	bitXor ('|' bitOr)?;and	:	bitOr ('&&' and)?;or	:	and ('||' or)?;assign	:	or (('='|'+='|'-='|'*='|'/='|'%='|'&='|'|='|'^='|'<<='|'>>=') assign)?;expr 	:	assign;atom    :   LITERAL    |   ID    |   '(' expr ')'    ;

ToohrVyk

238

ToohrVyk

Jul 29, 2007 at 3:04 PM

I do not know of any such method (and I have trouble imagining how it would work, since the tree itself is based on the 'A → A + B' rule of construction because of left-associativeness).

You can work around this problem by having your operations return lists of trees instead of trees, and "folding" the list into a tree whenever it is used as part of a lower-priority operation, thus placing it in the correct configuration.

An illustration in Menhir (which is LALR(1) IIRC, but the grammar being LL):

op:   | PLUS { '+' }  | MINUS { '-' };lBinaryAdd:	  | binaryMul { ($1,'+') }  | left=binaryMul op=op right=lBinaryAdd { (left,op)::right };binaryAdd:  lBinaryAdd {     (* Reverse the list and turn it into a tree *)    let rec make_tree = function       | [] -> assert (false)      | [r,_] -> r      | (r,op)::t -> Node(make_tree t,op,r)    in make_tree (List.rev $1)  };

swiftcoder

Author Mod

2,296

swiftcoder

Jul 29, 2007 at 7:00 PM

Yes, that looks like the way to go. I think I will implement it as a pre-processing pass on the AST tree, at least initially.
So all left-associative operators will be placed into lists, and then the transform pass will turn them into tree segments.
(I wish I was writing this in LISP/scheme, I *hate* manipulating trees in C++, but I am not familiar with a good parser framework there, nor do I want an additional language as a dependency for the compiler)

- Thanks for all your help

ToohrVyk

238

ToohrVyk

Jul 30, 2007 at 12:55 AM

Quote:
Original post by swiftcoder
(I wish I was writing this in LISP/scheme, I *hate* manipulating trees in C++, but I am not familiar with a good parser framework there, nor do I want an additional language as a dependency for the compiler)

Some personal advice: I usually write the tree manipulation code in O'Caml, and then translate it into C++ (using a translation protocol of my own). It's easier to handle that way. You could do the same with Scheme...

Zahlman

257

Zahlman

Aug 2, 2007 at 10:34 AM

Quote:
Original post by swiftcoder
I *hate* manipulating trees in C++, but I am not familiar with a good parser framework there, nor do I want an additional language as a dependency for the compiler)

Boost::spirit?

swiftcoder

Author Mod

2,296

swiftcoder

Aug 7, 2007 at 7:25 PM

Quote:
Original post by Zahlman
Quote:
Original post by swiftcoder
I *hate* manipulating trees in C++, but I am not familiar with a good parser framework there, nor do I want an additional language as a dependency for the compiler)

Boost::spirit?

Sorry, misplacement of punctuation on my part :)
I meant that I am not familiar with a good parser for Scheme (Ja, I know, YACC is in most implementations), and it is a fairly obscure language to have as a compiler dependency (i.e. pretty much no one outside of academia has it pre-installed).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.