c++ code completion status report

[Eray Ozkural (exa)]

On Saturday 05 January 2002 19:31, Gregor Zeitlinger wrote:
> On Sat, 5 Jan 2002, Richard Dale wrote:
> > 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.
>
> Yes, it does. Read http://www.acm.org/crossroads/xrds7-5/bison.html It
> properly shows that Bison is arcane. I'm currently working with flex/bison
> at university, and from a theoretical point of view, bison uses a parsing
> algorithm that is pretty fast and yet powerful enough for most languages
> (LALR(1)). However - it is not very intuitive, as you have to avoid
> left-recursion and other shift/reduce and reduce/reduce-errors. Algorithms
> like GLR can handle those easily, but have a slightly higher complexity,
> which doesn't really matter according to the author of the document cited
> above.
>
> Another possibility would be to take the same bison files as the GCC
> project. Don't know if they are any usable, though.

Nice article. Though LR(k) parsers are pretty common place (OTOH it would be 
inexact to call such an algorithm non-deterministic), and it's not that 
difficult to write your own LR(k) algorithm! It's just a hell lot of 
book-keeping to write a bottom-up parser. I think I'd written an LR(1) 
parser, hmm, you can express much of the code with recursion which makes it 
look very intuitive.  The old dragon book tries to do everything with for 
loops and stacks. Heh.

-- 
Eray Ozkural (exa) <erayo at cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C