MOAL.languages.formal_language_theory.grammars package

Submodules

MOAL.languages.formal_language_theory.grammars.analytic_context_free module

class MOAL.languages.formal_language_theory.grammars.analytic_context_free.AnalyticContextFreeGrammar[source]
class MOAL.languages.formal_language_theory.grammars.analytic_context_free.InvalidStringLength[source]
class MOAL.languages.formal_language_theory.grammars.analytic_context_free.TDPLAnalyticCFG[source]

Bases: MOAL.languages.formal_language_theory.grammars.analytic_context_free.AnalyticContextFreeGrammar

For a formal definition and examples, see wikipedia.org/wiki/Top-down_parsing_language

static _evaluate_all(start, rules=[], terminals=[])[source]

Non-recursive simple function, for first iteration.

static adjacent_intersection(str1, str2)[source]
static evaluate(start, rules, terminals)[source]
static evaluate_with_defaults(start, nonterminals=['a', 'x', 'B', 'S', '#', 'b'], terminals=['!'], ruleset=None)[source]
static intersection(str1, str2)[source]
static test_grammar(times, start, **kwargs)[source]

MOAL.languages.formal_language_theory.grammars.attribute_context_free module

class MOAL.languages.formal_language_theory.grammars.attribute_context_free.AttributeContextFreeGrammar[source]

Bases: MOAL.languages.formal_language_theory.grammars.context_free.ContextFreeGrammar

An ACFG is effectively a CFG that allows attribute properties to be embedded in the ruleset for later evaluation – this is pedestrian to any programming language that supports data structures, but it all comes from these simple foundations.

For a formal definition and examples, see wikipedia.org/wiki/Attribute_grammar

__getitem__(attr)[source]
__init__()[source]
_attr(semantic_rule)[source]

Get the attribute name from the semantic rule. It comes in as a list of [object, attribute]

_chars(token)[source]
_len(token)[source]
_parse_terminal(attr, token)[source]

Parse a terminal value given a attribute and token.

For this example, we won’t get too fancy, just force a string on all values.

_prop(token)[source]
_value(token)[source]
evaluate(tokens, evaluation='')[source]

A basic parser for a custom attribute grammar.

One thing to note is that ambiguous grammars need to be iterated over, since the duplicate rules can’t be mapped via dictionary key. Unambiguous grammars are therefore more performant, because the lookup is O(1) vs. O(N).

MOAL.languages.formal_language_theory.grammars.backus_naur module

MOAL.languages.formal_language_theory.grammars.backus_naur.naive_bnf_parser(grammar)[source]

A parser for Backus Naur Form grammars, represented as a dictionaries.

Traditional Grammar example: <date> ::= <month> <day> <year> <month> ::= “January” | “February | “March” | “April” | “May” | “June”

“July” | “August” | “September” | “November” | “December”

<day> ::= 1.. | ..31 <year> ::= 100.. | ..9999

Here we need something that is a bit more serializable – so we’ll make it JSON friendly. Each parseable tokens is either a <rule> or syntax; rules represent containers, and can even have other rules!

‘name’: {‘date’, ‘is_rule’: True, ‘vals’: [‘month’, ‘day’, ‘year’]}, ‘name’: {‘month’, ‘is_rule’: False, ‘vals’: ‘...’}, ‘name’: {‘day’, ‘is_rule’: False, ‘vals’: ‘...’}, ‘name’: {‘year’, ‘is_rule’: False, ‘vals’: ‘...’},

<name> ::= <firstname> <lastname> <firstname> ::= ‘string’ <lastname> ::= ‘string’

‘name’: {‘name’, ‘is_rule’: True, ‘vals’: []}, ‘name’: {‘firstname’, ‘is_rule’: False, ‘vals’: ‘...’}, ‘name’: {‘lastname’, ‘is_rule’: False, ‘vals’: ‘...’},

Args:
grammar (dict) - the grammar and rules to use for evaluation.
MOAL.languages.formal_language_theory.grammars.backus_naur.rand_day()[source]
MOAL.languages.formal_language_theory.grammars.backus_naur.rand_fname()[source]
MOAL.languages.formal_language_theory.grammars.backus_naur.rand_lname()[source]
MOAL.languages.formal_language_theory.grammars.backus_naur.rand_year()[source]

MOAL.languages.formal_language_theory.grammars.context_free module

class MOAL.languages.formal_language_theory.grammars.context_free.ContextFreeGrammar[source]

Bases: object

__contains__(word)

Tests if a word can be created using the existing internal grammar and rules.

__delitem__(rule)
__init__()
_get_rule(token)
_is_terminal(char)
_is_terminal_or(char)
add_rule(string)
delete_rules()
delete_tokens()
evaluate(tokens=None, evaluation='')

A basic parser for a custom attribute grammar.

One thing to note is that ambiguous grammars need to be iterated over, since the duplicate rules can’t be mapped via dictionary key. Unambiguous grammars are therefore more performant, because the lookup is O(1) vs. O(N).

evaluate_single(token, nonterminals, evaluation='')

Recursively evaluates a single rule with a token and a given set of non-terminals

set_rules(rules)
set_tokens(tokens)
exception MOAL.languages.formal_language_theory.grammars.context_free.InvalidTokenSet[source]

Bases: exceptions.Exception

MOAL.languages.formal_language_theory.grammars.context_free.cp()[source]
MOAL.languages.formal_language_theory.grammars.context_free.cu()[source]

MOAL.languages.formal_language_theory.grammars.context_sensitive module

class MOAL.languages.formal_language_theory.grammars.context_sensitive.ContextSensitiveGrammar[source]

Bases: MOAL.languages.formal_language_theory.grammars.context_free.ContextFreeGrammar

DEBUG = True
__init__()
_evaluate(groups, evaluation='')
evaluate(tokens=None, evaluation='')

A basic parser for a custom attribute grammar.

One thing to note is that ambiguous grammars need to be iterated over, since the duplicate rules can’t be mapped via dictionary key. Unambiguous grammars are therefore more performant, because the lookup is O(1) vs. O(N).

static get_substr_match(rule, string)

Return the index of the last matching item of the two strings. e.g. index = 1 for ‘[ab]cd’ and ‘[ab]zd’. If the index is the same as the length then the strings simply match.

static simple_rule(rule, string='')