jGuru Forums

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

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?