7.2.0. Building and Manipulating Grammars
 (lsh/libgraph/grammar.lsh)


functions for easily building grammars. The basic process consists in first building a grammar graph with null transitions (transitions matching no symbols) and then creating a graph without null transitions.

7.2.0.0. (NULL-PTR s)
 (lsh/libgraph/grammar.lsh)


RETURNS: t if s is (). CREATED: P.Haffner

7.2.0.1. Macros for Typing Labels
 (lsh/libgraph/grammar.lsh)



7.2.0.1.0. (LAB-ASCII str)
 (lsh/libgraph/grammar.lsh)


Label for an ASCII character

7.2.0.1.1. (LAB-NULL)
 (lsh/libgraph/grammar.lsh)


Label for the null transition

7.2.0.1.2. (LAB-MARKER string)
 (lsh/libgraph/grammar.lsh)


Label for marker links (e.g. field markers, junk markers, etc..) Argument str must be a 2 character string.

7.2.0.1.3. (LAB-WILD)
 (lsh/libgraph/grammar.lsh)


Label for matching any data with a reasonable score This is a "wildcard" label used for matching meaningful punctuations.

7.2.0.1.4. (LAB-JUNK)
 (lsh/libgraph/grammar.lsh)


Label for matching any data with a quite poor score This is a "junk" label for matching meaningless subimages before or after the interesting point.

7.2.0.1.5. (LAB-SKIP)
 (lsh/libgraph/grammar.lsh)


Label for matching any character, without calling the recognizer The default score will be 0

7.2.0.2. Gset: Multiple Sets of Integers
 (lsh/libgraph/grammar.lsh)



7.2.0.2.0. GMultiIntSet
 (lsh/libgraph/grammar.lsh)


This class represents efficiently a collection of sets of integers. This is used by the new version of gram-cleanup . Extra documentation will be added later...

7.2.0.3. Grammar Cleanup and Optimization
 (lsh/libgraph/grammar.lsh)



7.2.0.3.0. (gram-cleanup graph)
 (lsh/libgraph/grammar.lsh)


Returns a new graph containing no null transition and implementing the same grammar than graph .

7.2.0.4. Functions for Building Grammars
 (lsh/libgraph/grammar.lsh)



7.2.0.4.0. gram-or, gram-cat, gram-some, gram-many, gram-maybe
 (lsh/libgraph/grammar.lsh)


These functions allow for easily building grammars from regular expression style operators.

All these function take an arbitrary number of arguments which may be integer labels (using LAB macros), one character strings or complete grammars.

The resulting grammar may contain null transitions whose label is provided by macro LAB-NULL . These transitions must be removed using function gram-cleanup . 

 
(setq gr-digstring 
   (gram-some (gram-or (LAB-ASCII "0") 
                         (LAB-ASCII "1") )))
(setq gr-number 
   (gram-cat gr-digstring 
               (gram-maybe  "." gr-digstring) ) )
(setq grammar-for-numbers
   (gram-cleanup gr-number) )

7.2.0.4.1. gram2-or, gram2-some
 (lsh/libgraph/grammar.lsh)


These are optimizations of gram-or and gram-some devised by Patrick. Do not use before inquiring PH about limitations and potential headaches.

7.2.0.5. Setting the Penalties/Cost of Edges
 (lsh/libgraph/grammar.lsh)



7.2.0.5.0. (gram-penalty cost grammar)
 (lsh/libgraph/grammar.lsh)


Sets a cost penalty to all paths traversing a particular grammar. The cost will be added to the costs of all links arrving on the endnode. We assume that grammar grammar contains no null paths (i.e. paths between the startnode and the endnode with null transitions only).

7.2.0.6. Converting Grammar Paths to Strings
 (lsh/libgraph/grammar.lsh)



7.2.0.6.0. (gram-meaning meaning grammar)
 (lsh/libgraph/grammar.lsh)


Override the meaning fields in grammar grammar . Only one link in every path in grammar grammar will have a meaning equal to meaning . All other links will have a null meaning.

Note: The resulting grammar may be cleaned up using gram-cleanup .


7.2.0.7. Conversion from Regular Grammar to Matrix Representation
 (lsh/libgraph/grammar.lsh)



7.2.0.7.0. (grammar-to-matrix mat)
 (lsh/libgraph/grammar.lsh)


This function encodes a grammar into a matrix.

7.2.0.7.1. (matrix-to-grammar mat)
 (lsh/libgraph/grammar.lsh)


This function decodes a grammar encoded with grammar-to-matrix .

7.2.0.7.2. (gram-static lispgrammar)
 (lsh/libgraph/grammar.lsh)


Use this macro in compiled code to refer to a grammar defined by a lisp expression lispgrammar evaluated at compile time. This macro expand into a call to matrix-to-grammar on a static matrix.

7.2.0.8. Converting Strings to Label Sequences
 (lsh/libgraph/grammar.lsh)



7.2.0.8.0. (string-to-labels s)
 (lsh/libgraph/grammar.lsh)


Returns a matrix of integers containing the ascii codes of string s .

7.2.0.8.1. (labels-to-string im)
 (lsh/libgraph/grammar.lsh)


Returns a string made with characters whose ascii codes are in matrix im . Illegal ascii codes are marked with string "[?]".

7.2.0.9. Testing Label Sequences Against a Grammar
 (lsh/libgraph/grammar.lsh)



7.2.0.9.0. (gram-match grammar labels)
 (lsh/libgraph/grammar.lsh)


Returns t if labels in idx1 labels match grammar grammar .

7.2.0.10. Handling Trivgraphs
 (lsh/libgraph/grammar.lsh)



