Context-free grammar

cosmos 14th February 2017 at 3:35pm
Chomsky hierarchy Formal grammar

intro video

Ambiguity in parsing! Finding out if a grammar is ambiguous or not, is Undecidable! (see here). Also Undecidable to know if two grammars are the same.

Parse trees are used to give a string some Meaning in a Compiler (like that of a Programming language)

Ideas for designing grammars

Single-tree grammars: Grammars that only have one choice with non-terminals on the RHS

Deterministic push-down machines

(less powerful than context free languages, and equivalent to LRK grammars). Most Compilers are described with LRK grammars.

Non-deterministic push-down machines

(equivalent to Context free grammars)