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

http://en.wikipedia.org/wiki/LL_parser

http://en.wikipedia.org/wiki/LR_parser

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

Shifta terminal from the front of the input to the top of the stack.Reducea 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 bin First(γa).

Source: Louden (217-218).