Home » Modeling » TMF (Xtext) » Left recursion: from binary to n-ary operations
| Left recursion: from binary to n-ary operations [message #57815] |
Mon, 13 July 2009 18:46  |
Eclipse User |
|
|
|
Originally posted by: c.krause.cwi.nl
Hi all,
this is a grammar for arithmetical expressions, as suggested in a post
some weeks ago (thank you Sven, by the way):
PlusOperation returns Expression:
MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
right=MultiplyOperation)*;
MultiplyOperation returns Expression:
PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
right=PrimaryExpression)*;
PrimaryExpression returns Expression:
NumberLiteral |
'(' PlusOperation ')';
NumberLiteral :
value=INT;
If I uderstand it correctly, this avoids the left recursion and nicely
handles the priority of the operations. What I would like to do now is
to go from binary operations to n-ary. My plan would be to:
* make separate rules for +,-,*,/, and then
* to use something like {NaryOp.members += current}
Does that sound like a good plan or did I misunderstood something? Any
suggestions are of course more than welcome.
Cheers,
Christian Krause,
CWI Amsterdam
|
|
|
| Re: Left recursion: from binary to n-ary operations [message #57912 is a reply to message #57815] |
Mon, 13 July 2009 19:19  |
 Sven Efftinge
Messages: 1823
Registered: July 2009 |
Senior Member |
|
|
What exactly do you mean by n-ary?
A fixed size of operands greater than two (e.g. "foo ? bar : baz") or an
arbitrary concatenation of operations ending up as one model element
with any number of operands (like '1 + 2 + 3 + 4 + ...')?
Cheers,
Sven
Christian Krause schrieb:
> Hi all,
>
> this is a grammar for arithmetical expressions, as suggested in a post
> some weeks ago (thank you Sven, by the way):
>
> PlusOperation returns Expression:
> MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
> right=MultiplyOperation)*;
>
> MultiplyOperation returns Expression:
> PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
> right=PrimaryExpression)*;
>
> PrimaryExpression returns Expression:
> NumberLiteral |
> '(' PlusOperation ')';
>
> NumberLiteral :
> value=INT;
>
> If I uderstand it correctly, this avoids the left recursion and nicely
> handles the priority of the operations. What I would like to do now is
> to go from binary operations to n-ary. My plan would be to:
>
> * make separate rules for +,-,*,/, and then
> * to use something like {NaryOp.members += current}
>
> Does that sound like a good plan or did I misunderstood something? Any
> suggestions are of course more than welcome.
>
> Cheers,
> Christian Krause,
> CWI Amsterdam
>
|
|
|
| Re: Left recursion: from binary to n-ary operations [message #57936 is a reply to message #57912] |
Mon, 13 July 2009 19:48 |
| Eclipse User |
|
|
|
Originally posted by: c.krause.cwi.nl
I see that was a bit fuzzy. I mean an arbitrary length >= 2 (so at least
one occurrence of the (same) operand).
Cheers,
Christian
Sven Efftinge wrote:
> What exactly do you mean by n-ary?
> A fixed size of operands greater than two (e.g. "foo ? bar : baz") or an
> arbitrary concatenation of operations ending up as one model element
> with any number of operands (like '1 + 2 + 3 + 4 + ...')?
>
> Cheers,
> Sven
>
>
> Christian Krause schrieb:
>> Hi all,
>>
>> this is a grammar for arithmetical expressions, as suggested in a post
>> some weeks ago (thank you Sven, by the way):
>>
>> PlusOperation returns Expression:
>> MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
>> right=MultiplyOperation)*;
>>
>> MultiplyOperation returns Expression:
>> PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
>> right=PrimaryExpression)*;
>>
>> PrimaryExpression returns Expression:
>> NumberLiteral |
>> '(' PlusOperation ')';
>>
>> NumberLiteral :
>> value=INT;
>>
>> If I uderstand it correctly, this avoids the left recursion and nicely
>> handles the priority of the operations. What I would like to do now is
>> to go from binary operations to n-ary. My plan would be to:
>>
>> * make separate rules for +,-,*,/, and then
>> * to use something like {NaryOp.members += current}
>>
>> Does that sound like a good plan or did I misunderstood something? Any
>> suggestions are of course more than welcome.
>>
>> Cheers,
>> Christian Krause,
>> CWI Amsterdam
>>
|
|
|
| Re: Left recursion: from binary to n-ary operations [message #57984 is a reply to message #57936] |
Mon, 13 July 2009 20:03 |
Sven Efftinge
Messages: 1823
Registered: July 2009 |
Senior Member |
|
|
This could be written like this:
NaryOp returns Expression :
Operand ({NaryOp.operands+=current} '+' operands+=Operand ('+'
operands+=Operand)*)?;
Sven
Christian Krause schrieb:
> I see that was a bit fuzzy. I mean an arbitrary length >= 2 (so at least
> one occurrence of the (same) operand).
>
> Cheers,
> Christian
>
> Sven Efftinge wrote:
>> What exactly do you mean by n-ary?
>> A fixed size of operands greater than two (e.g. "foo ? bar : baz") or
>> an arbitrary concatenation of operations ending up as one model
>> element with any number of operands (like '1 + 2 + 3 + 4 + ...')?
>>
>> Cheers,
>> Sven
>>
>>
>> Christian Krause schrieb:
>>> Hi all,
>>>
>>> this is a grammar for arithmetical expressions, as suggested in a
>>> post some weeks ago (thank you Sven, by the way):
>>>
>>> PlusOperation returns Expression:
>>> MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
>>> right=MultiplyOperation)*;
>>>
>>> MultiplyOperation returns Expression:
>>> PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
>>> right=PrimaryExpression)*;
>>>
>>> PrimaryExpression returns Expression:
>>> NumberLiteral |
>>> '(' PlusOperation ')';
>>>
>>> NumberLiteral :
>>> value=INT;
>>>
>>> If I uderstand it correctly, this avoids the left recursion and
>>> nicely handles the priority of the operations. What I would like to
>>> do now is to go from binary operations to n-ary. My plan would be to:
>>>
>>> * make separate rules for +,-,*,/, and then
>>> * to use something like {NaryOp.members += current}
>>>
>>> Does that sound like a good plan or did I misunderstood something?
>>> Any suggestions are of course more than welcome.
>>>
>>> Cheers,
>>> Christian Krause,
>>> CWI Amsterdam
>>>
|
|
|
| Re: Left recursion: from binary to n-ary operations [message #58033 is a reply to message #57984] |
Mon, 13 July 2009 20:12 |
| Eclipse User |
|
|
|
Originally posted by: c.krause.cwi.nl
Dear Sven,
thank you for this quick and detailed help. I really appreciate it. I
think I know more or less how to go from here.
Cheers,
Christian
PS: I guess you don't happen to know whether Itemis is planning to open
an office in Berlin..
Sven Efftinge wrote:
> This could be written like this:
>
> NaryOp returns Expression :
> Operand ({NaryOp.operands+=current} '+' operands+=Operand ('+'
> operands+=Operand)*)?;
>
> Sven
>
>
> Christian Krause schrieb:
>> I see that was a bit fuzzy. I mean an arbitrary length >= 2 (so at
>> least one occurrence of the (same) operand).
>>
>> Cheers,
>> Christian
>>
>> Sven Efftinge wrote:
>>> What exactly do you mean by n-ary?
>>> A fixed size of operands greater than two (e.g. "foo ? bar : baz") or
>>> an arbitrary concatenation of operations ending up as one model
>>> element with any number of operands (like '1 + 2 + 3 + 4 + ...')?
>>>
>>> Cheers,
>>> Sven
>>>
>>>
>>> Christian Krause schrieb:
>>>> Hi all,
>>>>
>>>> this is a grammar for arithmetical expressions, as suggested in a
>>>> post some weeks ago (thank you Sven, by the way):
>>>>
>>>> PlusOperation returns Expression:
>>>> MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
>>>> right=MultiplyOperation)*;
>>>>
>>>> MultiplyOperation returns Expression:
>>>> PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
>>>> right=PrimaryExpression)*;
>>>>
>>>> PrimaryExpression returns Expression:
>>>> NumberLiteral |
>>>> '(' PlusOperation ')';
>>>>
>>>> NumberLiteral :
>>>> value=INT;
>>>>
>>>> If I uderstand it correctly, this avoids the left recursion and
>>>> nicely handles the priority of the operations. What I would like to
>>>> do now is to go from binary operations to n-ary. My plan would be to:
>>>>
>>>> * make separate rules for +,-,*,/, and then
>>>> * to use something like {NaryOp.members += current}
>>>>
>>>> Does that sound like a good plan or did I misunderstood something?
>>>> Any suggestions are of course more than welcome.
>>>>
>>>> Cheers,
>>>> Christian Krause,
>>>> CWI Amsterdam
>>>>
|
|
|
| Re: Left recursion: from binary to n-ary operations [message #58058 is a reply to message #58033] |
Mon, 13 July 2009 21:23 |
| Eclipse User |
|
|
|
Originally posted by: c.krause.cwi.nl
Since it might be useful for others as well, this is the grammar I'm
using now:
Addition returns Expression:
Subtraction ( {Addition.operands += current} ('+' operands +=
Subtraction)+)?;
Subtraction returns Expression:
Multiplication ( {Subtraction.operands += current} ('-' operands +=
Multiplication)+)?;
Multiplication returns Expression:
Division ( {Multiplication.operands += current} ('*' operands +=
Division)+)?;
Division returns Expression:
Operation ( {Division.operands += current} ('/' operands += Operation)+)?;
Operation returns Expression:
Literal | '(' Addition ')';
Literal:
Constant | Variable;
Variable returns Variable:
name=ID;
Constant returns Constant:
value=INT;
The only wrong thing now is that 'operands' should be an attribute of a
common superclass 'Operation', but this shouldn't be too difficult.
Anyway, thanks again for the help.
Cheers,
Christian
Christian Krause wrote:
> Dear Sven,
> thank you for this quick and detailed help. I really appreciate it. I
> think I know more or less how to go from here.
>
> Cheers,
> Christian
>
>
> PS: I guess you don't happen to know whether Itemis is planning to open
> an office in Berlin..
>
> Sven Efftinge wrote:
>> This could be written like this:
>>
>> NaryOp returns Expression :
>> Operand ({NaryOp.operands+=current} '+' operands+=Operand ('+'
>> operands+=Operand)*)?;
>>
>> Sven
>>
>> Christian Krause schrieb:
>>> I see that was a bit fuzzy. I mean an arbitrary length >= 2 (so at
>>> least one occurrence of the (same) operand).
>>>
>>> Cheers,
>>> Christian
>>>
>>> Sven Efftinge wrote:
>>>> What exactly do you mean by n-ary?
>>>> A fixed size of operands greater than two (e.g. "foo ? bar : baz")
>>>> or an arbitrary concatenation of operations ending up as one model
>>>> element with any number of operands (like '1 + 2 + 3 + 4 + ...')?
>>>>
>>>> Cheers,
>>>> Sven
>>>>
>>>>
>>>> Christian Krause schrieb:
>>>>> Hi all,
>>>>>
>>>>> this is a grammar for arithmetical expressions, as suggested in a
>>>>> post some weeks ago (thank you Sven, by the way):
>>>>>
>>>>> PlusOperation returns Expression:
>>>>> MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
>>>>> right=MultiplyOperation)*;
>>>>>
>>>>> MultiplyOperation returns Expression:
>>>>> PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
>>>>> right=PrimaryExpression)*;
>>>>>
>>>>> PrimaryExpression returns Expression:
>>>>> NumberLiteral |
>>>>> '(' PlusOperation ')';
>>>>>
>>>>> NumberLiteral :
>>>>> value=INT;
>>>>>
>>>>> If I uderstand it correctly, this avoids the left recursion and
>>>>> nicely handles the priority of the operations. What I would like to
>>>>> do now is to go from binary operations to n-ary. My plan would be to:
>>>>>
>>>>> * make separate rules for +,-,*,/, and then
>>>>> * to use something like {NaryOp.members += current}
>>>>>
>>>>> Does that sound like a good plan or did I misunderstood something?
>>>>> Any suggestions are of course more than welcome.
>>>>>
>>>>> Cheers,
>>>>> Christian Krause,
>>>>> CWI Amsterdam
>>>>>
|
|
|
| Re: Left recursion: from binary to n-ary operations [message #58158 is a reply to message #58058] |
Tue, 14 July 2009 08:39 |
Sven Efftinge
Messages: 1823
Registered: July 2009 |
Senior Member |
|
|
Hi Christian,
I think the mathmatical operators below are binary.
IMHO it is best practice to have them as such, because it makes it
simpler to work on them later on.
Why do you want them to be n-ary?
Cheers,
Sven
Christian Krause schrieb:
> Since it might be useful for others as well, this is the grammar I'm
> using now:
>
> Addition returns Expression:
> Subtraction ( {Addition.operands += current} ('+' operands +=
> Subtraction)+)?;
>
> Subtraction returns Expression:
> Multiplication ( {Subtraction.operands += current} ('-' operands +=
> Multiplication)+)?;
>
> Multiplication returns Expression:
> Division ( {Multiplication.operands += current} ('*' operands +=
> Division)+)?;
>
> Division returns Expression:
> Operation ( {Division.operands += current} ('/' operands +=
> Operation)+)?;
>
> Operation returns Expression:
> Literal | '(' Addition ')';
>
> Literal:
> Constant | Variable;
>
> Variable returns Variable:
> name=ID;
>
> Constant returns Constant:
> value=INT;
>
>
> The only wrong thing now is that 'operands' should be an attribute of a
> common superclass 'Operation', but this shouldn't be too difficult.
> Anyway, thanks again for the help.
>
> Cheers,
> Christian
>
>
> Christian Krause wrote:
>> Dear Sven,
>> thank you for this quick and detailed help. I really appreciate it. I
>> think I know more or less how to go from here.
>>
>> Cheers,
>> Christian
>>
>>
>> PS: I guess you don't happen to know whether Itemis is planning to
>> open an office in Berlin..
>>
>> Sven Efftinge wrote:
>>> This could be written like this:
>>>
>>> NaryOp returns Expression :
>>> Operand ({NaryOp.operands+=current} '+' operands+=Operand ('+'
>>> operands+=Operand)*)?;
>>>
>>> Sven
>>> Christian Krause schrieb:
>>>> I see that was a bit fuzzy. I mean an arbitrary length >= 2 (so at
>>>> least one occurrence of the (same) operand).
>>>>
>>>> Cheers,
>>>> Christian
>>>>
>>>> Sven Efftinge wrote:
>>>>> What exactly do you mean by n-ary?
>>>>> A fixed size of operands greater than two (e.g. "foo ? bar : baz")
>>>>> or an arbitrary concatenation of operations ending up as one model
>>>>> element with any number of operands (like '1 + 2 + 3 + 4 + ...')?
>>>>>
>>>>> Cheers,
>>>>> Sven
>>>>>
>>>>>
>>>>> Christian Krause schrieb:
>>>>>> Hi all,
>>>>>>
>>>>>> this is a grammar for arithmetical expressions, as suggested in a
>>>>>> post some weeks ago (thank you Sven, by the way):
>>>>>>
>>>>>> PlusOperation returns Expression:
>>>>>> MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
>>>>>> right=MultiplyOperation)*;
>>>>>>
>>>>>> MultiplyOperation returns Expression:
>>>>>> PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
>>>>>> right=PrimaryExpression)*;
>>>>>>
>>>>>> PrimaryExpression returns Expression:
>>>>>> NumberLiteral |
>>>>>> '(' PlusOperation ')';
>>>>>>
>>>>>> NumberLiteral :
>>>>>> value=INT;
>>>>>>
>>>>>> If I uderstand it correctly, this avoids the left recursion and
>>>>>> nicely handles the priority of the operations. What I would like
>>>>>> to do now is to go from binary operations to n-ary. My plan would
>>>>>> be to:
>>>>>>
>>>>>> * make separate rules for +,-,*,/, and then
>>>>>> * to use something like {NaryOp.members += current}
>>>>>>
>>>>>> Does that sound like a good plan or did I misunderstood something?
>>>>>> Any suggestions are of course more than welcome.
>>>>>>
>>>>>> Cheers,
>>>>>> Christian Krause,
>>>>>> CWI Amsterdam
>>>>>>
|
|
|
| Re: Left recursion: from binary to n-ary operations [message #58281 is a reply to message #58158] |
Tue, 14 July 2009 09:57 |
| Eclipse User |
|
|
|
Originally posted by: c.krause.cwi.nl
Hi Sven,
I understand your concern. I think in the end I will have only addition
and multiplication n-ary and the other two binary. I want to use the
associativity of _+_ and _*_ to simplify the model. If someone enters
(a+(b+c)) I can do a very simple model transformation and write it as
(a+b+c).
Cheers,
Christian
Sven Efftinge wrote:
> Hi Christian,
>
> I think the mathmatical operators below are binary.
> IMHO it is best practice to have them as such, because it makes it
> simpler to work on them later on.
>
> Why do you want them to be n-ary?
>
> Cheers,
> Sven
>
>
> Christian Krause schrieb:
>> Since it might be useful for others as well, this is the grammar I'm
>> using now:
>>
>> Addition returns Expression:
>> Subtraction ( {Addition.operands += current} ('+' operands +=
>> Subtraction)+)?;
>>
>> Subtraction returns Expression:
>> Multiplication ( {Subtraction.operands += current} ('-' operands
>> += Multiplication)+)?;
>>
>> Multiplication returns Expression:
>> Division ( {Multiplication.operands += current} ('*' operands +=
>> Division)+)?;
>>
>> Division returns Expression:
>> Operation ( {Division.operands += current} ('/' operands +=
>> Operation)+)?;
>>
>> Operation returns Expression:
>> Literal | '(' Addition ')';
>>
>> Literal:
>> Constant | Variable;
>>
>> Variable returns Variable:
>> name=ID;
>>
>> Constant returns Constant:
>> value=INT;
>>
>>
>> The only wrong thing now is that 'operands' should be an attribute of
>> a common superclass 'Operation', but this shouldn't be too difficult.
>> Anyway, thanks again for the help.
>>
>> Cheers,
>> Christian
>>
>>
>> Christian Krause wrote:
>>> Dear Sven,
>>> thank you for this quick and detailed help. I really appreciate it. I
>>> think I know more or less how to go from here.
>>>
>>> Cheers,
>>> Christian
>>>
>>>
>>> PS: I guess you don't happen to know whether Itemis is planning to
>>> open an office in Berlin..
>>>
>>> Sven Efftinge wrote:
>>>> This could be written like this:
>>>>
>>>> NaryOp returns Expression :
>>>> Operand ({NaryOp.operands+=current} '+' operands+=Operand ('+'
>>>> operands+=Operand)*)?;
>>>>
>>>> Sven Christian Krause schrieb:
>>>>> I see that was a bit fuzzy. I mean an arbitrary length >= 2 (so at
>>>>> least one occurrence of the (same) operand).
>>>>>
>>>>> Cheers,
>>>>> Christian
>>>>>
>>>>> Sven Efftinge wrote:
>>>>>> What exactly do you mean by n-ary?
>>>>>> A fixed size of operands greater than two (e.g. "foo ? bar : baz")
>>>>>> or an arbitrary concatenation of operations ending up as one model
>>>>>> element with any number of operands (like '1 + 2 + 3 + 4 + ...')?
>>>>>>
>>>>>> Cheers,
>>>>>> Sven
>>>>>>
>>>>>>
>>>>>> Christian Krause schrieb:
>>>>>>> Hi all,
>>>>>>>
>>>>>>> this is a grammar for arithmetical expressions, as suggested in a
>>>>>>> post some weeks ago (thank you Sven, by the way):
>>>>>>>
>>>>>>> PlusOperation returns Expression:
>>>>>>> MultiplyOperation ({BinaryOp.left=current} operator=('+'|'-')
>>>>>>> right=MultiplyOperation)*;
>>>>>>>
>>>>>>> MultiplyOperation returns Expression:
>>>>>>> PrimaryExpression ({BinaryOp.left=current} operator=('*'|'/')
>>>>>>> right=PrimaryExpression)*;
>>>>>>>
>>>>>>> PrimaryExpression returns Expression:
>>>>>>> NumberLiteral |
>>>>>>> '(' PlusOperation ')';
>>>>>>>
>>>>>>> NumberLiteral :
>>>>>>> value=INT;
>>>>>>>
>>>>>>> If I uderstand it correctly, this avoids the left recursion and
>>>>>>> nicely handles the priority of the operations. What I would like
>>>>>>> to do now is to go from binary operations to n-ary. My plan would
>>>>>>> be to:
>>>>>>>
>>>>>>> * make separate rules for +,-,*,/, and then
>>>>>>> * to use something like {NaryOp.members += current}
>>>>>>>
>>>>>>> Does that sound like a good plan or did I misunderstood
>>>>>>> something? Any suggestions are of course more than welcome.
>>>>>>>
>>>>>>> Cheers,
>>>>>>> Christian Krause,
>>>>>>> CWI Amsterdam
>>>>>>>
|
|
|
Goto Forum:
Current Time: Mon Dec 30 14:38:24 GMT 2024
Powered by FUDForum. Page generated in 0.03219 seconds |
] 
Search
Help
Register
Login
Home
