ELL(k)-Parsing and Efficient ELL(1)-Parser Generation

Diploma thesis of Reinhold Heckmann

Table of Contents / Inhaltsverzeichnis

0.	Introduction	1
1.	Operations on words and languages	3
2.	Regular expressions	9
3.	Extended grammar and regular derivation	16
4.	The grammar graph	20
5.	Fixed point theorems	24
6.	The first-sets	27
7.	The K-derivation	31
8.	Correlations between R- and K-derivation	34
9.	Treatment of non-reduced grammars	39
10.	The follow-sets	44
11.	The ELL(s) conditions	50
12.	Ambiguity and ELL(1) properties	56
13.	Efficient computation of first-  and follow-sets for s=1	61
14.	The computation of Ep	65
15.	Computation of Fi'-  and follow-sets	69
16.	The ELL(1) - parser	77
17.	The complexity of the ELL(1) parser	81
References		87