All the algorithms from Sudkamp's Languages and Machines implemented in Java.
You are welcome to fork this repo in order to complete unimplemented algorithms or to improve on the existing ones. Please try to stick as close to the pseudo-code from the book.
| Page | Number | Name (in 3rd edition) | Name (in repository) | File |
|---|---|---|---|---|
| 108 | 4.2.1 | Construction of Set of Nullable Vars | nullableVarsSet() | ContextFreeGrammar.java |
| 114 | 4.3.1 | Construction of the Set CHAIN(A) | chain( A ) | ContextFreeGrammar.java |
| 117 | 4.4.2 | Constr. of Set of Vars that Derive Terminal Strings | constructSetOfVarsThatDeriveTerminalStrings() | ContextFreeGrammar.java |
| 119 | 4.4.4 | Contruction of Set of Reachable Vars. | constructSetofReachableVars() | ContextFreeGrammar.java |
| 126 | 4.6.1 | CYK Algorithm | CYK.testMembership() | CYK.java |
| 172 | 5.6.3 | Contruction of DM, a DFA Equiv. to NFA M | ||
| 179 | 5.7.2 | Determination of Equivalent States of DFA | ||
| 194 | 6.2.2 | Construction of a Regular Expression from a Finite Automaton | constructFromFiniteAutomaton() | RegExp.java |
| 543 | 17.4.3 | Recursive Simulation of NonDeterministic Turing Machine | ||
| 558 | 18.2.1 | Breadth-First Top-Down Parser | ||
| 564 | 18.4.1 | Breadth-First Bottom-Up Parser | ||
| 581 | 19.4.1 | Construction of FIRSTk Sets | ||
| 583 | 19.5.1 | Construction of FOLLOWk Sets | ||
| 588 | 19.7.1 | Deterministic Parser for a Strong LL(k) Grammar | ||
| 591 | 19.8.3 | Deterministic Parser for an LL(k) Grammar | ||
| 600 | 20.2.1 | Parser for an LR(0) Grammar | ||
| 604 | 20.3.3 | Parser Utilizing the Deterministic LR(0) Machine | ||
| 618 | 20.5.4 | Parser for an LR(1) Grammar |
| Name | Name (In Repository) | File |
|---|---|---|
| Elimination of Chain Rules | removeChainRules() | ContextFreeGrammar.java |
| Remove Recursive Start Symbol | removeRecursiveStartSymbol() | ContextFreeGrammar.java |
To the extent possible under law, Thundergolfer has waived all copyright and related or neighboring rights to this work.