Parsing

Definition

Parsing takes an input word and context-free-grammar , and decides whether i s in the language of . If it is, a parser generates a proof of this in the form of a derivation or parse tree.

Input: word and CFG
Output: ? true or false?

Parsing Algorithms

We have our CYK algorithm, implemented in a more pedagogical way to show the intuition behind it.

Other parsing algorithms:

Algo	CYK	Early	LR(1)	LL(1)
Time		if ambiguous, otherwise, for most LR(k) grammars
Grammars	All	All	Many practical unambiguous grammars	A few practical grammars
Complexity (💀)	1.5 lectures	~3 lectures	6 lectures	~3 lectures
Correct Prefix Property	No	Yes	Yes	Yes

If LR1 accepts your grammar, then it's for sure unambiguous. However, if it rejects, it still could be unambiguous.

The Correct Prefix Property

When an input is not a word in the language, we want a detailed message indicating why the input could not be parsed.

The parser should return the longest prefix of the input that is also a prefix of some word in the language. That is, up to the point where it got stuck.

Definition

Suppose is an input to the parser, and can be decomposed into , where and are sequences of terminal symbols and is a terminal symbol.

Suppose (not in language).

If there exists such that and for all , , a parser has the correct prefix property if it rejects input after processing .