Pratt parser (recursive decent parser)

A pratt parser consists of 2 components (lexer, parser) that compliment each other. The lexer reads in a file (usually containing code) and turns it into tokens (similar but different from LLM's) according to syntax rules.

An example that most people should know is a math sum: \( 3∗(5+9)^2 \)

the tokenizer reads over it character by character, and makes a list of tokens with info about it using the following syntax rules:

E –> E + T | T  
T –> T * F | F  
F –> ( E ) | id

The lexer will turn the above sum into the following with the format "<value>" (<type> [<lineNr>:<columnNr>])

"3" (ATOM [1:1])
"*" (OPERATOR [1:2])
"(" (OPERATOR [1:3])
"5" (ATOM [1:4])
"+" (OPERATOR [1:5])
"9" (ATOM [1:6])
")" (OPERATOR [1:7])
"^" (OPERATOR [1:8])
"2" (ATOM [1:9])

An atom in this case stores a value whereas an operator (as the name implies) operates on its values. The tokens are stored as a list and passed to the parser.

The goal of the parser is to make an AST (Abstract Syntax Tree) from the tokens. To parse the tokens from the lexer it looks at the information of the current and next token to determine what type of node will be made. When looking at the math rules it can be represented in 2 token types: Atom and Operator.
Atom representing a number (or a value), and Operator being an operation that needs to be preformed on 2 atom's. to get the desired behavior the parser has to call itself recursively to solve inner parts of expressions that get added to the AST.

The above token-list turns into the following AST:

graph
  a(3)
  op1{{"✖"}}
  b(5)
  op2{{"➕"}}
  c(9)
  op3{{"^"}}
  d(2)

  op1 --- a
  op1 --- op3
  op3 --- op2
  op3 --- d
  op2 --- b
  op2 --- c

To get the solution of the sum we just have to walk the AST and resolve the operations:

1. 3 * result_of_^
2. result_of_^ = result_of_+ ^ 2
3. result_of_+ = node_left + node_right

These same steps are used to write a parser as part of a compiler (using simplified javascript as an example)

let sum = function(a, b) {
  return a + b;
}

graph LR
  %%{ init: { 'flowchart': { 'curve': 'linear' } } }%%
  o4{{=}}
  n4(sum)
  f1(function)
  n5(a)
  n6(b)
  s1(return)
  o5{{➕}}
  n7(a)
  n8(b)

  o4 --L--- n4
  o4 --R--- f1
  f1 --L--- n5 --- n6
  f1 --R--- s1
  s1 --- o5
  o5 --L--- n7
  o5 --R--- n8