Difference between an LL and Recursive Descent parser?

Posted by Noldorin on Stack Overflow See other posts from Stack Overflow or by Noldorin
Published on 2009-06-25T15:32:21Z Indexed on 2010/05/09 6:18 UTC
Read the original article Hit count: 392

Filed under:

parser

|

grammar

|

context-free-grammar

|

ll

|

recursive-descent

I've recently being trying to teach myself how parsers (for languages/context-free grammars) work, and most of it seems to be making sense, except for one thing. I'm focusing my attention in particular on LL(k) grammars, for which the two main algorithms seem to be the LL parser (using stack/parse table) and the Recursive Descent parser (simply using recursion).

As far as I can see, the recursive descent algorithm works on all LL(k) grammars and possibly more, whereas an LL parser works on all LL(k) grammars. A recursive descent parser is clearly much simpler than an LL parser to implement, however (just as an LL one is simply than an LR one).

So my question is, what are the advantages/problems one might encounter when using either of the algorithms? Why might one ever pick LL over recursive descent, given that it works on the same set of grammars and is trickier to implement?

Hopefully this question makes some amount of sense. Sorry if it doesn't - I blame my the fact that this entire subject is almost entirely new to me.

© Stack Overflow or respective owner

Related posts about parser

Core Data error when assigning variable with one-to-one relationship

as seen on Stack Overflow - Search for 'Stack Overflow'
I tried to assign a managed object (C) with its property another managed object (B) (a one-to-one relationship) in which this other managed object (B) has a to-many relationship with one other managed object (A). There is an error from this assignment in which I copied as follows: #0 0x020e53a7… >>> More
RapidXML - does not compile ?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am novice to rapidXML but first impresion was not positive, I made simple Visual Studio 6 C++ Hello World Application and added RapidXML hpp files to project and in main.cpp I put: #include "stdafx.h" #include < iostream > #include < string > #include "rapidxml.hpp" using namespace… >>> More
exception occured in java compiler

as seen on Stack Overflow - Search for 'Stack Overflow'
I am a beginner in Java.I have JDK1.7.0 installed on windows 7 OS.I just wrote a sample java file where the file was not getting compiled and throws the below error. Sam.java:5: ';' expected Sample p = New Sample(); An exception has occurred… >>> More
Coding a parser for a domain specific language in Java

as seen on Stack Overflow - Search for 'Stack Overflow'
We want to design a simple domain specific language for writing test scripts to automatically test a XML-based interface of one of our applications. A sample test would be: Get an input XML file from network shared folder or subversion repository Import the XML file using the interface Check if… >>> More
Doxygen C++ comment string parser in python?

as seen on Stack Overflow - Search for 'Stack Overflow'
Does anybody know of a python module to parse a doxygen style C++ comment string? I mean a string like this (simple example): /** * A constructor. * A more elaborate description of the constructor. * @param param1 test1 * @param param2 test2 */ and I would like to extract the brief… >>> More

Related posts about grammar

Convert The Context Free Grammar to LL1 Grammar

as seen on Stack Overflow - Search for 'Stack Overflow'
hi I want to write a program to gives grammar as input and change it to LL1. my problem is converting to LL1 I don't have any algorithm to convert. I earn grammar from some input text by a simple text analyzer but how I can change it to LL1 ? is there any algorithm that is clear to implement. >>> More
English Grammar Parsing in PHP (Link Grammar)

as seen on Stack Overflow - Search for 'Stack Overflow'
Is there anyway to use the Link Grammar or AbiSource grammar checker in PHP (or C# but I'd prefer php)? I need to have a tree structure for english sentences. Any ideas? The only things I found were in C and I can't use them on a shared host. >>> More
Good grammar for date data type for recursive descent parser LL(1)

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm building a custom expression parser and evaluator for production enviroment to provide a limited DSL to the users. The parser itself as the DSL, need to be simple. The parser is going to be built in an exotic language that doesn't support dynamic expression parsing nor has any parser generator… >>> More
Parsing a string, Grammar file.

as seen on Stack Overflow - Search for 'Stack Overflow'
How would I separate the below string into its parts. What I need to separate is each < Word including the angle brackets from the rest of the string. So in the below case I would end up with several strings 1. "I have to break up with you because " 2. "< reason " (without the spaces) 3. "… >>> More
Efficient Context-Free Grammar parser, preferably Python-friendly

as seen on Stack Overflow - Search for 'Stack Overflow'
I am in need of parsing a small subset of English for one of my project, described as a context-free grammar with (1-level) feature structures (example) and I need to do it efficiently . Right now I'm using NLTK's parser which produces the right output but is very slow. For my grammar of ~450 fairly… >>> More