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

Reinhold Heckmann / heckmann@absint.com