Annotation based parser generator

UDC 004.4, DOI: 10.2298/CSIS1002291P Annotation Based Parser Generator* Jaroslav Porubän1, Michal Forgáþ1, Miroslav Sabo1, and Marek BČhálek2 1 Department of Computers and Informatics, Technical University of Košice, Letná 9, 042 00 Košice, Slovak Republic {Jaroslav.Poruban, Michal.Forgac, Miroslav.Sabo}@tuke.sk 2 Department of Computer Science, FEI VŠB Technical University of Ostrava, 17. listopadu 15, 708 33 Ostrava-Poruba, Czech Republic [email protected] Abstract. The paper presents innovative parser construction method and parser generator prototype which generates a computer language parser directly from a set of annotated classes in contrast to standard parser generators which specify concrete syntax of a computer language using BNF notation. A language with textual concrete syntax is defined upon the abstract syntax definition extended with annotations in the presented approach. Annotations define instances of concrete syntax patterns in a language. Abstract syntax of a language is inevitable input of the parser generator as well as language’s concrete syntax pattern definitions. The process of parser implementation is presented on the concrete computer language – the Simple Arithmetic Language. The paper summarizes results of the studies of implemented parser generator and describes its role in the university courses. Keywords: parser generator; annotated model; abstract syntax; model to grammar transformation. 1. Introduction Computer languages are crucial tools in the development of software systems. By using computer languages we define the structure of a system and its behavior. Today's common industry practice is to create a software system as a composition of software artifacts written in more than one computer language. Developers use different languages and paradigms throughout the development of a software system according to a nature of concrete subproblem and their preferences. Besides the general-purpose programming languages (e. g. Java, C#) the domain-specific languages (DSL) [1][2] have become popular in the last decade. Nowadays, DSLs have their stable position in the development of software systems in many different * This work is supported by APVV Grant No. SK-CZ-0095-07 – Cooperation in Design and Implementation of Language Systems and by VEGA Grant No. 1/4073/07 – Aspect-oriented Evolution of Complex Software System. Jaroslav Porubän, Michal Forgáþ, Miroslav Sabo, and Marek BČhálek ComSIS Vol. 7, No. 2, Special Issue, April 2010 292 forms. Concerning abstraction level, it is possible to program closer to a domain. Furthermore DSLs enables explicit separation of knowledge in the system in natural structured form of domain. The growth of their popularity is probably connected with the growth of XML technology and using of standardized industry XML document parsers as a preferable option to the construction of language specific processors. A developer with minimal knowledge about language parsing is able to create a DSL with XML compliant concrete syntax using tools like JAXB [3]. Computer languages come in many flavors – as well known GPLs, DSLs, but also as APIs, ontologies [4], and even others. The one of the today’s hottest research topics in the field of computer language development is the tooling support. In the paper we concentrate on the parser generators for DSLs. Even though the research in the field of computer languages has the long history and parser generators for a textual language processing like YACC [5], Bison [6], JavaCC [7] and ANTLR [8] have their stable position in the computer language development the task of developing a computer language is still an expert task. Cook et al. [9] conclude that implementing a textual DSL by implementing its grammar can be a difficult and error-prone task, requiring significant expertise in language design and the use of a parser generator. Similarly, Mernik et al. [1] argue that DSL development is hard, requiring both domain knowledge and language development expertise. We present the novel method of a computer language design and implementation in the paper – abstract syntax driven parser generation. The rest of the paper has the following structure: In the section 2 we present main ideas behind our approach to a computer language development. The section 3 explains the method on example of simple but extensible arithmetic language. Section 4 describes the parser generator prototype –YAJCo. Section 5 summarizes the results of our experiments with YAJCo parser generator. Section 6 compares our work with the state of the art in the field of parser generators. The last section 7 concludes the paper and outlines the possibilities for further research in the field of parser generators and computer language development in general. 2. Abstract Syntax Directed Language Definition This section sketches the main ideas behind the innovative approach to the definition of a concrete syntax for a computer language with textual notation. Contrary to traditional methods of parser generation (e. g. YACC, JavaCC), we focus on the definition of abstract syntax rather than giving an excessive concentration on concrete syntax (see Fig. 1). In our approach the abstract syntax of a language is formally defined using standard classes well known from object-oriented programming and metamodels. Kleppe argues for concentrating on abstract syntax and metamodels when we define a computer language in [10]. Annotation Based Parser Generator ComSIS Vol. 7, No. 2, Special Issue, April 2010 293 Concrete syntax Traditional approach to a parser generation Abstract syntax Semantics Presented approach to a parser generation Semantics Abstract syntax Concrete syntax Concrete syntax Traditional approach to a parser generation Abstract syntax Semantics Concrete syntax Traditional approach to a parser generation Abstract syntax Semantics Presented approach to a parser generation Semantics Abstract syntax Concrete syntax Presented approach to a parser generation Semantics Abstract syntax Concrete syntax Fig. 1. Comparing traditional and presented approaches to a computer language parser generation Language Developer +YAJCo Parser Generator Tool Assistance Parser Parser Parser Parser Abstract syntax Abstract syntax ([SUHV VLRQ 1XPEHU $GG 6XE 1 11 1 Abstract syntax Abstract syntax ([SUHV VLRQ 1XPEHU $GG 6XE 1 11 1 YAJCo Parser Generator Concrete syntax Concrete syntax Abstract syntax Abstract syntax ( [ S U H V V L R Q 1 X P E H U $ G G 6 X E 1 11 1 @Operator @Token @Operator @Parentheses Concrete Syntax Pattern Extensions Concrete syntax Concrete syntax Abstract syntax Abstract syntax ( [ S U H V V L R Q 1 X P E H U $ G G 6 X E 1 11 1 @Operator @Token @Operator @Parentheses Concrete Syntax Pattern Extensions Fig. 2. Generating Language Parser using YAJCo’s parser generation approach In our approach the language implementation begins with the concept formalization in the form of abstract syntax. Language concepts are defined as classes and relationships between them. Upon such defined abstract syntax a developer defines both the concrete syntax through a set of source code annotations and the language semantics through the object methods. Annotations (called also attributes [11) are structured way of additional knowledge incorporated directly into the source code. During the phase of concrete syntax definition the parser generator assists a developer with suggestions and hints for making the concrete syntax unambiguous. Fig. 2 shows the whole process of parser implementation using the described approach. If the concrete syntax is unambiguously defined then parser generator automatically generates the parser from annotated classes. It is quite common to have multiple notations for one language. RELAX NG [12] is an example of such a language with two different notations – XML Jaroslav Porubän, Michal Forgáþ, Miroslav Sabo, and Marek BČhálek ComSIS Vol. 7, No. 2, Special Issue, April 2010 294 concrete syntax and compact concrete syntax. By using our approach different notations of the same language can share both abstract syntax and semantics. In some cases the evolution of concrete syntax does not require the modification of abstract syntax and semantics at all. This means that other notations of the same language are not affected by this type of language evolution. For instance, Fig. 3 presents the language with four different notations sharing the same abstract syntax and semantics. These notations (concrete syntaxes) are textual notation, XML notation, in-memory object notation and graphical notation. Concrete notations are interchangeable and developer selects among them according to his preferences. Abstract syntax Semantics Concrete syntax 1 textual notation Concrete syntax 2 graphical notation Concrete syntax 3 XML notation Concrete syntax 4 object notation Fig. 3. Computer language with multiple notations and shared abstract syntax and semantics 3. SAL Example This section presents our approach to a computer language definition using annotated classes on the example of Simple Arithmetic Language (SAL). This language expresses the arithmetic expressions with basic arithmetic binary operations of addition and multiplication, and unary operation of arithmetic negation. The expressions also contain integer numbers. The abstract syntax of SAL can be formally defined using BNF as follows. e,e1,e2Expression, nNumber e ::= Number n | UnaryMinus e | Add e1e2 | Mul e1e2 Variables e,e1,e2are metavariables from the Expression syntactical domain and nis the metavariable from the Number syntactical domain. The infix form of arithmetic operation is intentionally omitted to avoid the confusion with concrete syntax. Prefix names in productions (e. g. UnaryMinus, Mul) are used just to uniquely name the productions for semantic equations. The semantics of SAL is formally defined using Eval function which maps a value from syntactic domain Expression to a value from semantic domain Z (integers) and Value function which maps a value from syntactic domain Number to a value from semantic domain Z. Annotation Based Parser Generator ComSIS Vol. 7, No. 2, Special Issue, April 2010 295 Eval : Expression o Z Value : Number oZ The semantic function Eval is defined by the following equations. Eval [| Number n |] = Value [| n |] Eval [| UnaryMinus e|] = – Eval [| e |] Eval [| Add e1e2 |] = Eval [| e1 |] + Eval [| e2 |] Eval [| Mul e1e2 |] = Eval [| e1 |] * Eval [| e2 |] Certainly we can find many different notations for SAL. For example, we can write down a sentence from SAL in the following notation using standard symbols and the operator infix form. 1 + 2 * 7 In the Fig. 4, abstract syntax tree of the sentence above is depicted. Number 1 Number 2 Number 7 Mul Add Number 1 Number 2 Number 7 Mul Add Fig. 4. The abstract syntax tree of the expression 1 + 2 * 7 From the Fig. 4 it is apparent that depicted abstract syntax tree contains typed nodes corresponding to language concepts. The node types are Add, Mul and Number. Add node represents the binary operation of addition. It always has two child nodes respecting the nature of the binary operation of addition. The Mul node represents multiplicative operation and the leaf node Number represents an integer number. The Number node is attributed with the notation of a number. Unlike traditional approach, language definition will not start with the definition of SAL’s concrete syntax written in BNF. According to our approach, the object classes representing syntactic domains (language concept) are created at first. These classes define the abstract syntax of the language and also the semantics of the language as stated in the previous formal definition of the SAL. The concrete syntax will be specified later using source code annotations, expressing the concrete syntax patterns and their correspondence to the abstract syntax concepts. The main concept of the SAL is the Expression. It is pretty straightforward because SAL is the language of expressions. On the other side it is an abstract concept and it does not have concrete representation. From the semantic point of view every expression can be evaluated to a single integer value. This fact is denoted by semantic function eval of Expression class. Jaroslav Porubän, Michal Forgáþ, Miroslav Sabo, and Marek BČhálek ComSIS Vol. 7, No. 2, Special Issue, April 2010 296 abstract class Expression { //Semantic function – OOP method abstract int eval(); } The Expression class is declared to be abstract because it only defines the abstract concept of an expression from SAL and does not represent any abstract syntax graph node. Next, the different types of expressions can be incorporated into the SAL. The simplest form of an expression is a number expression. Number has its notation and the value. Firstly we will focus is on its value. The notation will be defined later during the definition of the concrete syntax. It needs to be expressed that number is a simple expression as well. This is done using “is-a” relationship, denoted with extends keyword in Java. Corresponding semantic equations are denoted in the comments above the methods. The code snippet below shows the class Number for integer numbers. class Number extends Expression { int value; //Eval [| Number n |] = Value [| n |] int eval() { return value; } } The unary operation of negation is defined in the following snippet of the UnaryMinus class. class UnaryMinus extends Expression { Expression expression; //Eval [| UnaryMinus e |] = – Eval [| e |] int eval() { return -expression.eval(); } } Since the addition is a kind of arithmetic expression in SAL, the binary operation of addition is defined in the class Add. Relationship “is-a” is therefore used again. class Add extends Expression { Expression expression1; Expression expression2; //Eval [| Add e1e2 |] = Eval [| e1 |] + Eval [| e2 |] int eval() { return expression1.eval() + expression2.eval(); } } Operation of multiplication is defined in the same style as binary operation Add. Annotation Based Parser Generator ComSIS Vol. 7, No. 2, Special Issue, April 2010 297 The class diagram in the Fig. 5 shows the hierarchy of SAL classes. The abstract syntax of arithmetic expression language has already been defined as well as the semantic function Eval using the classic OOP notation. The next step in the development of SAL is to define the concrete syntax for the language. Concrete syntax will be used when expression (sentence) will be stored in the textual form. ([SUHVVLRQ $GG 0XO 8QDU\0LQXV -expression1 1 -expression1 1 -expression2 1 -expression2 1 -expression 1 1 1XPEHU Fig. 5. Classes and their hierarchy in the simple arithmetic language (SAL) The specification of concrete syntax requires some additional information about textual representation of the language concepts. In SAL it is: x a number representation (notation), x notation for operations, x symbols for the operations of addition, multiplication and negation, x the form of the notation, the priority and associativity of all operations. The operations will be expressed in infix form using standard symbols + and *. Unary operation of negation will be in the prefix form denoted with the symbol -. The priority, associativity and symbols for the operations are listed in Table 1. The integer numbers are written using standard decimal notation with digits 0,1, …, 9. Table 1. Priority and associativity of SAL operators Operator Priority Associativity +1 (lowest) left * 2 left -3 (highest) right The class for integer numbers is augmented with concrete syntax source annotations in the following code snippet. Jaroslav Porubän, Michal Forgáþ, Miroslav Sabo, and Marek BČhálek ComSIS Vol. 7, No. 2, Special Issue, April 2010 298 class Number extends Expression { int value; Number(@Token("VALUE") long value) { this.value = value; } int eval() { return value; } } The @Token annotation with VALUE attribute defines the name of a regular expression for the number notation. As seen on the snippet the class constructor is augmented with the concrete syntax pattern. The regular expression can be defined as follows. @TokenDef(name = "VALUE", regexp = "[0-9]+") The format of a regular expression depends on the syntax for definition of regular expressions. The annotation @Token("VALUE") can even be omitted because the name of token can be derived directly from the name of the parameter (value in this case). The domain class for binary operation of addition augmented with concrete syntax annotations is shown below. class Add extends Expression { Expression expression1; Expression expression2; @Operator( associativity = Associativity.LEFT, priority = 1 ) Add(Expression expression1, @Before("+") Expression expression2) { this.expression1 = expression1; this.expression2 = expression2; } int eval() { return expression1.eval() + expression2.eval(); } } Concrete syntax for the operation of addition is defined in the class constructor. Parameters of constructor define the rule of composition of the operation. In the constructor body it can be observed that addition is composed of two expressions in textual form. It is important to notice that after the first expression (and before the second expression at the same time) token + will follow. Binary operation of multiplication is defined accordingly to the definition of addition. The domain class for unary operation of arithmetic negation is Annotation Based Parser Generator ComSIS Vol. 7, No. 2, Special Issue, April 2010 299 augmented with concrete syntax annotations as shown in the code snippet below. class UnaryMinus extends Expression { Expression expression; @Operator(priority = 3) UnaryMinus( @Before("-") Expression expression) { this.expression = expression; } int eval() { return -expression.eval(); } } As seen in the constructor the operation is defined as unary prefix operation. The last step in definition of the SAL’s concrete syntax is the definition for parentheses. This can be achieved simply by using the annotation on abstract class for expressions as shown below. @Parentheses(left = "(", right = ")") abstract class Expression { //... } Finally the concrete syntax for the language has been defined. The implemented YAJCo parser generator generates the language parser from annotated classes. The concrete syntax of SAL is automatically derived from these classes, their relationships and concrete syntax annotations. In the current implementation of the YAJCo it is the following LL(1) context-free grammar. Expr1 ::= Expr2 {"+" Expr2} Expr2 ::= Expr3 {"*" Expr3} Expr3 ::= "-" Expr3 | Expr Expr ::= Number | "(" Expr1 ")" Number ::= [0-9]+ 4. YAJCo Parser Generator The main goal of the approach is not to create a new parsing technology based on context-free grammars theory. The main idea is to integrate existing technologies into the higher level abstraction in which the language developer does not have to concentrate on concrete parsing technology but on the Jaroslav Porubän, Michal Forgáþ, Miroslav Sabo, and Marek BČhálek ComSIS Vol. 7, No. 2, Special Issue, April 2010 306 7. Conclusion In the paper we have presented solution for generating parsers for textual languages. The language itself is specified by a set of annotated classes. Annotations extend the classes with additional information required for specification of concrete syntax, for example keywords and operator notations. The developer can start with the definition of abstract syntax and continue with creation of language in incremental way using the standard refactoring tools. In proposed solution there is only one form of definition of abstract syntax graph nodes – by the classes. The grammar is derived directly from the source code of annotated domain classes. Even the examples are written in object-oriented programming language Java our solution is not strictly connected to Java language and can be easily ported to any other object-oriented language supporting the attribute-oriented programming. We believe that our solution can simplify the development of textual software languages. References 1. Mernik, M., Heering, J., Sloane, A. M.: When and How to Develop DomainSpecific Languages. ACM Computing Surveys, Vol. 37, No. 4, 316–344. (2005) 2. Pereira, M. J. V., Mernik, M., da Cruz, D., Henriques, P. R.: Program Comprehension for Domain-Specific Languages. ComSIS, Vol. 5, No. 2. (2008) 3. Ort, E., Mehta, B.: Java Architecture for XML Binding. Sun Microsystems, [Online]. Available: http://java.sun.com/developer/technicalArticles/WebServices/jaxb (current November 2009) 4. Návrat, P., Bieliková, M., Chudá, D., Rozinajová, V.: Intelligent Information Processing in Semantically Enriched Web. Lecture Notes in Computer Science, Vol. 5722/2009, 331-340. (2009) 5. Johnson, S. C.: YACC: Yet Another Compiler-Compiler. Unix Programmer's Manual Volume 2b. (1979) 6. Donnelly, C., Stallman, R.: Bison: The Yacc-compatible Parser Generator. (2006). 7. Java Compiler Compiler – The Java Parser Generator, (2009). [Online]. Available: https://javacc.dev.java.net (current November 2009) 8. Parr, T.: The Definitive ANTLR Reference: Building Domain-Specific Languages, Pragmatic Bookshelf, 376 pp. (2007) 9. Cook, S., Jones, G., Kent, S., Wills, A. C.: Domain-Specific Development with Visual Studio DSL Tools. Addison-Wesley Professional, 576 pp. (2007) 10. Kleppe, A. G.: A Language Description is More than a Metamodel. In: Fourth International Workshop on Software Language Engineering, 1 Oct 2007, Nashville, USA. 11. Cepa, V.: Attribute Enabled Software Development, VDM Verlag, 216 p. (2007) 12. van der Vlist, E.: Relax NG. O'Reilly Media, 304 pp. (2003) 13. Fowler, M.: Language Workbenches: The Killer-App for Domain Specific Languages? (2005) [Online]. (current November 2009) Available: http://www.martinfowler.com/articles/languageWorkbench.html 14. Stahl, T., Voelter, M.:Model-Driven Software Development: Technology, Engineering, Management. Wiley, 444 p. (2006) Annotation Based Parser Generator ComSIS Vol. 7, No. 2, Special Issue, April 2010 307 15. Greenfield, J., Short, K., Cook, S., Kent, S., Crupi, J.: Software Factories: Assembling Applications with Patterns, Models, Frameworks, and Tools. Wiley, 500 p. (2004) 16. Muller, P. A., Fondement, F., Fleurey, F., Hassenforder, M., Schneckenburger, R., Gérard, S., Jézéquel, J. M.: Model-Driven Analysis and Synthesis of Textual Concrete Syntax. Journal on Software and Systems Modeling (SoSyM), Volume 7 (4), Springer, 423-441. (2008) 17. Kollár, J., Václavík, P., Wassermann, ď.: Data driven Executable Language Model. In Proceedings of the International Multiconference on Computer Science and Information Technology, Mragowo, Poland, IEEE Computer Society Press, 667675. (2009), ISSN 1896-7094. Jaroslav Porubän is Associate professor at Department of Computers and Informatics, Technical university of Košice, Slovakia. He received his MSc. in Computer Science in 2000 and his PhD. in Computer Science in 2004. Since 2003 he is the member of the Department of Computers and Informatics at Technical University of Košice. He was involved in the research of profiling tools for process functional programming language. Currently the main subject of his research is the computer language engineering concentrating on design and implementation of domain-specific languages and computer language composition and evolution. Michal Forgáþis Assistant professor at Department of Computers and Informatics, Technical university of Košice, Slovakia. He received his MSc. in 2006 and his PhD. in Computer Science in 2009. Since 2009 he is the member of the Department of Computers and Informatics at Technical University of Košice. His scientific research is focused on the software evolution, software language engineering and adaptation of complex software systems. Miroslav Sabo is doctoral student at Department of Computers and Informatics, Technical University of Košice, Slovakia. He received his MSc. in Computer Science in 2008. The subject of his research is the utilization of generative methods in development and evolution of software systems in permanently changing environment. Marek BČhálek is Assistant professor at Department of Computer Science, FEI VŠB Technical University of Ostrava, Czech Republic. He received his MSc. in 2002. Since 2004 he is the member of the Department of Computer Science at Technical University of Ostrava. His scientific research is focused on programming languages, their evolution and application. Currently he is developing a tool for modeling of embedded systems based on functional programming paradigm. Received: November 16, 2009; Accepted: December 25, 2009.