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: 14665
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
;

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.

Report message to a moderator

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: 14665
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

Twitter : @chrdietrich
Blog : https://www.dietrich-it.de

Report message to a moderator

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: 14665
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

Twitter : @chrdietrich
Blog : https://www.dietrich-it.de

Report message to a moderator

Previous Topic:PostProcessing
Next Topic:Grammar help
Goto Forum:
  

[ Syndicate this forum (XML) ] [ RSS ]

Current Time: Thu Apr 25 13:20:14 GMT 2024

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

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

Back to the top

Sign up to our Newsletter

A fresh new issue delivered monthly