c++ code completion status report

Richard Dale Richard_Dale at tipitina.demon.co.uk
Sat Jan 5 17:47:05 UTC 2002

On Saturday 05 January 2002 11:43 am, Thomas Schilling wrote:
> > I wouldn't think a recursive descent parser could be used for anything
> > serious, though you said LL(k) rather than LL(1) which should make it
> > powerful enough. But it's still less capable than LR(k), no? Nah, I just
> woke
> > up, not in my parsing theory mood.
> The problem with LL(1) is that it forbids left recursion. So using LL(1)
> would complicate our grammar. And I already wrote some
> top-down-parser (I mean, I started to write one) until I found that
> I needed k > 1 (better: k >> 1). That would be very inefficient.
Just joking really - bison is fine!

Yes, to avoid left recursion, you would need to change rules about 'lists of 
things' like this:
list --> list ',' list_item

to this:
list --> list_item ',' list

No big deal really. It would probably be slower than a bison grammar too, and 
I don't know if such a non-deterministic parser generator exists.

I wrote LL(k) rather than LL(1) as I was thinking of an arbitrary look-ahead 
parser with backtracking. So k would be big enough to backtrack through every 
symbol in the current source file - more like prolog than recursive descent 
LL(1). It might mean that you wouldn't have to keep reparsing all of the 
source file, but could use backtracking to just undo the last few symbols 
parsed if the user retyped the current line.

-- Richard

More information about the KDevelop-devel mailing list