Returns a new grammar containing just useful rules.
969869
def remove_useless(self):
        """"""
        if not self.is_contextfree():
            raise ValueError("grammar must be context-free")
        by_lhs = collections.defaultdict(list)
        by_rhs = collections.defaultdict(list)
        for [lhs], rhs in self.rules:
            by_lhs[lhs].append((lhs, rhs))
            for y in rhs:
                if y in self.nonterminals:
                    by_rhs[y].append((lhs, rhs))
            
        agenda = collections.deque([self.start])
        reachable = set()
        while len(agenda) > 0:
            x = agenda.popleft()
            if x in reachable: continue
            reachable.add(x)
            for _, rhs in by_lhs[x]:
                for y in rhs:
                    if y in by_lhs:
                        agenda.append(y)

        agenda = collections.deque()
        productive = set()
        for [lhs], rhs in self.rules:
            if all(y not in self.nonterminals for y in rhs):
                agenda.append(lhs)
        while len(agenda) > 0:
            y = agenda.popleft()
            if y in productive: continue
            productive.add(y)
            for lhs, rhs in by_rhs[y]:
                if all(y not in self.nonterminals or y in productive for y in rhs):
                    agenda.append(lhs)

        g = Grammar()
        g.set_start(self.start)

        for [lhs], rhs in self.rules:
            if (lhs in reachable & productive and
                all(y not in self.nonterminals or y in reachable & productive for y in rhs)):
                g.add_rule([lhs], rhs)
        return g
