gocc

README

The toy compiler for Go

• It's based on rui314's chibicc and https://www.sigbus.info/compilerbook .
• This is for my own learning.

EBNF

Production  = name "=" [ Expression ] "." .
Expression  = Alternative { "|" Alternative } .
Alternative = Term { Term } .
Term        = name | token [ "…" token ] | Group | Option | Repetition .
Group       = "(" Expression ")" .
Option      = "[" Expression "]" .
Repetition  = "{" Expression "}" .

From : golang.org/x/exp

Documentation

Overview

code generator

parser

This file contains a recursive descent parser for Go(or Go-like language).

Most functions in this file are named after the symbols they are supposed to read from an input token list. For example, stmt() is responsible for reading a statement from a token list. The function then construct an AST node representing a statement.

Each function conceptually returns two values, an AST node and remaining part of the input tokens. The remaining tokens are returned the caller via a pointer argument. Because I imitate the structure of chibicc(https://github.com/rui314/chibicc).

Input tokens are represented by a linked list. Unlike many recursive descent parsers, we don't have the notion of the "input token stream". Most parsing functions don't change the global state of the parser. So it is very easy to lookahead arbitrary number of tokens in this parser.

This file implements the preprocessor.

The preprocessor tekes a list of tokens as an input and returns a new list of tokens as an output.

The preprocessing language is designed in such a way that that's guaranteed to stop even if there is a recursive macro. Informally speaking, a macro is applied only once for each token. That is, if a macro token T appears in a result of direct or indirect macro expansion of T, T won't be expanded any further. For example, if T is defined as U, and U is defined as T, then token T is expanded to U and then to T and the macro expansion stops at that point.

To archive the above behavior, we attach for each token a set of macro names from which the token is expanded. The set is called "hideset". Hideset is initially empty, and every time we expanded a macro, the macro name is added to the resulting tokens' hidesets.

The above macro expansion algorithm is explained in this document written by Dave Prossor, which is used as a basis for the standard's wording: https://github.com/rui314/chibicc/wiki/cpp.algo.pdf

tokenizier

Typing AST nodes