dcsimg
How to build correct TreeParser for arithmetics?
1 posts in topic
Flat View  Flat View
TOPIC ACTIONS:
 

Posted By:   Vladislav_Vyshemirsky
Posted On:   Thursday, May 8, 2003 04:44 AM

I have a simple arithmetics with + and * operations on terminals. My plain parser builds an AST for terms. I want to write a tree parser which implements the following transformations: (a + b) + c => a + (b + c); (a * b) * c => a * (b * c); (a + b) * c => (a * c) + (b * c); a * (b + c) => (a * b) + (a * c); where a, b and c are the subtrees. My simpliest rule shows the error: Ambiguous reference to AST element PLUS in rule expr expr :! ( #(PLUS #(PLUS expr expr) expr) ) => #(PLUS #(PLUS xa:expr xb:expr) xc:expr) { #expr = #([PLUS], xa, #([PLUS], xb, xc)); } |! ( #(MUL #(MUL expr exp   More>>

I have a simple arithmetics with + and * operations on terminals.

My plain parser builds an AST for terms.

I want to write a tree parser which implements the following transformations:

			
(a + b) + c => a + (b + c);
(a * b) * c => a * (b * c);
(a + b) * c => (a * c) + (b * c);
a * (b + c) => (a * b) + (a * c);

where a, b and c are the subtrees.


My simpliest rule shows the error: Ambiguous reference to AST element PLUS in rule expr

			
expr
:! ( #(PLUS #(PLUS expr expr) expr) ) => #(PLUS #(PLUS xa:expr xb:expr) xc:expr)
{ #expr = #([PLUS], xa, #([PLUS], xb, xc)); }
|! ( #(MUL #(MUL expr expr) expr) ) => #(MUL #(MUL ya: expr yb:expr) yc:expr)
{ #expr = #([MUL], ya, #([MUL], yb, yc)); }
|! ( #(MUL #(PLUS expr expr) expr) ) => #(MUL #(PLUS za:expr zb:expr) zc:expr)
{ #expr = #([PLUS], #([MUL], za, zc ), #([MUL], zb, zc)); }
|! ( #(MUL expr #(PLUS expr expr)) ) => #(MUL ka:expr #(PLUS kb:expr kc:expr))
{ #expr = #([PLUS], #([MUL], ka, kb), #([MUL], ka, kc)); }
| #(PLUS expr expr)
| #(MUL expr expr)
| ID
;


Please, explain how to implement correct TreeParser.    <<Less

Re: How to build correct TreeParser for arithmetics?

Posted By:   Monty_Zukowski  
Posted On:   Friday, May 9, 2003 08:50 AM

I don't see anything wrong with your code. The syntactic predicates should have taken care of the ambiguities.


There is, however, a better way to implement these types of rules. You could use JBurg with antlr as described at http://www.cs.usfca.edu/~parrt/course/652/labs/jburg.html.


I tried to reproduce your problem but I'm having trouble. Could post the smallest complete .g file that would reproduce your error?

About | Sitemap | Contact