Sila Dev Log: Initial Recursive Descent Parsing

Posted on 24th of August 2023 | 1860 words

Plug: Follow the Sila development here.

For the initial implementation of Sila’s parses, I decided to go with the recursive descent route due to its simplicity. So what it is? Recursive descent parsing is a top-down parsing technique employed to analyze the syntax of structured input, such as programming languages or mathematical expressions. It operates by breaking down the input into smaller, manageable components using a set of recursive functions that correspond to the non-terminal symbols in the grammar.

Beginning with a starting symbol, typically representing the highest-level construct, these functions are invoked recursively to recognize and process the various syntactic elements of the input. Each function handles a specific grammar rule, and by calling each other based on the grammar’s structure, the parser traverses the input while building a parse tree that reflects the hierarchical organization of the language’s syntax.

This approach allows for clear code organization and error reporting, though it can face challenges with certain types of grammars and may require augmentation with techniques like lookahead or memoization for optimal efficiency and effectiveness. But for early stages of the project, I don’t really mind that.

Parser Implementation

First I create some structures and helpers that I will be using in the parsing process.

(deftype ast-node-kind ()
  "Sila AST node kind."
  '(member
    :add
    :sub
    :mul
    :div
    :number))

(defstruct ast-node
  "Structure for Sila AST nodes."
  kind
  val
  lhs
  rhs)

