Based on my reading of issue 328, there is currently no way to provide disambiguation rules in stratego using Spoofax. This is because the tools are set up to use the tree before my own stratego rules would fire. Additionally, there is no way to specify stratego rules that will run before the other tools see the tree.

Both myself and the group I work with expected to be able to write stratego rules that can help disambiguate the tree without having to write java.

I suppose additionally, if you choose to force people to write java to do this, please provide some examples the same way there are examples in the *.esv files. Ideally there would be a place I can go when I create a new project and just start adding disambiguation rules.

I’m super surprised this hasn’t been requested yet, since it seems like one of the main selling points of stratego+sdf is that stratego can intelligently filter the parse tree.

Submitted by Chucky Ellison on 17 April 2011 at 21:10

Hi Chucky, so far we haven’t directly needed this (the other issue mentioned “I don’t really need it at this moment, but if it’s easy, it might come in handy sometime”). But if you have a use case for this we can certainly implement it on short notice.

Thanks for your quick response.

I will try to explain what we are doing. Perhaps you can tell us how best to go about it, although it seems basic enough that I feel like I may simply be missing a Spoofax concept. I diverge a little from the main issue below, so let me know if you’d like me to create multiple issues. Our issue might just be ignorance :)

We (my research group at U. Illinois, under Prof. Grigore Rosu) are working on an IDE for a language we are designing. We are actually trying out both Spoofax and Rascal in parallel, to see which works best for our purposes. We do research in formal methods and programming languages, but have relatively little experience with parsing. Spoofax has so far looked very promising. I’ll try to explain our expectations, which we can offer as a case study in what non-parsing-people could be thinking when coming to your tool.

The grammar of our language is quite complicated, and it is very hard to disambiguate it solely with SDF. There are some relatively simple stratego rules we can apply to filter and thus disambiguate the tree, however. So far we have not had to write any java code, and thus have been able to focus purely on design (no low level coding to get the tool to do what we want). Our understanding is that stratego is commonly used to disambiguate trees, so it surprised us that we couldn’t disambiguate trees in Spoofax using stratego. It seems that if we can’t write stratego that would manipulate the tree BEFORE the cool IDE stuff looks at the tree, then it means that people have to either write completely unambiguous grammars in order to use Spoofax, or start really tearing into the implementation (which we don’t know how to do).

Eventually we will want to do something (e.g., perform compilation) with our AST, so we will have to write java, but the pure stratego approach seems natural for Spoofax.

Actually, we’ve been unable to figure any of the Java parts out at all. I suggest putting basic examples in your new project the same as with the *.esv and *.str files, as those helped tremendously. I think a good way to go would be to write a traversal over the tree in java, perhaps simply printing the tree out in prefix form. Then show how information generated here could wind up back in the IDE.

We had expected that any constructors we declared would be automatically turned into classes, with appropriate getters and setters and a generic visitation mechanism. We had seen this previously in the Beaver parser generator, but it does not seem to be the case here. I remind you we are semanticists with little experience with parsing, so we don’t know what is common. In the example provided with Spoofax, it looked like any generated Java was being completely written by hand in stratego. This might work, but it seems like duplicating the grammar, which means twice the effort, as well as fragility when the grammar changes.

Even if the classes above aren’t generated, presumably there is a parser being generated for our language, but we have no idea where it is (we looked at all the documentation). Presumably this parser can at least return an ATerm object, or something similar, but we don’t know how to do this.

We appreciate any guidance you can offer.

Alright, I added a new editor service so you can now specify disambiguation with Stratego rules. Commited with revision 22569, available from the nightly update site (http://lclnet.nl/update/nightly).

You can use it by specifying what Stratego rule name to use for disambiguation in YourLang-main.esv:

disambiguator: mylang-disambiguate

and then in one of the Stratego files you can define a rule like:

mylang-disambiguate:
amb(…) -> …

mylang-disambiguate:
amb(…) -> <debug(!“testing”)>

About the Java solution: that stuff really isn’t all that easy, as you have to work with abstract syntax tree data structures, token data structures, and position information attachments. With this a Stratego-based solution you can just reason at the term level instead.

Let me know how this works out and if you need any help.

We have tried this out, and it seems to work great! Thanks so much for such a quick response.

There may be a NullPointerException bug lurking in the implementation, after rewriting the name of a node in the AST, but we are trying to find a small test case to replicate this.

Thanks again!

Great! :) It hasn’t been extensively tested, so there may well be some bug in there. Could you post a stack trace?

Hi, my name is Radu, and I work in the same team with Chucky.
Sorry for the late post, we had some difficulties with the registration on this site.

This is the error I’m getting when I rewrite some terms in the AST at the disambiguation level:

