Hacking Off

20% Time All the Time

Parser and Grammar Classification Notes

Notes on (mostly Bottom-Up) parsing. Amassing these in the direction of creating some CFG tools. Prospects:

  • language classifier
  • NFA/DFA graphing for CFGs
  • bottom-up parser generator




A bottom-up parser has two possible actions (besides “accept”):

  1. Shift a terminal from the front of the input to the top of the stack.
  2. Reduce a string α at the top of the stack to a nonterminal A, given the BNF choice A → α

Source: Louden (198).

Definition of LR(1) transitions (part 1).

  1. Given an LR(1) item [A → α•Xγ, a], where X is any symbol (terminal or nonterminal), there is a transition on X to the item [A → αX•γ, a].

  2. Given an LR(1) item [A → α•Bγ, a], where B is a nonterminal, there are ε-transitions to items [B → •Β, b] for every production B → Β and for every token b in First(γa).

Source: Louden (217-218).