Previous Next |

Conway [1963] describes a predictive (recursive-descent) parser, with a notion of FIRST sets and left-factoring. LL(*k*) parsing theory was formalized by Lewis and Stearns [1968]. LR(*k*) parsing was developed by Knuth [1965]; the SLR and LALR techniques by DeRemer [1971]; LALR(1) parsing was popularized by the development and distribution of Yacc [Johnson 1975] (which was not the first parser generator, or "compiler-compiler", as can be seen from the title of the cited paper). Image 3.29 summarizes many theorems on subset relations between grammar classes. Heilbrunner [1981] shows proofs of several of these theorems, including LL(*k*) ⊂ LR(*k*) and LL(1) 6 ⊊ LALR(1) (see Exercise 3.14). Backhouse [1979] is a good introduction to theoretical aspects of LL and LR parsing. Aho et al. [1975] showed how deterministic LL or LR parsing engines can handle ambiguous grammars, with ambiguities resolved by precedence directives (as described in ).

Burke and Fisher [1987] invented the error-repair tactic that keeps a *K* token queue and two parse stacks.

JaVa |
Previous Next |