java.lang.NullPointerException
at org.strategoxt.imp.runtime.services.InputTermBuilder.tryGetProjectPath(InputTermBuilder.java:115)
at org.strategoxt.imp.runtime.services.StrategoObserver.configureRuntime(StrategoObserver.java:788)
at org.strategoxt.imp.runtime.services.StrategoObserver.invoke(StrategoObserver.java:671)
at org.strategoxt.imp.runtime.services.StrategoBuilder.invokeObserver(StrategoBuilder.java:305)
at org.strategoxt.imp.runtime.services.StrategoBuilder.execute(StrategoBuilder.java:185)
at org.strategoxt.imp.runtime.services.StrategoBuilder.access$1(StrategoBuilder.java:170)
at org.strategoxt.imp.runtime.services.StrategoBuilder$1.run(StrategoBuilder.java:157)
at org.eclipse.core.internal.jobs.Worker.run(Worker.java:54)

Internal error evaluating editor-resolve (NullPointerException; see error log)

I get the first one when I press "Show Abstract syntax (for selection)", for something selected. Most of the times it works for the entire text. The second error appears when I hover over some text.

My disambiguation is like this (sample that triggers the error):
mydisambiguate =
bottomup(try(\Id1Var(x) -> Id2Var(x)))

Probably I’m rewriting that term and I lose some info about the location of the node, because debug(!“Test”) shows the tree correctly.

Okay, that stack trace indicates that the parent references were not reinitialized after the transformation. I just committed a fix for that in revision 22758. Unfortunately, the nightly build is broken at the moment (Rob, if you’re reading this..? :o)

Hi again, I’ve seen that you’ve reached a stable build with revision 22830, but the eclipse update site is still at r22601.
I would really like to use the fix you’ve committed because I keep triggering bugs in the editor, maybe this is a more stable version.
Can you help me with this?

Hi Radu,

You may have to reload the repository a few times, there appears to be some caching that prevents any update from working the first time. (i.e. help -> install new software -> available software sites -> select the spoofax update site -> reload, then try again to install. Repeat one more time if necessary. If then it still doesn’t work then something else may be broken.)

Works now, thanks. I believe the Internet was broken last night (I kept getting Request Timed out).
The null pointer exception is fixed, but there still is a bug somewhere.

I keep getting something like this (the index varies):
Description - "Internal parsing error: java.lang.IndexOutOfBoundsException: Index: 816, Size: 816 (recovery failed)"
Resource - ImpConditionalBuiltins.k
Path - /K/test
Location - line 0
Type - org.strategoxt.imp.runtime.parsemarker

The scenario is not always the same, but the error is triggered after reparsing one or more test files.
Sometimes it appears while I modify a single file. Sometimes I get it after I reopen a test file.
The sources are correct, because if I close eclipse and reopen it, the same file that generated the error, is parsed correctly.

Please tell me if you need more information about this, or a small example...

Do you have a stack trace for that one? It might be in the error log (Window menu, show view, error log).

!ENTRY org.strategoxt.imp.runtime 4 0 2011-05-13 15:56:12.166
!MESSAGE Internal parsing error: Index: 798, Size: 798
!STACK 0
java.lang.IndexOutOfBoundsException: Index: 798, Size: 798
	at java.util.ArrayList.RangeCheck(Unknown Source)
	at java.util.ArrayList.get(Unknown Source)
	at org.spoofax.jsglr.client.imploder.Tokenizer.getTokenAt(Tokenizer.java:81)
	at org.spoofax.jsglr.client.imploder.Tokenizer.bindAstNode(Tokenizer.java:293)
	at org.spoofax.jsglr.client.imploder.Tokenizer.initAstNodeBinding(Tokenizer.java:278)
	at org.strategoxt.imp.runtime.parser.CustomDisambiguator.transferAttachments(CustomDisambiguator.java:85)
	at org.strategoxt.imp.runtime.parser.CustomDisambiguator.disambiguate(CustomDisambiguator.java:72)
	at org.strategoxt.imp.runtime.parser.SGLRParseController.parse(SGLRParseController.java:291)
	at org.strategoxt.imp.runtime.parser.SGLRParseController.parse(SGLRParseController.java:1)
	at org.strategoxt.imp.runtime.dynamicloading.DynamicParseController.parse(DynamicParseController.java:168)
	at org.eclipse.imp.editor.ParserScheduler.run(ParserScheduler.java:86)
	at org.eclipse.core.internal.jobs.Worker.run(Worker.java:54)

Also forgot to say that sometimes when I press the "Transform" button I get an error
saying "Could not load builders" or "Editor is still analyzing".

Looking just at the stack trace and code, it’s hard to tell what’s going on. But I added a range check to r22882 that may help. The other problems you’re getting are caused by the parser not having an AST ready for inspection, which makes sense as the parser fails with this exception you’re getting.

Radu: thanks for your demo project, I think I figured out the remaining problem. Should be fixed in r22899.