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”):
- Shift a terminal from the front of the input to the top of the stack.
- 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).
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].
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).