Home » Modeling » TMF (Xtext) » XText parsing expressions with non-binary AST structure
XText parsing expressions with non-binary AST structure [message #792754] |
Tue, 07 February 2012 11:10 |
Joel Greenyer Messages: 170 Registered: July 2009 |
Senior Member |
|
|
Hi,
I'm defining rules for parsing expressions like "a & b | c" following the pattern described in Sven Efftinge's blog (http://blog.efftinge.de/2010/08/parsing-expressions-with-xtext.html).
So, since "&" (AND) has precedence before "|" (OR), the OR-rule looks something like this.
Or returns Expression:
And ({Or.left=current} '|' right=And)*;
This structure implies an AST where the nodes always have two children (left and right). So, if I am not mistaken, for example "a | b | c" would result in an AST like this
'|'
/ \
'|' c
/ \
a b
However, is it possible to define parsing rules so that if I have an OR expression with multiple parts "a | b | c", I get a structure like this
'|'
/ | \
a b c
i.e, in the model, there will be an Or-expression with a multi-valued reference to its child expressions?
I tried defining a rules like
Or returns Expression:
And {Or.childExpr+=current} ('|' childExpr+=And)*;
or
Or returns Expression:
childExpr+=And ('|' childExpr+=And)*;
but this does not work.
Any idea?
Thanks
Joel
|
|
|
Re: XText parsing expressions with non-binary AST structure [message #792780 is a reply to message #792754] |
Tue, 07 February 2012 11:55 |
Sebastian Zarnekow Messages: 3118 Registered: July 2009 |
Senior Member |
|
|
Hi Joel,
this should do the trick:
Or returns Expression:
And ({Or.childExpr+=current} ('|' childExpr+=And)+)?;
Let me know if you have questions regarding the above pattern.
Regards,
Sebastian
--
Need professional support for Eclipse Modeling?
Go visit: http://xtext.itemis.com
Am 07.02.12 12:10, schrieb Joel Greenyer:
> Hi,
> I'm defining rules for parsing expressions like "a & b | c" following
> the pattern described in Sven Efftinge's blog
> (http://blog.efftinge.de/2010/08/parsing-expressions-with-xtext.html).
>
> So, since "&" (AND) has precedence before "|" (OR), the OR-rule looks
> something like this.
>
> Or returns Expression:
> And ({Or.left=current} '|' right=And)*;
>
> This structure implies an AST where the nodes always have two children
> (left and right). So, if I am not mistaken, for example "a | b | c"
> would result in an AST like this
>
> '|'
> / \
> '|' c
> / \
> a b
>
> However, is it possible to define parsing rules so that if I have an OR
> expression with multiple parts "a | b | c", I get a structure like this
>
> '|'
> / | \
> a b c
>
> i.e, in the model, there will be an Or-expression with a multi-valued
> reference to its child expressions?
>
> I tried defining a rules like
>
> Or returns Expression:
> And {Or.childExpr+=current} ('|' childExpr+=And)*;
>
> or
>
> Or returns Expression:
> childExpr+=And ('|' childExpr+=And)*;
>
> but this does not work.
>
> Any idea?
>
> Thanks
>
> Joel
|
|
| | |
Re: XText parsing expressions with non-binary AST structure [message #792934 is a reply to message #792919] |
Tue, 07 February 2012 15:30 |
Joel Greenyer Messages: 170 Registered: July 2009 |
Senior Member |
|
|
Hi Hendrik,
that's exactly what I needed. You make my day :)
I agree that the solution of the binary-tree AST is nice from a grammar/language design perspective and fine in most cases.
It is, however, difficult in my case, because I'm developing an automated transformation towards that language. If the AST has this binary-tree structure, I need different transformation rules for creating the first, a next, or the last part expression in this structure. Having a many-valued feature instead allows me to have just one rule and less constraints.
Thanks!
Joel
On 07.02.2012 16:10, Henrik Lindberg wrote:
> On 2012-07-02 15:19, Joel Greenyer wrote:
>> Hi Sebastian,
>> actually, after trying different things, it turned out that the rule
>>
>> Or returns Expression:
>> And {Or.childExpr+=current} ('|' childExpr+=And)*;
>>
>> and having an according one for the and-expressions does work.
>> I think I didn't let my files be parsed or something else was wrong that
>> I can't reproduce now.
>>
>> Your solution unfortunately does not work. I get many warnings
>> "Decision can match input such as ... using multiple alternatives"
>>
>> The only downside is now that the AST for an expression like "a|b|c"
>> looks like this
>>
>> '|'
>> / | \
>> / | \
>> '&' '&' '&'
>> | | |
>> a b c
>>
>> I.e., it always creates the "and expression" nodes.
>> Even if I write "!a", it will crate an AST
>>
> You are creating the instance of before having seen the operator
> And {Or.childExpr+=current} ('|' childExpr+=And)*;
>
> i.e. - do something like:
> And ({Or.childExpr+=current} ('|' childExpr+=And)+)?;
>
>
>>
>> Is there any way to simplify this?
>>
>
> What exactly do you think is wrong/bad/not-simple with the binary solution where the expressions have a left and a right side? That is easy to handle when generating or evaluating. The only downside is if you are writing lots of code by hand that creates these expressions - but you can write a helper for that.
>
> Regards
> - henrik
|
|
|
Re: XText parsing expressions with non-binary AST structure [message #792994 is a reply to message #792934] |
Tue, 07 February 2012 16:41 |
Sebastian Zarnekow Messages: 3118 Registered: July 2009 |
Senior Member |
|
|
Strange, I don't see how Henriks suggestion's different from my one ..
anyway, good to know that it works.
--
Need professional support for Eclipse Modeling?
Go visit: http://xtext.itemis.com
Am 07.02.12 16:30, schrieb Joel Greenyer:
> Hi Hendrik,
> that's exactly what I needed. You make my day :)
>
> I agree that the solution of the binary-tree AST is nice from a
> grammar/language design perspective and fine in most cases.
> It is, however, difficult in my case, because I'm developing an
> automated transformation towards that language. If the AST has this
> binary-tree structure, I need different transformation rules for
> creating the first, a next, or the last part expression in this
> structure. Having a many-valued feature instead allows me to have just
> one rule and less constraints.
>
> Thanks!
>
> Joel
>
>
> On 07.02.2012 16:10, Henrik Lindberg wrote:
>> On 2012-07-02 15:19, Joel Greenyer wrote:
>>> Hi Sebastian,
>>> actually, after trying different things, it turned out that the rule
>>>
>>> Or returns Expression:
>>> And {Or.childExpr+=current} ('|' childExpr+=And)*;
>>>
>>> and having an according one for the and-expressions does work.
>>> I think I didn't let my files be parsed or something else was wrong that
>>> I can't reproduce now.
>>>
>>> Your solution unfortunately does not work. I get many warnings
>>> "Decision can match input such as ... using multiple alternatives"
>>>
>>> The only downside is now that the AST for an expression like "a|b|c"
>>> looks like this
>>>
>>> '|'
>>> / | \
>>> / | \
>>> '&' '&' '&'
>>> | | |
>>> a b c
>>>
>>> I.e., it always creates the "and expression" nodes.
>>> Even if I write "!a", it will crate an AST
>>>
>> You are creating the instance of before having seen the operator
>> And {Or.childExpr+=current} ('|' childExpr+=And)*;
>>
>> i.e. - do something like:
>> And ({Or.childExpr+=current} ('|' childExpr+=And)+)?;
>>
>>
>>>
>>> Is there any way to simplify this?
>>>
>>
>> What exactly do you think is wrong/bad/not-simple with the binary
>> solution where the expressions have a left and a right side? That is
>> easy to handle when generating or evaluating. The only downside is if
>> you are writing lots of code by hand that creates these expressions -
>> but you can write a helper for that.
>>
>> Regards
>> - henrik
>
|
|
|
Goto Forum:
Current Time: Sat Apr 27 05:03:02 GMT 2024
Powered by FUDForum. Page generated in 0.03294 seconds
|