IsChainNT.hs

{-  Copyright 2010 Dominique Devriese

    This file is part of the grammar-combinators library.

    The grammar-combinators library is free software: you can
    redistribute it and/or modify it under the terms of the GNU
    Lesser General Public License as published by the Free
    Software Foundation, either version 3 of the License, or (at
    your option) any later version.

    Foobar is distributed in the hope that it will be useful, but
    WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General
    Public License along with Foobar. If not, see
    <http://www.gnu.org/licenses/>.
-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}

module Text.GrammarCombinators.Utils.IsChainNT (
  isChainNT
  ) where

import Text.GrammarCombinators.Base

-- A rule is a chain rule if it is a sequence of epsilons followed by
-- a single reference to another NT, possibly followed by more epsilons
data IsChainNT (phi :: * -> *) (r :: * -> *) t rr v = MkITR {
  ruleIsEpsilon :: Bool,
  ruleIsChain :: Bool
  }

instance ProductionRule (IsChainNT phi r t rr) where
  ra >>> rb = 
    let eps = ruleIsEpsilon ra && ruleIsEpsilon rb
        chain = ruleIsChain ra && ruleIsEpsilon rb ||
               ruleIsChain rb && ruleIsEpsilon ra
    in MkITR eps chain
  _ ||| _ = MkITR False False
  die = MkITR False False
  endOfInput = MkITR False False

instance EpsProductionRule (IsChainNT phi r t rr) where
  epsilon _ = MkITR True False

instance LiftableProductionRule (IsChainNT phi r t rr) where
  epsilonL _ _ = MkITR True False

instance TokenProductionRule (IsChainNT phi r t rr) t where
  token _ = MkITR False False
  anyToken = MkITR False False

instance (EqFam phi) => RecProductionRule (IsChainNT phi r t rr) phi r where
  ref _ = MkITR False True

instance (EqFam phi) => LoopProductionRule (IsChainNT phi r t rr) phi r where
  manyRef _ = MkITR False False

-- | Detect if a given non-terminal in a given extended context free 
-- grammar is a chain non-terminal. An NT is a chain NT if all of
-- its productions are chain rules.
isChainNT :: (EqFam phi) => GExtendedContextFreeGrammar phi t r rr -> phi idx -> Bool
isChainNT gram idx = ruleIsChain (gram idx)