TERM PAPER

System Software

Topic: Compiler Generator

Name: Animesh Poddar

Section: K1R04

Roll: A07

Registration no.: 11003532

Course Code: CSE318

Submitted to:

Ms. Himanshi

Introduction

In the field of computer sciences, we define a compiler-compiler or compiler generator as a tool which creates a parser, interpreter, or compiler from some form of formal description of a language and machine. The earliest and still most common form of compiler-compiler is a parser generator, whose input is a grammar (usually in BNF) of a programming language, and whose generated output is the source code of a parser often used as a component of a compiler. Similarly, code generator-generators (such as J Burg) exist, but such tools have not yet reached maturity.

The ideal compiler-compiler takes a description of a programming language and a target instruction set architecture, and automatically generates a usable compiler from them. In practice, the state of the art has yet to reach this degree of sophistication and most compiler generators are not capable of handling semantic or target architecture information.

History

The first compiler-compiler to use that name was written by Tony Brooker in 1960 and was used to create compilers for the Atlas computer at the University of Manchester, including the Atlas Auto code compiler. However it was rather different from modern compiler-compilers, and today would probably be described as being somewhere between a highly customizable generic compiler and an extensible-syntax language. The name 'compiler-compiler' was far more appropriate for Brooker's system than it is for most modern compiler-compilers, which are more accurately described as parser generators. It is almost certain that the "Compiler Compiler" name has entered common use due to YACC rather than Brooker's work being remembered.

Different Variants of Compiler Generator

A typical parser generator associates executable code with each of the rules of the grammar that should be executed when these rules are applied by the parser. These pieces of code are sometimes referred to as semantic action routines since they define the semantics of the syntactic structure that is analyzed by the parser. Depending upon the type of parser that should be generated, these routines may construct a parse tree (or abstract syntax tree), or generate executable code directly.

One of the earliest (1964), surprisingly powerful, versions of compiler-compilers is META II, which accepted grammars and code generation rules, and is able to compile in itself and other languages.

Some experimental compiler-compilers take as input a formal description of programming language semantics, typically using denotation semantics. This approach is often called 'semantics-based compiling', and was pioneered by Peter Mosses' Semantic Implementation System (SIS) in 1978. However, both the generated compiler and the code it produced were inefficient in time and space. No production compilers are currently built in this way, but research continues.

The Production Quality Compiler-Compiler project at Carnegie-Mellon University does not formalize semantics, but does have a semi-formal framework for machine description.

Compiler-compilers exist in many flavors, including bottom-up rewrite machine generators used to tile syntax trees according to a rewrite grammar for code generation, and attribute grammar parser generators (e.g. ANTLR can be used for simultaneous type checking, constant propagation, and more during the parsing stage).

Some types of Compiler Compiler

▪ ANTLR In computer-based language recognition, ANTLR (pronounced Antler), or Another Tool for Language Recognition, is a parser generator that uses LL(*) parsing. ANTLR is the successor to the Purdue Compiler Construction Tool Set (PCCTS), first developed in 1989, and is under active development. Its maintainer is professor Terence Parr of the University of San Francisco. ANTLR takes as input a grammar that specifies a language and generates as output source code for a recognizer for that language. At the moment, ANTLR supports generating code in the programming languages Ada95, Action Script, C, C#, Java, JavaScript, Objective-C, Perl, Python, and Ruby. A language is specified using a context-free grammar which is expressed using Extended Backus–Naur Form (EBNF). ANTLR allows generating lexers, parsers, tree parsers, and combined lexer-parsers. Parsers can automatically generate abstract syntax trees which can be further processed with tree parsers. ANTLR provides a single consistent notation for specifying lexers, parsers, and tree parsers. This is in contrast with other parser/lexer generators and adds greatly to the tool's ease of use. By default, ANTLR reads a grammar and generates a recognizer for the language defined by the grammar (i.e. a program that reads an input stream and generates an error if the input stream does not conform to the syntax specified by the grammar). If there are no syntax errors, then the default action is to simply exit without printing any message. In order to do something useful with the language, actions can be attached to grammar elements in the grammar. These actions are written in the programming language in which the recognizer is being generated. When the recognizer is being generated, the actions are embedded in the source code of the recognizer at the appropriate points. Actions can be used to build and check symbol tables and to emit instructions in a target language, in the case of a compiler. As well as lexers and parsers, ANTLR can be used to generate tree parsers. These are recognizers that process abstract syntax trees which can be automatically generated by parsers. These tree parsers are unique to ANTLR and greatly simplify the processing of abstract syntax trees. ANTLR 3 is free software, published under a three-clause BSD License. Prior versions were released as public domain software. While ANTLR itself is free, however, the documentation necessary to use it is not. The ANTLR manual is a commercial book, The Definitive ANTLR Reference. Free documentation is limited to a handful of tutorials, code examples, and very basic API listings.

