Editing LL(k) ---- LL(1) Parsers
Please note that you are now editing the latest revision of this page, which is not the approved one shown by default.
Warning: You are not logged in.
Your IP address will be recorded in this page's edit history.The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | + | '''LL(k)''' - '''''L'''eft to right, '''L'''eftmost derivation with '''k''' lookahead symbols '' | |
+ | <br><br> | ||
+ | |||
+ | An '''LL(k)''' parser is a top-down parser, that is, it decides which production to use by looking at the next k tokens. This means that an LL(k) grammar must not have a point where the alternative productions have the same prefix, and that a production cannot be left-recursive - the left hand side must always resolve to a terminal. In addition, an LL(k) grammar must have a fixed value of k. Most LL(k) parsers are actually LL(1) parsers that use lookahead trees where it's necessary to disambiguate rules. | ||
+ | <br><br> | ||
+ | |||
+ | <FONT COLOR="#00FF00">LL(k) parser generators</FONT> | ||
+ | <br><br> | ||
+ | |||
+ | Modern parser generators that generate LL parsers with multi-token lookahead include: | ||
+ | <ul> | ||
+ | <li>'''ANTLR (old PCCTS)''' [INSERIR LINK]</li> | ||
+ | <li> '''Coco/R''' [INSERIR LINK]</li> | ||
+ | <li> '''JavaCC'''</li> | ||
+ | <li> '''Parsec'''</li> | ||
+ | <li> '''SLK'''</li> | ||
+ | <li> '''Spirit Parser Framework'''</li> | ||
+ | </ul> | ||
+ | <br><br> | ||
+ | |||
+ | Please give a look at following document (definitions over LL(1) parsers and algorithm to construct table based LL(1)): [http://epl.di.uminho.pt/~gepl/LP/AlgorithmLL1.pdf Algorithm.pdf] | ||
+ | <br><br> | ||
+ | |||
+ | Example of a LL(1) grammar and his table: [http://epl.di.uminho.pt/~gepl/LP/LittleGarden.pdf LittleGarden.pdf] | ||
+ | |||
+ | [[Category:Basic Concepts]] |