[Haskell-beginners] Nullable attribute of a language grammar howto

1 Sep 2008

      The following is my first attempt at specifying a language
grammar.  The method of specification is to define an algebra
for the grammar expression.  This algebra is GramExpr with
constants from enums ArithInp and ArithVar.  The functions
correspond to the choice and concatenation operators in
compiler texts.

Specification of grammar worked OK, as shows by the successful compile
of all the prints for each expression as well as the successful print
of the list of GramProd's.  However, when I tried to calculate
the Nullable attributes of the expressions, I ran into problems.
What I wanted to do was execute a homomorphism from the grammar
expressions to another algebra, the GramNull algebra.  This GramNull
algebra will eventually produce a set of recursive equations
corresponding to the grammar productions.  The solution of these
equations will calculate whether a non-terminal (a member of
the enum ArithVar) can derive the empty string.

Would someone please let me know what I'm doing wrong or suggest a
better way of calculating the Nullable attribute of the
non-terminals. Eventually, I'd like to calculate the First and Follow
attributes in a similar way.

The source file is:
<--- gram_alg.hs ---
{-
Purpose:
  Algebraic specification of language grammar.
-}
module Main where

data ArithInp
  = Ident
  | Plus
  | Mult
  | ParenLeft
  | ParenRight
  deriving(Enum,Show)
data ArithVar
  = Term
  | Factor
  | Expr
  deriving(Enum,Show)

data GramExpr inp_type var_type --Grammar Expresson, i.e. the rhs of a 
production.
  = NullExpr --the empty string, i.e. the epsilon in Compiler texts.
  | InpExpr inp_type --a terminal, i.e. an inp_type, is a Grammar Expression
  | VarExpr var_type --a non-terminal, i.e. a var_type, is a Grammar 
Expression
  | (:|)  (GramExpr inp_type var_type) (GramExpr inp_type var_type)

    {-
      :|  is the choice grammar operator. E.g. input, i, matches
        x | y
      if i either matches x or y.
    -} 

  | (:>>) (GramExpr inp_type var_type) (GramExpr inp_type var_type)

    {-
      :>>  is the concatenation grammar operator. E.g. input, i, matches
        x :>> y
      if i matches x followed by y.
    -}
  deriving(Show)

data GramProd inp_type var_type
  = (:==) var_type (GramExpr inp_type var_type)
  deriving(Show)

data GramNull inp_type var_type
  = OneNull  --can derive empty string,
  | ZeroNull --can't derive empty string.
  | VarNull var_type --unknow whether var_type can derive empty string
  | AltNull (GramNull inp_type var_type) (GramNull inp_type var_type)
  | CatNull (GramNull inp_type var_type) (GramNull inp_type var_type)
  deriving(Show)

expr2null :: (GramExpr inp_type var_type) -> (GramNull inp_type var_type)
{-
  expr2null GramExpr
  returns a GramNull expression which indicates whether the GramExpr
  can derive the empty string.
-}

expr2null NullExpr = OneNull
expr2null (InpExpr inp_valu) = ZeroNull::(GramNull inp_type var_type)
expr2null (VarExpr var_valu) = (VarNull var_valu)::(GramNull inp_type 
var_type)

main = do
{ print Ident
; print Expr
; print (InpExpr Ident::GramExpr ArithInp ArithVar)
; print (VarExpr Expr::GramExpr ArithInp ArithVar)
; print ((InpExpr Ident :| VarExpr Factor)::GramExpr ArithInp ArithVar)
; print ((InpExpr Ident :>>VarExpr Factor)::GramExpr ArithInp ArithVar)
; print ((Factor :== InpExpr Ident)::GramProd ArithInp ArithVar)
; print ([ Factor :==
           (   InpExpr Ident
           :|  (   InpExpr ParenLeft
               :>> VarExpr Expr
               :>> InpExpr ParenRight
               )
           )
         , Term :==
           (   VarExpr Factor
           :>> InpExpr Mult
           :>> VarExpr Factor
           )
         , Expr :==
           (   VarExpr Term
           :>> InpExpr Plus
           :>> VarExpr Term
           )
         ]
         ::[GramProd ArithInp ArithVar])
         {-
           The above arg to print is the arithmetic expression grammar.
         -}

; print ((expr2null (InpExpr Mult))::(GramNull ArithInp ArithVar))
; print ((expr2null (VarExpr Factor))::(GramNull ArithInp ArithVar))
;}
...
--- gram_alg.hs ---
The compile output is:
<--- gram_alg.compile ---
Compilation started at Mon Sep  1 11:02:19
make -k
runghc -XMultiParamTypeClasses -XPatternSignatures gram_alg.hs

gram_alg.hs:62:40:
    Couldn't match expected type `var_type1'
           against inferred type `var_type'
      `var_type1' is a rigid type variable bound by
                  the polymorphic type
                    `forall inp_type var_type1. GramNull inp_type var_type1'
                    at gram_alg.hs:62:31
      `var_type' is a rigid type variable bound by
                 the type signature for `expr2null' at gram_alg.hs:53:32
    In the first argument of `VarNull', namely `var_valu'
    In the expression: (VarNull var_valu) :: GramNull inp_type var_type
    In the definition of `expr2null':
        expr2null (VarExpr var_valu)
                    = (VarNull var_valu) :: GramNull inp_type var_type
make: *** [all] Error 1
...
--- gram_alg.compile ---
TIA.

-regards,
Larry

[Haskell-beginners] Nullable attribute of a language grammar howto

Larry Evans