Avoiding inherited attributes in bottom-up parsing

Tobias Carlsson <toca@serop.abb.se>
27 Aug 1999 12:30:06 -0400

          From comp.compilers

Related articles
Avoiding inherited attributes in bottom-up parsing toca@serop.abb.se (Tobias Carlsson) (1999-08-27)
Re: Avoiding inherited attributes in bottom-up parsing rkrayhawk@aol.com (1999-08-28)
Re: Avoiding inherited attributes in bottom-up parsing world!cfc@uunet.uu.net (Chris F Clark) (1999-08-28)
Re: Avoiding inherited attributes in bottom-up parsing torbenm@diku.dk (1999-09-05)
Re: Avoiding inherited attributes in bottom-up parsing martin.jourdan@directprovider.net (1999-09-10)
Avoiding inherited attributes in bottom-up parsing sassa@is.titech.ac.jp (1999-09-10)
| List of all articles for this month |

From: Tobias Carlsson <toca@serop.abb.se>
Newsgroups: comp.compilers
Date: 27 Aug 1999 12:30:06 -0400
Organization: ABB Sweden
Keywords: parse, attribute

In the dragon book one can read about evaluation of inherited attributes
in bottom-up parsing. I think that inherited attributes should be
avoided in bottom up parsing.
To get access to inherited attributes (without using globals), one must
index the parser stack, that compromises the principles of the stack
machine and is a great place for bugs to hide, because when indexing the
parser stack, one must always have the same symbols on the stack. This
makes the grammar hard to change or reuse.


The dragon book also describes a technique for replacing inherited
attributes by synthesized attributes,
example: Declaration in Pascal (page 315-316, dragon book)


Decl -> id List
List -> , id List
                | : Type
Type -> int
                | char


Now the type attribute can be synthesized as the rules are reduced. The
only thing negative about this is that the grammar becomes messy, it's
difficult to see the overall context.


A better approach (I think), is that the first rule displays what going
on ( Decl -> List : Type ), you don't have to read the hole grammar to
understand the context.


Decl -> List : Type { install_Type(Type.t); }
                | epsilon
List -> id ListP { install_Id(id); }
ListP -> , id ListP { install_Id(id); }
                | epsilon
Type -> int { Type.t=int; }
                | char { Type.t=char; }




I think this way makes the grammar easier to read and there's no need
for inherited attributes, since you install attributes in the symbol
table as they appear in the grammar. That increases understandability
alot. The negative aspect is that you have to access the symbol table a
second time to install the type of the identifier. The "install_Type"
function knows which id's to install the type for, since these are the
only ones with the type undefined.


Any comments on this, positive or negative, would be interesting to
read.


/Tobias Carlsson,
dal96tcn@idt.mdh.se


Post a followup to this message

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