cosmos
4th November 2016 at 2:43pm
See Formal language
Formal grammar
Defined by either:
- variables, terminals, production rules, and starting symbols. See Formal language.
- an automaton.
Ambiguous grammar is one in which a given string in its language has more than one valid derivation/parse tree. The problem of knowing whether a grammar is ambiguous or not is Undecidable
Parsing expression grammar are a class of grammars, similar to Context-free grammars, but that cannot be ambiguous. It is conjectured that there exist context-free languages that cannot be parsed by a PEG, but this is not yet proven.[1] PEGs are well-suited to parsing computer languages.
