Re: Avoiding inherited attributes in bottom-up parsing

Tobias Carlsson, dal96tcn@idt.mdh.se,
posted an engaging enquiry about inherited attributes (quoted verbatim infra
for clarity).


Permit me to comment on just parts of it. The challenge dealt with in
the cited dragon book example for Pascal declarations is brought about
by the language rules per se (the grammar of the language), not by the
techniques of coding in the parser 'grammar rules'.


For example, in C you might have


  what_type witch-1, witch-2, ..., witch-n;


As you scan forward in the text of this declaration you commence with
an understanding of what you need to be doing. And you can do it to
each witch-w encountered, AT THE TIME EACH INDIVIDUAL ITEM IS
PARSED. The attriutes of the witches are known when you meet them.


Same exemplified in Pascal,


    witch-1, witch-2, ... witch-n : what_type;


Now, BECAUSE OF THE LANGUAGE RULES, not the strategy used in any
parser, each wicked witch-w has a gostly, indefinite, appearance until
the end fo the declaration.


As far as your install_.. procedures (see posting below), I think that
your install_Type() will occur too late in time, being after all the
relevant witches have completed their haunt. That is, each invocation
of install_Id() will happen BEFORE the type is known.


All of the witches will be melted down (reduced) before we ever know
what direction to point their type attribute.


This problem originates in the Pascal Language specification, that
allows postfixing the type declarator.


Because of the delayed action, necessitated by the language rules, you
will need a chain to link you to each witch-w needing the completed
attribute information. With your coding strategy, you will be required
to establish the links in install_Id(); and walk the list in
install_Id(). That will be your code, and you will need to spend
development time and processing resources to accomplish it.


(Your statement:
<<
The "install_Type" function knows which id's to install the type for, since
these are the only ones with the type undefined.
>>


is non-trivial to say the least. You have implied your own custum
linked list, or an exhastive scan of the entire symbol table for each
declaration, an arithmetically progressing load.)


The use of a technique like inherited attributes is also a chaining
device that walks the parse stack, handing the resolution information
fire brigade style from data item instantiation to data item
instantaition. This technique exploits code and data structures inside
of the perfected parser algorithm. And the resources must be used
already, by the parser, so you add no major burden to the resources,
and have less to debug.




I think you will find many that agree with your sentiments generally,
that "... inherited attributes should be avoided in bottom up parsing
..." But I think that you will always find it challenging to code a
parser that encounters a declaration for witch_w, in a list of
witches-n, at a time that it does not possess all of the attribute
specification.


The compromise that you mention when indexing the parser stack, is
real, and references back to any token deeper than zero, does bring
about the problems you mention. But any code you write on your own to
walk a list of delayed resolution items is going to gain those
problems (or exact a resource toll to avoid them).


Your concerns are well founded, and well expressed. Try not to paint
yourself into a corner where you are maintaining a lot of code that
provides functions the parser can deliver.


Best Wishes,
Bob Rayhawk
RKRayhawk@aol.com

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