515171
function buildGrammar(match, namespace, optOhmGrammarForTesting) {
  var builder = new Builder();
  var decl;
  var currentRuleName;
  var currentRuleFormals;
  var overriding = false;
  var metaGrammar = optOhmGrammarForTesting || ohmGrammar;

  // A visitor that produces a Grammar instance from the CST.
  var helpers = metaGrammar.createSemantics().addOperation('visit', {
    Grammar: function(n, s, open, rs, close) {
      var grammarName = n.visit();
      decl = builder.newGrammar(grammarName, namespace);
      s.visit();
      rs.visit();
      var g = decl.build();
      g.source = this.source.trimmed();
      if (grammarName in namespace) {
        throw errors.duplicateGrammarDeclaration(g, namespace);
      }
      namespace[grammarName] = g;
      return g;
    },

    SuperGrammar: function(_, n) {
      var superGrammarName = n.visit();
      if (superGrammarName === 'null') {
        decl.withSuperGrammar(null);
      } else {
        if (!namespace || !(superGrammarName in namespace)) {
          throw errors.undeclaredGrammar(superGrammarName, namespace, n.source);
        }
        decl.withSuperGrammar(namespace[superGrammarName]);
      }
    },

    Rule_define: function(n, fs, d, _, b) {
      currentRuleName = n.visit();
      currentRuleFormals = fs.visit()[0] || [];
      // If there is no default start rule yet, set it now. This must be done before visiting
      // the body, because it might contain an inline rule definition.
      if (!decl.defaultStartRule && decl.ensureSuperGrammar() !== Grammar.ProtoBuiltInRules) {
        decl.withDefaultStartRule(currentRuleName);
      }
      var body = b.visit();
      var description = d.visit()[0];
      var source = this.source.trimmed();
      return decl.define(currentRuleName, currentRuleFormals, body, description, source);
    },
    Rule_override: function(n, fs, _, b) {
      currentRuleName = n.visit();
      currentRuleFormals = fs.visit()[0] || [];
      overriding = true;
      var body = b.visit();
      var source = this.source.trimmed();
      var ans = decl.override(currentRuleName, currentRuleFormals, body, null, source);
      overriding = false;
      return ans;
    },
    Rule_extend: function(n, fs, _, b) {
      currentRuleName = n.visit();
      currentRuleFormals = fs.visit()[0] || [];
      var body = b.visit();
      var source = this.source.trimmed();
      var ans = decl.extend(currentRuleName, currentRuleFormals, body, null, source);
      return ans;
    },
    RuleBody: function(_, terms) {
      var args = terms.visit();
      return builder.alt.apply(builder, args).withSource(this.source);
    },

    Formals: function(opointy, fs, cpointy) {
      return fs.visit();
    },

    Params: function(opointy, ps, cpointy) {
      return ps.visit();
    },

    Alt: function(seqs) {
      var args = seqs.visit();
      return builder.alt.apply(builder, args).withSource(this.source);
    },

    TopLevelTerm_inline: function(b, n) {
      var inlineRuleName = currentRuleName + '_' + n.visit();
      var body = b.visit();
      var source = this.source.trimmed();
      var isNewRuleDeclaration =
          !(decl.superGrammar && decl.superGrammar.rules[inlineRuleName]);
      if (overriding && !isNewRuleDeclaration) {
        decl.override(inlineRuleName, currentRuleFormals, body, null, source);
      } else {
        decl.define(inlineRuleName, currentRuleFormals, body, null, source);
      }
      var params = currentRuleFormals.map(function(formal) { return builder.app(formal); });
      return builder.app(inlineRuleName, params).withSource(body.source);
    },

    Seq: function(expr) {
      return builder.seq.apply(builder, expr.visit()).withSource(this.source);
    },

    Iter_star: function(x, _) {
      return builder.star(x.visit()).withSource(this.source);
    },
    Iter_plus: function(x, _) {
      return builder.plus(x.visit()).withSource(this.source);
    },
    Iter_opt: function(x, _) {
      return builder.opt(x.visit()).withSource(this.source);
    },

    Pred_not: function(_, x) {
      return builder.not(x.visit()).withSource(this.source);
    },
    Pred_lookahead: function(_, x) {
      return builder.lookahead(x.visit()).withSource(this.source);
    },

    Lex_lex: function(_, x) {
      return builder.lex(x.visit()).withSource(this.source);
    },

    Base_application: function(rule, ps) {
      return builder.app(rule.visit(), ps.visit()[0] || []).withSource(this.source);
    },
    Base_range: function(from, _, to) {
      return builder.range(from.visit(), to.visit()).withSource(this.source);
    },
    Base_terminal: function(expr) {
      return builder.terminal(expr.visit()).withSource(this.source);
    },
    Base_paren: function(open, x, close) {
      return x.visit();
    },

    ruleDescr: function(open, t, close) {
      return t.visit();
    },
    ruleDescrText: function(_) {
      return this.sourceString.trim();
    },

    caseName: function(_, space1, n, space2, end) {
      return n.visit();
    },

    name: function(first, rest) {
      return this.sourceString;
    },
    nameFirst: function(expr) {},
    nameRest: function(expr) {},

    terminal: function(open, cs, close) {
      return cs.visit().join('');
    },

    oneCharTerminal: function(open, c, close) {
      return c.visit();
    },

    terminalChar: function(_) {
      return common.unescapeChar(this.sourceString);
    },

    escapeChar: function(_) {
      return this.sourceString;
    },

    NonemptyListOf: function(x, _, xs) {
      return [x.visit()].concat(xs.visit());
    },
    EmptyListOf: function() {
      return [];
    },

    _terminal: function() {
      return this.primitiveValue;
    }
  });
  return helpers(match).visit();
}
478020
def new_empty(self, name):
        """"""
        if name in self:
            raise KeyError("Already have rule {}".format(name))
        new = Rule(self.engine, name)
        self._cache[name] = new
        self.send(self, rule=new, active=True)
        return new
