Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Removing Left Recursion
Removing Left Recursion [message #1784868] Wed, 04 April 2018 22:10 Go to next message
Mohd Danish is currently offline Mohd DanishFriend
Messages: 49
Registered: October 2017
Member
Hello Christian,

The grammar below is left recursive and I have solved it through left factoring, could you please let me know if I have done it correctly or not.


ANTLR GRAMMAR:

pure_exp : QualfiedName '(' pure_exp_list ')'
| QualfiedName
'(' function_list ')'
'(' pure_exp_list ')'
| QualfiedName '[' pure_exp_list ']'
| QualfiedName ('(' pure_exp_list ')')?
| op=(NEGATION | NEGATION_CREOL | MINUS) pure_exp
| l=pure_exp op=(MULT | DIV | MOD) r=pure_exp
| l=pure_exp op=(PLUS | MINUS) r=pure_exp
| l=pure_exp op=(LT | GT | LTEQ | GTEQ) r=pure_exp
| l=pure_exp op=(EQEQ | NOTEQ) r=pure_exp
| l=pure_exp op='&&' r=pure_exp
| l=pure_exp op='||' r=pure_exp
| var_or_field_ref
| INTLITERAL
| STRINGLITERAL
| 'this'
| 'null'
| 'if' c=pure_exp 'then' l=pure_exp 'else' r=pure_exp
| 'case' c=pure_exp '{' casebranch* '}'
| 'let' '(' type_use ID ')' '=' i=pure_exp
'in' b=pure_exp
| '(' pure_exp ')'
;

XTEXT GRAMMAR:

Pure_exp:
QualfiedName '(' pure_exp_list=Pure_exp_list ')'
|QualfiedName'('function_list+=Function_list ')' '('pure_exp_list=Pure_exp_list ')'
|{Pure_exp}QualfiedName ('('function_expr=Pure_exp_list')')?
|QualfiedName '['variadic_exp_list=Pure_exp_list']'
|'if' if=Pure_exp 'then' then=Pure_exp (=>'else' else=Pure_exp)?
|'case' case=Pure_exp '{' casebranch+=Case_branch* '}'
|'let' '(' type_use=Type_use ID ')' '=' i=Pure_exp 'in' b=Pure_exp
|Or_expr
;

//Or_expr
Or_expr returns Pure_exp:
And_expr ({Or_expr.left=current} op=OROR right=And_expr)*
;

//And_expr
And_expr returns Pure_exp:
Equality_expr({And_expr.left=current} op=ANDAND right=Equality_expr)*
;

//Equality_expr
Equality_expr returns Pure_exp:
Comparison_expr({Equality_expr.left=current} op=(EQEQ|NOTEQ) right=Comparison_expr)*
;

//Comparison_expr
Comparison_expr returns Pure_exp:
PlusOrMinus_expr({Comparison_expr.left=current} op=(LT|GT|LTEQ|GTEQ) right=PlusOrMinus_expr)*
;

//PlusOrMinus
PlusOrMinus_expr returns Pure_exp:
MulDivOrMod_expr({PlusOrMinus_expr.left=current} op=(PLUS|MINUS) right=MulDivOrMod_expr)*
;

//MulDivOrMod_expr
MulDivOrMod_expr returns Pure_exp:
Primary_expr({MulDivOrMod_expr.left=current} op=(MULT|DIV|MOD) right=Primary_expr)*
;

//Primary_expr
Primary_expr returns Pure_exp:
'('Pure_exp')'
|(NEGATION|NEGATION_CREOL|MINUS) pure_exp=Pure_exp
|Atomic_expr
;

//Atomic_expr
Atomic_expr returns Pure_exp:
{Pure_exp}INT
|{Pure_exp}STRINGLITERAL
|ref=Var_or_field_ref
|{Pure_exp}'this'
|{Pure_exp}'null'

;

[Updated on: Wed, 04 April 2018 22:11]

Report message to a moderator

Re: Removing Left Recursion [message #1784881 is a reply to message #1784868] Thu, 05 April 2018 07:12 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 12386
Registered: July 2009
Senior Member
from a high overview that looks ok but

- grammar is incomplete
- you still seem to have a aversion agains some assignments....
- the unary primary part is a bit wired. should be something like

Unary_Expr returns Pure_exp: op=("!"|"~"|"-") epr=Primary_expr | Primary_expr;

//Primary_expr
Primary_expr returns Pure_exp:
'('Pure_exp')'
|
Atomic_expr
;


Need professional support for Xtext, Xpand, EMF?
Go to: https://xtext.itemis.com
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de

[Updated on: Thu, 05 April 2018 07:30]

Report message to a moderator

Re: Removing Left Recursion [message #1784948 is a reply to message #1784881] Fri, 06 April 2018 08:58 Go to previous messageGo to next message
Mohd Danish is currently offline Mohd DanishFriend
Messages: 49
Registered: October 2017
Member
Hello Christian,

I have written the grammar for If else statement and await statement. But still, during runtime, the editor shows error. I have also found about the dangling problem in if else statement but I have corrected it accordingly, could you please suggest where am I doing wrong.

ANTLR Grammar:

//Statement

stmt : type_exp ID ('=' exp)? ';'
| var_or_field_ref '=' exp ';'
| 'skip' ';'
| 'return' exp ';'
| 'assert' exp ';'
| '{' stmt* '}'
| 'if' '(' c=pure_exp ')' l=stmt ('else' r=stmt)?
| 'while' '(' c=pure_exp ')' stmt
| 'foreach' '(' i=ID 'in' l=pure_exp ')' stmt

| 'try' b=stmt
'catch' (('{' casestmtbranch* '}') | casestmtbranch)
('finally' f=stmt)?
| 'await' guard ';'
| 'suspend' ';'
| 'duration' '(' f=pure_exp ',' t=pure_exp ')' ';'
| 'throw' pure_exp ';'
| 'die' pure_exp ';'
| 'movecogto' pure_exp ';'
| exp ';'
| 'case' c=pure_exp '{' casestmtbranch* '}'
;

//Guard

guard : var_or_field_ref '?'
| 'duration' '(' min=pure_exp ',' max=pure_exp ')'
| e=pure_exp
| l=guard '&' r=guard
;

//Pure_exp

pure_exp : QualfiedName '(' pure_exp_list ')'
| QualfiedName
'(' function_list ')'
'(' pure_exp_list ')'
| QualfiedName '[' pure_exp_list ']'
| QualfiedName ('(' pure_exp_list ')')?
| op=(NEGATION | NEGATION_CREOL | MINUS) pure_exp
| l=pure_exp op=(MULT | DIV | MOD) r=pure_exp
| l=pure_exp op=(PLUS | MINUS) r=pure_exp
| l=pure_exp op=(LT | GT | LTEQ | GTEQ) r=pure_exp
| l=pure_exp op=(EQEQ | NOTEQ) r=pure_exp
| l=pure_exp op='&&' r=pure_exp
| l=pure_exp op='||' r=pure_exp
| var_or_field_ref
| INTLITERAL
| STRINGLITERAL
| 'this'
| 'null'
| 'if' c=pure_exp 'then' l=pure_exp 'else' r=pure_exp
| 'case' c=pure_exp '{' casebranch* '}'
| 'let' '(' type_use ID ')' '=' i=pure_exp
'in' b=pure_exp
| '(' pure_exp ')'
;


XTEXT Grammar:

//Statement

Stmt: {Stmt}//stmt_annotations=Annotations
(type_exp=Type_exp ID ('=' exp=Exp)? ';'
|var_or_field_ref=Var_or_field_ref '=' exp=Exp ';'
|'skip' ';'
|'return' exp=Exp ';'
|'assert' exp=Exp ';'
|'{' stmt+=Stmt* '}'
|'if' '(' pure_exp=Pure_exp ')' ifStmt=Stmt (=>'else' elseStmt=Stmt)?
|'while' '(' condition=Pure_exp ')' whilestmt=Stmt
|'foreach' '(' name=ID 'in' l=Pure_exp ')' foreachstmt=Stmt
|'try' trystmt=Stmt 'catch'
(('{'casestmtbranch+=Casestmtbranch*'}')
|casestmtbranch+=Casestmtbranch) ('finally' stmt+=Stmt )?
|'await' ref=Guard ';'
|'suspend' ';'
|'duration' '(' f=Pure_exp ',' t=Pure_exp ')' ';'
|'throw' throwPureExp=Pure_exp ';'
|'die' diePureExp=Pure_exp ';'
|'movecogto' moveCogTo=Pure_exp ';'
|exp=Exp ';'
|'case' case=Pure_exp '{' casestmtbranch+=Casestmtbranch* '}')
;

//Case statement Branch
Casestmtbranch:
pattern=Pattern '=>' stmt=Stmt
;

Pattern:{Pattern}('_'
|INT
|STRINGLITERAL
|ID
|QualfiedName('('(pattern+=Pattern(',' pattern+=Pattern )*)?')'))

;

// Guard

Guard:ref=Var_or_field_ref '?'
|'duration' '(' min=Pure_exp ',' max=Pure_exp ')'
|AndGuard
;

AndGuard returns Guard:
PrimaryGuard({AndGuard.left=current} op='&' right=PrimaryGuard)*
;
PrimaryGuard returns Guard:
'(' Guard ')'
| guard=Pure_exp
;

Var_or_field_ref:('this' '.')? name=ID ;

Type_use: name=QualfiedName
('<' type_use+=Type_use (',' type_use+=Type_use)* '>')? ;

Type_exp:name=QualfiedName
('<' p+=Type_use (',' p+=Type_use)* '>')?;


//Pure_exp

Pure_exp:
QualfiedName '(' pure_exp_list+=Pure_exp_list ')'
|QualfiedName'('function_list+=Function_list ')' '('pure_exp_list+=Pure_exp_list ')'
|{Pure_exp}QualfiedName ('('function_expr+=Pure_exp_list')')?
|QualfiedName '['variadic_exp_list+=Pure_exp_list']'
|Or_expr
|'if' if=Pure_exp 'then' then=Pure_exp (=>'else' else=Pure_exp)?
|'case' case=Pure_exp '{' casebranch+=Case_branch* '}'
|'let' '(' type_use=Type_use ID ')' '=' i=Pure_exp 'in' b=Pure_exp



;

//Or_expr
Or_expr returns Pure_exp:
And_expr ({Or_expr.left=current} op=OROR right=And_expr)*
;

//And_expr
And_expr returns Pure_exp:
Equality_expr({And_expr.left=current} op=ANDAND right=Equality_expr)*
;

//Equality_expr
Equality_expr returns Pure_exp:
Comparison_expr({Equality_expr.left=current} op=(EQEQ|NOTEQ) right=Comparison_expr)*
;

//Comparison_expr
Comparison_expr returns Pure_exp:
PlusOrMinus_expr({Comparison_expr.left=current} op=(LT|GT|LTEQ|GTEQ) right=PlusOrMinus_expr)*
;

//PlusOrMinus
PlusOrMinus_expr returns Pure_exp:
MulDivOrMod_expr({PlusOrMinus_expr.left=current} op=(PLUS|MINUS) right=MulDivOrMod_expr)*
;

//MulDivOrMod_expr
MulDivOrMod_expr returns Pure_exp:
Primary_expr({MulDivOrMod_expr.left=current} op=(MULT|'/'|MOD) right=Uniary_expr)*
;


Uniary_expr returns Pure_exp:
op=(NEGATION|NEGATION_CREOL|MINUS) pure_exp=Pure_exp|Primary_expr
;

//Primary_expr
Primary_expr returns Pure_exp:
'('Pure_exp')'
|Atomic_expr
;

//Atomic_expr
Atomic_expr returns Pure_exp:
{Pure_exp}INT
|{Pure_exp}STRINGLITERAL
|ref=Var_or_field_ref
|{Pure_exp}'this'
|{Pure_exp}'null'
|{Pure_exp}STRING


;

Exp: Eff_expr | Pure_exp
;

Eff_expr: (pure_exp=Pure_exp | var=[Var_or_field_ref|ID]) '.' 'get'
|'new' 'local'? QualfiedName '(' list+=Pure_exp_list ')'
|'await'? Pure_exp NEGATION name=ID '(' list+=Pure_exp_list ')'
| Pure_exp '.' name=ID '(' list+=Pure_exp_list ')'
|((Delta_id|'core') '.')? 'original' '(' list+=Pure_exp_list ')'
;

Pure_exp_list :{Pure_exp_list}(pure_exp+=Pure_exp (',' pure_exp+=Pure_exp)*)?
;

//Delta ID
Delta_id: name=ID
;


Runtime Error in Ifelse Statement:

Multiple markers at this line
- missing ')' at '=='
- mismatched input ')' expecting ';'
- no viable alternative at input '('


Runtime Error in Await Statement:

Multiple markers at this line
- no viable alternative at input '!='
- no viable alternative at input 'server'


Find the attached file.


Re: Removing Left Recursion [message #1784969 is a reply to message #1784948] Fri, 06 April 2018 11:27 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 12386
Registered: July 2009
Senior Member
sorry that is too much for me to digg into.

please minify grammar and example as much as you can


Need professional support for Xtext, Xpand, EMF?
Go to: https://xtext.itemis.com
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Removing Left Recursion [message #1784970 is a reply to message #1784969] Fri, 06 April 2018 11:31 Go to previous message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 12386
Registered: July 2009
Senior Member
is in your grammar else is required / you have multiple ifs.
other tipps:
adapt the workflow to generate a debuggrammar (parserGenerator={debugGrammar=true}) // or something like that
and use antlrworks to analysze


Need professional support for Xtext, Xpand, EMF?
Go to: https://xtext.itemis.com
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Previous Topic:PostProcessing
Next Topic:Grammar help
Goto Forum:
  


Current Time: Thu Nov 15 18:54:42 GMT 2018

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

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

Back to the top