LL parsing, LR parsing, complexity, and automata
Rob Taylor · ACM SIGCSE Bulletin · 2002
It is well known that pushdown-stack automata find application within the syntactic analysis phase of compilation. Nonetheless, in most compiler design textbooks the relation between popular parsing algorithms and the theory of deterministic pushdown-stack automata remains implicit. We show that it is not difficult to implement these algorithms as deterministic automata. These implementations in turn yield instructive time/space analyses of the implemented algorithms.