Forlan Manual

The `Gram` Module

Synopsis

signature GRAM structure Gram :> GRAM

This module defines the abstract type of grammars.

Interface

type concr = {vars : Sym.sym Set.set, start : Sym.sym, prods : Prod.prod Set.set} type gram val valid : concr -> bool val fromConcr : concr -> gram val toConcr : gram -> concr val fromString : string -> gram val input : string -> gram val toPP : gram -> PP.pp val toString : gram -> string val output : string * gram -> unit val variables : gram -> Sym.sym Set.set val startVariable : gram -> Sym.sym val productions : gram -> Prod.prod Set.set val compare : gram Sort.total_ordering val equal : gram * gram -> bool val numVariables : gram -> int val numProductions : gram -> int val alphabet : gram -> Sym.sym Set.set val sub : gram * gram -> bool val checkPT : gram -> PT.pt -> unit val validPT : gram -> PT.pt -> bool val renameVariables : gram * SymRel.sym_rel -> gram val renameVariablesCanonically : gram -> gram val isomorphism : gram * gram * SymRel.sym_rel -> bool val findIsomorphismOpt : gram * gram -> SymRel.sym_rel option val findIsomorphism : gram * gram -> SymRel.sym_rel val isomorphic : gram * gram -> bool val renameAlphabet : gram * SymRel.sym_rel -> gram val parsable : gram -> Sym.sym * Str.str -> bool val generatedFromVariable : gram -> Sym.sym * Str.str -> bool val generated : gram -> Str.str -> bool val parseOpt : gram -> Sym.sym * Str.str -> PT.pt option val parse : gram -> Sym.sym * Str.str -> PT.pt val parseAlphabetFromVariableOpt : gram -> Sym.sym * Str.str -> PT.pt option val parseAlphabetFromVariable : gram -> Sym.sym * Str.str -> PT.pt val parseAlphabetOpt : gram -> Str.str -> PT.pt option val parseAlphabet : gram -> Str.str -> PT.pt val reachableFrom : gram -> Sym.sym Set.set -> Sym.sym Set.set val reachableFromBackwards : gram -> Sym.sym Set.set -> Sym.sym Set.set val reachify : gram -> gram val reachified : gram -> bool val simplify : gram -> gram val simplified : gram -> bool val eliminateVariable : gram * Sym.sym -> gram val eliminateVariableOpt : gram * Sym.sym -> gram option val eliminateVariableConstraints : gram * Sym.sym * int option * int option -> gram val eliminateVariableConstraintsOpt : gram * Sym.sym * int option * int option -> gram option val restart : gram -> gram val restartOpt : gram -> gram option val nullableVariables : gram -> Sym.sym Set.set val hasNoEmptyProductions : gram -> bool val eliminateEmptyProductions : gram -> gram val hasNoEmptyOrUnitProductions : gram -> bool val eliminateEmptyAndUnitProductions : gram -> gram val inChomskyNormalForm : gram -> bool val chomskyNormalForm : gram -> gram val toStrSetOpt : gram -> Str.str Set.set option val toStrSet : gram -> Str.str Set.set val emptyStr : gram val emptySet : gram val fromStr : Str.str -> gram val fromSym : Sym.sym -> gram val fromStrSet : Str.str Set.set -> gram val union : gram * gram -> gram val concat : gram * gram -> gram val closure : gram -> gram val genUnion : gram list -> gram val genConcat : gram list -> gram val fromFA : FA.fa -> gram val fromReg : Reg.reg -> gram val rev : gram -> gram val prefix : gram -> gram val inter : gram * EFA.efa -> gram val minus : gram * DFA.dfa -> gram

Description

type concr = {vars : Sym.sym Set.set, start : Sym.sym, prods : Prod.prod Set.set}

The concrete type of pre-grammars, records consisting of a finite set vars ("variables") of symbols, a symbol start ("start variable"), and a finite set prods ("productions") of productions.

type gram

The abstract type of grammars, consisting of those pre-grammars concr of type concr such that:

#start concr is an element of #vars concr; and
for all elements (q, bs) of #prods concr, q is an element of #vars concr.

We say that concr is valid iff concr satisfies the above conditions.

valid concr

tests whether conr is valid.

fromConcr concr

returns concr. Issues an error message if concr is not valid.

toConcr gram