907150
protected static Iterable<Keyword> getAllKeywords(Grammar grammar) {
		final Map<String, Keyword> keywords = new HashMap<>();
		final List<ParserRule> rules = GrammarUtil.allParserRules(grammar);
		for (final ParserRule parserRule : rules) {
			final List<Keyword> list = typeSelect(eAllContentsAsList(parserRule), Keyword.class);
			for (final Keyword keyword : list) {
				keywords.put(keyword.getValue(), keyword);
			}
		}
		final List<EnumRule> enumRules = GrammarUtil.allEnumRules(grammar);
		for (final EnumRule enumRule : enumRules) {
			final List<Keyword> list = typeSelect(eAllContentsAsList(enumRule), Keyword.class);
			for (final Keyword keyword : list) {
				keywords.put(keyword.getValue(), keyword);
			}
		}
		return keywords.values();
	}
1128001
def from_dict(cls, rules_dict: dict, default_rule=None, raise_error=False):
        """"""

        # Parse the rules stored in the dictionary
        rules = {k: _parser.parse_rule(v, raise_error)
                 for k, v in rules_dict.items()}

        return cls(rules, default_rule)
472619
public function analyze(): iterable
    {
        if (\count($this->rules) === 0) {
            throw new GrammarException('No rules specified');
        }

        $this->parsedRules = [];

        foreach ($this->rules as $delegate) {
            $this->ruleName = $delegate->getRuleName();
            $nodeId = $delegate->isKept()
                ? $delegate->getRuleName()
                : null;

            $pNodeId = $nodeId;
            $rule = $this->rule($delegate->getInnerTokens(), $pNodeId);

            if ($rule === null) {
                $error = \sprintf('Error while parsing rule %s.', $delegate->getRuleName());
                throw new GrammarException($error, 1);
            }

            $zeRule = $this->parsedRules[$rule];
            $zeRule->setName($delegate->getRuleName());

            if ($nodeId !== null) {
                $zeRule->setDefaultId($nodeId);
            }

            unset($this->parsedRules[$rule]);
            $this->parsedRules[$delegate->getRuleName()] = $zeRule;
        }

        foreach ($this->parsedRules as $builder) {
            yield $builder->build();
        }
    }
1215371
def _from_dict(cls, _dict):
        """"""
        args = {}
        if 'grammars' in _dict:
            args['grammars'] = [
                Grammar._from_dict(x) for x in (_dict.get('grammars'))
            ]
        else:
            raise ValueError(
                'Required property \'grammars\' not present in Grammars JSON')
        return cls(**args)
409317
def rule(pattern, *dependencies, &block)
      if block.nil?
        Rule.new(pattern, *dependencies)
      else
        Rule.new(pattern, *dependencies) do |rule|
          rule.define(&block)
        end
      end
    end
1171926
def create_rule(*args, &block)
      pattern, args, deps = resolve_args(args)
      pattern = Regexp.new(Regexp.quote(pattern) + '$') if String === pattern
      @rules << [pattern, args, deps, block]
    end