(defun skip-to-token (val tok)
  "Search for token which is `val'. Returns `nil' when not found.

TODO(topi): Probably should do some proper error handling if `val' isn't
found."
  (cond ((eq (token-kind tok) :eof) nil)
        ((equal (token-val tok) val) tok)
        (t (search-token val (token-next tok)))))

For now, I’m interested in parsing something simple like 2 / (1 + 1) * 8, so simple multiplicative calculations and expressions inside parenthesis. So if I would write some metanotation like BNF for that, it would look something like this:

expr ::== mul ( '+' mul | '-' mul ) *
mul ::== primary ( '*' primary | '/' primary ) *
primary ::== '(' expr ')' | number

`expr`

This function is responsible for parsing arithmetic expressions. It follows the grammar rule: expr ::= mul ( '+' mul | '-' mul ) *. It starts by calling the mul function to parse the initial term. Then, it enters a loop to handle addition and subtraction operators. If it encounters a +, it parses the next term using mul and creates an AST node representing addition. If it encounters a -, it does the same for subtraction.

The loop continues until it encounters an operator that’s not + or -, at which point it returns the parsed expression node and the remaining token stream.

(defun expr (tok)
  "expr ::== mul ( '+' mul | '-' mul ) *"
  (multiple-value-bind (node rest)
      (mul tok)
    (loop
      (cond ((eq (token-val rest) #\+)
             (multiple-value-bind (node2 rest2)
                 (mul (token-next rest))
               (setf node (make-ast-node :kind :add :lhs node :rhs node2))
               (setf rest rest2)))
            ((eq (token-val rest) #\-)
             (multiple-value-bind (node2 rest2)
                 (mul (token-next rest))
               (setf node (make-ast-node :kind :sub :lhs node :rhs node2))
               (setf rest rest2)))
            (t
             (return-from expr
               (values node rest)))))))

`mul`

Parsing mul expressions works in a similar fashion:

(defun mul (tok)
  "mul ::== primary ( '*' primary | '/' primary ) *"
  (multiple-value-bind (node rest)
      (primary tok)
    (loop
      (cond ((eq (token-val rest) #\*)
             (multiple-value-bind (node2 rest2)
                 (primary (token-next rest))
               (setf node (make-ast-node :kind :mul :lhs node :rhs node2))
               (setf rest rest2)))
            ((eq (token-val rest) #\/)
             (multiple-value-bind (node2 rest2)
                 (primary (token-next rest))
               (setf node (make-ast-node :kind :div :lhs node :rhs node2))
               (setf rest rest2)))
            (t
             (return-from mul
               (values node rest)))))))

`primary`

This function parses primary expressions, which can be either numeric values or sub-expressions enclosed in parentheses. It follows the grammar rule: primary ::= '(' expr ')' | number. If the current token is a number, it creates an AST node representing a numeric value. If the token is an opening parenthesis, it recursively calls the expr function to parse the enclosed expression and skips to the closing parenthesis. It then returns the parsed node and the remaining token stream.

(defun primary (tok)
  "primary ::== '(' expr ')' | number"
  (cond ((eq (token-kind tok) :num)
         (values (make-ast-node :kind :number :val (token-val tok))
                 (token-next tok)))
        ((eq (token-val tok) #\()
         (multiple-value-bind (node rest)
             (expr (token-next tok))
           (values node (token-next (skip-to-token #\) rest)))))
        (t (error 'parser-error))))

Testing the Initial Parser

For now, I will be testing this parser only from the REPL. Firing up it, and running the command should print something like this:

* (expr (tokenize "2 / (1 + 1) * 8"))
#S(AST-NODE
   :KIND :MUL
   :VAL NIL
   :LHS #S(AST-NODE
           :KIND :DIV
           :VAL NIL
           :LHS #S(AST-NODE :KIND :NUMBER :VAL 2 :LHS NIL :RHS NIL)
           :RHS #S(AST-NODE
                   :KIND :ADD
                   :VAL NIL
                   :LHS #S(AST-NODE :KIND :NUMBER :VAL 1 :LHS NIL :RHS NIL)
                   :RHS #S(AST-NODE :KIND :NUMBER :VAL 1 :LHS NIL :RHS NIL)))
   :RHS #S(AST-NODE :KIND :NUMBER :VAL 8 :LHS NIL :RHS NIL))
#S(SILA/LEXER::TOKEN :KIND :EOF :POS 15 :LEN NIL :VAL NIL :NEXT NIL)
*

Here we can see how our parser parses the expressions inside it. Transforming it to ASCII would look something like this:

     Mul(*)
    /     \
 Div(/)    8
 /   \
2   Add(+)
     /  \
    1    1

Code Generation

Assembly code of something like 2 / (1 + 1) * 8 is still quite simple, but definitely more instruction will be needed compared to the simple addition and subtraction. Assembly code for it would equal to:

	.globl main
main:
	mov $8, %rax
	push %rax
	mov $1, %rax
	push %rax
	mov $1, %rax
	pop %rdi
	add %rdi, %rax
	push %rax
	mov $2, %rax
	pop %rdi
	cqo
	idiv %rdi, %rax
	pop %rdi
	imul %rdi, %rax
	ret

So what is happening here:

Initializing and Pushing Values:
- mov $8, %rax: This instruction moves the immediate value 8 into the %rax register.
- push %rax: The value in %rax (which is now 8) is pushed onto the stack.
Further Operations:
- mov $1, %rax: Another immediate value, 1, is moved into the %rax register.
- push %rax: The value in %rax (now 1) is pushed onto the stack.
- mov $1, %rax: Yet another immediate value, 1, is moved into %rax.
- pop %rdi: The top value from the stack (1) is popped into the %rdi register.
- add %rdi, %rax: The value in %rdi (previously 1) is added to the value in %rax (also 1), and the result is stored in %rax.
More Operations:
- push %rax: The value in %rax (now 2) is pushed onto the stack.
- mov $2, %rax: The immediate value 2 is moved into %rax.
- pop %rdi: The top value from the stack (2) is popped into %rdi.
Division and Multiplication:
- cqo: This instruction extends the sign of %rax into %rdx in preparation for the division operation.
- idiv %rdi, %rax: The value in %rax (now 2) is divided by the value in %rdi (previously 1). The quotient is stored in %rax and the remainder in %rdx.
- pop %rdi: The value 2 is popped from the stack and stored in %rdi.
- imul %rdi, %rax: The value in %rax (the quotient of the division) is multiplied by the value in %rdi (previously 2), and the result is stored in %rax.

Implementation

For the code generation aspects, we can start by creating some unit tests since we already know what would be the output of our function:

(deftest test-emit-asm-div-mul-parens
  (let ((emit-asm-tests '(("2 / (1 + 1) * 8" . "  .globl main
main:
  mov $8, %rax
  push %rax
  mov $1, %rax
  push %rax
  mov $1, %rax
  pop %rdi
  add %rdi, %rax
  push %rax
  mov $2, %rax
  pop %rdi
  cqo
  idiv %rdi, %rax
  pop %rdi
  imul %rdi, %rax
  ret
"))))
    (dolist (test emit-asm-tests)
      (ok (string-equal (sila::emit-asm (car test)) (cdr test))
          (format nil "Expect to be equal: ~%~a~%=>~a"
                  `(sila::emit-asm ,(car test))
                  (cdr test))))))

The implementation aspects also will be relatively straight forward.

(defun asm-inst (inst)
  (format nil "  ~a~%" inst))

(defun asm-directive (dir)
  (asm-inst dir))

(defun asm-label (label)
  (format nil "~a:~%" label))

(defun asm-push ()
  (asm-inst "push %rax"))

(defun asm-pop (reg)
  (asm-inst (format nil "pop %~a" reg)))

