Bridging grammarware and modelware is still challenging, though often required as a prerequisite for several model-driven engineering scenarios. For instance, in model-driven reverse engineering, program code has to be lifted to the model level before model-driven techniques are applicable. Manually building metamodels based on given grammars introduces a signi cant overhead and may lead to inconsistencies between the resulting metamodels and the grammars, especially when dealing with large languages. In previous work, we have investigated a purely translational approach that is able to semi-automatically generate metamodels from grammars by utilizing user input. In this work, we aim to provide a higher degree of automation by combining the translational approach with by-example techniques to reduce the manual e ort. In particular, knowledge is derived from concrete programs to further re ne the produced metamodels. We demonstrate a transformation chain that combines translational and by-example techniques to produce Ecore-based metamodels from EBNFbased grammars.
In the last decade, much e ort has been invested to bridge the gap between
GrammarWare (GW) [
Challenge. We explored such scenarios in the ARTIST project1 [
Contribution. To reduce the manual e ort and the heavy involvement of users
in the development of bridges between GW and MW, we present in this paper a
transformation chain that semi-automatically generates Ecore-based
metamodels from given EBNF grammars [
Structure. In Section 2, we brie y describe the background of our work and introduce a motivating example that shows one particular challenge when moving from GW to MW, namely how to infer types of cross-references that are not represented in EBNF-based grammars. In Section 3, we present our transformation chain and demonstrate its application on the motivating example by relying on EBNF in the GW technical space, and Xtext2 and Ecore in the MW 1 http://www.artist-project.eu 2 http://www.eclipse.org/Xtext technical space. In this context, the application of Xtext as a mediator in the transformation chain is novel. Xtext appears to be useful because it provides features of both technical spaces. We conclude with an outlook towards an extensive evaluation of our approach in Section 4. 2
With today's language development tools and established model transformation techniques, metamodels and corresponding parsers/printers can be automatically generated from grammars de ned with meta languages residing in the MW technical space. Exploiting this automatic generation for producing metamodels also from EBNF-based grammars, i.e., grammar de nitions residing in the GW technical space, relies on two assumptions: (i) the heterogeneities of the meta-languages used in GW and MW can be resolved on a syntactical level, and (ii) the information needed to produce high quality metamodels is provided by artifacts of the GW technical space. We assume in our transformation chain EBNF as the meta-language in the GW context, and Xtext and Ecore as the meta-languages in the MW context.
Xtext is a language for de ning textual syntaxes of languages and allows the generation of Ecore-based metamodels and corresponding parsers/printers. Hence, Xtext and Ecore are well integrated with each other. As a result, the challenge is to bridge EBNF with one of the two candidates. Xtext seems to be the preferable choice as an intermediate format, thereby avoiding to lose the concrete syntax elements typically expressed in an EBNF grammar because Ecore is capable of representing elements from an abstract syntax perspective, only. Thus, Xtext may serve as a mediator between EBNF and Ecore as it is a hybrid approach, comprising technological features and meta-language concepts from both technical spaces. 2.1
Let us take MiniJava3 as a concrete example language that is expressed in EBNF and for which we want to generate a metamodel. Furthermore, for the purpose of this paper, let us focus on one concrete production rule from the MiniJava grammar, as shown in Listing 1.1.
C l a s s D e c l a r a t i o n = " class " , Identifier , [ " extends " , I d e n t i f i e r ] ; I d e n t i f i e r = f 'a ' j 'b ' j . . . g
Straightforwardly translating the ClassDeclaration production rule expressed in EBNF to a parsing rule expressed in Xtext would result in the Xtext-based grammar given in Listing 1.2. 3 MiniJava is a small language related to Java that is mainly used for teaching purposes. More information on the language may be found at: http://cs.fit.edu/ ~ryan/cse4251/mini_java_grammar.html
C l a s s D e c l a r a t i o n : " c l a s s " n a me=I D E N T I F I E R ( " e x t e n d s " s u p e r C l a s s= ,! I D E N T I F I E R ) ? ; terminal I D E N T I F I E R : ( ' a ' j ' b ' j . . . ) ;
Besides some small syntactical di erences, we are able to express the ClassDeclaration rule in both meta-languages in a similar way. However, Xtext provides several additional features compared to EBNF. These features facilitate the generation of meaningful Ecore-based metamodels from Xtext-based grammars. In particular, Xtext allows us to distinguish between di erent kinds of rule calls. In the context of our example, the rst rule call is used to express the name of a declared MiniJava class while the second rule call actually represents a cross-reference to the class, which serves as super class. If we do not distinguish between these two di erent intentions of the rule calls, we would end up with just having String-typed attributes in the corresponding Ecore-based metaclasses generated from the Xtext grammar instead of having typed references as well. Figure 1(a) depicts the metaclass corresponding to the ClassDeclaration rule in Listing 1.2. However, what we actually would like to achieve is the metaclass as illustrated in Figure 1(b) because it provides a typed reference for expressing inheritance relationships between MiniJava classes.
(a) (b)
When taking a closer look at our ClassDeclaration rule in Listing 1.2, a better solution is to make use of Xtext's support for cross-references and exploit built-in terminals provided in terms of a library. Listing 1.3 depicts the required Xtext grammar to obtain the desired metaclass in Figure 1(b).
C l a s s D e c l a r a t i o n : " c l a s s " n a me=ID ( " e x t e n d s " s u p e r C l a s s =[
,! C l a s s D e c l a r a t i o n ] ) ? ;
This example shows that with a straightforward translation of EBNF-based grammars to Xtext-based grammars, we may not obtain the metamodel which we would expect from the perspective of the MW technical space. Thus, additional e ort is required to produce meaningful metamodels in the expected quality. In the following, we present a concrete transformation chain that is able to generate metamodels comprising typed cross-references. The type information is inferred from example programs expressed in terms of the original grammar. 4 M 3 M 2 M 1 M
Grammarware
EBNF.ebnf aLang.ebnf aProg.java
XText.xtext
0 EBNF.xtext t2m
Now we are able to apply MDE techniques to actually shift a given language de nition represented as a model towards Xtext 2 by applying a model transformation we developed in ATL between the metamodels of EBNF and Xtext. By relying on the printer capabilities provided by Xtext, the generation of an Xtext-based grammar for a given language de nition is achieved 3 . This also eliminates the M4 meta-level. The generation of an Ecore-based metamodel for the language de nition expressed as an Xtext-based grammar 4 is out-ofthe-box provided by Xtext. Furthermore, the Xtext-based representation of the language de nition allows to exploit further the capabilities of Xtext, namely to parse programs that conform to the given language 5 . The result of our transformation chain, i.e., the Ecore-based metamodel and the models representing the programs, is fully operable, though the quality of the generated metamodels requires improvement 6 to render them useful for future MDE tasks that rely on these metamodels. A by-example approach is the technique of choice to achieve such improvements in this paper. In particular, information is derived in this step from programs that is missing in the grammar.
EBNF.ecore M2M XText.ecore
XText.xtext
Ecore.ecore aLang.xmi 2m2m aLang.xmi 3m2t aLang.xtext 4t2m aLang.ecore aProg.xmi 6 m 2 m 3.1
To reach the MW technical space for the given artifacts in the GW technical space, our current approach is to express EBNF in Xtext4 to enable the parsing of language de nitions expressed in EBNF as well as to parse programs conforming to this language de nitions.
To automatically generate the Xtext grammar in Listing 1.3 from the EBNF grammar given in Listing 1.1, the actual intention behind the Identi er needs to be expressed and the type of the reference is required to be known if the intention refers to a cross-reference, as discussed in the motivating example. Therefore, we introduced dedicated annotations into our Xtext-based EBNF grammar to ensure an e ective transformation of the intention behind rule calls. Listing 1.4 shows the annotated version of the ClassDeclaration production rule. The user has to mark the rule calls that refer to the provision of the identi er values for a language concept (cf. @id annotation) as well as for rule calls that actually represent references to other elements (cf. @idref annotation).
Listing 1.4: Annotated production rule ClassDeclartion in EBNF C l a s s D e c l a r a t i o n = " c l a s s " , @id I d e n t i f i e r , [ " e x t e n d s " , @ i d r e f ( ,! s u p e r C l a s s ) I d e n t i f i e r ] ; I d e n t i f i e r = f ' a ' j ' b ' j . . . g ;
Although with this approach the dedicated rules in the model transformation to generate the expected result can be triggered, the type of the superClass reference remains generic. While the annotations may be manually introduced even in large grammars with reasonable e ort, the decision for an adequate type appears to be challenging in general when just reasoning on the grammars without taking a look on a larger example base. Here our design rationale is that information that may be inferred by the user in a local context, e.g., by looking at one particular production rule, is provided by the user, while information that requires reasoning on a global scope is derived automatically by the help of analyzing examples. 3.2
On a general level, concepts of EBNF straightforwardly map to concepts of Xtext. As Xtext provides a richer set of concepts compared to EBNF, the model transformation between them needs to resolve certain heterogeneities. From a technical perspective, the model transformation addresses features of Xtext that are required to obtain an operable parser/printer. For example, identi ers are often only informally speci ed by EBNF grammars. Xtext provides built-in terminals that already ful ll the typical requirements. Perhaps, even more important, the model transformation needs to deal with conceptual aspects as well. Besides the di culties that may arise with LL-based parsing, e ectively dealing with our annotations in the EBNF grammar falls in this category. Listing 1.5 4 An Xtext-based EBNF implementation can be found under http://xtexterience.
wordpress.com/2011/05/13/an-ebnf-grammar-in-xtext shows the required adaptations in the EBNF grammar for providing annotations in language de nitions.
E x p r e s s i o n _ R u l e _ R e f e r e n c e returns E x p r e s s i o n : (f E x p r e s s i o n _ R u l e _ R e f e r e n c e g ( ( ( idRef ?= " @idref " ) ( " ( " ,!refName=NAME " ) " ) ?) j ( idName?=" @id " ) ) ? rule =[ ,! P r o d u c t i o n R u l e j NAME ] ) ;
Rule calls annotated with @id are transformed to \name" attributes while @idref leads to a more complex output in the sense that a common production rule is temporarily introduced as a default candidate for the reference end-point.
Listing 1.6 shows the automatically generated Xtext grammar for the ClassDeclaration parsing rule. Compared to Listing 1.3, the type of superClass is not yet ClassDeclaration as this information cannot be inferred solely from the given grammar. Instead, CommonReferenceRule serves as intermediate placeholder by generalizing all other existing production rules in the grammar. Ideally, example programs allow us to subsequently infer the most speci c types as depicted in the re ned version of the grammar in Listing 1.3.
Listing 1.6: Automatically generated parser rule ClassDeclartion in Xtext C l a s s D e c l a r a t i o n : " class " name=ID ( " extends " s u p e r C l a s s =[
,! C o m m o n R e f e r e n c e R u l e ] ) ? ;
C o m m o n R e f e r e n c e R u l e : C l a s s D e c l a r a t i o n j . . . j . . . ; 3.3
Inspired by existing work on bottom-up (meta)modeling [
By having the initially produced Xtext grammar as shown in Listing 1.6, we already have the possibility to parse the programs into models. In these models, the concrete links between model elements are available that can be analyzed to produce the information to further re ne the generated cross-references of the Xtext grammar and in the corresponding Ecore metamodel.
In the by-example based re nement step, we apply a select/infer/adapt process that|as the name already suggests|selects the language de nition parts that may need further re nements, infers additional information from the examples, and adapts the language de nition part by incorporating the newly inferred information.
For our concrete task of inferring the exact types, i.e., the most speci c types, of cross-references, we show the used algorithm of the by-example reasoning process in Listing 1.7 using OCL-like pseudo code notation. As input we need the metamodel to be re ned (the re ned version of it is the output of the algorithm) and the example base represented by a set of models that are produced from a set of programs by the parser generated from our initial metamodel.
var mm : M e t am o d e l ; -- input / output var mb : Set f Model g ; -- input -- s el e c t i on phase Set f R e f er e n c e g r e f s T o A d a p t = mm . g e t C r o s s R e f e r e n c e s ( ) ; r e f s T o A d a p t > foreach ( ref j -- i nf e r e n ce phase Set f Link g links = mb > collect ( m j m . g e t L i n k s O f T y p e ( ref ) ) > ,!flatten ( ) ; Set f Class g classes = links > collect ( l j l . g e t T a r g e t T y p e ( ) ) > ,!asSet ( ) ; -- a d a p t a t i o n phase i f classes . size ( ) = 1 then ref . s e t T a r g e t T y p e ( classes . first ( ) ) ; else i f . . . endif endif )
Due to space limitations, we only show one concrete case of the type re nement process. First, we collect in the selection phase all cross-references available in the metamodel (because all of them are only typed to CommonReferenceRule in the initial version of the metamodel). For the inference phase, we iterate over this set of references and for each reference we query the instantiated links from all models to collect the types of the target objects referenced by the links. By converting this collection to a set, we get the information that we need for the adaptation phase. Here we only discuss one possible case, namely if all referenced objects are of the same type, i.e., the set has only one entry, that results in a simple adaptation by just setting the type of the reference under study to the inferred type. In cases where objects are referenced that are of di erent types, more sophisticated adaptations are necessary, e.g., the introduction of new classes that act as super classes for the inferred types, because in Ecore only one type is allowed for each reference. Coming back to our motivating example, when executing this algorithm on a set of example models, we are able to transform the Xtext grammar shown in Listing 1.6 into the Xtext grammar of Listing 1.3. From the latter, the meta-class as shown in Figure 1(b) can be automatically derived that represents the expected metamodel de nition for the MiniJava grammar excerpt. 4
With the implementation of our transformation chain and the experimentation with the MiniJava grammar, we achieved initial evidence that metamodels can be automatically generated from grammars and re ned by applying by-example based techniques. By having the latter step, we are able to infer additional knowledge about the language that is not directly presented in the grammar de nitions but in other tools residing in the GW technical space such as compilers. Furthermore, the assumption of having enough examples to provide meaningful re nements of metamodels seems valid, because the trigger for producing the metamodels is the existence of GW artifacts that should be transferred to MW.
On the basis of our results, we plan an extensive evaluation of our approach
with grammars from well-established languages such as Java or C# as next
steps. In particular, di erent variants of a Java metamodel [