Loading page…
Grammar notation, parsing algorithms, AST construction, and error recovery.
::= '+' | | separates alternatives (choice)ε = empty production (no tokens consumed)* { } )? [ ] )FIRST(X)
// Terminals that can start a string derived from X
FIRST(a) = {a} for terminal a
FIRST(ε) = ∅
FIRST(A→X₁X₂...Xₙ) = FIRST(X₁) ∪ (FIRST(X₂) if ε∈FIRST(X₁)) ∪ ...FOLLOW(A)
// Terminals that can appear immediately after A in a derivation
FOLLOW(S) ⊇ {$} for start symbol S
For A → αBβ: FOLLOW(B) ⊇ FIRST(β) - {ε}
For A → αB (or ε∈FIRST(β)): FOLLOW(B) ⊇ FOLLOW(A)| Algorithm | Complexity | Grammar Class | Implementation |
|---|---|---|---|
| Recursive Descent | O(n) | LL(1) w/ backtrack | Hand-written, easy |
| LL(1) Table-Driven | O(n) | LL(1) | Parse table + stack |
| LR(0) | O(n) | LR(0) (limited) | Shift-reduce table |
| SLR(1) | O(n) | SLR (subset of LALR) | Follow-based reduction |
| LALR(1) | O(n) | Most programming languages | **yacc/bison default** |
| LR(1) / GLR | O(n) / O(n³) | Full LR / ambiguous | Powerful, space-heavy |
| Earley | O(n³) worst | All CFGs | Academic, flexible |
Common AST Node Types
typedef enum {
NODE_PROGRAM, // root
NODE_FUNC_DEF, // function definition
NODE_VAR_DECL, // variable declaration
NODE_BINARY_OP, // a + b, a * b
NODE_UNARY_OP, // -a, !a, *p
NODE_IF, // if-else
NODE_WHILE, // while loop
NODE_RETURN, // return statement
NODE_CALL, // function call
NODE_INT_LITERAL, // 42
NODE_IDENTIFIER, // variable name
} NodeType;;, }) is found. Crude but robust.if x > 0 then → insert ( before x.| CYK | O(n³) | CNF grammars | Used in NLP |