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: 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 Version 4.12
Copyright © 2019 Alley Stoughton