701066
def transform_to_chomsky_normal_form(grammar, inplace=False):
    # type: (Grammar, bool) -> Grammar
    
    # Copy if required
    if inplace is False:
        grammar = copy(grammar)
    # Create nonterminals rewritable to the terminal.
    # They will be inserted into the grammar as needed.
    fill = TerminalsFilling(grammar)
    to_process = Queue()
    for r in grammar.rules:
        to_process.put(r)
    while not to_process.empty():
        rule = to_process.get()  # type: Type[Rule]
        # Check, if rule must be split
        if len(rule.right) > 2:
            grammar.rules.remove(rule)
            # create nonterm that represent group on the right
            created_nonterm = type("ChomskyGroup[" + rule.__name__ + "]",
                                   (ChomskyGroupNonterminal,),
                                   ChomskyGroupNonterminal.__dict__.copy())  # type: Type[ChomskyGroupNonterminal]
            created_nonterm.group = rule.right[1:]
            # create rule that replace current
            created_left_rule = type("ChomskySplit[" + rule.__name__ + "]",
                                     (ChomskySplitRule,),
                                     ChomskySplitRule.__dict__.copy())  # type: Type[ChomskySplitRule]
            created_left_rule.rule = ([rule.fromSymbol], [rule.right[0], created_nonterm])
            created_left_rule.from_rule = rule
            # create rule with symbols on the right
            created_right_rule = type("ChomskyRest[" + rule.__name__ + "]",
                                      (ChomskyRestRule,),
                                      ChomskyRestRule.__dict__.copy())  # type: Type[ChomskyRestRule]
            created_right_rule.rule = ([created_nonterm], rule.right[1:])
            created_right_rule.from_rule = rule
            # add it to the grammar
            grammar.nonterminals.add(created_nonterm)
            grammar.rules.add(created_left_rule, created_right_rule)
            to_process.put(created_left_rule)
            to_process.put(created_right_rule)
        # check, if must replace terminal
        elif len(rule.right) == 2:
            if rule.right[0] in grammar.terminals:
                # first symbol is terminal
                # remove rule from grammar
                grammar.rules.remove(rule)
                # get nonterminal rewritable to the terminal and add that rules into the grammar implicitly
                symb = fill.get(rule.right[0])
                # create rule replacing the original one
                created = type("ChomskyLeft[" + rule.__name__ + "]",
                               (ChomskyTerminalReplaceRule,),
                               ChomskyTerminalReplaceRule.__dict__.copy())  # type: Type[ChomskyTerminalReplaceRule]
                created.rule = ([rule.fromSymbol], [symb, rule.right[1]])
                created.from_rule = rule
                created.replaced_index = 0
                # add it into the grammar
                grammar.rules.add(created)
                to_process.put(created)
            elif rule.right[1] in grammar.terminals:
                # second symbol is terminal
                # remove rule from grammar
                grammar.rules.remove(rule)
                # get nonterminal rewritable to the terminal and add that rules into the grammar implicitly
                symb = fill.get(rule.right[1])
                # create rule replacing the original one
                created = type("ChomskyRight[" + rule.__name__ + "]",
                               (ChomskyTerminalReplaceRule,),
                               ChomskyTerminalReplaceRule.__dict__.copy())
                created.rule = ([rule.fromSymbol], [rule.right[0], symb])
                created.from_rule = rule
                created.replaced_index = 1
                # add it into the grammar
                grammar.rules.add(created)
                to_process.put(created)
    return grammar
1062707
def on_rule(node, compiled_grammar)
      name = process(node.children[0], compiled_grammar)

      if compiled_grammar.has_terminal?(name)
        compiled_grammar.add_error(
          "the rule name #{name.inspect} is already used as a terminal name",
          node.source_line
        )
      end

      if compiled_grammar.has_rule_with_branches?(name)
        compiled_grammar.add_error(
          "the rule #{name.inspect} has already been defined",
          node.source_line
        )

        return
      end

      branches = node.children[1..-1].map do |child|
        process(child, compiled_grammar)
      end

      rule = compiled_grammar.lookup_rule(name)

      rule.branches.concat(branches)
    end
1124651
public static RePairGrammar buildGrammar(SAXRecords saxRecords) {

    RePairGrammar grammar = NewRepair.parse(saxRecords.getSAXString(SPACE));

    return grammar;

  }
647634
def new(cls, *args, **kwargs):
        """"""
        new = cls(make_default(getattr(cls, 'spec', {})))
        new.update(args[0] if args and not kwargs else kwargs)
        return new
