Safe Haskell	Safe-Inferred
Language	Haskell2010

CheckCFGAmbiguity

Description

(I assume you have read description at https://hackage.haskell.org/package/check-cfg-ambiguity .)

Example. Let's check grammar of expressions of form 1 + (2 + 3) for ambiguity.

>>> import CheckCFGAmbiguity
>>> import qualified Data.Map as M
>>> :{
checkAmbiguity (M.fromList [
  ("expr", [[N "term"],
            [N "expr", T "+", N "term"]]),
  ("term", [[T "number"],
            [T "(", N "expr", T ")"]])
]) "expr" 10
:}
SeemsUnambiguous

Synopsis

data TerminalOrNonterminal t n
- = T t
- | N n
checkAmbiguity :: (Ord n, Ord t) => Map n [[TerminalOrNonterminal t n]] -> n -> Int -> Result
data Result
- = WrongCount
- | NTNotFound
- | NoStart
- | EmptyLang
- | Ambiguous
- | SeemsUnambiguous

Documentation

data TerminalOrNonterminal t n Source #

Constructors

T t
N n

Instances

Instances details

(Show t, Show n) => Show (TerminalOrNonterminal t n) Source #
Instance details Defined in CheckCFGAmbiguity Methods showsPrec :: Int -> TerminalOrNonterminal t n -> ShowS # show :: TerminalOrNonterminal t n -> String # showList :: [TerminalOrNonterminal t n] -> ShowS #
(Eq t, Eq n) => Eq (TerminalOrNonterminal t n) Source #
Instance details Defined in CheckCFGAmbiguity Methods (==) :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> Bool # (/=) :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> Bool #
(Ord t, Ord n) => Ord (TerminalOrNonterminal t n) Source #
Instance details Defined in CheckCFGAmbiguity Methods compare :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> Ordering # (<) :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> Bool # (<=) :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> Bool # (>) :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> Bool # (>=) :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> Bool # max :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> TerminalOrNonterminal t n # min :: TerminalOrNonterminal t n -> TerminalOrNonterminal t n -> TerminalOrNonterminal t n #

checkAmbiguity Source #

Arguments

:: (Ord n, Ord t)
=> Map n [[TerminalOrNonterminal t n]]	Grammar (see example above)
-> n	Start nonterminal
-> Int	Count of steps. I don't try to document precise meaning of this argument
-> Result

Checks grammar for ambiguity (see example above). Before actual ambiguity checking this function checks that every nonterminal generates nonempty language. If some nonterminal generates empty language, this function reports this and doesn't do actual ambiguity checking

data Result Source #

Constructors

WrongCount	Count of steps is less than 1
NTNotFound	Some nonterminal from RHS is not found in LHS
NoStart	Start nonterminal is not found in LHS
EmptyLang	Some nonterminal generates empty language
Ambiguous	The grammar is 100% ambiguous (i. e. the library was able to find ambiguous string)
SeemsUnambiguous	The grammar seems to be unambiguous (i. e. the library was not able to find ambiguous string after specified number of steps)

Instances

Instances details

Show Result Source #
Instance details Defined in CheckCFGAmbiguity Methods showsPrec :: Int -> Result -> ShowS # show :: Result -> String # showList :: [Result] -> ShowS #
Eq Result Source #
Instance details Defined in CheckCFGAmbiguity Methods (==) :: Result -> Result -> Bool # (/=) :: Result -> Result -> Bool #
Ord Result Source #
Instance details Defined in CheckCFGAmbiguity Methods compare :: Result -> Result -> Ordering # (<) :: Result -> Result -> Bool # (<=) :: Result -> Result -> Bool # (>) :: Result -> Result -> Bool # (>=) :: Result -> Result -> Bool # max :: Result -> Result -> Result # min :: Result -> Result -> Result #

The following two grammars are from https://github.com/ollef/Earley/issues/54

>>> checkAmbiguity (Data.Map.fromList [("r1", [[T "A"], [N "r1"]])]) "r1" 10
Ambiguous

>>> checkAmbiguity (Data.Map.fromList [("r1", [[N "r1"], [T "A"]])]) "r1" 10
Ambiguous