xtext dealing with left recursion grammar

Question

I am using xtext 2.4 and want to support both map and set, my grammar looks like this

<term> ::- <collection>
<collection> ::- <map> | <set>
<map> ::- '{' (<term> ':' <term> (',' <term> ':' <term> )*)? '}'
<set> ::- '{' (<term> (',' <term>)* )+ '}'

so it could be simplified as

<term> ::- '{' (<term> ':' <term> (',' <term> ':' <term> )*)? '}' |
           '{' (<term> (',' <term>)* )+ '}'

antlr complains about this grammar begin left recursion, I'm not sure why, since it has '{' in the right hand side.

Even if I want to factor the same part out, I don't know how to do that in xtext, since a EObject now being split into two production rules, and the parsed data cannot store in the same object.

any help?

============================================================================ Corresponding xtext grammar I wrote is

grammar org.xtext.problem.Term with org.eclipse.xtext.common.Terminals

generate term "http://www.xtext.org/problem/Term"

Term:
    term = Collection
;

Collection:
    MyMap | MySet
; 

MyMap:
    {MyMap} '{'( keys+= Term ':' values += Term ( ',' keys+=Term ':' values +=Term)*  )?'}'
;

MySet:
    {MySet} '{'( values += Term ( ',' values +=Term)*  )?'}'
;

Error messages (starts with error(211)):

0    [main] INFO  lipse.emf.mwe.utils.StandaloneSetup  - Registering platform uri '/Users/jcwu/opensource/xtext-problemistic'
116  [main] INFO  lipse.emf.mwe.utils.StandaloneSetup  - Adding generated EPackage 'org.eclipse.xtext.xbase.XbasePackage'
454  [main] INFO  clipse.emf.mwe.utils.GenModelHelper  - Registered GenModel 'http://www.eclipse.org/Xtext/Xbase/XAnnotations' from 'platform:/resource/org.eclipse.xtext.xbase/model/Xbase.genmodel'
459  [main] INFO  clipse.emf.mwe.utils.GenModelHelper  - Registered GenModel 'http://www.eclipse.org/xtext/xbase/Xtype' from 'platform:/resource/org.eclipse.xtext.xbase/model/Xbase.genmodel'
479  [main] INFO  clipse.emf.mwe.utils.GenModelHelper  - Registered GenModel 'http://www.eclipse.org/xtext/xbase/Xbase' from 'platform:/resource/org.eclipse.xtext.xbase/model/Xbase.genmodel'
479  [main] INFO  clipse.emf.mwe.utils.GenModelHelper  - Registered GenModel 'http://www.eclipse.org/xtext/common/JavaVMTypes' from 'platform:/resource/org.eclipse.xtext.common.types/model/JavaVMTypes.genmodel'
1660 [main] INFO  ipse.emf.mwe.utils.DirectoryCleaner  - Cleaning /Users/jcwu/opensource/xtext-problemistic/org.xtext.problem.term/../org.xtext.problem.term/src-gen
1665 [main] INFO  ipse.emf.mwe.utils.DirectoryCleaner  - Cleaning /Users/jcwu/opensource/xtext-problemistic/org.xtext.problem.term/../org.xtext.problem.term.ui/src-gen
1666 [main] INFO  ipse.emf.mwe.utils.DirectoryCleaner  - Cleaning /Users/jcwu/opensource/xtext-problemistic/org.xtext.problem.term/../org.xtext.problem.term.tests/src-gen
2033 [main] INFO  ipse.xtext.generator.LanguageConfig  - generating infrastructure for org.xtext.problem.Term with fragments : ImplicitRuntimeFragment, ImplicitUiFragment, GrammarAccessFragment, EcoreGeneratorFragment, SerializerFragment, ResourceFactoryFragment, XtextAntlrGeneratorFragment, ValidatorFragment, ImportNamespacesScopingFragment, QualifiedNamesFragment, BuilderIntegrationFragment, GeneratorFragment, FormatterFragment, LabelProviderFragment, OutlineTreeProviderFragment, QuickOutlineFragment, QuickfixProviderFragment, ContentAssistFragment, XtextAntlrUiGeneratorFragment, Junit4Fragment, RefactorElementNameFragment, TypesGeneratorFragment, XbaseGeneratorFragment, CodetemplatesGeneratorFragment, CompareFragment
4115 [main] INFO  clipse.emf.mwe.utils.GenModelHelper  - Registered GenModel 'http://www.xtext.org/problem/Term' from 'platform:/resource/org.xtext.problem.term/src-gen/org/xtext/problem/Term.genmodel'
error(211): ../org.xtext.problem.term/src-gen/org/xtext/problem/parser/antlr/internal/InternalTerm.g:119:1: [fatal] rule ruleCollection 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.
5918 [main] ERROR enerator.CompositeGeneratorFragment  - java.io.FileNotFoundException: ../org.xtext.problem.term/src-gen/org/xtext/problem/parser/antlr/internal/InternalTermLexer.java (No such file or directory)
org.eclipse.emf.common.util.WrappedException: java.io.FileNotFoundException: ../org.xtext.problem.term/src-gen/org/xtext/problem/parser/antlr/internal/InternalTermLexer.java (No such file or directory)
    at org.eclipse.xtext.util.Files.readFileIntoString(Files.java:129)
    at org.eclipse.xtext.generator.parser.antlr.AbstractAntlrGeneratorFragment.suppressWarningsImpl(AbstractAntlrGeneratorFragment.java:132)
    at org.eclipse.xtext.generator.parser.antlr.AbstractAntlrGeneratorFragment.suppressWarnings(AbstractAntlrGeneratorFragment.java:142)
    at org.eclipse.xtext.generator.parser.antlr.AbstractAntlrGeneratorFragment.suppressWarnings(AbstractAntlrGeneratorFragment.java:138)
    at org.eclipse.xtext.generator.parser.antlr.XtextAntlrGeneratorFragment.generate(XtextAntlrGeneratorFragment.java:49)
    at org.eclipse.xtext.generator.CompositeGeneratorFragment.generate(CompositeGeneratorFragment.java:92)
    at org.eclipse.xtext.generator.LanguageConfig.generate(LanguageConfig.java:113)
    at org.eclipse.xtext.generator.Generator.generate(Generator.java:361)
    at org.eclipse.xtext.generator.Generator.invokeInternal(Generator.java:128)
    at org.eclipse.emf.mwe.core.lib.AbstractWorkflowComponent.invoke(AbstractWorkflowComponent.java:126)
    at org.eclipse.emf.mwe.core.lib.Mwe2Bridge.invoke(Mwe2Bridge.java:34)
    at org.eclipse.emf.mwe.core.lib.AbstractWorkflowComponent.invoke(AbstractWorkflowComponent.java:201)
    at org.eclipse.emf.mwe2.runtime.workflow.AbstractCompositeWorkflowComponent.invoke(AbstractCompositeWorkflowComponent.java:35)
    at org.eclipse.emf.mwe2.runtime.workflow.Workflow.run(Workflow.java:19)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Runner.run(Mwe2Runner.java:102)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Runner.run(Mwe2Runner.java:62)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Runner.run(Mwe2Runner.java:52)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Launcher.run(Mwe2Launcher.java:74)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Launcher.main(Mwe2Launcher.java:35)
Caused by: java.io.FileNotFoundException: ../org.xtext.problem.term/src-gen/org/xtext/problem/parser/antlr/internal/InternalTermLexer.java (No such file or directory)
    at java.io.FileInputStream.open(Native Method)
    at java.io.FileInputStream.<init>(FileInputStream.java:138)
    at java.io.FileInputStream.<init>(FileInputStream.java:97)
    at org.eclipse.xtext.util.Files.readFileIntoString(Files.java:126)
    ... 18 more
error(211): ../org.xtext.problem.term.ui/src-gen/org/xtext/problem/ui/contentassist/antlr/internal/InternalTerm.g:176:1: [fatal] rule rule__Collection__Alternatives 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.
6617 [main] ERROR enerator.CompositeGeneratorFragment  - java.io.FileNotFoundException: ../org.xtext.problem.term.ui/src-gen/org/xtext/problem/ui/contentassist/antlr/internal/InternalTermLexer.java (No such file or directory)
org.eclipse.emf.common.util.WrappedException: java.io.FileNotFoundException: ../org.xtext.problem.term.ui/src-gen/org/xtext/problem/ui/contentassist/antlr/internal/InternalTermLexer.java (No such file or directory)
    at org.eclipse.xtext.util.Files.readFileIntoString(Files.java:129)
    at org.eclipse.xtext.generator.parser.antlr.AbstractAntlrGeneratorFragment.suppressWarningsImpl(AbstractAntlrGeneratorFragment.java:132)
    at org.eclipse.xtext.generator.parser.antlr.AbstractAntlrGeneratorFragment.suppressWarnings(AbstractAntlrGeneratorFragment.java:142)
    at org.eclipse.xtext.generator.parser.antlr.AbstractAntlrGeneratorFragment.suppressWarnings(AbstractAntlrGeneratorFragment.java:138)
    at org.eclipse.xtext.generator.parser.antlr.XtextAntlrUiGeneratorFragment.generate(XtextAntlrUiGeneratorFragment.java:53)
    at org.eclipse.xtext.generator.CompositeGeneratorFragment.generate(CompositeGeneratorFragment.java:92)
    at org.eclipse.xtext.generator.LanguageConfig.generate(LanguageConfig.java:113)
    at org.eclipse.xtext.generator.Generator.generate(Generator.java:361)
    at org.eclipse.xtext.generator.Generator.invokeInternal(Generator.java:128)
    at org.eclipse.emf.mwe.core.lib.AbstractWorkflowComponent.invoke(AbstractWorkflowComponent.java:126)
    at org.eclipse.emf.mwe.core.lib.Mwe2Bridge.invoke(Mwe2Bridge.java:34)
    at org.eclipse.emf.mwe.core.lib.AbstractWorkflowComponent.invoke(AbstractWorkflowComponent.java:201)
    at org.eclipse.emf.mwe2.runtime.workflow.AbstractCompositeWorkflowComponent.invoke(AbstractCompositeWorkflowComponent.java:35)
    at org.eclipse.emf.mwe2.runtime.workflow.Workflow.run(Workflow.java:19)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Runner.run(Mwe2Runner.java:102)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Runner.run(Mwe2Runner.java:62)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Runner.run(Mwe2Runner.java:52)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Launcher.run(Mwe2Launcher.java:74)
    at org.eclipse.emf.mwe2.launch.runtime.Mwe2Launcher.main(Mwe2Launcher.java:35)
Caused by: java.io.FileNotFoundException: ../org.xtext.problem.term.ui/src-gen/org/xtext/problem/ui/contentassist/antlr/internal/InternalTermLexer.java (No such file or directory)
    at java.io.FileInputStream.open(Native Method)
    at java.io.FileInputStream.<init>(FileInputStream.java:138)
    at java.io.FileInputStream.<init>(FileInputStream.java:97)
    at org.eclipse.xtext.util.Files.readFileIntoString(Files.java:126)
    ... 18 more
6650 [main] INFO  text.generator.junit.Junit4Fragment  - generating Junit4 Test support classes
6682 [main] INFO  text.generator.junit.Junit4Fragment  - generating Compare Framework infrastructure
7118 [main] INFO  .emf.mwe2.runtime.workflow.Workflow  - Done.

Answer 1

A working Xtext grammar for your problem is this:

Model: term += Term*;

Term: c=Collection;

Collection: ( => Map | Set );

Map: '{' {Map} ( entries += MapEntry ( ',' entries += MapEntry )* )? '}';
MapEntry: key=Term ':' value=Term;

Set: '{' ( values += Term ( ',' values += Term )* )+ '}';

Thing to notice:

• The => syntactic predicate in the Collection rule. This directs Xtext/ANTLR into the right direction. (Docu here)

• The {Map} "simple action" (Docu here) creates a Map even if the content is empty.

• The additional MapEntry rule is also required because otherwise you have nothing to hold key/value pairs.

• Your grammar allow both {}{}{} and {}, {}, {} within a Set. This may or may not be what you want.

So it seems to me, that the Xtext/ANTLR error message about LL recursion is not the most appropriate in this case. It is not about LL recursion but about ambiguities in the grammar which sometimes can be solved by applying =>. See the linked docs for more details.

Just for reference: The grammar can parse simple and nested stuff like this:

// Maps
{}
{ {} : {} }
{ {} : {}, {} : {}}

// Sets
{ {} }
{ {} {} {} {} }
{ {}, {}, {}, {} }

// nested / mixed
{ { { {}:{} } } : {}, {} : { {}:{} }}
{ { { {}:{} } } : {}, {} : { {}:{ {}{}{} } }}