Compiler

A compiler takes in programs of a language, produces programs of a language.

If we think deeper, what are required of such a function?

A mapping! Different parts of the program should map to the output.

To get this different parts we use lexical analysis which gives us our syntactic tokens, e.g. if, else, let.

Then we use parsing to create an intermediate representation which has an interface we can work with.

We then have semantic analysis to understand the semantics of our source program, and finally use code generation to output program in target language.

Phases

Common tools used

  • yacc, bison, (f)lex Not modern but stable. No inbuilt support for unicode.

  • ANTLR Modern

  • Definite clause grammars https://www.metalevel.at/prolog/dcg https://github.com/indocomsoft/aoc2020/blob/main/16/ans.pl http://csci431.artifice.cc/notes/prolog-parsing.html

  • Parser combinators Combining various parsers.

See also

What is Flex?