▪ Bison GNU bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification of a context-free language, warns about any parsing ambiguities, and generates a parser (either in C, C++, or Java) which reads sequences of tokens and decides whether the sequence conforms to the syntax specified by the grammar. Bison generates LALR parsers. Bison also supports “Generalized Left-to-right Rightmost” (GLR) parsers for grammars that are not LALR. In POSIX mode, Bison is compatible with YACC, but also supports several improvements over this earlier program. Flex, an automatic lexical analyzer, is often used with Bison, to tokenize input data and provide Bison with tokens. Bison is licensed as free software and is available in source code form. Earlier releases of Bison used to stipulate that parts of its output were protected under the GPL, due to the inclusion of the yyparse() function from the original source code in the output. However, an exception was made, to allow other licenses to apply to the use of the output. ▪ Coco/R Coco/R is a compiler generator that takes an L-attributed Extended Backus–Naur Form (EBNF) grammar of a source language and generates a scanner and a parser for that language. The scanner works as a deterministic finite automaton. It supports Unicode characters in UTF-8 encoding and can be made case-sensitive or case-insensitive. It can also recognize tokens based on their right-hand-side context. In addition to terminal symbols the scanner can also recognize pragmas, which are tokens that are not part of the syntax but can occur anywhere in the input stream (e.g. compiler directives or end-of-line characters). The parser uses recursive descent; LL(1) conflicts can be resolved by either a multi-symbol look ahead or by semantic checks. Thus the class of accepted grammars is LL(k) for an arbitrary k. Fuzzy parsing is supported by so-called ANY symbols that match complementary sets of tokens. Semantic actions are written in the same language as the generated scanner and parser. The parser's error handling can be tuned by specifying synchronization points and "weak symbols" in the grammar. Coco/R checks the grammar for completeness, consistency, non-redundancy as well as for LL(1) conflicts. There are versions of Coco/R for most modern languages (Java, C#, C++, Pascal, Modula-2, Modula-3, Delphi, VB.NET, Python, Ruby and others). The latest versions from the University of Linz are those for C#, Java and C++. For the Java version, there is an Eclipse plug-in and for C#, a Visual Studio plug-in. There are also sample grammars for Java and C#. Coco/R was originally developed at the University of Linz and is distributed under the terms of a slightly relaxed GNU General Public License. ▪ DMS Software Reengineering Toolkit

The DMS(R) Software Reengineering toolkit is a proprietary set of program transformation tools available for automating custom source program analysis, modification, translation or generation of software systems for arbitrary mixtures of source languages for large scale software systems. DMS has been used to implement a wide variety of practical tools, include domain-specific languages (such as code generation for factory control), test coverage and profiling tools, clone detection, language migration tools, and C++ component reengineering. The toolkit provides means for defining language grammars and will produce parsers which automatically construct abstract syntax trees (ASTs), and pretty printers to convert original or modified ASTs back into compliable source text. The parse trees capture and the pretty printers regenerate, complete detail about the original source program, including source position, comments, radix and format of numbers, etc., to ensure that regenerated source text is as recognizable to a programmer as the original text modulo any applied transformations. Many program analysis and transformation tools are limited to ASCII or Western European character sets such as ISO-8859; DMS can handle these as well as UTF-8, UTF-16, EBCDIC, Shift-JIS and a variety of Microsoft character encodings. DMS uses GLR parsing technology, enabling it to handle all practical context-free grammars. Semantic predicates extend this capability to interesting non-context-free grammars (FORTRAN requires matching of multiple DO loops with shared CONTINUE statements by label; GLR with semantic predicates enables the DMS Fortran parser to produce ASTs for correctly nested loops as it parses). DMS provides attribute grammar evaluators for computing custom analyses over ASTs, such as metrics, and including special support for symbol table construction. Other program facts can be extracted by built-in control- and data- flow analysis engines, local and global pointer analysis, whole-program call graph extraction, and symbolic range analysis by abstract interpretation. ▪ Lemon Lemon is a parser generator, maintained as part of the SQLite project that generates an LALR parser in the C programming language from an input context-free grammar. The generator is quite simple, implemented in a single C source file with another file used as a template for output. Lexical analysis is performed externally. Lemon is similar to bison and YACC; however it is not compatible with these programs. The grammar input format is different to help prevent common coding errors. Other distinctive features include a reentrant, thread-safe output parser, and the concept of "non-terminal destructors" that try to make it easier to avoid leaking memory. SQLite uses Lemon with a hand-coded tokenize to parse SQL strings. In 2008 a Lemon-generated parser was suggested to replace the bison-generated parser used for the PHP programming language; as of 2010 this project was listed as "in the works". ▪ Java CC Java CC (Java Compiler Compiler) is an open source parser generator and lexical analyzer generator for the Java programming language. Java CC is similar to YACC in that it generates a parser from a formal grammar written in EBNF notation, except the output is Java source code. Unlike YACC, however, Java CC generates top-down parsers, which limits it to the LL(k) class of grammars (in particular, left recursion cannot be used). Java CC also generates lexical analyzers in a fashion similar to lex. The tree builder that accompanies it, JJ Tree, constructs its trees from the bottom up. Java CC is licensed under a BSD license. ▪ Packrat parser In computer science, a parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG. This is closer to how string recognition tends to be done in practice, e.g. by a recursive descent parser. Unlike CFGs, PEGs cannot be ambiguous; if a string parses, it has exactly one valid parse tree. This makes PEGs well-suited to parsing computer languages, but not natural languages.

