Parsers

2026-11-18

notes / Compilers

Slides

Top Down Parsing

Eliminating Left Recursion

replace

E : E + T | T

with

E  : TE'
E' : +TE' | eps

Left Factoring

replace

S  : if (expr) S else S
   | if (expr) S
   | other

with (take common part out)

S  : if (expr) S S'
   | other
S' : else S 
   | eps

Recursive Descent

import re

def tokenize(expression):
    """
    look for numbers or brackets or operators
    """
    token_pattern = r"(\d+|[()\^+\-*/])"
    tokens = re.findall(token_pattern, expression)
    return tokens

# parse functions for each non terminal
def parse_factor(tokens):
    """
    F -> (E) | number
    """
    token = tokens.pop(0)
    if token == "(":
        result = parse_expression(tokens)
        # HACK: prolly should check below statement
        tokens.pop(0) # get rid of )
        return result
    else:
        return float(token)

def parse_exponent(tokens):
    """
    X -> F ^ X | F
    """
    left = parse_factor(tokens)
    while tokens and tokens[0] == "^":
        op = tokens.pop(0)
        right = parse_exponent(tokens)
        if op == "^":
            left **= right
    return left

def parse_term(tokens):
    """
    T -> X*T | X/T | X
    """
    left = parse_exponent(tokens)
    while tokens and tokens[0] in "*/":
        op = tokens.pop(0)
        right = parse_exponent(tokens)
        # NOTE: backtracking happening here
        # to eliminate start predicting shit (LL(1))
        if op == "*":
            left *= right
        else:
            left /= right
    return left

def parse_expression(tokens):
    """
    E -> T + E | T - E | T
    """
    left = parse_term(tokens)
    while tokens and tokens[0] in "+-":
        op = tokens.pop(0)
        right = parse_term(tokens)
        if op == "+":
            left += right
        else: 
            left -= right
    return left

def evaluate_expression(expression):
    tokens = tokenize(expression)
    result = parse_expression(tokens)
    return result

expr = "init"
while expr:
    try:
        print("parser: ", end='')
        expr = input()
        print(evaluate_expression(expr))
    except EOFError:
        print()
        print("parser: exiting")
        break

First and Follow sets

First :

"""
A := BC
"""
if eps not in first(B):
    first(A) = first(B) 
else if eps in first(B):
    first(A) = (first(B) - {eps}) U (first(C))

Follow:

"""
A := BC
"""
follow(C) = follow(A)
if eps not in follow(C):
    follow(B) = first(C) 
else if eps in follow(C):
    follow(B) = (first(C) - {eps}) U (follow(A))

LL(1) Grammars

for each production "A -> a":
    for each terminal "a" in first("A"):
        M["A"]["a"] = "A -> a"
    if eps in first("A"):
        for each "b" in follow("A"):
            M["A"]["b"] = "A -> eps"

example 1

S : +SS
  | *SS
  | a

FIRST(S)={+,*,a}

FOLLOW(S)={+,*,a,$}

Non terminal a + * $
S S -> a S -> +SS S -> *SS

example 2

S : (S)S
  | eps

FIRST(S)={(,ε}

FOLLOW(S)={),$}

( ) $
S S -> (S)S S -> ε S -> ε

Bottom Up Parsing

Shift-Reduce Method

stack input action
$ a * a $ shift
$ a * a $ reduce F -> a
$ F * a $ reduce T -> F
$ T * a $ shift
$ T * a $ shift
$ T * a $ reduce F -> a
$ T * F $ reduce T -> T * F
$ T $ reduce E -> T
$ E $ accept

Caution

not good with ambiguous grammars

LR Parsers (LR(0))

LR(0) parsers

LR(0) parsers don't lookahead, so you reduce on every input token for a state

Simple LR Parsers

Now you are looking ahead one token. So you will only reduce when you encounter symbols in the follow set of the required non-terminal, instead of filling up every cell.

CLR Parsers

Example of LR(1) parser. So you make LR(1) automaton which includes a lookahead token derived from the first/follow sets

similar to SLR parser but a bit more specific. Also takes a lot more memory and everyone hates it

LALR Parsers

its preferred over SLR just because of this lol

linked from