= Parsers
== automata

pushdown automaton := machine which maintains a stack and can only access the top element
stack automaton := machine which maintains a stack and can read any element of the stack

== parser classification

source: https://www.youtube.com/watch?v=OIKL6wFjFOo&list=PLBlnK6fEyqRgPLTKYaRhcMt8pVKl4crr6

Top-down parsers
  with backtracking
    brute forcing
  without backtracking [cannot deal with left recursion, thus determinism required]
    Recursive Descent Parsers
    Predictive Parsers
      LL(1)
      LL(k)
Bottom-up parsers
  Operator Precedence Parsers [the only one capable of handling ambiguity]
  LR parsers [also “Shift-Reduce parsers”, the subitems are ordered - LR(0) is least powerful - CLR(1) most powerful]
    LR(0)
    SLR(1)
    LALR(1)
    CLR(1)

related: Chart parser (stores hypothesized results for handling ambiguity)
PEG parsers :=
  generate a recursive descent parser
  … with infinite lookahead (via predicates),
  … applies an `actions` concept,
  … and PEG requires evaluation of the left-most item in alternatives first

packrat parsing :=
  the rules might be written such that a non-terminal is read twice (“<ident> ( <expr> ) | <ident>”)
  speedup by memoizing (non-terminal, position in source code)