Constructing An LL(k) Parsing Table
Until the mid 1990s, it was widely believed that LL(k) parsing (for k > 1) was impractical, since the parser table would have exponential size in k in the worst case. This perception changed gradually after the release of the PCCTS around 1992, when it was demonstrated that many programming languages 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(1) parser tables to construct a restricted LR parser with a fixed one-token lookahead.
Read more about this topic: LL Parser
Famous quotes containing the words constructing and/or table:
“The very hope of experimental philosophy, its expectation of constructing the sciences into a true philosophy of nature, is based on induction, or, if you please, the a priori presumption, that physical causation is universal; that the constitution of nature is written in its actual manifestations, and needs only to be deciphered by experimental and inductive research; that it is not a latent invisible writing, to be brought out by the magic of mental anticipation or metaphysical mediation.”
—Chauncey Wright (1830–1875)
“When you got to the table you couldn’t go right to eating, but you had to wait for the widow to tuck down her head and grumble a little over the victuals, though there warn’t really anything the matter with them. That is, nothing only everything was cooked by itself. In a barrel of odds and ends it is different; things get mixed up, and the juice kind of swaps around, and the things go better.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)