[Verse 1] When your grammar's in Chomsky Normal Form CYK algorithm takes the storm Bottom-up it builds a table three-dimensional Dynamic programming so essential N cubed complexity it takes But every parse tree it makes Fill the chart from small to large CYK's got parsing in charge [Chorus] Six algorithms parsing strong CYK and Earley sing along LL descends from left to right LR shifts and that's alright Generators make it easy Yacc and ANTLR so breezy Parse the language, build the tree Automata sets us free [Verse 2] Earley parser's smart and keen Handles any grammar scene Three sets working in harmony Predictions, scans, and completions free N cubed for general case N squared when unambiguous grace But practical grammars linear time Earley's rhythm and its rhyme [Chorus] Six algorithms parsing strong CYK and Earley sing along LL descends from left to right LR shifts and that's alright Generators make it easy Yacc and ANTLR so breezy Parse the language, build the tree Automata sets us free [Verse 3] LL parsing looks ahead Top-down strategy widespread Left to right it reads the stream Leftmost derivation's dream But LR shifts and then reduces Bottom-up approach produces Deterministic subsets clean Real compilers' parsing machine [Bridge] Don't write parsers by your hand Parser generators take command Yacc and Bison lead the way ANTLR helps us code today Grammar rules you specify Generated parser on the fly [Chorus] Six algorithms parsing strong CYK and Earley sing along LL descends from left to right LR shifts and that's alright Generators make it easy Yacc and ANTLR so breezy Parse the language, build the tree Automata sets us free [Outro] From CNF to LR states Every parsing method creates Abstract syntax trees so fine Automata theory's design
← 5 Closure Properties of CFLs | 1 The Turing Machine (TM) →