Eclipse Community Forums: TMF (Xtext) » Grammar with a post-fix operator

Home » Modeling » TMF (Xtext) » Grammar with a post-fix operator(Is it possible to describe this grammar with xtext?)

Grammar with a post-fix operator [message #1854494]

Mon, 22 August 2022 09:29

Eclipse User

I'm trying to describe an expression language that supports a kind of postfix operator. I'm struggling with how this can be expressed in XText. As a MWE, the language should support parsing two kinds of expressions:
1. projections of the form <expression> -> <attribute>, and
2. existence checks for an attribute of the form <expression> -> <attribute> exists.

Examples of the language:

variable -> attr

This should be parsed into a ProjectionExpression with expression set to variable and attribute set to attr.

variable -> attr exists

This should be parsed into a ExistsExpression with expression set to variable and attribute set to attr.

variable -> attr -> nestedAttr exists

This should be parsed into a ExistsExpression with expression set to a ProjectionExpression (corresponding to variable -> attr) and attribute set to nestedAttr.

Now I tried something like the grammar below, but obviously this does not work as XText will always create a ProjectionExpression if it encounters a ->, and never consider ExistsExpression as an alternative. Is there a workaround for this?

Note: I want a clear distinction between an ExistsExpression and a ProjectionExpression in the parsed AST. I do not want to join these concepts in any way. (otherwise, it would be easy to make exists a boolean attribute of the ProjectionExpression, but for downstream processes, I would like to treat them as separate classes)

Expression: ExistsExpression;

ExistsExpression returns Expression:
  ProjectionExpression (=>({ExistsExpression.expression=current} '->' attribute=[Attribute] 'exists'))?
;

ProjectionExpression returns Expression:
  PrimaryExpression (=>({ProjectionExpression.expression=current} '->' attribute=[Attribute]))*
;

PrimaryExpression returns Expression:
  VariableReference
;

VariableReference returns Expression:
	{VariableReference} reference=[Attribute]
;

Attribute:
  name=ID
;

[Updated on: Mon, 22 August 2022 13:17] by Moderator

Re: Grammar with a post-fix operator [message #1854634 is a reply to message #1854494]

Wed, 31 August 2022 06:20

Eclipse User

Okay, my conclusion is that this is not possible to describe with a left-recursive parser, as it requires backtracking to determine which parsing rule applies.

My workaround in short: make a clear distinction between concrete and abstract syntax, i.e., describe lower-level concrete syntax in XText (e.g., <expression> -> <attribute> exists?), then transform this in a post-processing step (e.g., with a DerivedStateComputer) to higher-level abstract syntax (e.g., convert ConcreteProjectionExpression into AbstractProjectionExpression or AbstractExistsExpression depending on whether exists is absent or present).

Re: Grammar with a post-fix operator [message #1854647 is a reply to message #1854634]

Wed, 31 August 2022 18:54

Eclipse User

I'm not sure that would help but have you tried configuring the parser generator in the mwe2 workflow to enable backtracking?

I don't have a precise pointer but I think the Xtext documentation mentions it somewhere.

Hope this helps.

Re: Grammar with a post-fix operator [message #1854653 is a reply to message #1854647]

Thu, 01 September 2022 03:20

Eclipse User

Hi Elie

You're right. It would work with backtracking enabled. However, enabling backtracking has some other side effects that we wish to avoid (e.g., performance hit, and it will hide some warnings that might give an indication when there is something wrong with our grammar).

Thanks for the remark though! Maybe other people that find backtracking acceptable will find it useful.

Re: Grammar with a post-fix operator [message #1854912 is a reply to message #1854653]

Sat, 17 September 2022 15:13

Eclipse User

Hi

It seems that you are finding that living with the combined limitations of
- unhelpful/over-precise model
- unhelpful syntax
-unhelpful tooling
prevents an easy solution.

I find that relaxing a bad grammar often helps, which has the benefits that the simpler grammar is more in line with user expectations and the subsequent validation can give the user helpful messages, rather than confusing syntax failures.

How about something like

ExistsOrProjectionExpression returns Expression:
PrimaryExpression (=>({ExistsOrProjectionExpression .expression=current} '->' attribute=[Attribute]) isExists?='exists')*
;

so that both are parsed as one and you just have to rewrite later if you really need to promote the parsed 'isExists' field to distinct classes.

Regards

Ed Willink

Re: Grammar with a post-fix operator [message #1854918 is a reply to message #1854912]

Sun, 18 September 2022 05:00

Eclipse User

Hi Ed

It seems that you arrived at the same conclusion as me. :) The solution I came up with is exactly that: start with a loose "lower level" syntax, and convert that in a post-processing step into a "higher level" AST that is more convenient to process, e.g., for the type system or for code generators.

Note that I wouldn't have these strict requirements if I was just working in a small team on a small language. That is not the case however. To be precise, I'm working on the Rosetta DSL, which is an open source project supporting multiple code generators (currently 8, but that number is growing) and a fairly complex type system using the Xsemantics framework. Making the syntax as convenient as possible is therefore necessary: the more I can do in the first step, the less that all of these downstream tasks need to worry about. Joining AST concepts such as projections and exists expressions into one breaks the single responsibility principle, which worried me.

Thank you for your interesting analysis. Always open to discussion.

Regards

Simon Cockx

[Updated on: Sun, 18 September 2022 05:08] by Moderator

Re: Grammar with a post-fix operator [message #1854919 is a reply to message #1854918]

Sun, 18 September 2022 07:07

Eclipse User

Hi

My insights come from my PhD that amongst other things resulted in the only yaccable grammar for C++; I identified a superset grammar that could defer type resolution till parsing had completed.

Currently I struggle with OCL for which the specification advocates a user/grammar-friendly Concrete Syntax that is significantly distant from the information-friendly Abstract Syntax necessitating a non-trivial CS2AS conversion.

You appear to need only a minor CS2AS conversion and so long as you can keep it simple that can work well. IMHO the naive assumption that useful languages can have a single CS/AS is naive, although I keep trying to see how OCL could have a smaller more manageable distance.

Once you accept the need for a (minor) CS2AS you can move on and solve problems effectively rather than fudging the consequences of no CS2AS.

Regards

Ed Willink

Previous Topic:	Semantic Token support on Xtext LSP
Next Topic:	state for support of Python-like whitespace-/newline-sensitive languages

Goto Forum:

-=] Back to Top [=-

Current Time: Wed Mar 19 02:48:00 EDT 2025

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter