Compute all LR(0) states for the grammar.  Links
are added to between some states so that the LR(1) follow sets
can be computed later.
346287
function FindStates()
    {
        PHP_ParserGenerator_Config::Configlist_init();
    
        /* Find the start symbol */
        if ($this->start) {
            $sp = PHP_ParserGenerator_Symbol::Symbol_find($this->start);
            if ($sp == false) {
                PHP_ParserGenerator::ErrorMsg($this->filename, 0,
                    "The specified start symbol \"%s\" is not " .
                    "in a nonterminal of the grammar.  \"%s\" will be used as the start " .
                    "symbol instead.", $this->start, $this->rule->lhs->name);
                $this->errorcnt++;
                $sp = $this->rule->lhs;
            }
        } else {
            $sp = $this->rule->lhs;
        }
    
        /* Make sure the start symbol doesn't occur on the right-hand side of
        ** any rule.  Report an error if it does.  (YACC would generate a new
        ** start symbol in this case.) */
        for ($rp = $this->rule; $rp; $rp = $rp->next) {
            for ($i = 0; $i < $rp->nrhs; $i++) {
                if ($rp->rhs[$i]->type == PHP_ParserGenerator_Symbol::MULTITERMINAL) {
                    foreach ($rp->rhs[$i]->subsym as $subsp) {
                        if ($subsp === $sp) {
                            PHP_ParserGenerator::ErrorMsg($this->filename, 0,
                                "The start symbol \"%s\" occurs on the " .
                                "right-hand side of a rule. This will result in a parser which " .
                                "does not work properly.", $sp->name);
                            $this->errorcnt++;
                        }
                    }
                } elseif ($rp->rhs[$i] === $sp) {
                    PHP_ParserGenerator::ErrorMsg($this->filename, 0,
                        "The start symbol \"%s\" occurs on the " .
                        "right-hand side of a rule. This will result in a parser which " .
                        "does not work properly.", $sp->name);
                    $this->errorcnt++;
                }
            }
        }
    
        /* The basis configuration set for the first state
        ** is all rules which have the start symbol as their
        ** left-hand side */
        for ($rp = $sp->rule; $rp; $rp = $rp->nextlhs) {
            $newcfp = PHP_ParserGenerator_Config::Configlist_addbasis($rp, 0);
            $newcfp->fws[0] = 1;
        }
    
        /* Compute the first state.  All other states will be
        ** computed automatically during the computation of the first one.
        ** The returned pointer to the first state is not used. */
        $newstp = array();
        $newstp = $this->getstate();
        if (is_array($newstp)) {
            $this->buildshifts($newstp[0]); /* Recursively compute successor states */
        }
    }
222818
def p_state_invariant_section(self, p):
        ''''''
        if len(p) == 6:
            p[0] = ('invariants', p[3])
        elif len(p) == 5:
            p[0] = ('invariants', [])
        self._print_verbose('invariants')
