A new grammatical transformation into LL(k) form (Extended Abstract)
Michael M. Hammer · 1974
For some time, it has been recognized that left-to-right deterministic top-down parsing has a number of features to recommend it. The logic of such a parser is easily expressed as a one-state pushdown machine, and very flexible translations can readily be performed in conjunction with top-down processing. The major difficulty with this style of parsing is that there are relatively few grammars which satisfy the rather restrictive requirements to admit of top-down parsing (the LL(k) grammars), in comparsion with grammars that can be parsed deterministically bottom-up (the LR(k) grammars). There has been some research along the lines of trying to apply transformations to non-LL(k) grammars in order to convert them into equivalent LL(k) form [1,2,3]; the most successful approach has been that of Rosenkrantz and Lewis [4]. They define class of grammars, the LC(k) grammars, which can be parsed in a mixed hybrid of top-down bottom-up techniques; this class strictly includes the LL(k) grammars, as well as many interesting but non-LL(k) grammars. They then provide a deterministic algorithm for converting any LC(k) grammar into an equivalent LL(k) grammar.