762574
def load_grammar(self, grammar_text, grammar_name='<?>'):
        ""

        try:
            tree = self.canonize_tree.transform( self.parser.parse(grammar_text+'\n') )
        except UnexpectedCharacters as e:
            context = e.get_context(grammar_text)
            raise GrammarError("Unexpected input at line %d column %d in %s: \n\n%s" %
                               (e.line, e.column, grammar_name, context))
        except UnexpectedToken as e:
            context = e.get_context(grammar_text)
            error = e.match_examples(self.parser.parse, {
                'Unclosed parenthesis': ['a: (\n'],
                'Umatched closing parenthesis': ['a: )\n', 'a: [)\n', 'a: (]\n'],
                'Expecting rule or terminal definition (missing colon)': ['a\n', 'a->\n', 'A->\n', 'a A\n'],
                'Alias expects lowercase name': ['a: -> "a"\n'],
                'Unexpected colon': ['a::\n', 'a: b:\n', 'a: B:\n', 'a: "a":\n'],
                'Misplaced operator': ['a: b??', 'a: b(?)', 'a:+\n', 'a:?\n', 'a:*\n', 'a:|*\n'],
                'Expecting option ("|") or a new rule or terminal definition': ['a:a\n()\n'],
                '%import expects a name': ['%import "a"\n'],
                '%ignore expects a value': ['%ignore %import\n'],
            })
            if error:
                raise GrammarError("%s at line %s column %s\n\n%s" % (error, e.line, e.column, context))
            elif 'STRING' in e.expected:
                raise GrammarError("Expecting a value at line %s column %s\n\n%s" % (e.line, e.column, context))
            raise

        tree = PrepareGrammar().transform(tree)

        # Extract grammar items
        defs = classify(tree.children, lambda c: c.data, lambda c: c.children)
        term_defs = defs.pop('term', [])
        rule_defs = defs.pop('rule', [])
        statements = defs.pop('statement', [])
        assert not defs

        term_defs = [td if len(td)==3 else (td[0], 1, td[1]) for td in term_defs]
        term_defs = [(name.value, (t, int(p))) for name, p, t in term_defs]
        rule_defs = [options_from_rule(*x) for x in rule_defs]

        # Execute statements
        ignore, imports = [], {}
        for (stmt,) in statements:
            if stmt.data == 'ignore':
                t ,= stmt.children
                ignore.append(t)
            elif stmt.data == 'import':
                if len(stmt.children) > 1:
                    path_node, arg1 = stmt.children
                else:
                    path_node, = stmt.children
                    arg1 = None

                if isinstance(arg1, Tree):  # Multi import
                    dotted_path = tuple(path_node.children)
                    names = arg1.children
                    aliases = dict(zip(names, names))  # Can't have aliased multi import, so all aliases will be the same as names
                else:  # Single import
                    dotted_path = tuple(path_node.children[:-1])
                    name = path_node.children[-1]  # Get name from dotted path
                    aliases = {name: arg1 or name}  # Aliases if exist

                if path_node.data == 'import_lib':  # Import from library
                    base_paths = []
                else:  # Relative import
                    if grammar_name == '<string>':  # Import relative to script file path if grammar is coded in script
                        try:
                            base_file = os.path.abspath(sys.modules['__main__'].__file__)
                        except AttributeError:
                            base_file = None
                    else:
                        base_file = grammar_name  # Import relative to grammar file path if external grammar file
                    if base_file:
                        base_paths = [os.path.split(base_file)[0]]
                    else:
                        base_paths = [os.path.abspath(os.path.curdir)]

                try:
                    import_base_paths, import_aliases = imports[dotted_path]
                    assert base_paths == import_base_paths, 'Inconsistent base_paths for %s.' % '.'.join(dotted_path)
                    import_aliases.update(aliases)
                except KeyError:
                    imports[dotted_path] = base_paths, aliases

            elif stmt.data == 'declare':
                for t in stmt.children:
                    term_defs.append([t.value, (None, None)])
            else:
                assert False, stmt

        # import grammars
        for dotted_path, (base_paths, aliases) in imports.items():
            grammar_path = os.path.join(*dotted_path) + EXT
            g = import_grammar(grammar_path, base_paths=base_paths)
            new_td, new_rd = import_from_grammar_into_namespace(g, '__'.join(dotted_path), aliases)

            term_defs += new_td
            rule_defs += new_rd

        # Verify correctness 1
        for name, _ in term_defs:
            if name.startswith('__'):
                raise GrammarError('Names starting with double-underscore are reserved (Error at %s)' % name)

        # Handle ignore tokens
        # XXX A slightly hacky solution. Recognition of %ignore TERMINAL as separate comes from the lexer's
        #     inability to handle duplicate terminals (two names, one value)
        ignore_names = []
        for t in ignore:
            if t.data=='expansions' and len(t.children) == 1:
                t2 ,= t.children
                if t2.data=='expansion' and len(t2.children) == 1:
                    item ,= t2.children
                    if item.data == 'value':
                        item ,= item.children
                        if isinstance(item, Token) and item.type == 'TERMINAL':
                            ignore_names.append(item.value)
                            continue

            name = '__IGNORE_%d'% len(ignore_names)
            ignore_names.append(name)
            term_defs.append((name, (t, 1)))

        # Verify correctness 2
        terminal_names = set()
        for name, _ in term_defs:
            if name in terminal_names:
                raise GrammarError("Terminal '%s' defined more than once" % name)
            terminal_names.add(name)

        if set(ignore_names) > terminal_names:
            raise GrammarError("Terminals %s were marked to ignore but were not defined!" % (set(ignore_names) - terminal_names))

        resolve_term_references(term_defs)

        rules = rule_defs

        rule_names = set()
        for name, _x, _o in rules:
            if name.startswith('__'):
                raise GrammarError('Names starting with double-underscore are reserved (Error at %s)' % name)
            if name in rule_names:
                raise GrammarError("Rule '%s' defined more than once" % name)
            rule_names.add(name)

        for name, expansions, _o in rules:
            used_symbols = {t for x in expansions.find_data('expansion')
                              for t in x.scan_values(lambda t: t.type in ('RULE', 'TERMINAL'))}
            for sym in used_symbols:
                if sym.type == 'TERMINAL':
                    if sym not in terminal_names:
                        raise GrammarError("Token '%s' used but not defined (in rule %s)" % (sym, name))
                else:
                    if sym not in rule_names:
                        raise GrammarError("Rule '%s' used but not defined (in rule %s)" % (sym, name))

        return Grammar(rules, term_defs, ignore_names)
