FAdo.cgf

Context Free Grammars Manipulation.

Basic context-free grammars manipulation for building uniform random generetors

class CFGGenerator(cfgr, size)[source]

CFG uniform genetaror

..seealso: Generating words in a context-free language uniformly at random. Harry Mairson

Information Processing Letters, 49-2, 95-92. 1994

Object initialization :param cfgr: grammar for the random objects :type cfgr: CNF :param size: size of objects :type size: integer

generate()[source]

Generates a new random object generated from the start symbol

Returns:

object

Return type:

string

class CFGrammar(gram)[source]

Class for context-free grammars

Variables:

  • Rules – grammar rules

  • Terminals – terminals symbols

  • Nonterminals – nonterminals symbols

  • Start (str) – start symbol

  • ntr – dictionary of rules for each nonterminal

Initialization

Parameters:

gram – is a list for productions; each production is a tuple (LeftHandside, RightHandside) with LeftHandside nonterminal, RightHandside list of symbols, First production is for start symbol

NULLABLE()[source]

Determines which nonterminals X ->* []

makenonterminals()[source]

Extracts C{nonterminals} from grammar rules.

maketerminals()[source]

Extracts C{terminals} from the rules. Nonterminals must already exist

class CNF(gram, mark='A@')[source]

Chomsky Normal Form. No useless nonterminals or eepsipsilon rules are ALLOWED… Given a CFG grammar description generates one in CNF Then its possible to random generate words of a given size. Before some pre-calculations are needed.

Initialization

Parameters:

gram – is a list for productions; each production is a tuple (LeftHandside, RightHandside) with LeftHandside nonterminal, RightHandside list of symbols, First production is for start symbol

chomsky()[source]

Transform to CNF

elim_unitary()[source]

Elimination of unitary rules

CYKParserTable(gramm, word)[source]

Evaluates CYK parser table

Parameters:

  • gramm (CNF) – grammar

  • word (str) – word to be parsed

Returns:

the CYK table

Return type:

list of lists of symbols

class REStringRGenerator(Sigma=None, size=10, cfgr=None, epsilon=None, empty=None, ident='Ti')[source]

Uniform random Generator for reStrings

Uniform random generator for regular expressions. Used without arguments generates an uncollapsible re

over {a,b} with size 10. For generate an arbitary re over an alphabet of 10 symbols of size 100: reStringRGenerator (smallAlphabet(10),100,reGrammar[“g_regular_base”])

Parameters:

  • Sigma (list|set) – re alphabet (that will be the set of grammar terminals)

  • size (int) – word size

  • cfgr – base grammar

  • epsilon – if not None is added to a grammar terminals

  • empty – if not None is added to a grammar terminals

Note

the grammar can have already this symbols

gRules(rules_list, rulesym='->', rhssep=None, rulesep='|')[source]

Transforms a list of rules into a grammar description.

Parameters:

  • rules_list (list) – is a list of rule where rule is a string of the form: Word rulesym Word1 … Word2 or Word rulesym []

  • rulesym (str) – LHS and RHS rule separator

  • rhssep (str) – RHS values separator (None for white chars)

  • rulesep (str) – rule separator

Returns:

a grammar description

Return type:

list

smallAlphabet(k, sigma_base='a')[source]

Easy way to have small alphabets

Parameters:

  • k – alphabet size (must be less than 52)

  • sigma_base – initial symbol

Returns:

alphabet

Return type:

list