returns gram.

fromString s

inputs a grammar from s.

input fil

inputs a grammar from the file named fil.

toPP gram

returns a pretty-printing expression for gram.

toString gram

pretty-prints gram to a string.

output(fil, gram)

pretty-prints gram to the file fil.

variables gram

returns the variables of gram.

startVariable gram

returns the start variable of gram.

productions gram

returns the productions of gram.

compare(gram1, gram2)

returns

  case SymSet.compare(variables gram1, variables gram2) of
       LESS    => LESS
     | EQUAL   =>
         (case Sym.compare(startVariable gram1, startVariable gram2) of
               LESS    => LESS
             | EQUAL   =>
                 ProdSet.compare(productions gram1, productions gram2)
             | GREATER => GREATER)
     | GREATER => GREATER

equal(gram1, gram2)

tests whether gram1 and gram2 are equal.

numVariables gram

returns the number of variables of gram.

numProductions gram

returns the number of productions of gram.

alphabet gram

returns the alphabet of gram.

sub(gram1, gram2)

tests whether gram1 is a sub-grammar of gram2.

checkPT gram pt

checks whether pt is valid for gram, silently returning (), if it is, and explaining why it isn't, if it's not.

validPT gram pt

tests whether pt is valid for gram.

renameVariables(gram, rel)

renames the variables of gram using the bijection rel. Issues an error message if rel isn't a bijection from the variables of gram to a set that's disjoint from the alphabet of gram.

renameVariablesCanonically gram

canonically renames the variables of gram.

isomorphism(gram1, gram2, rel)

tests whether rel is an isomorphism from gram1 to gram2.

findIsomorphismOpt(gram1, gram2)

returns SOME of an isomorhism from gram1 to gram2, if gram1 and gram2 are isomorphic, and NONE, if gram1 and gram2 are not isomorphic.

findIsomorphism(gram1, gram2)

tries to find an isomorphism from gram1 to gram2. Issues an error message if such an isomorphism doesn't exist.

isomorphic(gram1, gram2)

tests whether gram1 and gram2 are isomorphic.

renameAlphabet(gram, rel)

renames the alphabet of gram using the bijection rel. Issues an error message if rel is not a bijection from a superset of the alphabet of gram to some set.

parsableFrom gram (a, w)

tests whether w is parsable from a using gram.

generatedFromVariable gram (q, w)

tests whether w is generated from the variable q using gram. Issues an error message if q is not a variable of gram.

generated gram w

tests whether w is generated by gram.

parseOpt gram (a, w)

If w is a string over the union of the variables of gram and the alphabet of gram, and a is a variable of gram or a symbol of w, then parseOpt returns SOME of a minimal parse of w from a using gram, if such a parse exists, and NONE, if such a parse does not exist. Issues an error message if w has a symbol that is neither a variable of gram nor an element of the alphabet of gram, or if a is neither a variable of gram nor a symbol of w.

parse gram (a, w)

If w is a string over the union of the variables of gram and the alphabet of gram, and a is a variable of gram or a symbol of w, then parse tries to find a minimal parse of w from a using gram. Issues an error message if w has a symbol that is neither a variable of gram nor an element of the alphabet of gram, or if a is neither a variable of gram nor a symbol of w, or if such a parse doesn't exist.

parseAlphabetFromVariableOpt gram (q, w)

If q is a variable of gram and w is a string over the alphabet of gram, then parseAlphabetFromVariableOpt returns SOME of a minimal parse of w from q using gram, if such a parse exists, and NONE, if such a parse does not exist. Issues an error message if q is not a variable of gram, or w contains a symbol that isn't in the alphabet of gram.

parseAlphabetFromVariable gram (q, w)

If q is a variable of gram and w is a string over the alphabet of gram, then parseAlphabetFromVariable tries to find a minimal parse of w from q using gram. Issues an error message if q is not a variable of gram, or w contains a symbol that isn't in the alphabet of gram, or such a parse doesn't exist.

parseAlphabetOpt gram w

If w is a string over the alphabet of gram, then parseAlphabetOpt returns SOME of a minimal parse of w from the start variable of gram using gram, if such a parse exists, and NONE, if such a parse does not exist. Issues an error message if w contains a symbol that isn't in the alphabet of gram.

parseAlphabet gram w

