Nut parser explain

Here we are going to show a simple example how to write a Nut parser. Let's simplify it and do only parsing of an expression. An expression in Nut is:

1) applying function, it has the form: "(" operator arguments ... ")". The operator can be either builtin or defined. Builtin operators are simple arithmetic and logic operators such as + - * / and or not. A defined operator is a function definition, started with "def".
2) a numeric constant
3) a variable (either local or global)

let's tackle the first case, applying function. To parse (op arg...) we do the following. To start with we expect one token is already been read into a global variable "tok".

A general structure of a parser looks like this:

parse is
if tok is null then 0     ; stop parsing
<expect "(">
tok = read-a-token
; now we have read the operator, we know the number of its argument, called "arity"
; loop to read argument
   for i = 1 to arity
      tok = read-a-token
; do some action here to generate code here
<expect ")">

Action to generate an intermediate data structure

Parsing just checks if an input source is grammatically correct. To make use of it to generate some output we need to take some action during parsing. It is easier to think of generating a tree, called "parse tree" to be use later to generate machine codes.

To build a tree we use and operator "cons" that takes one atom and a list and outputs a new list containing that atom in front of the list. For example, let A, B, C be atoms.

(cons A (B C)) becomes (A B C)

The parse tree for (+ 2 3) is

+
/ \
2 3

or in terms of "cons": (cons '+ (cons 2 (cons 3 nil)))

consing 3 to nil becomes (3). This is to build up the fist node in the list. So we refine the parse function to generate this structure:

parseExp
if tok == "("
    read-a-token
    nm = parseName
    e = parseEL
    out (cons nm e)
if tok isNumber
    n = atoi token
    out lit.n
parseName ; else it is a name

parseName
output index to variable, handle left-hand side value (assignment)

parseEL
read-a-token
if tok == ")" return NIL
e = parseExp
e2 = parseEL
out (cons e e2)

26 June 2009