-- A recursive-descent parser for computing the maximum of blocks

-- the type of tokens delivered by the scanner:
data Token = Assign | Begin | End | Seq -- for sequential composition
   deriving (Eq,Show)

-- Inherited attribute: d (depth of a block)
-- Synthesize attribute: m (maximum depth)
parse :: [Token] -> (Int,[Token])
parse ts = stm 1 ts

stm :: Int -> [Token] -> (Int,[Token])
stm d (t:ts) =
  case t of
    Seq -> let (m1,ts1) = stm d ts
               (m2,ts2) = stm d ts1
            in (max m1 m2, ts2)
    _   -> block d (t:ts)

block :: Int -> [Token] -> (Int,[Token])
block d (t:ts) =
  case t of
    Assign -> (d, ts)
    Begin  -> let (m,End:ts1) = stm (d+1) ts
               in (m,ts1)

main1 = parse [Seq, Assign, Begin, Assign, End]

main2 = parse [Seq, Assign, Begin, Seq, Begin, Assign, End, Assign, End]