If w is a string over the alphabet of gram, then parseAlphabet tries to find a minimal parse of w from the start variable of gram using gram. Issues an error message if w contains a symbol that isn't in the alphabet of gram, or such a parse doesn't exist.

reachableFrom gram qs

returns the set of variables of gram that are reachable from the variables qs. Issues an error message if qs contains a symbol that isn't a variable of gram.

reachableFromBackwards gram qs

returns the set of variables of gram that are backwards-reachable from the variables qs. Issues an error message if qs contains a symbol that isn't a variable of gram.

reachify gram

reachifies gram.

reachified gram

tests whether gram is reachified.

simplify gram

simplifies gram.

simplified gram

tests whether gram is simplified.

eliminateVariable(gram, q)

eliminates the variable q from gram, if this is possible, and issues an appropriate error message, otherwise.

eliminateVariableOpt(gram, q)

returns SOME gram', where gram' is the result of eliminating the variable q from gram, if this is possible, and returns NONE, otherwise.

eliminateVariableConstraints(gram, q, selfProdsMaxOpt, selfProdsSizeMaxOpt)

behaves like eliminateVariable(gram, q), but fails with an appropriate error message if, after simplification, the number of productions in the grammar involving q is more than selfProdsMaxOpt, or there is a production involving q whose right hand side has size bigger than selfProdsSizeMaxOpt.

eliminateVariableConstraintsOpt(gram, q, selfProdsMaxOpt, selfProdsSizeMaxOpt)

returns SOME gram', where gram' is the result of calling eliminateVariableConstraints with the same arguments, if that call terminates without an exception, and returns NONE, otherwise.

restart gram

If there is only one production involving the start variable st of gram, and that production is to a single variable q, then restart returns the result of eliminating that production (along with st), and making q be the new start variable; otherwise, restart issues an appropriate error message.

restartOpt gram

If there is only one production involving the start variable st of gram, and that production is to a single variable q, then

restartOpt
gram

returns SOME gram', where gram' is the result of eliminating that production (along with st), and making q be the new start variable; otherwise, restartOpt returns NONE.

nullableVariables gram

returns the set of nullable variables of gram.

hasNoEmptyProductions gram

tests whether gram has no empty productions.

eliminateEmptyProductions gram

convert gram to a grammar with no empty productions. (The new grammar will be equivalent to gram, except that it won't generate %, even if gram does.)

hasNoEmptyOrUnitProductions gram

tests whether gram has no empty or unit productions.

eliminateEmptyAndUnitProductions gr

convert gram to a grammar with no empty or unit productions. (The new grammar will be equivalent to gram, except that it won't generate %, even if gram does.)

inChomskyNormalForm gram

tests whether gram is in Chomsky Normal Form.

chomskyNormalForm gram

puts gram into Chomsky Normal Form. (The new grammar will be equivalent to gram, except that it won't generate %, even if gram does.)

toStrSetOpt gram

returns SOME of the language denoted by gram, if this language is finite, and NONE, if this language is infinite.

toStrSet gram

returns the language denoted by gram. Issues an error message if the language denoted by gram is infinite.

emptyStr

is the canonical empty string grammar.

emptySet

is the canonical empty set grammar.

fromStr x

returns the canonical grammar for x.

fromSym a

returns the canonical grammar for a.

fromStrSet xs

returns the canonical grammar for xs.

union(gram1, gram2)

returns the union of gram1 and gram2.

concat(gram1, gram2)

returns the concatentation of gram1 and gram2.

closure gram

returns the closure of gram.

genUnion

is defined by:

  fun genUnion nil             = emptySet
    | genUnion [gram]          = gram
    | genUnion (gram :: grams) = union(gram, genUnion grams)

genConcat

is defined by:

  fun genConcat nil             = emptyStr
    | genConcat [gram]          = gram
    | genConcat (gram :: grams) = concat(gram, genConcat grams)

fromFA fa

converts fa to a grammar.

fromReg reg

converts reg to a grammar.

rev gram

returns the reversal of gram.

prefix gram

returns the prefix-closure of gram.

inter(gram, efa)

returns the intersection of gram and efa.

minus(gram, dfa)

returns the difference of gram and dfa.

[ Top | Parent | Root | Contents | Index ]

Forlan Manual

The Gram Module

Synopsis

Interface

Description

The `Gram` Module