A LR parser implementation in Nim.

LR parsers (https://en.wikipedia.org/wiki/LR_parser) are a way to convert format grammars (sets of rules) into a program that can convert some text into a structured tree structure.

They can be used to parse expressions such as: x+x*x+x into (x+(x*x))+x.

More complex grammar allow to parse source code to create programming languages.

To parse a string, you need to first split it into tokens as the parser only accepts seqs of Tokens (a token is a wrapper around a string, that provides information about the position of the token for error reporting)

To do this, you can write your own tokenizer (for example, input.split(" ").mapIt(Token(content: it)) can be a simple tokenizer), or you can use the tokenize function that provides basic tokenizing abilities and outputs tokens instead of strings.

Example:

import tables, strutils

let input_string = """
        4 * 41 + 3 * (7 + 2)
    """
# The ruleset
let grammar = @[
    ("E", @["E", "+", "T"]),
    ("E", @["T"]),
    ("T", @["T", "*", "F"]),
    ("T", @["F"]),
    ("F", @["(", "E", ")"]),
    ("F", @["LIT"]),
]

# We need to convert the strings to ids so that the parser understands them
let tokenIdTable = makeTokenIdTable(grammar) # returns a Table[string, int]
let int_grammar = convertGrammar(grammar, tokenIdTable)

proc labeler(s: string): int =
    # Function that will detect the types of the tokens
    if s[0] == '*': return tokenIdTable["*"]
    if s[0] == '+': return tokenIdTable["+"]
    if s[0] == '(': return tokenIdTable["("]
    if s[0] == ')': return tokenIdTable[")"]
    return tokenIdTable["LIT"]

# Build the grammar to use it.
# This might take time so consider doing this at compile time for maximum performance.
let full_grammar = constructGrammar(int_grammar)

# We convert the string into "tokens" (i.e a seq of strings with some metadata)
let tokens = tokenize(input_string, @["*", "+", "(", ")"], @[" ", "\t",
        "\n"], labeler)

# We parse the string
let ast = parse(tokens, full_grammar)

# We evaluate the tree
proc eval(t: TokenTreeRef): int =
    if t.content != "":
        let r = parseInt(t.content)
        return r

    if t.children.len == 3:
        # id is the type of the token.
        if t.id == tokenIdTable["E"]:
            return eval(t.children[0]) + eval(t.children[2])
        if t.id == tokenIdTable["T"]:
            return eval(t.children[0]) * eval(t.children[2])
        if t.id == tokenIdTable["F"]:
            return eval(t.children[1])

    return eval(t.children[0])

let r = eval(ast)
echo input_string.strip, " = ", r

Types

TokenTreeRef = ref Token
Token = object children*: seq[TokenTreeRef] content*: string id*: int charcount*: int line*: int col*: int: Represents a piece of string. Might be inside an AST. When in an AST, the children tokens are in children. (col,line) are the position of the token in the original string/file. charcount is the position in the string in bytes. id is the type of the token given by the TokenLabeler
TokenLabeler = proc (s: string): int
Grammar = object table: seq[Table[int, (StateTypes, int)]] grammar: seq[(int, seq[int])]: Internal representation of the set of rules provided

Procs

proc `$`(ttr: TokenTreeRef): string {...}{.raises: [ValueError], tags: [].}
proc tokenize(s: string; tokenBreakersThatAreTokens: seq[string]; tokenBreakers: seq[string]; tl: TokenLabeler): seq[Token] {...}{. raises: [], tags: [].}: Split the string s along the tokenBreakers and returns it as a list of tokens
proc constructGrammar(grammar: seq[(int, seq[int])]): Grammar {...}{. raises: [KeyError], tags: [].}: Build a parsing table from a given grammar. Be careful, the size of the grammar is
proc parseAll(input_string: seq[Token]; g: Grammar; debugTable: Table[int, string]): seq[TokenTreeRef] {...}{. raises: [ValueError, KeyError], tags: [].}
proc parse(input_string: seq[Token]; g: Grammar): TokenTreeRef {...}{. raises: [ValueError, KeyError], tags: [].}: Perform the parsing of a sequence of tokens. Returns a tree made of tokens, that follows the set of rules described in the grammar g provided. In case of syntax errors, print the location of the error and return a partially parsed tree. Use parseAll if you need better error management
proc convertGrammar[T: enum](g: seq[(T, seq[T])]): seq[(int, seq[int])]
proc makeTokenIdTable[T](g: seq[(T, seq[T])]): Table[T, int]
proc convertGrammar[T](g: seq[(T, seq[T])]; tab: Table[T, int]): seq[ (int, seq[int])]

lrparser

Types

Procs