(defun generate-expr (node)
  (let ((asm ""))
    (flet ((asm-conc (inst)
             (setf asm (concatenate 'string asm inst))))
      (when (eq (ast-node-kind node) :number)
        (asm-conc (asm-inst (format nil "mov $~d, %rax"
                                    (ast-node-val node))))
        (return-from generate-expr asm))
      (asm-conc (generate-expr (ast-node-rhs node)))
      (asm-conc (asm-push))
      (asm-conc (generate-expr (ast-node-lhs node)))
      (asm-conc (asm-pop "rdi"))
      (alexandria:switch ((ast-node-kind node) :test #'eq)
        (:add (asm-conc (asm-inst "add %rdi, %rax")))
        (:sub (asm-conc (asm-inst "sub %rdi, %rax")))
        (:mul (asm-conc (asm-inst "imul %rdi, %rax")))
        (:div (asm-conc (asm-inst "cqo"))
              (asm-conc (asm-inst "idiv %rdi, %rax")))
        (t (error 'parser-error))))
    asm))

This function recursively generates assembly code from an abstract syntax tree node representing an arithmetic expression. It constructs assembly instructions based on the kind of node encountered. It concatenates these instructions into a string that represents the generated assembly code.

For a number node, it generates a move instruction (mov) to load the value into %rax.
For binary operations (addition, subtraction, multiplication, division), it generates assembly for the right-hand side expression, pushes %rax onto the stack, generates assembly for the left-hand side expression, pops the value into %rdi, and then performs the corresponding operation.

Then lastly we just define the emit function, like so:

(defun emit-asm (src)
  "Emit assembly code from given source code. Currently emits only x86-64 and
only Linux is tested."
  (let ((asm ""))
    (flet ((asm-conc (inst)
             (setf asm (concatenate 'string asm inst))))
      (multiple-value-bind (node rest)
          (expr (tokenize src))
        (unless (eq (token-kind rest) :eof)
          (error 'parser-error :error-msg "Extra tokens"))
        (asm-conc (asm-directive ".globl main"))
        (asm-conc (asm-label "main"))
        (asm-conc (generate-expr node))
        (asm-conc (asm-inst "ret"))))
    asm))

Again, we can test it directly in the REPL first:

* (emit-asm "2 / (1 + 1) * 8")
"  .globl main
main:
  mov $8, %rax
  push %rax
  mov $1, %rax
  push %rax
  mov $1, %rax
  pop %rdi
  add %rdi, %rax
  push %rax
  mov $2, %rax
  pop %rdi
  cqo
  idiv %rdi, %rax
  pop %rdi
  imul %rdi, %rax
  ret
"

Seems to work. Now to run the tests:

# make test
rove sila.asd

Testing System sila/tests

;; testing 'sila/tests'
test-compilation-and-compare-rc
  ✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "0" 0) to be true. (2726ms)
  ✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "5 + 40 - 20" 25) to be true. (2693ms)
  ✓ Expect (COMPILE-PROGRAM-AND-COMPARE-RC "2 / (1 + 1) * 8" 8) to be true. (2703ms)
test-emit-asm-integer
  ✓ Expect to be equal:
    (EMIT-ASM 0)
    =>  .globl main
    main:
      mov $0, %rax
      ret

  ✓ Expect to be equal:
    (EMIT-ASM 42)
    =>  .globl main
    main:
      mov $42, %rax
      ret

test-emit-asm-add-sub
  ✓ Expect to be equal:
    (EMIT-ASM 5+20-4)
    =>  .globl main
    main:
      mov $4, %rax
      push %rax
      mov $20, %rax
      push %rax
      mov $5, %rax
      pop %rdi
      add %rdi, %rax
      pop %rdi
      sub %rdi, %rax
      ret

  ✓ Expect to be equal:
    (EMIT-ASM     5   +  20  -  4   )
    =>  .globl main
    main:
      mov $4, %rax
      push %rax
      mov $20, %rax
      push %rax
      mov $5, %rax
      pop %rdi
      add %rdi, %rax
      pop %rdi
      sub %rdi, %rax
      ret

test-emit-asm-div-mul-parens
  ✓ Expect to be equal:
    (EMIT-ASM 2 / (1 + 1) * 8)
    =>  .globl main
    main:
      mov $8, %rax
      push %rax
      mov $1, %rax
      push %rax
      mov $1, %rax
      pop %rdi
      add %rdi, %rax
      push %rax
      mov $2, %rax
      pop %rdi
      cqo
      idiv %rdi, %rax
      pop %rdi
      imul %rdi, %rax
      ret


✓ 1 test completed

Summary:
  All 1 test passed.

Cool, seems to work!

NB: If you want to read earlier posts of this dev log, head over here.