220110
def from_fsm(f):
	'''
		
	'''
	# Make sure the supplied alphabet is kosher. It must contain only single-
	# character strings or `fsm.anything_else`.
	for symbol in f.alphabet:
		if symbol == fsm.anything_else:
			continue
		if isinstance(symbol, str) and len(symbol) == 1:
			continue
		raise Exception("Symbol " + repr(symbol) + " cannot be used in a regular expression")

	# We need a new state not already used
	outside = object()

	# The set of strings that would be accepted by this FSM if you started
	# at state i is represented by the regex R_i.
	# If state i has a sole transition "a" to state j, then we know R_i = a R_j.
	# If state i is final, then the empty string is also accepted by this regex.
	# And so on...

	# From this we can build a set of simultaneous equations in len(f.states)
	# variables. This system is easily solved for all variables, but we only
	# need one: R_a, where a is the starting state.

	# The first thing we need to do is organise the states into order of depth,
	# so that when we perform our back-substitutions, we can start with the
	# last (deepest) state and therefore finish with R_a.
	states = [f.initial]
	i = 0
	while i < len(states):
		current = states[i]
		if current in f.map:
			for symbol in sorted(f.map[current], key=fsm.key):
				next = f.map[current][symbol]
				if next not in states:
					states.append(next)
		i += 1

	# Our system of equations is represented like so:
	brz = {}
	for a in f.states:
		brz[a] = {}
		for b in f.states | {outside}:
			brz[a][b] = nothing

	# Populate it with some initial data.
	for a in f.map:
		for symbol in f.map[a]:
			b = f.map[a][symbol]
			if symbol == fsm.anything_else:
				brz[a][b] |= ~charclass(f.alphabet - {fsm.anything_else})
			else:
				brz[a][b] |= charclass({symbol})
		if a in f.finals:
			brz[a][outside] |= emptystring

	# Now perform our back-substitution
	for i in reversed(range(len(states))):
		a = states[i]

		# Before the equation for R_a can be substituted into the other
		# equations, we need to resolve the self-transition (if any).
		# e.g.    R_a = 0 R_a |   1 R_b |   2 R_c
		# becomes R_a =         0*1 R_b | 0*2 R_c
		loop = brz[a][a] * star # i.e. "0*"
		del brz[a][a]

		for right in brz[a]:
			brz[a][right] = loop + brz[a][right]

		# Note: even if we're down to our final equation, the above step still
		# needs to be performed before anything is returned.

		# Now we can substitute this equation into all of the previous ones.
		for j in range(i):
			b = states[j]

			# e.g. substituting R_a =  0*1 R_b |      0*2 R_c
			# into              R_b =    3 R_a |        4 R_c | 5 R_d
			# yields            R_b = 30*1 R_b | (30*2|4) R_c | 5 R_d
			univ = brz[b][a] # i.e. "3"
			del brz[b][a]

			for right in brz[a]:
				brz[b][right] |= univ + brz[a][right]

	return brz[f.initial][outside].reduce()
457301
def compute_dominators(nodes):
    '''
        
    '''
    changed = True

    for n in nodes:
        n.dominators = set(nodes)

    while changed:
        changed = False

        for node in nodes:
            new_set = intersection_predecessor(node).union({node})
            if new_set != node.dominators:
                node.dominators = new_set
                changed = True

    # compute immediate dominator
    for node in nodes:
        idom_candidates = set(node.dominators)
        idom_candidates.remove(node)

        for dominator in node.dominators:
            if dominator != node:
                [idom_candidates.remove(d) for d in dominator.dominators if d in idom_candidates and d!=dominator]

        assert len(idom_candidates)<=1
        if idom_candidates:
            idom = idom_candidates.pop()
            node.immediate_dominator = idom
            idom.dominator_successors.add(node)
277763
public void rnnClearPreviousState() {
        if (layers == null)
            return;
        for (int i = 0; i < layers.length; i++) {
            if (layers[i] instanceof RecurrentLayer)
                ((RecurrentLayer) layers[i]).rnnClearPreviousState();
            else if (layers[i] instanceof MultiLayerNetwork) {
                ((MultiLayerNetwork) layers[i]).rnnClearPreviousState();
            } else if(layers[i] instanceof BaseWrapperLayer && ((BaseWrapperLayer)layers[i]).getUnderlying() instanceof RecurrentLayer){
                ((RecurrentLayer) ((BaseWrapperLayer)layers[i]).getUnderlying()).rnnClearPreviousState();
            }
        }
    }
1145076
def extract(grammar, inputdata, fixed_start = False, return_first=False):
    
    if not inputdata:
        return []
    checker = checker_factory(grammar)

    totallen = len(inputdata)
    from pydsl.grammar.PEG import Choice
    try:
        maxl = grammar.maxsize or totallen
    except NotImplementedError:
        maxl = totallen
    try:
        #minl = grammar.minsize #FIXME: It won't work with incompatible alphabets
        minl = 1
    except NotImplementedError:
        minl = 1
    if fixed_start:
        max_start = 1
    else:
        max_start = totallen
    result = []
    for i in range(max_start):
        for j in range(i+minl, min(i+maxl, totallen) + 1):
            slice = inputdata[i:j]
            check = checker.check(slice)
            if check:
                this_pt = PositionToken(slice, grammar, i, j)
                if return_first:
                    return this_pt
                result.append(this_pt)
    return result
601721
def _yield_all(self, l):
        '''
        
        '''
        if l is not None:
            if type(l) in [list, tuple]:
                for f in l:
                    for x in self._yield(f): yield x
            else:
                for x in self._yield(l): yield x
293232
def _epsilon_closure(self, state):
        
        closure = set([state.stateid])
        stack = [state]
        while True:
            if not stack:
                break
            s = stack.pop()
            for arc in s:
                if self.isyms.find(arc.ilabel) != EPSILON or \
                        arc.nextstate in closure:
                    continue
                closure.add(arc.nextstate)
                stack.append(self.states[arc.nextstate])
        return closure
191240
void parse() {
        int state;
        RBBIRuleParseTable.RBBIRuleTableElement tableEl;

        state = 1;
        nextChar(fC);
        //
        // Main loop for the rule parsing state machine.
        //   Runs once per state transition.
        //   Each time through optionally performs, depending on the state table,
        //      - an advance to the the next input char
        //      - an action to be performed.
        //      - pushing or popping a state to/from the local state return stack.
        //
        for (;;) {
            // Quit if state == 0.  This is the normal way to exit the state machine.
            //
            if (state == 0) {
                break;
            }

            // Find the state table element that matches the input char from the rule, or the
            //    class of the input character.  Start with the first table row for this
            //    state, then linearly scan forward until we find a row that matches the
            //    character.  The last row for each state always matches all characters, so
            //    the search will stop there, if not before.
            //
            tableEl = RBBIRuleParseTable.gRuleParseStateTable[state];
            if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("scan") >= 0) {
                System.out.println("char, line, col = (\'" + (char) fC.fChar
                        + "\', " + fLineNum + ", " + fCharNum + "    state = "
                        + tableEl.fStateName);
            }

            for (int tableRow = state;; tableRow++) { // loop over the state table rows associated with this state.
                tableEl = RBBIRuleParseTable.gRuleParseStateTable[tableRow];
                if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("scan") >= 0) {
                    System.out.print(".");
                }
                if (tableEl.fCharClass < 127 && fC.fEscaped == false
                        && tableEl.fCharClass == fC.fChar) {
                    // Table row specified an individual character, not a set, and
                    //   the input character is not escaped, and
                    //   the input character matched it.
                    break;
                }
                if (tableEl.fCharClass == 255) {
                    // Table row specified default, match anything character class.
                    break;
                }
                if (tableEl.fCharClass == 254 && fC.fEscaped) {
                    // Table row specified "escaped" and the char was escaped.
                    break;
                }
                if (tableEl.fCharClass == 253 && fC.fEscaped
                        && (fC.fChar == 0x50 || fC.fChar == 0x70)) {
                    // Table row specified "escaped P" and the char is either 'p' or 'P'.
                    break;
                }
                if (tableEl.fCharClass == 252 && fC.fChar == -1) {
                    // Table row specified eof and we hit eof on the input.
                    break;
                }

                if (tableEl.fCharClass >= 128 && tableEl.fCharClass < 240 && // Table specs a char class &&
                        fC.fEscaped == false && //   char is not escaped &&
                        fC.fChar != -1) { //   char is not EOF
                    UnicodeSet uniset = fRuleSets[tableEl.fCharClass - 128];
                    if (uniset.contains(fC.fChar)) {
                        // Table row specified a character class, or set of characters,
                        //   and the current char matches it.
                        break;
                    }
                }
            }

            if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("scan") >= 0) {
                System.out.println("");
            }
            //
            // We've found the row of the state table that matches the current input
            //   character from the rules string.
            // Perform any action specified  by this row in the state table.
            if (doParseActions(tableEl.fAction) == false) {
                // Break out of the state machine loop if the
                //   the action signalled some kind of error, or
                //   the action was to exit, occurs on normal end-of-rules-input.
                break;
            }

            if (tableEl.fPushState != 0) {
                fStackPtr++;
                if (fStackPtr >= kStackSize) {
                    System.out.println("RBBIRuleScanner.parse() - state stack overflow.");
                    error(RBBIRuleBuilder.U_BRK_INTERNAL_ERROR);
                }
                fStack[fStackPtr] = tableEl.fPushState;
            }

            if (tableEl.fNextChar) {
                nextChar(fC);
            }

            // Get the next state from the table entry, or from the
            //   state stack if the next state was specified as "pop".
            if (tableEl.fNextState != 255) {
                state = tableEl.fNextState;
            } else {
                state = fStack[fStackPtr];
                fStackPtr--;
                if (fStackPtr < 0) {
                    System.out.println("RBBIRuleScanner.parse() - state stack underflow.");
                    error(RBBIRuleBuilder.U_BRK_INTERNAL_ERROR);
                }
            }

        }
        
        // If there are no forward rules throw an error.
        //
        if (fRB.fTreeRoots[RBBIRuleBuilder.fForwardTree] == null) {
            error(RBBIRuleBuilder.U_BRK_RULE_SYNTAX);
        }

        //
        // If there were NO user specified reverse rules, set up the equivalent of ".*;"
        //
        if (fRB.fTreeRoots[RBBIRuleBuilder.fReverseTree] == null) {
            fRB.fTreeRoots[RBBIRuleBuilder.fReverseTree] = pushNewNode(RBBINode.opStar);
            RBBINode operand = pushNewNode(RBBINode.setRef);
            findSetFor(kAny, operand, null);
            fRB.fTreeRoots[RBBIRuleBuilder.fReverseTree].fLeftChild = operand;
            operand.fParent = fRB.fTreeRoots[RBBIRuleBuilder.fReverseTree];
            fNodeStackPtr -= 2;
        }

        //
        // Parsing of the input RBBI rules is complete.
        // We now have a parse tree for the rule expressions
        // and a list of all UnicodeSets that are referenced.
        //
        if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("symbols") >= 0) {
            fSymbolTable.rbbiSymtablePrint();
        }
        if (fRB.fDebugEnv != null && fRB.fDebugEnv.indexOf("ptree") >= 0) {
            System.out.println("Completed Forward Rules Parse Tree...");
            fRB.fTreeRoots[RBBIRuleBuilder.fForwardTree].printTree(true);
            System.out.println("\nCompleted Reverse Rules Parse Tree...");
            fRB.fTreeRoots[RBBIRuleBuilder.fReverseTree].printTree(true);
            System.out.println("\nCompleted Safe Point Forward Rules Parse Tree...");
            if (fRB.fTreeRoots[RBBIRuleBuilder.fSafeFwdTree] == null) {
                System.out.println("  -- null -- ");
            } else {
                fRB.fTreeRoots[RBBIRuleBuilder.fSafeFwdTree].printTree(true);
            }
            System.out.println("\nCompleted Safe Point Reverse Rules Parse Tree...");
            if (fRB.fTreeRoots[RBBIRuleBuilder.fSafeRevTree] == null) {
                System.out.println("  -- null -- ");
            } else {
                fRB.fTreeRoots[RBBIRuleBuilder.fSafeRevTree].printTree(true);
            }
        }
    }
1032628
private List<SequenceState<S, O, D>> retrieveMostLikelySequence() {
        // Otherwise an HMM break would have occurred and message would be null.
        assert !message.isEmpty();

        final S lastState = mostLikelyState();

        // Retrieve most likely state sequence in reverse order
        final List<SequenceState<S, O, D>> result = new ArrayList<>();
        ExtendedState<S, O, D> es = lastExtendedStates.get(lastState);
        while(es != null) {
            final SequenceState<S, O, D> ss = new SequenceState<>(es.state, es.observation,
                    es.transitionDescriptor);
            result.add(ss);
            es = es.backPointer;
        }

        Collections.reverse(result);
        return result;
    }
1306913
def _check_state_denotations(self, state: GrammarBasedState, worlds: List[NlvrLanguage]) -> List[bool]:
        
        assert state.is_finished(), "Cannot compute denotations for unfinished states!"
        # Since this is a finished state, its group size must be 1.
        batch_index = state.batch_indices[0]
        instance_label_strings = state.extras[batch_index]
        history = state.action_history[0]
        all_actions = state.possible_actions[0]
        action_sequence = [all_actions[action][0] for action in history]
        return self._check_denotation(action_sequence, instance_label_strings, worlds)
606535
function collect_states_recursive( array &$states, Grammar $Grammar, array $excluded, $threadId ){
		// recursion check
		if( $this->threadId === $threadId ){
			//echo "Recursion in $this \n";
			return;
		}
		$this->threadId = $threadId;
		// add denied first terminals into array
		$excluded = array_merge( $excluded, $Grammar->excluded_terminals($this->nt) );
		// Follow e-transitions recursively to gather all possible states
		foreach( $this->etransitions as $s => $State ){
			$State->collect_states_passthru( $states, $Grammar, $excluded, $threadId );
		}
	}
1309102
protected static List<Grammar> getEffectivelyUsedGrammars(final Grammar grammar) {
		final List<AbstractRule> allRules = GrammarUtil.allRules(grammar);
		final List<Grammar> map = ListExtensions.<AbstractRule, Grammar>map(allRules, it -> GrammarUtil.getGrammar(it));
		final Iterable<Grammar> filter = IterableExtensions.<Grammar>filter(map, it -> Boolean.valueOf(it != grammar));
		final Set<Grammar> set = IterableExtensions.<Grammar>toSet(filter);
		return IterableExtensions.<Grammar>toList(set);
	}
1233110
def _add_epsilon_states(self, stateset, gathered_epsilons):
    '''
    
    '''
    for i in list(stateset):
      if i not in gathered_epsilons:
        gathered_epsilons[i] = {}
        q = _otq()
        q.append(i)
        while q:
          s = q.popleft()
          for j in self._transitions.setdefault(s, {}).setdefault(NFA.EPSILON, set()):
            gathered_epsilons[i][j] = s if j not in gathered_epsilons[i] else self.choose(s, j)
            q.append(j)
      stateset.update(gathered_epsilons[i].keys())
39239
def state(self, states=None):
        
        if states is None or not states:
            return self
        nodes = []
        for node in self.nodes:
            if any(state.lower() == node.state.lower() for state in states):
                nodes.append(node)
        self.nodes = nodes
        return self
118164
def determinize(self) -> DFA:
        

        nfa = self

        new_states = {macro_state for macro_state in powerset(nfa._states)}
        initial_state = frozenset([nfa._initial_state])
        final_states = {q for q in new_states if len(q.intersection(nfa._accepting_states)) != 0}
        transition_function = {}

        for state_set in new_states:
            for action in nfa._alphabet:

                next_macrostate = set()
                for s in state_set:
                    for next_state in nfa._transition_function.get(s, {}).get(action, set()):
                        next_macrostate.add(next_state)

                next_macrostate = frozenset(next_macrostate)
                transition_function.setdefault(state_set, {})[action] = next_macrostate

        return DFA(new_states, set(nfa._alphabet), initial_state, set(final_states), transition_function)
15910
function FindLinks()
    {
        /* Housekeeping detail:
        ** Add to every propagate link a pointer back to the state to
        ** which the link is attached. */
        foreach ($this->sorted as $info) {
            $info->key->stp = $info->data;
        }
        
        /* Convert all backlinks into forward links.  Only the forward
        ** links are used in the follow-set computation. */
        for ($i = 0; $i < $this->nstate; $i++) {
            $stp = $this->sorted[$i];
            for ($cfp = $stp->data->cfp; $cfp; $cfp = $cfp->next) {
                for ($plp = $cfp->bplp; $plp; $plp = $plp->next) {
                    $other = $plp->cfp;
                    PHP_ParserGenerator_PropagationLink::Plink_add($other->fplp, $cfp);
                }
            }
        }
    }