Re: Inherited attributes in available LALR parser generators?

sperber@midi.informatik.uni-tuebingen.de) writes:
>... I'd be especially interested in purely functional variants.


I have written a SLR parser generator in Gofer (a Haskell variant) that
generates purely functional parsers (also in Gofer). Even though the
sematic value of a production is a function of the attributes of its
right-hand side (and thus apparently purely synthesized), inherited
attributes are easily simulated by using higher order functions. An
example from the manual is


Exp -> letT var equals Exp inT Exp
                                                                $ \env-> x6 ((x2,x4 env):env) $
          | Exp1 $ x1 $


Exp1 -> Exp1 plus Term $ \env-> x1 env + x3 env $
            | Exp1 minus Term $ \env-> x1 env - x3 env $
            | Term $ x1 $


Term -> Term times Factor $ \env-> x1 env * x3 env $
            | Term divide Factor $ \env-> x1 env / x3 env $
            | Factor $ x1 $


Factor -> integer $ \env-> intval x1 $
                | var $ \env-> lookup x1 env $
                | lpar Exp rpar $ x2 $




The semantic `function' is given in $...$ after the production. The
variables x1 ... xn refer to the semantic values of the 1st to nth
symbol on the right-hand side (like $0 to $n in yacc).


In this example the type of a semantic value is


environment -> value


where environment = [(name,value)]. In this way, the environment is an
inherited attribute and is thus given as argument to the semantic
functions of the right-hand side nonterminals.


You can have any number of synthesized and inherited attributes and
you don't have to worry about the order of attribute evaluation, since
the underlying language is lazy. I have even used recursively defined
attributes in some examples.


The parser generator is available by anonymous ftp from ftp.diku.dk in
the directory pub/diku/dists, in the file Ratatosk.tar.Z. Unpack this
by


                uncompress < Ratatosk.tar.Z | tar xvpf -


which creates a directory Ratatosk, containing the system.


The package contains a manual, sources for the parser generator and
scanner generator and some example files, including files for
bootstrapping the system.


Torben Mogensen (torbenm@diku.dk)
--

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