Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Bug 327038

Summary:	Consider deriving an Action-Free grammar
Product:	[Modeling] TMF	Reporter:	Moritz Eysholdt <moritz.eysholdt>
Component:	Xtext	Assignee:	Project Inbox <tmf.xtext-inbox>
Status:	CLOSED FIXED	QA Contact:
Severity:	normal
Priority:	P3	CC:	sebastian.zarnekow
Version:	1.0.1	Flags:	sebastian.zarnekow: indigo+
Target Milestone:	---
Hardware:	PC
OS:	Mac OS X - Carbon (unsup.)
Whiteboard:
Bug Depends on:	333976
Bug Blocks:

Description Moritz Eysholdt

2010-10-05 16:02:58 EDT

Currently, the ConcreteSyntaxValidation can not handle grammar rule containing assigned actions. As mentioned by Sebastian, it should be possible to derive an action-free grammar from any grammar.  

Example:
(In reply to comment https://bugs.eclipse.org/bugs/show_bug.cgi?id=267583#c4)
> Btw: Did you consider to transform the grammar for use cases such as the
> IConcreteSyntaxValidator to remove the complicated parts, e.g.
> 
> Foo:
>   Bar ({Zonk.baz=current} op=.. foo=Bar)*;
> 
> can be seen by the CSV (but not by the parser) as
> 
> Foo:
>   Zonk | Bar;
> 
> Zonk:
>   baz=Foo op=.. foo=Bar;

We should investigate this further... if this works for all cases, this could allow the ConcreteSyntaxValidatior to be handle Actions as well.

Furthermore, this could be one building block for a Serializer based on a declarative approach (rather than the current one, which is based on a backtracking approach).

Both the ConcreteSyntaxValidator and a Declarative Serializer are not afraid of grammatical left/right recursion :D (due to their declarative approach)

Comment 1 Moritz Eysholdt

2010-12-01 17:36:07 EST

I sketched some examples, please review. The numbering of the identifiers is a result of avoiding validation errors in the xtext editor.


/******* Example 1: Binary Tree **************/

Expression11:
  Prim11 ({Add11.left=current} "+" right=Prim11)*;
  
Prim11:
  {Val} name=ID;
  

/*-------- 1. remove assigned actions. -------*/

Expression12:
  Prim12 | Add12;
  
Add12:
  left=(Prim12|Add12) "+" right=Prim12;
  
Prim12:
  {Val} name=ID;

  
/*--------  2. remove unassigned rule calls. ------*/

Expression13:
  {Val} name=ID | {Add13} left=(Prim13|Add13) "+" right=Prim13;
  
Add13:
  left=(Prim13|Add13) "+" right=Prim13;
  
Prim13:
  {Val} name=ID;
  
/*--------  3. simplification. ------*/

Expression14: // this equals Prim14Add14
  {Val} name=ID | {Add14} left=Expression14 "+" right=Prim14;
  
Prim14:
  {Val} name=ID;

  
/******* Example 2: No Tree at all, just a tuple **************/

Expression21:
  Prim21 ({Add21.left=current} "+" right=Prim21)?;
  
Prim21:
  {Val} name=ID;
  

/*-------- 1. remove assigned actions. -------*/

Expression22:
  Prim22 | Add22;
  
Add22:
  left=Prim22 "+" right=Prim22;
  
Prim22:
  {Val} name=ID;

  
/******* Example 3: N-ary Tree **************/

Expression31:
  Prim31 ({Add31.children+=current} ("+" children+=Prim31)+)?;
  
Prim31:
  {Val} name=ID;
  

/*-------- 1. remove assigned actions. -------*/

Expression32:
  Prim32 | Add32;
  
Add32:
  children+=Prim32 ("+" children+=Prim32)*;
  
Prim32:
  {Val} name=ID;
  
  
/***** Example 4: A path (which is actually a binary tree) **********/

Path41: 
  {Root41} name=ID ({Segment41.parent=current} "." name=ID)*;
  
/*-------- 1. remove assigned actions. -------*/
  
Path42:
  Root42 | Segment42;
  
Segment42:
  parent=(Root42|Segment42) "." name=ID;
  
Root42:
  name=ID;
  

/************ Example 5: Expressions with Add, Mult, Parenthesis **/


Addition51 returns Expr51:
  Multiplication51 ({Add51.left=current} "+" right=Multiplication51)*;
  
Multiplication51 returns Expr51:
  Prim51 ({Mult51.left=current} "*" right=Prim51)*;
  
Prim51 returns Expr51:
  {Val} name=ID | "(" Addition51 ")";

/*-------- 1. remove assigned actions. -------*/

Addition52 returns Expr52:
  Multiplication52 | Add52;
  
Add52:
  left=(Multiplication52 | Add52) "+" right=Multiplication52;
   
Multiplication52 returns Expr52:
  Prim52 | Mult52;
  
Mult52:
  left=(Prim52 | Mult52) "*" right=Prim52;
   
Prim52 returns Expr52:
  {Val} name=ID | "(" Addition52 ")";
  
  
/*---------- 2a. inlining unassigend rule calls -----------*/
// this is not suitable for serialization since it contains 
// recursion via unassigned rule calls.
// Addition -> Add -> Mult -> Prim -> Addition ...

Addition53 returns Expr53:
  Prim53 | Mult53 | Add53;
  
Add53:
  left=(Prim53 | Mult53 | Add53) "+" right=(Prim53 | Mult53);
   
Mult53:
  left=(Prim53 | Mult53) "*" right=Prim53;
   
Prim53 returns Expr53:
  {Val} name=ID | "(" Addition53 ")";

/*---------- 2b. inlining unassigend rule calls -----------*/
  
Addition54 returns Expr54:
  {Val} name=ID  /* | 
  "(" Addition54 ")" */ | 
  {Mult54} left=(Prim54 | Mult54) "*" right=Prim54 | 
  {Add54} left=(Prim54 | Mult54 | Add54) "+" right=(Prim54 | Mult54);
  
Add54:
   left=(Prim54 | Mult54 | Add54) "+" right=(Prim54 | Mult54);
   
Mult54:
   left=(Prim54 | Mult54) "*" right=Prim54;
   
Prim54 returns Expr54:
  {Val} name=ID | "(" Addition54 ")";
  
/*---------- 2c. inlining unassigend rule calls -----------*/
  
Addition55 returns Expr55: // this equals Prim55Mult55Add55
  {Val}    name=ID | 
  {Mult55} left=Prim55Mult55 "*" right=Prim55 | 
  {Add55}  left=Addition55   "+" right=Prim55Mult55;
  
Prim55Mult55 returns Expr55:
  {Val}       name=ID | 
  {Add55} "(" left=Addition55   "+" right=Prim55Mult55 ")" |
  {Mult55}    left=Prim55Mult55 "*" right=Prim55; 
  
Prim55 returns Expr55:
  {Val}        name=ID |
  {Add55}  "(" left=Addition55   "+" right=Prim55Mult55 ")" |
  {Mult55} "(" left=Prim55Mult55 "*" right=Prim55 ")";

Comment 2 Moritz Eysholdt

2011-01-11 09:33:34 EST

depends on bug 333976: The proposed GrammarConstraintProvider implements this algorithm.

Comment 3 Sebastian Zarnekow

2011-05-17 16:55:04 EDT

Since the new serializer architecture is based on such a grammar, I consider this one to be done. Please reopen if I missed something.

Comment 4 Karsten Thoms

2017-09-19 17:07:30 EDT

Closing all bugs that were set to RESOLVED before Neon.0

Comment 5 Karsten Thoms

2017-09-19 17:19:10 EDT

Closing all bugs that were set to RESOLVED before Neon.0