Re: Generating a simple hand-coded like recursive descent parser

Karsten Nyblad <148f3wg02@sneakemail.com> writes:


> Robert A Duff asks if anybody has tried parsing C or C++ without using
> a context sensitive grammar, and mentions that in Ada the grammar for
> array indexing and function calls are similar.


Thanks to all who answered!


> In C you can write an expression (a)-b*c. If a is a type then(a)-b*c is
> equivalent to ((a)-b)*c, but if a is a variable then (a)-b*c is
> equivalent to (a)-(b*c). To put it an other way: In Ada you will want
> a parse tree of the same structure independently of whether a subtree is
> an array indexing or a function call. It is simply a question of
> putting the right labels on the nodes.


Actually, that's not true of Ada, although the examples I gave did not
show it. In particular, X(Y) could mean a call to X passing Y as argument,
or an array indexing (among other things). If it's an array indexing,
X could be an array, or a call to a zero-argument function returning an
array, or the dereference of a call to a zero-argument function
returning a pointer to an array. Therefore, we don't know (based purely
on a context-free grammar) whether Y is a subtree of the call or not.
We don't even know how many nodes there are (call, indexing, call and
indexing, dereference and call and indexing). Therefore, we must
restructure the tree (a little) based on semantic information.


For Ada, I can't imagine doing all that with feedback from semantic
analysis to parser.


>...In C and C++ it is not enough to put some other labels on some
>nodes. You will want to reorder the tree, and that reordering will
>be so complex, that it is easier to use a context sensitive grammar.


That I can believe.


- Bob

Return to the comp.compilers page.
Search the comp.compilers archives again.