7.2.0.10.0. (count-labels graphin)
 (lsh/libgraph/grammar.lsh)


count the number of links with labels in a trivial graph

7.2.0.10.1. (count-meanings graphin)
 (lsh/libgraph/grammar.lsh)


count the number of links with meanings in a trivial graph

7.2.0.10.2. (trivgraph-to-labels graphin)
 (lsh/libgraph/grammar.lsh)


This function returns an integer vector containing value of slots label for each link in the single path of trivial graph graphin . This function returns a matrix with a single element equal to -1 when the graph contains no path.

7.2.0.10.3. (trivgraph-to-meanings graphin)
 (lsh/libgraph/grammar.lsh)


This function returns an integer vector containing value of slots meaning for each link in the single path of trivial graph graphin . Links whose slot meaning contains (LAB-NULL) are discarded. This function returns a matrix with a single element equal to -1 when the graph contains no meaningful path.

7.2.0.10.4. (trivgraph-to-data graphin)
 (lsh/libgraph/grammar.lsh)


This function returns a gptr vector containing value of slots data for each link in the single path of trivial graph graphin .

7.2.0.10.5. (trivgraph-to-costs graphin scores)
 (lsh/libgraph/grammar.lsh)


((-obj- (GGraph)) graphin):
((-idx1- (-flt-)) scores):
CREATED: P.Haffner
COMPILABLE: Yes
DESCRIPTION: This function just copies the scores of the meaningful links
of trivial graph <graph> into matrix <scores>. It does not apply the
squashing function applied by <trivgraph-to-scores>.

7.2.0.10.6. (trivgraph-to-meaningful-costs graph scores)
 (lsh/libgraph/grammar.lsh)


This function just copies the scores of the meaningful links of trivial graph graph into matrix scores . It does not apply the squashing function applied by trivgraph-to-meaningful-costs .

7.2.0.10.7. (trivgraph-to-scores graph scores)
 (lsh/libgraph/grammar.lsh)


This function copies the squashed scores of the links of trivial graph graph into matrix scores .

7.2.0.10.8. (trivgraph-to-meaningful-scores graph scores)
 (lsh/libgraph/grammar.lsh)


This function copies the squashed scores of the meaningful links of trivial graph graph into matrix scores .

7.2.0.11. Selecting Path that Produce a Particular Label Sequence
 (lsh/libgraph/grammar.lsh)



7.2.0.11.0. (g-restrict-to-meanings graph meanings)
 (lsh/libgraph/grammar.lsh)


Creates a new graph which implements the subset of paths of graph graph whose links with non null meanings implement the meanings given in the integer matrix meaning . The links of the new graph have the same cost, label, meaning and data than the original links.

(This code is derived from g-compose )


7.2.0.11.1. (g-restrict-to-meanings-2 graph labels)
 (lsh/libgraph/grammar.lsh)


See: (g-restrict-to-meanings graph labels )
This function is similat to g-restrict-to-meanings . However the data fields of the restricted graph point to the original link instead of to the data pointed to by the original link.

7.2.0.11.2. (g-restrict-to-labels graph labels)
 (lsh/libgraph/grammar.lsh)


Creates a new graph which implements the subset of paths of graph graph whose links implement the labels given in the integer matrix meaning . The links of the new graph have the same cost, label, meaning and data than the original links.

(This code is derived from g-compose )


7.2.0.11.3. (g-restrict-to-labels-2 graph labels)
 (lsh/libgraph/grammar.lsh)


See: (g-restrict-to-labels graph labels )
This function is similat to g-restrict-to-labels . However the data fields of the restricted graph point to the original link instead of to the data pointed to by the original link.

7.2.0.12. Additional Grammar Functions
 (lsh/libgraph/grammar.lsh)



7.2.0.12.0. (lab-to-str lab)
 (lsh/libgraph/grammar.lsh)


((-int-) lab):
RETURNS: a string of 1 or 4 characters
CREATED: P.Haffner
COMPILABLE: Yes
DESCRIPTION: transcodes an integer into a string of one or 2 characters.
(2 characters are returned between brackets)
See: (str-to-lab s )

7.2.0.12.1. (str-to-lab s)
 (lsh/libgraph/grammar.lsh)


((-str-) s):
RETURNS: integer
CREATED: P.Haffner
COMPILABLE: Yes
DESCRIPTION: Transcodes a 1 or 2 character string into an integer
See: (lab-to-str lab )

7.2.0.12.2. (gram-match-meaning grammar meanings)
 (lsh/libgraph/grammar.lsh)


Returns t if meanings in idx1 meanings match grammar grammar .

7.2.0.12.3. (gram-match-string grammar <list of strings>)
 (lsh/libgraph/grammar.lsh)


for each string in the list, check it it can be generated as meanings of the graph grammar

7.2.0.12.4. (string-to-labels2 s)
 (lsh/libgraph/grammar.lsh)


Returns a matrix of integers containing the ascii codes of string s . Unlike straing-to-labels, brackets [xx] means double ascii codes.
See: (string-to-labels s )

7.2.0.12.5. (labels-to-string2 im)
 (lsh/libgraph/grammar.lsh)


Returns a string made with characters whose ascii codes are in matrix im . Unlike labels-to-string, double ascii codes are quoted in brackets [xx].
See: (labels-to-string im )

7.2.0.13. Graph Analysis
 (lsh/libgraph/grammar.lsh)



7.2.0.13.0. (g-complexity graph)
 (lsh/libgraph/grammar.lsh)


((-obj- (GGraph)) graph):
CREATED: P.Haffner
COMPILABLE: Yes
DESCRIPTION: display useful information about a graph
- number of nodes
- number of links
- number of links for different labels
- perpexity.