248970
function duplicateRuleDeclaration(ruleName, grammarName, declGrammarName, optSource) {
  var message = "Duplicate declaration for rule '" + ruleName +
      "' in grammar '" + grammarName + "'";
  if (grammarName !== declGrammarName) {
    message += " (originally declared in '" + declGrammarName + "')";
  }
  return createError(message, optSource);
}
1198787
def build_valid_keywords_grammar(keywords=None):
    """"""
    from invenio_query_parser.parser import KeywordQuery, KeywordRule, \
        NotKeywordValue, SimpleQuery, ValueQuery

    if keywords:
        KeywordRule.grammar = attr('value', re.compile(
            r"(\d\d\d\w{{0,3}}|{0})\b".format("|".join(keywords), re.I)))

        NotKeywordValue.grammar = attr('value', re.compile(
            r'\b(?!\d\d\d\w{{0,3}}|{0}:)\S+\b:'.format(
                ":|".join(keywords))))

        SimpleQuery.grammar = attr(
            'op', [NotKeywordValue, KeywordQuery, ValueQuery])
    else:
        KeywordRule.grammar = attr('value', re.compile(r"[\w\d]+(\.[\w\d]+)*"))
        SimpleQuery.grammar = attr('op', [KeywordQuery, ValueQuery])
663787
def replaceRule(oldRule, newRule):
        # type: (Rule, Rule) -> Rule
        
        for par in oldRule.from_symbols:
            par._set_to_rule(newRule)
            newRule._from_symbols.append(par)
        for ch in oldRule.to_symbols:
            ch._set_from_rule(newRule)
            newRule._to_symbols.append(ch)
        return newRule