Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
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 13:29 Go to next message
Simon Cockx is currently offline Simon CockxFriend
Messages: 13
Registered: October 2021
Junior Member
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 17:17]

Report message to a moderator

Re: Grammar with a post-fix operator [message #1854634 is a reply to message #1854494] Wed, 31 August 2022 10:20 Go to previous messageGo to next message
Simon Cockx is currently offline Simon CockxFriend
Messages: 13
Registered: October 2021
Junior Member
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 22:54 Go to previous messageGo to next message
Elie Richa is currently offline Elie RichaFriend
Messages: 62
Registered: February 2016
Member
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.


Elie Richa, Ph.D
Software Engineer, AdaCore
https://www.adacore.com
Re: Grammar with a post-fix operator [message #1854653 is a reply to message #1854647] Thu, 01 September 2022 07:20 Go to previous messageGo to next message
Simon Cockx is currently offline Simon CockxFriend
Messages: 13
Registered: October 2021
Junior Member
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 19:13 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 7517
Registered: July 2009
Senior Member
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 09:00 Go to previous messageGo to next message
Simon Cockx is currently offline Simon CockxFriend
Messages: 13
Registered: October 2021
Junior Member
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 09:08]

Report message to a moderator

Re: Grammar with a post-fix operator [message #1854919 is a reply to message #1854918] Sun, 18 September 2022 11:07 Go to previous message
Ed Willink is currently offline Ed WillinkFriend
Messages: 7517
Registered: July 2009
Senior Member
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:
  


Current Time: Mon Sep 26 12:47:10 GMT 2022

Powered by FUDForum. Page generated in 0.02006 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top