Editing LL parser (section)

== Constructing an LL(''k'') parsing table ==

The construction for LL(1) parsers can be adapted to LL(''k'') for ''k'' > 1 with the following modifications:
* the truncated product is defined <math>U \cdot V = \{ (uv):k \mid u \in U, v \in V \}</math>, where ''w'':''k'' denotes the initial length-''k'' prefix of words of length > ''k'', or ''w'', itself, if ''w'' has length ''k'' or less,
* '''Fo'''(''S'') = {'''$'''<sup>k</sup>}
* Apply '''Fi'''(''αβ'') = '''Fi'''(''α'') ⋅ '''Fi'''(''β'') also in step 2 of the '''Fi''' construction given for LL(1).
* In step 2 of the '''Fo''' construction, for ''A<sub>j</sub>'' → ''wA<sub>i</sub>w''{{prime}} simply add '''Fi'''(''{{prime|w}}'')·'''Fo'''(''A<sub>j</sub>'') to '''Fo'''(''A<sub>i</sub>'').
where an input is suffixed by ''k'' end-markers '''$''', to fully account for the ''k'' lookahead context.  This approach eliminates special cases for ε, and can be applied equally well in the LL(1) case.

Until the mid-1990s, it was widely believed that {{clarify span|LL(''k'') parsing|reason=Should be 'table-based LL(k) parsing'? I saw several ad hoc recursive-descent parsers in common use in the 1970s and 1980s. Moreover, if the *language* is LL(k), the *parser* can't do anything about it.|date=February 2024}} (for ''k'' > 1) was impractical,<ref>{{cite book |last1=Fritzson |first1=Peter A. |title=Compiler Construction: 5th International Conference, CC '94, Edinburgh, U.K., April 7–9, 1994. Proceedings |date=23 March 1994 |publisher=Springer Science & Business Media |isbn=978-3-540-57877-2 |language=en}}</ref>{{rp|263–265}} since the parser table would have [[exponential function|exponential]] size in ''k'' in the worst case. This perception changed gradually after the release of the [[Antlr|Purdue Compiler Construction Tool Set]] around 1992, when it was demonstrated that many [[programming language]]s can be parsed efficiently by an LL(''k'') parser without triggering the worst-case behavior of the parser.  Moreover, in certain cases LL parsing is feasible even with unlimited lookahead.  By contrast, traditional parser generators like [[yacc]] use [[LALR parser|LALR(1)]] parser tables to construct a restricted [[LR parser]] with a fixed one-token lookahead.