Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Left Recursion(Problem with a nested left-recursion )
Left Recursion [message #1700825] Tue, 07 July 2015 12:55 Go to next message
tam ay is currently offline tam ayFriend
Messages: 44
Registered: May 2015
Member
Hi everone,

like the most I have a problem with left-recursion in the grammar definition, although I read the helpful articles.
"Type" is used recursively in a nested expression and I don't know how to solve that. I would be very happy if someone could help me. Thanks a lot!!

Here is a part of the grammar:

OrdinaryVariableDeclaration:
	ordinaryDeclaration=DeclarationWithoutInit |
	ordinaryDeclaration=DeclarationWithInit |
	ordinaryDeclaration=SignalDeclaration
;

DeclarationWithoutInit:
	{DeclarationWithoutInit} (type=TeachType | type=Type) ":" variableIdList=VariableIdList ";"
;

VariableIdList:
	name+=VariableIdentifier ("," name+=VariableIdentifier)*
;

TeachType:
	name=TeachTypeDescription
;

TeachTypeDescription:
	"TEACH" type=PredefinedType
;

Type:
	PredefinedType | StructuredTypeIdentifier | StructuredTypeDescription
;

PredefinedType:
	SimpleType | StandardType |  SystemType
;

SystemType:
	name=SystemTypeIdentifier
;

StandardType:
	name=StandardTypeIdentifier
;

StructuredTypeDescription:
	RecordTypeDescription | ArrayTypeDescription | ListTypeDescription | FileTypeDescription
;

RecordTypeDescription:
	"RECORD" componentList=ComponentList "ENDRECORD"
;

ComponentList:
	type+=Type ":" componentIdList+=ComponentIdList (";" type+=Type ":" componentIdList+=ComponentIdList)*
;

ComponentIdList:
	name+=ComponentIdentifier ("," name+=ComponentIdentifier)*
;

ArrayTypeDescription:
	"ARRAY" "[" indexBoundList=IndexBoundList "]" "OF" (type=Type | type=TeachType)
;

IndexBoundList:
	indexBound+=IndexBound ("," indexBound+=IndexBound)*
;

IndexBound:
	left=Expression ".." right=Expression
;

ListTypeDescription:
	"LIST" "OF" (type=Type | type=TeachType)
;

FileTypeDescription:
	"FILE" "OF" type=Type
;





The ERROR:

error(211): ../org.xtext.irl/src-gen/org/xtext/aIRL/parser/antlr/internal/InternalAIRL.g:1454:1: [fatal] rule ruleOrdinaryVariableDeclaration has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
Re: Left Recursion [message #1700883 is a reply to message #1700825] Tue, 07 July 2015 20:44 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
hi,

unfortunately your grammar is incomplete.
you should minimize it to a small grammar that reproduces the problem
on how to get a general idea how to do expressions
http://blog.efftinge.de/2010/08/parsing-expressions-with-xtext.html
additionally you can use antlrworks and org.eclipse.xtext.generator.parser.antlr.DebugAntlrGeneratorFragment to analzye


Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Left Recursion [message #1700924 is a reply to message #1700883] Wed, 08 July 2015 08:34 Go to previous messageGo to next message
tam ay is currently offline tam ayFriend
Messages: 44
Registered: May 2015
Member
Hi,

thank you for your response. Unfortunately it is difficult to reproduce that problem in a small example since their a few other dependencies.

I already know the posted link but I will try the other mechanisms to solve the problem.

I upload the grammar in case you could figure the problem at one glance. At least I would be very happy if you have some other hints, as I face that problem for 3 days. Smile

Thank you!!
  • Attachment: Grammar.zip
    (Size: 1.48MB, Downloaded 83 times)

[Updated on: Wed, 08 July 2015 08:36]

Report message to a moderator

Re: Left Recursion [message #1700932 is a reply to message #1700924] Wed, 08 July 2015 09:32 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
what is the semantic of Precedence

Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Left Recursion [message #1700940 is a reply to message #1700932] Wed, 08 July 2015 10:33 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
throw out as much as you can from your grammar (e.g. start with an expression)

So you should have a look at

- Path
- Object
- CallOrRecord
- Precedence vs. Atomic: (Expression)

(i cannot help you more because that may involve a huge amout of time.


Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Left Recursion [message #1700951 is a reply to message #1700940] Wed, 08 July 2015 11:35 Go to previous message
tam ay is currently offline tam ayFriend
Messages: 44
Registered: May 2015
Member
Ok thank you.
Previous Topic:Left/Right optionals
Next Topic:Cross reference for multiple identifers
Goto Forum:
  


Current Time: Tue Mar 19 02:00:20 GMT 2024

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

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

Back to the top