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

http://programmers.stackexchange.com/questions/19541/what-are-the-main-advantages-and-disadvantages-of-ll-and-lr-parsing

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).