LL parser An LL parser is a table-based top-down parser for a subset of the context-free grammars. It parses the input from Left to right, and constructs a Leftmost derivation of the sentence (Hence LL, compare with LR parser). The class of grammars which are parsable in this way is known as the LL grammars. Older programming languages sometimes use LL grammars because it is simple to create parsers for them by hand - using either the table-based method described here, or a recursive descent parser. An LL parser is called an LL(k) parser if it uses k tokens of look-ahead when parsing a sentence. If such a parser exists for a certain grammar and it can parse sentences of this grammar without backtracking then it is called an LL(k) grammar. Of these grammars, LL(1) grammars, although fairly restrictive, are very popular because the corresponding LL parsers only need to look at the next token to make their parsing decisions. Architecture of an LL parser A table-based top-down parser can be schematically presented as in Figure 1. Figure 1. Architecture of a table-based top-down parser +---+---+---+---+---+---+ Input: | ( | 1 | + | 1 | ) | $ | +---+---+---+---+---+---+ ^ | Stack: | +----------+ +---+ | | | + |<------| Parser |-----> Output +---+ | | | S | +----------+ +---+ ^ | ) | | +---+ | | $ | +----------+ +---+ | Parsing | | table | +----------+ The parser has an input buffer, a stack on which it keeps symbols from the grammar, a parsing table which tells it what grammar rule to use given the symbols on top of its stack and its input tape. To explain its workings we will use the following small grammar: (1) S -> F (2) S -> ( S + F ) (3) F -> 1 The parsing table for this grammar looks as follows: ( ) 1 + $ S 2 - 1 - - F - - 3 - - (Note that there is also a column for the special terminal $ that is used to indicate the end of the input stream.) Depending on the top-most symbol on the stack and the current symbol in the input stream, the parser applies the rule stated in the matching row and column of the parsing table (e.g. if there is a 'S' on the top of the parser stack and a '1' in the front-most position of the input stream, the parser executes rule number 1, i.e. it replaces the 'S' on its stack by 'F'). When the parser starts it always starts on its stack with [ S, $ ] where $ is a special terminal to indicate the bottom of the stack and the end of the input stream, and S is the start symbol of the grammar. The parser will attempt to rewrite the contents of this stack to what it sees on the input stream. However, it only keeps on the stack what still needs to be rewritten. For example, let's assume that the input is "( 1 + 1 )". When the parser reads the first "(" it knows that it has to rewrite S to "( S + F )" and writes the number of this rule to the output. The stack then becomes: [ (, S, +, F, ), $ ] In the next step it removes the '(' from its input stream and from its stack: [ S, +, F, ), $ ] Now the parser sees an '1' on its input stream so it knows that it has to apply rule (1) and then rule (3) from the grammar and write their number to the output stream. This results in the following stacks: [ F, +, F, ), $ ] [ 1, +, F, ), $ ] In the next two steps the parser reads the '1' and '+' from the input stream and also removes them from the stack, resulting in: [ F, ), $ ] In the next three steps the 'F' will be replaced on the stack with '1', the number 3 will be written to the output stream and then the '1' and ')' will be removed from the stack and the input stream. So the parser ends with both '$' on its stack and on its input steam. In this case it will report that it has accepted the input string and on the output stream it has written the list of numbers [ 2, 1, 3, 3 ] which is indeed a leftmost derivation of the input string in reverse (therefore, the derivation goes like this: S -> ( S + F ) -> ( F + F ) -> ( 1 + F ) -> ( 1 + 1 )). As can be seen from the example the parser performs three types of steps depending on whether the top of the stack is a nonterminal, a terminal or the special symbol $: If the top is a nonterminal then it looks up in the parsing table on the basis of this nonterminal and the symbol on the input stream which rule of the grammar it should use to replace it with on the stack. The number of the rule is written to the output stream. If the parsing table indicates that there is no such rule then it reports an error and stops. If the top is a terminal then it compares it to the symbol on the input stream and if they are equal they are both removed. If they are not equal the parser reports an error and stops. If the top is $ and on the input stream there is also a $ then the parser reports that it has successfully parsed the input, otherwise it reports an error. In both cases the parser will stop. These steps are repeated until the parser stops, and then it will have either completely parsed the input and written a leftmost derivation to the output stream or it will have reported an error. Constructing an LL(1) parsing table In order to fill the parsing table we have to establish what grammar rule the parser should choose if it sees a nonterminal A on the top of its stack and symbol a on its input stream. It is easy to see that such a rule should be of the form A → w and that the language corresponding with w should have at least one string starting with a. For this purpose we define the First-set of w, written here as Fi(w), as the terminals with which the strings that belong to w start plus ε if the empty strings also belongs to w. Given a grammar with the rules A1 → w1, ..., An → wn we can compute the Fi(wi) and Fi(Ai) for every rule as follows: initialize every Fi(wi) and Fi(Ai) with the empty set add Fi(wi) to Fi(wi) for every rule Ai → wi where Fi is defined as follows: Fi(a w' ) = for every terminal a Fi(A w' ) = Fi(A) for every nonterminal A with ε not in Fi(A) Fi(A w' ) = Fi(A) \ ∪ Fi(w' ) for every nonterminal A with ε in Fi(A) Fi(ε) = add Fi(wi) to Fi(Ai) for every rule Ai → wi repeat the steps 2 and 3 until all Fi sets stay the same. Unfortunately the First-sets are not sufficient to compute the parsing table. This is because a right-hand side w of a rule might ultimately be rewritten to the empty string. So the parser should also use the a rule A → w if ε is in Fi(w) and it sees on the input stream a symbol that could follow A. Therefore we also need the Follow-set of A, written as Fo(A) here, which is defined as the set of terminals a such that there is a string of symbols αAaβ that can be derived from the start symbol. Computing the Follow-sets for the nonterminals in a grammar can be done as follows: initialize every Fo(Ai) with the empty set if there is a rule of the form Aj → wAiw' then if the terminal a is in Fi(w' ) then add a to Fo(Ai) if ε is in Fi(w' ) then add Fo(Aj) to Fo(Ai) repeat step 2 until all Fo sets stay the same. Now we can define exactly which rules will be contained where in the parsing table. If T[A, a] denotes the entry in the table for nonterminal A and terminal a then T[A,a] contains the rule A → w iff a is in Fi(w) or ε is in Fi(w) and a is in Fo(A). If the table will contain at most one rule in every one of its cells then the parser will always know which rule it has to use and can therefore parse strings without backtracking. It is precisely in this case that the grammar is called an LL(1) grammar. Constructing an LL(k) parsing table Until the mid 1990s, it was widely believed that LL(k) parsing (for k>1) is impractical, since the size of the parse table would (in general, in the worst case) have to have exponential complexity in k. This perception changed gradually after the release of the Purdue Compiler Construction Tool Set (PCCTS, now known as ANTLR) 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/GNU bison use a LALR(1) parse tables to construct a restricted LR parser with a fixed one-token lookahead. LL(k) parser generators Modern parser generators that generate LL parsers with multi-token lookahead include: ANTLR : Home page Coco/R : Home page JavaCC : Home page PCCTS is now ANTLR, there is an archived site at http://www.polhode.com/pccts.html SLK : Strong LL(k) parsing, Home page has an indepth discussion of LL (k) parsing Most Popular Articles: Music    Musical Instruments    Guitar    Classical Music    History    Music Definition    Country Music    Rock Music    Pop Music    Hip Hop    Rap    DJ    Video Games    Casino Games    Poker    Blackjack    Casinos    Real Estate    Loan    Auction    eBay    Marketing    Search Engine Optimization    File Sharing    MP3    Music Industry    Kazaa    Internet    Supermodel    Fashion    Fashion Designers    Erotica    Modeling    Clothing    Boots    Shoes    Diamond Engagement Rings    Diamond    Rugs    Gospel Music    Affiliate    E-Commerce    Radio This article is licensed under the GNU Free Documentation License at http://www.gnu.org/copyleft/fdl.html You may copy and modify it as long as the entire work (including additions) remains under this license. You must provide a link to http://www.gnu.org/copyleft/fdl.html for use of this content. To view or edit this article at Wikipedia go to http://www.wikipedia.org/wiki/LL_parser