Compiler-compiler: Difference between revisions

Content deleted Content added

Inline

Revision as of 21:30, 14 February 2018

In computer science, a compiler-compiler or compiler generator is a programming tool that creates a parser, interpreter, or compiler from some form of formal description of a language and machine. The input may be a text file containing the grammar written in BNF or EBNF that defines the syntax of a programming language, and whose generated output is some source code of the parser for the programming language, although other definitions exist.^[1]

Usually, the resulting source code will have to be extended upon before a complete compiler emerges.

Variants

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 itself and other languages.

Some experimental compiler-compilers take as input a formal description of programming language semantics, typically using denotational semantics. This approach is often called 'semantics-based compiling', and was pioneered by Peter Mosses' Semantic Implementation System (SIS) in 1978.^[2] 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 (see JBurg) 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).

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 Autocode compiler. However it was rather different from modern compiler-compilers, and today would probably be described as being somewhere between a highly customisable 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.^{[citation needed]}

Other examples of parser generators in the yacc vein are ANTLR, Coco/R, CUP,^{[citation needed]} GNU bison, Eli,^[3] FSL,^{[citation needed]} SableCC, SID (Syntax Improving Device),^[4] and JavaCC. While useful, pure parser generators only address the parsing part of the problem of building a compiler. Tools with broader scope, such as PQCC, Coco/R and DMS Software Reengineering Toolkit provide considerable support for more difficult post-parsing activities such as semantic analysis, code optimization and generation.

Several compiler-compilers

ANTLR
Bison
Coco/R
Coco-2
DMS Software Reengineering Toolkit, a program transformation system with parser generators.
Lemon
META II
parboiled, a Java library for building parsers.
Packrat parser
PackCC, a packrat parser with left recursion support.
PQCC, a compiler-compiler that is more than a parser generator.
Syntax Improving Device (SID)
SYNTAX, an integrated toolset for compiler construction.
TREEMETA
Yacc
Xtext
XPL
JavaCC

Notes

^ "A SYNTAX DIRECTED COMPILER FOR ALGOL 60" Edgar T. Irons, Communications of the ACM Volume 4 Issue 1, Jan. 1961."
^ Peter Mosses, "SIS: A Compiler-Generator System Using Denotational Semantics," Report 78-4-3, Dept. of Computer Science, University of Aarhus, Denmark, June 1978
^ Robert W. Gray et al., "Eli: A complete, flexible compiler construction system." Communications of the ACM 35:2:121-130, 1992; see also http://eli.colorado.edu/
^ J.M. Foster, "A syntax improving program." The Computer Journal 11:1:31-34, 1968

References

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.

External links

Computer50.org, Brooker Autocodes
Catalog.compilertools.net, The Catalog of Compiler Construction Tools
Labraj.uni-mb.si, Lisa
Skenz.it, Jflex and Cup resources Template:It icon

[name-1] "A SYNTAX DIRECTED COMPILER FOR ALGOL 60" Edgar T. Irons, Communications of the ACM Volume 4 Issue 1, Jan. 1961."

[2] Peter Mosses, "SIS: A Compiler-Generator System Using Denotational Semantics," Report 78-4-3, Dept. of Computer Science, University of Aarhus, Denmark, June 1978

[3] Robert W. Gray et al., "Eli: A complete, flexible compiler construction system." Communications of the ACM 35:2:121-130, 1992; see also http://eli.colorado.edu/

[4] J.M. Foster, "A syntax improving program." The Computer Journal 11:1:31-34, 1968

[1]

[2]

[3]

[4]

@@ Line 21: / Line 21: @@
 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 (Manchester)|Atlas]] computer at the [[University of Manchester]], including the [[Atlas Autocode]] compiler.  However it was rather different from modern compiler-compilers, and today would probably be described as being somewhere between a highly customisable generic compiler and an [[Extensible programming|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.{{Citation needed|date=February 2007}}
-Other examples of parser generators in the yacc vein are [[ANTLR]], [[Coco/R]], CUP,{{Citation needed|date=March 2012}} [[GNU bison]], Eli,<ref>Robert W. Gray ''et al.'', "Eli: A complete, flexible compiler construction system." ''Communications of the ACM'' '''35''':2:121-130, 1992; see also http://eli.colorado.edu/</ref> FSL,{{Citation needed|date=March 2012}} [[SableCC]], SID (Syntax Improving Device),<ref>J.M. Foster, "A syntax improving program." ''The Computer Journal'' '''11''':1:31-34, 1968</ref> and [[JavaCC]].  While useful, pure parser generators only address the parsing part of the  problem of building a compiler.  Tools with broader scope, such as [[PQCC]], [[Coco/R]] and [[DMS Software Reengineering Toolkit]] provide considerable support for more difficult  post-parsing activities such as semantic analysis, code optimization and generation.
+Other examples of parser generators in the yacc vein are [[ANTLR]], [[Coco/R]], CUP,{{Citation needed|date=March 2012}} [[GNU bison]], Eli,<ref>Robert W. Gray ''et al.'', "Eli: A complete, flexible compiler construction system." ''Communications of the ACM'' '''35''':2:121-130, 1992; see also http://eli.colorado.edu/</ref> FSL,{{Citation needed|date=March 2012}} [[SableCC]], SID (Syntax Improving Device),<ref>J.M. Foster, "[https://academic.oup.com/comjnl/article-pdf/11/1/31/1172766/110031.pdf A syntax improving program]." ''The Computer Journal'' '''11''':1:31-34, 1968</ref> and [[JavaCC]].  While useful, pure parser generators only address the parsing part of the  problem of building a compiler.  Tools with broader scope, such as [[PQCC]], [[Coco/R]] and [[DMS Software Reengineering Toolkit]] provide considerable support for more difficult  post-parsing activities such as semantic analysis, code optimization and generation.
 == Several compiler-compilers ==

v t e Parsing algorithms
Top-down	Earley LL Recursive descent Tail recursive
Bottom-up	Precedence Simple Operator Shunting-yard LR Simple Look-ahead Canonical Generalized CYK Recursive ascent Shift-reduce
Mixed, other	Combinator Chart Left corner Statistical
Related topics	PEG Definite clause grammar Deterministic parsing Dynamic programming Memoization Parser generator LALR Parse tree AST Scannerless parsing History of compiler construction Comparison of parser generators Operator-precedence grammar