Can Xtext be used for parsing general purpose programming languages?

Question

I'm currently developing a general-purpose agent-based programming language (its syntaxt will be somewhat inspired by Java, and we are also using object in this language).

Since the beginning of the project we were doubtful about the fact of using ANTLR or Xtext. At that time we found out that Xtext was implementing a subset of the feature of ANTLR. So we decided to use ANLTR for our language losing the possibility to have a full-fledged Eclipse editor for free for our language (such a nice features provided by Xtext).

However, as the best of my knowledge, this summer the Xtext project has done a big step forward. Quoting from the link:

What are the limitations of Xtext?

Sven: You can implement almost any kind of programming language or DSL with Xtext. There is one exception, that is if you need to use so called 'Semantic Predicates' which is a rather complicated thing I don't think is worth being explained here. Very few languages really need this concept. However the prominent example is C/C++. We want to look into that topic for the next release.

And that is also reinforced in the Xtext documentation:

What is Xtext? No matter if you want to create a small textual domain-specific language (DSL) or you want to implement a full-blown general purpose programming language. With Xtext you can create your very own languages in a snap. Also if you already have an existing language but it lacks decent tool support, you can use Xtext to create a sophisticated Eclipse-based development environment providing editing experience known from modern Java IDEs in a surprisingly short amount of time. We call Xtext a language development framework.

If Xtext has got rid of its past limitations why is it still not possible to find a complex Xtext grammar for the best known programming languages (Java, C#, etc.)?

On the ANTLR website you can find tons of such grammar examples, for what concerns Xtext instead the only sample I was able to find is the one reported in the documentation. So maybe Xtext is still not mature to be used for implementing a general purpose programming language? I'm a bit worried about this... I would not start to re-write the grammar in Xtext for then to recognize that it was not suited for that.

Sulfonmethane

Answer 1

I think nobody implemented Java or C++ because it is a lot of work (even with Xtext) and the existing tools and compilers are excellent. However, you could have a look at Xbase and Xtend, which is the expression language we ship with Xtext. It is built with Xtext and is quite a good proof for what you can build with Xtext. We have done that in about 4 person months.

I did a couple of screencasts on Xtend:

http://blog.efftinge.de/2011/03/xtend-screencast-part-1-basics.html
http://blog.efftinge.de/2011/03/xtend-screencast-part-2-switch.html
http://blog.efftinge.de/2011/03/xtend-screencast-part-3-rich-strings-ie.html

Note, that you can simply embed Xbase expressions into your language.

Pains

it's a pleasure to have one of the Xtext chiefs reply my question,thank for your interest.I was not expecting to have a complete suite of tools to work with Java/C++ realised on top of Xtext(as you said there is no need for this).I was looking for some good example of complex Xtext grammar.For ANTLR you will find plenty popular programming languages grammars ready to be used. That's not the case for Xtext, so I was wondering if it possible i.e. to seamlessly write a Java grammar in Xtext since in other forums,with previous version of Xtext,you deeply discouraged people to do so. – Sulfonmethane

The best example for a programming language implemented with Xtext is Xtend and Xbase. Its scoping is fully implemented, it supports full Java.generics and Scala-like type inference. The grammars can be found here: goo.gl/QGR9d and goo.gl/7kl23 – Pains

Many many thanks Sven! I will have a good look at it!It seems to be a really good test case for seing Xtext in action. I let you know the result of my investigations :) – Sulfonmethane

After a while I can say: yes it can and quite seamlessly. Xtext is such a great tool. Thank for all your work Sven!! – Sulfonmethane

Answer 2

I can't speak for what Xtext is or does well.

I can speak to the problem of developing robust tools for processing real languages, based on our experience with the DMS Software Reengineering Toolkit, which we imagine is a language manipulation framework.

First, parsing of real languages usually involves something messy in lexing and/or parsing, due to the historical ways these languages have evolved. Java is pretty clean. C# has context-dependent keywords and a rudimentary preprocessor sort of like C's. C has a full blown preprocessor. C++ is famously "hard to parse" due to ambiguities in the grammar and shenanigans with template syntax. COBOL is fairly ugly, doesn't have any reference grammars, and comes in a variety of dialects. PHP will turn you to stone if you look at it because it is so poorly defined. (DMS has parsers for all of these, used in anger on real applications).

Yet you can parse all of these with most of the available parsing technologies if you try hard enough, usually by abusing the lexer or the parser to achieve your goals (how the GNU guys abused Bison to parse C++ by tangling lexical analysis with symbol table lookup is a nice ugly case in point). But it takes a lot of effort to get the language details right, and the reference manuals are only close approximations of the truth with respect to what the compilers really accept.

If Xtext has a decent parsing engine, one can likely do this with Xtext. A brief perusal of the Xtext site sounds like the lexers and parsers are fairly decent. I didn't see anything about the "Semantic Predicate"s; we have them in DMS and they are lifesavers in some of the really dark corners of parsing. Even using the really good parsing technology (we use GLR parsers), it would be very hard to parse COBOL data declarations (extracting their nesting structure during the parse) without them.

