KaneAI - World’s First E2E Software Testing Agent.Book a Demo 
How to use nonterminal method in avocado
Best Python code snippet using avocado_python
first_and_follow.py
Source:first_and_follow.py 
...21 def __compute_first__(nt: Nonterminal):22 if nt in computed_already:23 return24 nt_first = set()25 for pr in self.__grammar.get_production_rules_by_lhs_nonterminal(nt):26 for symbol in pr.rhs:27 if isinstance(symbol, Epsilon) or isinstance(symbol, Terminal):28 nt_first.add(symbol)29 break30 elif isinstance(symbol, Nonterminal) and symbol != nt:31 if symbol not in computed_already:32 __compute_first__(symbol)33 s_first = self.get_first_of_nonterminal(symbol).copy()34 if epsilon not in s_first:35 nt_first = nt_first.union(s_first)36 break37 else:38 s_first.remove(epsilon)39 nt_first = nt_first.union(s_first)40 if symbol == pr.rhs[-1]:41 if pr.lhs not in computed_already and pr.lhs != nt:42 __compute_first__(pr.lhs)43 lhs_first = self.get_first_of_nonterminal(pr.lhs).copy()44 if len(lhs_first) == 0:45 nt_first.add(Epsilon())46 else:47 nt_first = nt_first.union(lhs_first)48 computed_already.add(nt)49 self.__first[nt] = nt_first50 epsilon = Epsilon()51 computed_already = set()52 for nonterminal in self.__grammar.nonterminals:53 __compute_first__(nonterminal)54 def __compute_follow(self):55 def __split_rhs_by_duplicate_nonterminal__(pr: ProductionRule, nt: Nonterminal):56 counter = 057 for s in pr.rhs:58 if s == nt:59 counter += 160 if counter == 1:61 return [pr]62 prs = []63 rhs = []64 for i in range(len(pr.rhs) - 1, -1, -1):65 rhs.insert(0, pr.rhs[i])66 if pr.rhs[i] == nt:67 prs.append(ProductionRule(pr.lhs, rhs[:]))68 return prs69 def __compute_follow__(nt: Nonterminal):70 if nt in computed_already:71 return72 nt_follow = self.get_follow_of_nonterminal(nt) # $ is added beforehand73 for pr in self.__grammar.get_production_rules_by_rhs_nonterminal(nt):74 for __pr__ in __split_rhs_by_duplicate_nonterminal__(pr, nt):75 found_nt = False76 rhs = []77 for symbol in __pr__.rhs:78 if found_nt:79 rhs.append(symbol)80 if symbol == nt:81 found_nt = True82 check_lhs = True83 for symbol in rhs:84 if isinstance(symbol, Terminal):85 nt_follow.add(symbol)86 check_lhs = False87 break88 elif isinstance(symbol, Nonterminal):89 s_first = self.get_first_of_nonterminal(symbol).copy()90 if epsilon not in s_first:91 nt_follow = nt_follow.union(s_first)92 if symbol != rhs[-1]:93 check_lhs = False94 break95 else:96 s_first.remove(epsilon)97 nt_follow = nt_follow.union(s_first)98 check_lhs = True99 if check_lhs:100 if __pr__.lhs not in computed_already and __pr__.lhs != nt:101 __compute_follow__(__pr__.lhs)102 lhs_follow = self.get_follow_of_nonterminal(__pr__.lhs).copy()103 nt_follow = nt_follow.union(lhs_follow)104 computed_already.add(nt)105 self.__follow[nt] = nt_follow106 epsilon = Epsilon()107 computed_already = set()108 self.__follow[self.__grammar.start_symbol] = {Dollar()}109 for nonterminal in self.__grammar.nonterminals:110 __compute_follow__(nonterminal)111 # region Getters112 @property113 def first(self) -> Dict[Nonterminal, Set[Symbol]]:114 return self.__first115 @property116 def follow(self) -> Dict[Nonterminal, Set[Symbol]]:117 return self.__follow118 # endregion119 def __repr__(self):120 newline = '\n'121 return f"=== First ===\n{newline.join([repr(entry) for entry in self.__first.items()])}\n\n" \122 f"=== Follow ===\n{newline.join([repr(entry) for entry in self.__follow.items()])} "123 def __str__(self):124 return repr(self)125 def get_first_of_nonterminal(self, nonterminal: Nonterminal) -> Set[Symbol]:126 if nonterminal in self.__first:127 return self.__first[nonterminal]128 return set()129 def get_follow_of_nonterminal(self, nonterminal: Nonterminal) -> Set[Symbol]:130 if nonterminal in self.__follow:131 return self.__follow[nonterminal]132 return set()133@pytest.mark.parametrize(134 "grammar,first,follow",135 [136 (137 Grammar(138 [139 Nonterminal('S'),140 Nonterminal('B'),141 Nonterminal('D'),142 Nonterminal('C'),143 Nonterminal('E'),...
generator.py
Source:generator.py
1# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved.2# Licensed to PSF under a Contributor Agreement.3# Modifications:4# Copyright David Halter and Contributors5# Modifications are dual-licensed: MIT and PSF.6"""7This module defines the data structures used to represent a grammar.8Specifying grammars in pgen is possible with this grammar::9 grammar: (NEWLINE | rule)* ENDMARKER10 rule: NAME ':' rhs NEWLINE11 rhs: items ('|' items)*12 items: item+13 item: '[' rhs ']' | atom ['+' | '*']14 atom: '(' rhs ')' | NAME | STRING15This grammar is self-referencing.16This parser generator (pgen2) was created by Guido Rossum and used for lib2to3.17Most of the code has been refactored to make it more Pythonic. Since this was a18"copy" of the CPython Parser parser "pgen", there was some work needed to make19it more readable. It should also be slightly faster than the original pgen2,20because we made some optimizations.21"""22from ast import literal_eval23from typing import TypeVar, Generic, Mapping, Sequence, Set, Union24from parso.pgen2.grammar_parser import GrammarParser, NFAState25_TokenTypeT = TypeVar("_TokenTypeT")26class Grammar(Generic[_TokenTypeT]):27 """28 Once initialized, this class supplies the grammar tables for the29 parsing engine implemented by parse.py. The parsing engine30 accesses the instance variables directly.31 The only important part in this parsers are dfas and transitions between32 dfas.33 """34 def __init__(self,35 start_nonterminal: str,36 rule_to_dfas: Mapping[str, Sequence['DFAState[_TokenTypeT]']],37 reserved_syntax_strings: Mapping[str, 'ReservedString']):38 self.nonterminal_to_dfas = rule_to_dfas39 self.reserved_syntax_strings = reserved_syntax_strings40 self.start_nonterminal = start_nonterminal41class DFAPlan:42 """43 Plans are used for the parser to create stack nodes and do the proper44 DFA state transitions.45 """46 def __init__(self, next_dfa: 'DFAState', dfa_pushes: Sequence['DFAState'] = []):47 self.next_dfa = next_dfa48 self.dfa_pushes = dfa_pushes49 def __repr__(self):50 return '%s(%s, %s)' % (self.__class__.__name__, self.next_dfa, self.dfa_pushes)51class DFAState(Generic[_TokenTypeT]):52 """53 The DFAState object is the core class for pretty much anything. DFAState54 are the vertices of an ordered graph while arcs and transitions are the55 edges.56 Arcs are the initial edges, where most DFAStates are not connected and57 transitions are then calculated to connect the DFA state machines that have58 different nonterminals.59 """60 def __init__(self, from_rule: str, nfa_set: Set[NFAState], final: NFAState):61 assert isinstance(nfa_set, set)62 assert isinstance(next(iter(nfa_set)), NFAState)63 assert isinstance(final, NFAState)64 self.from_rule = from_rule65 self.nfa_set = nfa_set66 # map from terminals/nonterminals to DFAState67 self.arcs: Mapping[str, DFAState] = {}68 # In an intermediary step we set these nonterminal arcs (which has the69 # same structure as arcs). These don't contain terminals anymore.70 self.nonterminal_arcs: Mapping[str, DFAState] = {}71 # Transitions are basically the only thing that the parser is using72 # with is_final. Everyting else is purely here to create a parser.73 self.transitions: Mapping[Union[_TokenTypeT, ReservedString], DFAPlan] = {}74 self.is_final = final in nfa_set75 def add_arc(self, next_, label):76 assert isinstance(label, str)77 assert label not in self.arcs78 assert isinstance(next_, DFAState)79 self.arcs[label] = next_80 def unifystate(self, old, new):81 for label, next_ in self.arcs.items():82 if next_ is old:83 self.arcs[label] = new84 def __eq__(self, other):85 # Equality test -- ignore the nfa_set instance variable86 assert isinstance(other, DFAState)87 if self.is_final != other.is_final:88 return False89 # Can't just return self.arcs == other.arcs, because that90 # would invoke this method recursively, with cycles...91 if len(self.arcs) != len(other.arcs):92 return False93 for label, next_ in self.arcs.items():94 if next_ is not other.arcs.get(label):95 return False96 return True97 def __repr__(self):98 return '<%s: %s is_final=%s>' % (99 self.__class__.__name__, self.from_rule, self.is_final100 )101class ReservedString:102 """103 Most grammars will have certain keywords and operators that are mentioned104 in the grammar as strings (e.g. "if") and not token types (e.g. NUMBER).105 This class basically is the former.106 """107 def __init__(self, value: str):108 self.value = value109 def __repr__(self):110 return '%s(%s)' % (self.__class__.__name__, self.value)111def _simplify_dfas(dfas):112 """113 This is not theoretically optimal, but works well enough.114 Algorithm: repeatedly look for two states that have the same115 set of arcs (same labels pointing to the same nodes) and116 unify them, until things stop changing.117 dfas is a list of DFAState instances118 """119 changes = True120 while changes:121 changes = False122 for i, state_i in enumerate(dfas):123 for j in range(i + 1, len(dfas)):124 state_j = dfas[j]125 if state_i == state_j:126 del dfas[j]127 for state in dfas:128 state.unifystate(state_j, state_i)129 changes = True130 break131def _make_dfas(start, finish):132 """133 Uses the powerset construction algorithm to create DFA states from sets of134 NFA states.135 Also does state reduction if some states are not needed.136 """137 # To turn an NFA into a DFA, we define the states of the DFA138 # to correspond to *sets* of states of the NFA. Then do some139 # state reduction.140 assert isinstance(start, NFAState)141 assert isinstance(finish, NFAState)142 def addclosure(nfa_state, base_nfa_set):143 assert isinstance(nfa_state, NFAState)144 if nfa_state in base_nfa_set:145 return146 base_nfa_set.add(nfa_state)147 for nfa_arc in nfa_state.arcs:148 if nfa_arc.nonterminal_or_string is None:149 addclosure(nfa_arc.next, base_nfa_set)150 base_nfa_set = set()151 addclosure(start, base_nfa_set)152 states = [DFAState(start.from_rule, base_nfa_set, finish)]153 for state in states: # NB states grows while we're iterating154 arcs = {}155 # Find state transitions and store them in arcs.156 for nfa_state in state.nfa_set:157 for nfa_arc in nfa_state.arcs:158 if nfa_arc.nonterminal_or_string is not None:159 nfa_set = arcs.setdefault(nfa_arc.nonterminal_or_string, set())160 addclosure(nfa_arc.next, nfa_set)161 # Now create the dfa's with no None's in arcs anymore. All Nones have162 # been eliminated and state transitions (arcs) are properly defined, we163 # just need to create the dfa's.164 for nonterminal_or_string, nfa_set in arcs.items():165 for nested_state in states:166 if nested_state.nfa_set == nfa_set:167 # The DFA state already exists for this rule.168 break169 else:170 nested_state = DFAState(start.from_rule, nfa_set, finish)171 states.append(nested_state)172 state.add_arc(nested_state, nonterminal_or_string)173 return states # List of DFAState instances; first one is start174def _dump_nfa(start, finish):175 print("Dump of NFA for", start.from_rule)176 todo = [start]177 for i, state in enumerate(todo):178 print(" State", i, state is finish and "(final)" or "")179 for arc in state.arcs:180 label, next_ = arc.nonterminal_or_string, arc.next181 if next_ in todo:182 j = todo.index(next_)183 else:184 j = len(todo)185 todo.append(next_)186 if label is None:187 print(" -> %d" % j)188 else:189 print(" %s -> %d" % (label, j))190def _dump_dfas(dfas):191 print("Dump of DFA for", dfas[0].from_rule)192 for i, state in enumerate(dfas):193 print(" State", i, state.is_final and "(final)" or "")194 for nonterminal, next_ in state.arcs.items():195 print(" %s -> %d" % (nonterminal, dfas.index(next_)))196def generate_grammar(bnf_grammar: str, token_namespace) -> Grammar:197 """198 ``bnf_text`` is a grammar in extended BNF (using * for repetition, + for199 at-least-once repetition, [] for optional parts, | for alternatives and ()200 for grouping).201 It's not EBNF according to ISO/IEC 14977. It's a dialect Python uses in its202 own parser.203 """204 rule_to_dfas = {}205 start_nonterminal = None206 for nfa_a, nfa_z in GrammarParser(bnf_grammar).parse():207 # _dump_nfa(nfa_a, nfa_z)208 dfas = _make_dfas(nfa_a, nfa_z)209 # _dump_dfas(dfas)210 # oldlen = len(dfas)211 _simplify_dfas(dfas)212 # newlen = len(dfas)213 rule_to_dfas[nfa_a.from_rule] = dfas214 # print(nfa_a.from_rule, oldlen, newlen)215 if start_nonterminal is None:216 start_nonterminal = nfa_a.from_rule217 reserved_strings: Mapping[str, ReservedString] = {}218 for nonterminal, dfas in rule_to_dfas.items():219 for dfa_state in dfas:220 for terminal_or_nonterminal, next_dfa in dfa_state.arcs.items():221 if terminal_or_nonterminal in rule_to_dfas:222 dfa_state.nonterminal_arcs[terminal_or_nonterminal] = next_dfa223 else:224 transition = _make_transition(225 token_namespace,226 reserved_strings,227 terminal_or_nonterminal228 )229 dfa_state.transitions[transition] = DFAPlan(next_dfa)230 _calculate_tree_traversal(rule_to_dfas)231 return Grammar(start_nonterminal, rule_to_dfas, reserved_strings) # type: ignore232def _make_transition(token_namespace, reserved_syntax_strings, label):233 """234 Creates a reserved string ("if", "for", "*", ...) or returns the token type235 (NUMBER, STRING, ...) for a given grammar terminal.236 """237 if label[0].isalpha():238 # A named token (e.g. NAME, NUMBER, STRING)239 return getattr(token_namespace, label)240 else:241 # Either a keyword or an operator242 assert label[0] in ('"', "'"), label243 assert not label.startswith('"""') and not label.startswith("'''")244 value = literal_eval(label)245 try:246 return reserved_syntax_strings[value]247 except KeyError:248 r = reserved_syntax_strings[value] = ReservedString(value)249 return r250def _calculate_tree_traversal(nonterminal_to_dfas):251 """252 By this point we know how dfas can move around within a stack node, but we253 don't know how we can add a new stack node (nonterminal transitions).254 """255 # Map from grammar rule (nonterminal) name to a set of tokens.256 first_plans = {}257 nonterminals = list(nonterminal_to_dfas.keys())258 nonterminals.sort()259 for nonterminal in nonterminals:260 if nonterminal not in first_plans:261 _calculate_first_plans(nonterminal_to_dfas, first_plans, nonterminal)262 # Now that we have calculated the first terminals, we are sure that263 # there is no left recursion.264 for dfas in nonterminal_to_dfas.values():265 for dfa_state in dfas:266 transitions = dfa_state.transitions267 for nonterminal, next_dfa in dfa_state.nonterminal_arcs.items():268 for transition, pushes in first_plans[nonterminal].items():269 if transition in transitions:270 prev_plan = transitions[transition]271 # Make sure these are sorted so that error messages are272 # at least deterministic273 choices = sorted([274 (275 prev_plan.dfa_pushes[0].from_rule276 if prev_plan.dfa_pushes277 else prev_plan.next_dfa.from_rule278 ),279 (280 pushes[0].from_rule281 if pushes else next_dfa.from_rule282 ),283 ])284 raise ValueError(285 "Rule %s is ambiguous; given a %s token, we "286 "can't determine if we should evaluate %s or %s."287 % (288 (289 dfa_state.from_rule,290 transition,291 ) + tuple(choices)292 )293 )294 transitions[transition] = DFAPlan(next_dfa, pushes)295def _calculate_first_plans(nonterminal_to_dfas, first_plans, nonterminal):296 """297 Calculates the first plan in the first_plans dictionary for every given298 nonterminal. This is going to be used to know when to create stack nodes.299 """300 dfas = nonterminal_to_dfas[nonterminal]301 new_first_plans = {}302 first_plans[nonterminal] = None # dummy to detect left recursion303 # We only need to check the first dfa. All the following ones are not304 # interesting to find first terminals.305 state = dfas[0]306 for transition, next_ in state.transitions.items():307 # It's a string. We have finally found a possible first token.308 new_first_plans[transition] = [next_.next_dfa]309 for nonterminal2, next_ in state.nonterminal_arcs.items():310 # It's a nonterminal and we have either a left recursion issue311 # in the grammar or we have to recurse.312 try:313 first_plans2 = first_plans[nonterminal2]314 except KeyError:315 first_plans2 = _calculate_first_plans(nonterminal_to_dfas, first_plans, nonterminal2)316 else:317 if first_plans2 is None:318 raise ValueError("left recursion for rule %r" % nonterminal)319 for t, pushes in first_plans2.items():320 new_first_plans[t] = [next_] + pushes321 first_plans[nonterminal] = new_first_plans...
tests.py
Source:tests.py
...81 self.test_gram = PCFG()82 self.nonterminal = NonterminalSymbol('a')83 self.markup_class = MarkupSet('TEST_MARKUP')84 self.markup = Markup("MARKUP", self.markup_class)85 def test_add_nonterminal(self):86 """87 test adding a nonterminal to a PCFG88 """89 nonterminal = NonterminalSymbol('a')90 self.test_gram.add_nonterminal(nonterminal)91 test_nonterminals = {'a': NonterminalSymbol('a')}92 self.assertEqual(self.test_gram.nonterminals, test_nonterminals)93 def test_add_rule(self):94 """95 test adding a rule to an existing nonterminal in PCFG96 """97 self.test_gram.add_nonterminal(self.nonterminal)98 test_derivation = [NonterminalSymbol('b'), "aaaaade"]99 self.test_gram.add_rule(self.nonterminal, test_derivation)100 test_rules = [Rule(self.nonterminal, test_derivation)]101 self.assertEqual(self.test_gram.nonterminals.get(str(self.nonterminal.tag)).rules, test_rules)102 def test_remove_rule(self):103 """104 test that it successfully removes an implemented rule105 """106 self.test_gram.add_nonterminal(self.nonterminal)107 test_derivation = [NonterminalSymbol('b'), "aaaaade"]108 self.test_gram.remove_rule(self.nonterminal, test_derivation)109 self.assertEqual(self.test_gram.nonterminals.get(str(self.nonterminal.tag)).rules, [])110 def test_expansion(self):111 """112 test expansions of our grammar113 """114 self.test_gram.add_nonterminal(self.nonterminal)115 a_prod = parse_rule("[[b]], this is a test of expansion")116 self.test_gram.add_rule(self.nonterminal, a_prod)117 self.test_gram.add_nonterminal(a_prod[0])118 b_prod = parse_rule("Wow")119 self.test_gram.add_rule(a_prod[0], b_prod)120 test_string = "Wow, this is a test of expansion"121 test_deriv = IntermediateDeriv(set(), TerminalSymbol("Wow, this is a test of expansion"))122 self.assertEqual(self.test_gram.expand(NonterminalSymbol('a')), test_deriv)123 def test_recursive_nt_addition(self):124 """125 add_rule should add all nonterminals present in derivation126 that are not in the grammar to the grammar127 """128 self.test_gram.add_nonterminal(self.nonterminal)129 a_prod = parse_rule("[[b]], this is a test of expansion")130 self.test_gram.add_rule(self.nonterminal, a_prod)131 self.assertEqual(2, len(self.test_gram.nonterminals))132 def test_markup_class_addition(self):133 """134 tests to ensure that if we add a markup to a nonterminal, and that markup class does not already135 exist within our PCFG markup class list, we add it to the markup class list136 """137 self.nonterminal.add_markup(self.markup)138 self.test_gram.add_nonterminal(self.nonterminal)139 test = set()140 test.add(self.markup)141 self.assertEqual(self.test_gram.markup_class[self.markup.tagset.__str__()], test)142 def test_expansion_returns_markup(self):143 """make sure our expansions return markup correctly"""144 self.nonterminal.add_markup(self.markup)145 self.test_gram.add_nonterminal(self.nonterminal)146 def test_empty_expansion(self):147 """148 test that expansions of nonterminals with no productions works correctly149 """150 self.test_gram.add_nonterminal(self.nonterminal)151 a_prod = parse_rule("[[b]], this is a test of expansion")152 self.test_gram.add_rule(self.nonterminal, a_prod)153 self.test_gram.add_nonterminal(a_prod[0])154 test_string = IntermediateDeriv(set(), "[[b]], this is a test of expansion")155 self.assertEqual(self.test_gram.expand(NonterminalSymbol('a')), test_string)156 def test_modify_app_rate(self):157 """158 test that application rates are correctly modified159 """160 self.test_gram.add_nonterminal(self.nonterminal)161 a_prob = parse_rule("test of application_rate")162 self.test_gram.add_rule(self.nonterminal, a_prob)163 old_app = self.test_gram.nonterminals.get(str(self.nonterminal.tag)).rules[0].application_rate164 self.test_gram.modify_application_rate(self.nonterminal, 0, 5)165 new_app = self.test_gram.nonterminals.get(str(self.nonterminal.tag)).rules[0].application_rate166 self.assertNotEqual(old_app, new_app)167 self.assertEqual(new_app, 5)168 def test_returns_system_vars(self):169 """170 test that our function correctly returns the list of system variables171 defined by the user within the program172 """173 self.test_gram.add_nonterminal(self.nonterminal)174 system_var_prod = parse_rule("[[affimative]], [name], [[I think]] his hair is[hair_color]")175 self.test_gram.add_rule(self.nonterminal, system_var_prod)176 self.assertEqual(2, len(self.test_gram.system_vars))177 system_var_prod_2 = parse_rule("Ah yes, [player_name]")178 self.test_gram.add_rule(system_var_prod[0], system_var_prod_2)179 self.assertEqual(3, len(self.test_gram.system_vars))180 test_system_vars = []181 test_system_vars.append(SystemVar("name"))182 test_system_vars.append(SystemVar("hair_color"))183 test_system_vars.append(SystemVar("player_name"))184 self.assertEqual(test_system_vars, self.test_gram.system_vars)185if __name__ == '__main__':...
Automation Testing Tutorials
Learn to execute automation testing from scratch with LambdaTest Learning Hub. Right from setting up the prerequisites to run your first automation test, to following best practices and diving deeper into advanced test scenarios. LambdaTest Learning Hubs compile a list of step-by-step guides to help you be proficient with different test automation frameworks i.e. Selenium, Cypress, TestNG etc.
LambdaTest Learning Hubs:
- JUnit Tutorial
- TestNG Tutorial
- Webdriver Tutorial
- WebDriverIO Tutorial
- Protractor Tutorial
- Selenium 4 Tutorial
- Jenkins Tutorial
- NUnit Tutorial
- Jest Tutorial
- Playwright Tutorial
- Cypress Tutorial
- PyTest Tutorial
YouTube
You could also refer to video tutorials over LambdaTest YouTube channel to get step by step demonstration from industry experts.
Run avocado automation tests on LambdaTest cloud grid
Perform automation testing on 3000+ real desktop and mobile devices online.
Try LambdaTest Now !!
Get 100 minutes of automation test minutes FREE!!
Was this article helpful?
