5/05/2011

A tiny attribute grammar exercise

(C) 2011, Ralf Laemmel

Let's map Knuth' attribute grammar example to Haskell. This has been done many times. In fact, there is a long track of excellent research on the relation between attribute grammars and functional programming. For instance, see the work by Doaitse Swierstra and team over many years. Our development here is meant to just illustrate the basic mapping in an as simple and self-contained manner as possible.

One should notice that the chosen example (due to Knuth) requires laziness for the straightforward encoding that is leveraged
below. Hence, C programmers are encouraged to try to transcribe this Haskell program to their favorite language.

The following context-free grammar is assumed:


digit : '0'
digit : '1'
digits : digit
digits : digits digit
number : digits
number : digits '.' digits


That is, we deal with binary numbers---both integer and fractional numbers.

We use the following algebraic datatypes to model the grammar:


data Digit = Zero | One
data Digits = Single Digit | Several Digits Digit
data Number = Int Digits | Frac Digits Digits


Let us now associate attributes with the nonterminals:


* digit:
- inh. p -- position of digit
- syn. v -- value of digit
* digits:
- inh. p -- position of digits
- syn. v -- value of digits
- syn. l -- length of digits
* number:
- syn. v -- value of number


In Haskell, we can introduce designated type aliases to capture the names of the attributes, and the association of nonterminals with attributes is modeled with the signatures for functions that are expected to model the semantic equations. (We could also use record types, but Haskell's record system is not quite convenient in this context.) Here, the assumption is that those functions carry one argument for the syntactial part, another argument for (the tuple of) the inherited attributes, and the result corresponds to (the tuple of) the synthesized attributes. Thus:


-- Type synonyms for attributes
type Val = Float
type Pos = Int
type Len = Int

-- Functions for semantic equations
digit :: Digit -> Pos -> Val
digits :: Digits -> Pos -> (Val,Len)
number :: Number -> Val


Here are the semantic equations for the example:


digit : '0'
v.digit = 0

digit : '1'
v.digit = 2^^p.digit

digits : digit
v.digits = v.digit
l.digits = 1
p.digit = p.digits

digits : digits' digit
v.digits = v.digits' + v.digit
p.digit = p.digits
p.digits' = p.digits + 1
l.digits = l.digits' + 1

number : digits
v.number = v.digits
p.digits = 0

number : digits '.' digits'
v.number = v.digits + v.digits'
p.digits = 0
p.digits' = -l.digits'


We implement these semantic equations as equations defining the functions from syntax times inherited attributes to synthesized attributes.


digit Zero _ = 0
digit One p = 2^^p

digits (Single d) p = (digit d p,1)
digits (Several ds d) p = (v,l)
where
v = v' + v''
l = l' + 1
(v',l') = digits ds (p+1)
v'' = digit d p

number (Int ds) = fst (digits ds 0)
number (Frac ds1 ds2) = v1+v2
where
(v1,l1) = digits ds1 0
(v2,l2) = digits ds2 (-l2)


Let us evaluate 10.01.


main = do print (number n)
where
n = Frac ds ds'
ds = Several (Single One) Zero
ds' = Several (Single Zero) One

> main
2.25


Regards,
Prof. Fisch

No comments:

Post a Comment