You have an interesting problem in that your language isn't well defined yet. That will make your initial parsers somewhat messy, and you'll revise them a lot. Here's where strong parsing technology helps you: if you can revise your grammar easily you can focus on what you want your language to look like, rather than focusing on fighting the lexer and parser. The fact that you can change your language definition means in fact that if Xtext has some limitations, you can probably bend your language syntax to match without huge amounts of pain. ANTLR does have the proven ability to parse a language pretty much as you imagine it, modulo the usual amount of parser hacking.

What is never discussed is what else is needed to process a language for real. The first thing you need to be able to do is to construct ASTs, which ANTLR and YACC will help you do; I presume Xtext does also. You also need symbol tables, control and data flow analysis (both local and global), and machinery to transform your language into something else (presumably more executable). Doing just symbol tables you will find surprisingly hard; C++ has several hundred pages of "how to look up an identifier"; Java generics are a lot tougher to get right than you might expect. You might also want to prettyprint the AST back to source code, if you want to offer refactorings. (EDIT: Here both ANTLR and Xtext offer what amounts to text-template driven code generation).

Yet these are complex mechanisms that take as much time, if not more than building the parser. The reason DMS exists isn't because it can parse (we view this just as the ante in a poker game), but because all of this other stuff is very hard and we wanted to amortize the cost of doing it all (DMS has, we think, excellent support for all of these mechanisms but YMMV).

On reading the Xtext overview, it sounds like they have some support for symbol tables but it is unclear what kind of assumption is behind it (e.g., for C++ you have to support multiple inheritance and namespaces).

If you are already started down the ANTLR road and have something running, I'd be tempted to stay the course; I doubt if Xtext will offer you a lot of additional help. If you really really want Xtext's editor, then you can probably switch at the price of restructuring what grammar you have (this is a pretty typical price to pay when changing parsing paradigms). Expect most of your work to appear after you get the parser right, in an ad hoc way. I doubt you will find Xtext or ANTLR much different here.

Roshelle

Hi Ira thanks a lot for the reply. The link is wrong, should be semdesigns.com/products/DMS/DMSToolkit.html right? However thanks for the reference I will give it a look. I know that we will have to face all the issues you pointed out, we are taking this book as reference for now pragprog.com/titles/tpdsl/language-implementation-patterns. Even if you think that ANLR and Xtext are not so different I still wonder why I cannot find Xtext grammar for java and other languages like in the case of ANTLR... – Sulfonmethane

Great answer Ira, as usual! A small nitpick though: "Here ANTLR offers nothing AFAIK", ANTLR does have support for emitting text/code using StringTemplate. Given an AST (or just a simple parse tree), you could use ANTLR to generate source code again without having to worry about indentation and other manual painstaking output-operations. You'll have to create your own code-template and mix custom code inside the ANTLR grammar, so it's not as easy as 1-2-3, but still, it is possible. (for those interested about this, Google for "ANTLR output template") – Milissamilissent

@the_dark_destructor: Well, for one thing Xtext is apparantly rather new and it takes time to build up a library of real, robust language definitions. Given their focus on Java, I'm kind of surprised they don't have a full Java grammar; the rest don't surprise given its newness. – Roshelle

@Bart Kiers: thanks for the clarification, I learn something new even from my own answers :-} I've revised my answer to take your observation into account. – Roshelle

Answer 3

I guess the most simple answer to your question is: Many general purpose languages can be implemented using Xtext. But since there is no general answer to which parser-capabilities a general purpose languages needs, there is no general answer to your questions.

However, I've got a few pointers:

• With Xtext 2.0 (released this summer), Xtext supports syntactic predicates. This is one of the most requested features to handle ambiguous syntax without enabling antlr's backtracking.

• You might want to look at the brand-new languages Xbase and Xtend, which are (judging based on their capabilities) general-purpose and which are developed using Xtext. Sven has some nice screen casts in his blog: http://blog.efftinge.de/

Regarding your question why we don't see Xtext-grammars for Java, C++, etc.: With Xtext, a language is more than just a grammar, so just having a grammar that describes a language's syntax is a good starting point but usually not an artifact valuable enough for shipping. The reason is that with an Xtext-grammar you also define the AST's structure (Abstract Syntax Tree, and an Ecore Model in fact) including true cross references. Since this model is the main internal API of your language people usually spend a lot of thought designing it. Furthermore, to resolve cross references (aka linking) you need to implement scoping (as it is called in Xtext). Without a proper implementation of scoping you can either not have true cross references in your model or you'll get many lining errors.

A guess my point is that creating a grammar + designing the AST model + implementing scoping is just a little more effort that taking a grammar from some language-zoo and translating it to Xtext's syntax.

Haymo