Lisparser

Lisparser is another parser invented by User:Hakerh400 (the previous one was Elevated Parser). Lisparser uses a Lisp-like syntax to parse a Lisp-like source code. This parser does not have an intermediate state. It does not construct abstract syntax tree initially (if we do not count pure lists as tree nodes). Instead, it starts to interpret the program while the program is still being parsed. It saves a lot of time and speeds up the computation.

Overview

The source code of a program that can be parsed using Lisparser consists of elements. Each element is either a list or an identifier. A list contains zero or more elements. An identifier can contain any character except whitespace and parentheses.

Example of a program's source code:

(program
  (var x 5)
  (var y 7)
  (var z (+ x y))
  (print z)
)

Lisparser can be used to write a simple parser to parse and execute this program (parsing and executing happens at the same time in Lisparser).

Commands

Lisparser has the following commands:

• (s x) - Checks whether element x is a scalar (an identifier)
• (v x) - Checks whether element x is a vector (a list)
• (ident x) - Asserts that element x is an identifier
• (ident x y) - Asserts that element x is an identifier whose string representation is y
• (list x) - Asserts that element x is a list
• (uni x) - Asserts that x has exactly one element and returns that element
• (n x) - Asserts that x is a list and returns its length
• (m x) - Asserts that x is an ident and returns its name as a string
• (is-nat x) - Checks whether x is an identifier representing a natural number (but asserts that x is an identifier)
• (is-int x) - Checks whether x is an identifier representing an integer (but asserts that x is an identifier)
• (get-nat x) - Asserts that x is an identifier representing a natural number and returns its value as a bigint
• (get-int x) - Asserts that x is an identifier representing an integer and returns its value as a bigint
• (len x y z) - Asserts that x is a list whose length $n$ satisfies $y\leq n\leq z$
• (lenp x y) - Asserts that x is a list whose length $n$ satisfies $y\leq n$
• (lenm x y) - Asserts that x is a list whose length $n$ satisfies $n\leq y$
• (e x i) - Asserts that x is a list with at least $i+1$ elements and return $i$-th element (0-indexed)
• (a x i f) - Asserts that x is a list with at least $i$ elements and return its elements as an array starting from index $i$ with unary function f applied to each element
• (ta x t f) - Asserts that x is a list with at least 1 element and that the first element is an identifier whose string representation is t, and return its elements as an array starting from index 1 with unary function f applied to each element
• (empty x) - Checks whether x is an empty list (but asserts that x is a list)
• (type x t) - Asserts that x is a list with at least 1 element and that the first element is an identifier whose string representation is t
• (fst x) - Same as (e x 0)
• (snd x) - Same as (e x 1)
• (last x) - Same as (e x (- (n x) 1)) - this is basically the last element of x
• (elems x) - Same (a x 0 (lambda (x) x)) - this simply returns all the elements of x (which is implicitly asserted to be a list)
• (ch-num x) - For an ident returns 0, for a list returns the number of elements
• (get-ch x i) - Similar to (e x i), but can be used only in recursive iterations (not very important to explain that)
• (top-down x f) - Iterate x as a tree using a top-down iterator calling f for each element
• (bottom-up x f) - Iterate x as a tree using a bottom-up iterator calling f for each element
• (iter x f) - Iterate x using a top-down and then bottom-up iterator calling f for each element and passing an extra argument that is 0 for top-down and 1 for bottom-up
• (cont) - Skip a branch in the iteration process
• (break) - Skip the entire sub-tree in the iteration process
• (to-str x) - Returns a stringified representation of x
• (spacing-type x s) - For list x sets the spacing type to s (used when calling to-str)
• (spacing-start x i) - For list x sets the spacing start to index $i$ (used when calling to-str) - basically all whitespace between elements before index $i$ are space characters, while s is used starting from $i$

Exceptions

• (err x msg) - Throws an error with message msg with all relevant information (source file path, line, stack trace and the message)
• (warn x msg) - Same as err, but shows a warning instead of throwing an error.

Integration with Node.js

The parser is written in Node.js and implements all commands as JavaScript methods. It uses generator functions trick to allow unlimited recursion depth. For example, you can recursively traverse a list containing hundreds of millions of nested lists without triggering a stack overflow.

Examples

Brainlisp is an example of a program that uses Lisparser. See the Brainlisp interpreter.

Interpreters

These interpreters use the parser.