Compiler-compiler: Difference between revisions

Revision as of 20:51, 14 November 2023

Revision as of 18:46, 23 November 2023

Line 4:

{{Use dmy dates|date=January 2020|cs1-dates=y}}

In [[computer science]], a '''compiler-compiler''' or '''compiler generator''' is a programming tool that creates a [[parsing|parser]], [[interpreter (computer software)|interpreter]], or [[compiler]] from some form of formal description of a [[programming language]] and machine. The most common type of compiler-compiler is called a '''parser generator'''<ref>{{cite book |url=https://www.worldcat.org/oclc/70775643 |title=Compilers : principles, techniques, & tools |date=2007 |others=Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Alfred V. Aho |isbn=978-0-321-48681-3 |edition=Second |___location=Boston |page=287 |oclc=70775643}}</ref> which handles only syntactic analysis.

The most common type of compiler-compiler is called a '''parser generator'''.<ref>{{cite book |url=https://www.worldcat.org/oclc/70775643 |title=Compilers : principles, techniques, & tools |date=2007 |others=Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Alfred V. Aho |isbn=978-0-321-48681-3 |edition=Second |___location=Boston |page=287 |oclc=70775643}}</ref> It handles only syntactic analysis.

A [[formal grammar|grammar]] file is supplied as the input for a parser generator. This is typically written in [[Backus–Naur form]] (BNF) or [[extended Backus–Naur form]] (EBNF) and defines the [[Syntax (programming languages)|syntax]] of a target programming language.

[[Source code]] for a parser of the programming language is returned as the parser generator's output. This source code can then be compiled into a parser, which may be either standalone or embedded. The compiled parser then accepts the source code of the target programming language as an input and performs an action or outputs an [[abstract syntax tree]] (AST).

Parser generators do not handle the [[Semantics (computer science)|semantics]] of the AST, or the [[Code generation (compiler)|generation of machine code]] for the target machine.<ref name="name">"A Syntax Directed Compiler for ALGOL 60" Edgar T. Irons, Communications of the ACM Volume 4 Issue 1, Jan. 1961.</ref>

A '''metacompiler''' is a software development tool used mainly in the construction of [[compiler]]s, [[Translator (computing)|translators]], and [[interpreter (computing)|interpreters]] for other programming languages.<ref name="McGraw"/> The input to a metacompiler is a [[computer program]] written in a [[Domain-specific language|specialized]] programming [[metalanguage]] designed mainly for the purpose of constructing compilers.<ref name="McGraw"/><ref name="CWIC" /> The language of the compiler produced is called the object language. The minimal input producing a compiler is a [[Metaprogramming|metaprogram]] specifying the object language grammar and [[Semantics (computer science)|semantic]] transformations into an [[object program]].<ref name="CWIC" /><ref name="TMETA" />

== 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 an analytical grammar with output facilities [[Code generation (compiler)|that produce stack machine]] code, and is able to compile its own source code and other languages.

Line 28 ⟶ 19:

Compiler-compilers exist in many flavors, including bottom-up rewrite machine generators (see [http://jburg.sourceforge.net/ 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).

=== Parser Generators ===

A [[formal grammar|grammar]] file is supplied as the input for a parser generator. This is typically written in [[Backus–Naur form]] (BNF) or [[extended Backus–Naur form]] (EBNF) and defines the [[Syntax (programming languages)|syntax]] of a target programming language. 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.

[[Source code]] for a parser of the programming language is returned as the parser generator's output. This source code can then be compiled into a parser, which may be either standalone or embedded. The compiled parser then accepts the source code of the target programming language as an input and performs an action or outputs an [[abstract syntax tree]] (AST).

Parser generators do not handle the [[Semantics (computer science)|semantics]] of the AST, or the [[Code generation (compiler)|generation of machine code]] for the target machine.<ref name="name">"A Syntax Directed Compiler for ALGOL 60" Edgar T. Irons, Communications of the ACM Volume 4 Issue 1, Jan. 1961.</ref>

===Metacompilers===