# C Abstract Syntax Tree

The unit at [comp/c/ast.fs] builds expressions ASTs out of tokenized
[comp/c/tok] C source. ASTs are mostly for expressions, but also sometimes only
for symbols or literals, which is why we make a distinction between "ast<" and
"exprast<". See below.

An AST is made out of [mem/cons] representing operators in relation to operands.
An operator is a numerical ID that is an index in the operator list. An
operators always know how to read its operands, so we never have to second-guess
the AST structure through "iscons?". When we pass AST pointers around, we always
pass a pointer to a cons where "car" is an operator ID.

Operators aren't just binary and unary operators. It's also special operators
like funcall (a function call), lit (literal number) and sym (symbol). Those
names refer to operator IDs.

The value of "cdr" depends on the operator, but the general principle is that
it's cons all the way down to lit or sym. The cdr of a lit is the literal number
itself. The cdr of a sym is a string with the symbol name.

Unary operators's cdr are a cons of another operator. Binary operators' cdr are
a pair of operators.

funcall's cdr is list with the first element is an operator (most of the time a
sym, but can also be an expression). Then follows a list of operators until 0 is
met, which marks the end of arguments.

Examples:

  a + b * c   --> (+ ((sym a) (* ((sym b) (sym c)))))
  foo(a, b+42) --> (funcall ((sym foo), (sym a), (+ ((sym b) (lit 42)))))

## Operators

Operators are indexes from the small list of operators. If you look in the
source code, you'll see a stringlist that determines its IDs. Some operators
such as function calls aren't detected through simple exact match, so they have
constants (in this case, funcall) associated with their ID.

Some operator symbols are ambiguous. In those cases, the symbol is associated
with one of the forms and the other form is given a constant:

-   --> binop    prefix: neg
++  --> prefix   postfix: postinc
--  --> prefix   postfix: postdec
*   --> binop    prefix: deref
&   --> binop    prefix: ref

### The comma situation

In terms of the C specification, "," is an operator. This unit exposes "," as
a regular binary operator.

Parsing-wise, however, it poses a problem because of ambiguity in many contexts,
that is:

* Function calls
* Declaration lists
* Array literals
* Enum declarations

This is why there's a distinction between "ast<", which doesn't parse the ","
and "exprast<" which does.

## Almost pure AST

One of the driving principles behind this unit is that the AST is oblivious to
actual types or symbols. When we refer to symbols in the AST, they're only
symbols in the sense that their place in the parsed syntax fits the role of
symbol. Otherwise, they're just identifiers to be plugged later at generation
time.

### .. but those pesky typecasts!

**HOWEVER**, typecasts are a mess. Some situations are ambiguous, for example:

  (uint)*p++;

If you don't know that "uint" is a type, this could very well be this AST:

  (* (sym uint) (deref (postinc (sym p))))

when we know very well that it's actually:

  (typecast uint 0 (deref (postinc (sym p))))

Multiply (deref) and subtract (neg) are the only cases where there's this
unsolvable ambiguity. In these very cases, we perform a type lookup (of "uint"
in the case above). If the type is found, it's a typecast. Otherwise, it's a
multiply/subtract.

### ... which leads us to sizeof

We can theoretically defer sizeof all the way up to the "expr" layer, but it's
overall simpler to take a bit of the weight right here, at the cost of having
the AST layer to type lookups. But since we're already doing it for typecasts,
we allow ourselves to do it for sizeof().

So, the rule is: if the first token in the sizeof() is an identifier, perform
a type lookup on it. If a type is found, we're in "type size" mode. We parse
trailing "*" characters, if any, then yield a "lit" AST element corresponding
to the size.

Otherwise, it's a "symbol sizeof()". We parse the interior of the parens and
yield "sizeof" AST element with the resulting AST in it, letting the "expr"
layer sort it out.

## Example usage

  needs comp/c/ast
  cctok$
  ast< a*(b+c(42)); read; .ast
  \ prints: (* (sym a) (+ (sym b) (funcall (sym c) (lit 0000002a))))

## API

ast< ( -- ast )
  Using comp/c/tok, parse one ident-or-lit-or-expr from the input stream,
  yielding the result as an AST structure as described above.

  Unlike "exprast<" below, this word doesn't parse the ",".

exprast< ( -- ast )
  Like "ast<", but also consider "," as an operator. See "The comma situation"
  above.

.ast ( ast -- )
  Print AST in a human-readable form.
