Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Syntax Tree Generation in Clojure

I'm writing a compiler, really for educational purposes. I have generated tokens from my input and want to generate an AST. I have a function that takes the list of tokens and recurses to generate the ast. In most parsers you'd have a pointer to the lexer so every time you process tokens in the tree you'd advance the lexer. I dont know how to advance the lexer when you hit a part that needs to generate deeper nodes in the tree since you can't modify the structure of the lexer list.

As an example with a clojure program like this (+ 1 2 (+ 1 1)). It would advance to the + and then recurse and generate the node properly, but the lexer reprocesses the + 1 1 after it returns from generating the node, so you end up with a tree like this:

Root
---> +
---> 1
---> 2
-----> +
-----> 1
-----> 1
---> +
---> 1
---> 1
like image 435
Justin Thomas Avatar asked Oct 22 '22 11:10

Justin Thomas


1 Answers

In Lisp/Clojure you program directly to the abstract syntax tree expressed via Lisp data structures. Moreover, you can programmatically act on those Lisp data structures leading to macros. So, in conclusion you already have your AST.

like image 139
Julien Chastang Avatar answered Oct 26 '22 12:10

Julien Chastang