▪ PQCC, a compiler-compiler that is more than a parser generator. The Production Quality Compiler-Compiler Project (or PQCC) was a long-term project led by William Wulf at Carnegie Mellon University to produce an industrial-strength compiler-compiler. PQCC would produce full, optimizing programming language compilers from descriptions of the programming language and the target machine. Though the goal of a fully automatic process was not realized, PQCC technology and ideas were the basis of production compilers from Inter metrics, Tartan Laboratories, and others. The focus of the project was on the semantics and machine-dependent phases of compilation, since lexical and syntactic analysis was already well-understood. Each phase was formalized in a manner that permits expression in table-driven form. The automatic construction of the compiler then consists of deriving these tables from the semantic definitions of the language and target machine. Though this approach was largely successful for target machine description, it was less so for semantics. ▪ Visual Lang Lab, a visual parser generator for JVM languages. Visual Lang Lab (Visual Language Laboratory) is a completely visual, open source parser generator for JVM (Java Virtual Machine) languages. Visual Lang Lab allows users to create, edit and test graphical grammar-trees that represent grammar rules, without any textual (BNF, EBNF, ABNF, etc.) grammar specification. Visual Lang Lab was The Java Posse's Project of the Week for episode 364. A Quick Tour and Rapid Prototyping for Scale are tutorials that use examples from other sources. An introductory article, Grammar without Tears is available online. Visual Lang Lab provides a graphical user interface (GUI) This interactive IDE (Integrated Development Environment)-style interface differentiates it from other parser generators. The grammar-trees are executable, and can be test-run at the click of a GUI button. Parsers can be created and tested entirely within the user interface without additional tools or skills. Because of its ease of use, Visual Lang Lab is an effective prototype and training environment. It also allows the use of semantic actions (written as Scala or JavaScript functions) embedded within the grammar where needed. A comment on lambda-the-ultimate in October 2004 describes Visual Lang Lab as a YACC with a GUI. Most other parser generators for Java (e.g. Java CC, ANTLR) use a textual grammar specification in Extended Backus-Naur Form (EBNF) or Parsing expression grammar (PEG). However, unlike them, the Visual Lang Lab instead creates a visual grammar of the language, using its GUI. Visual Lang Lab's grammar-trees are equivalent to PEGs; they support sequences, ordered choices, multiplicities (*, +, ?), as well as syntactic and semantic predicates. These grammar-trees are turned directly into instances of Scala's Parser type at run-time. The grammar-trees and other GUI features are intuitive, and the user does not have to understand PEGs or Scala programming, but familiarity with Scala's standard data types is useful in understanding the abstract syntax tree (AST). ▪ YACC The computer program YACC is a parser generator developed by Stephen C. Johnson at AT&T Corporation for the UNIX operating system in 1970. The name is an acronym for "Yet Another Compiler Compiler." It generates a parser (the part of a compiler that tries to make syntactic sense of the source code) based on an analytic grammar written in a notation similar to BNF. YACC used to be available as the default parser generator on most UNIX systems. It has since been supplanted as the default by more recent, largely compatible, programs such as Berkeley YACC, GNU bison, MKS YACC and Abraxas PCYACC. An updated version of the original AT&T version is included as part of Sun's Open Solaris project. Each offers slight improvements and additional features over the original YACC, but the concept has remained the same. YACC has also been rewritten for other languages, including Rat for, ML, Ada, Pascal, Java, Python, Ruby and Common Lisp. The parser generated by YACC is a LALR parser. In order to run it requires an external lexical analyzer. Lexical analyzer generators, such as Lex or Flex are widely available. The IEEE POSIX P1003.2 standard defines the functionality and requirements for both Lex and YACC. Some versions of AT&T YACC have become open source. For example, source code (for different implementations) is available with the standard distributions of Plan 9 and Open Solaris.

References

• Stephen C. Johnson. YACC: Yet Another Compiler-Compiler. Unix Programmer's Manual Vol 2b, 1979.

• http://vll.java.net/TheGUI.html

• http://www.scala-lang.org/api/current/scala/util/parsing/combinator/RegexParsers.html

• http://www.antlr.org/pipermail/antlr-interest/2004-February/006340.html

• http://www.gnu.org/software/bison/manual/html_node/Pure-Calling.html

• http://www.hwaci.com/sw/lemon/