private function computeRuleReducible()

in src/parser/PhutilParserGenerator.php [420:522]

• 46 lines of code
• 15 McCabe index (conditional complexity)

  private function computeRuleReducible($rule, array &$reducible) {
    $epsilon = $this->getEpsilonSymbol();
    $end = $this->getEndSymbol();

    $productions = $this->rules[$rule];

    // In the first pass, try to find a trivially reducible production, e.g. one
    // with epsilon or only terminals. Also, remove recursive productions (those
    // which directly involve the rule itself) because we know we won't be able
    // to reduce them. If we're lucky, this will allow us to determine that the
    // rule is reducible without recursion. For example, we can immediately
    // reduce these productions:
    //
    //    R -> a
    //    R -> b c d
    //    R -> (epsilon)
    //
    // We can never reduce these productions:
    //
    //    R -> R
    //    R -> a R b
    //
    // We might be able to reduce these productions, but they aren't as cheap
    // or easy to figure out, since we need to first determine if other rules
    // can be reduced:
    //
    //    R -> X Y
    //    R -> X a
    //
    // If we find a reduction, we return immediately.

    foreach ($productions as $key => $production) {
      $has_only_terminals = true;
      foreach ($production as $symbol) {
        if ($symbol == $end) {
          break;
        } else if ($symbol == $epsilon) {
          // The rule contains an epsilon production, which can always reduce
          // it.
          return true;
        } else if ($symbol == $rule) {
          // The rule contains itself; this production is never reducible. We
          // must find another reducible production.
          unset($productions[$key]);
          continue 2;
        } else if ($this->isTerminal($symbol)) {
          // This is a terminal; keep looking. We'll be able to reduce the
          // production if it contains only terminals.
          continue;
        } else {
          // This is a rule, so we can't trivially reduce it. We'll keep it
          // for the next round if we can't find any trivial reductions.
          $has_only_terminals = false;
          break;
        }
      }

      if ($has_only_terminals) {
        return true;
      }
    }

    // If we have no productions left, this rule can't be reduced.
    if (empty($productions)) {
      return false;
    }

    // We have remaining productions which include other rules. Look for a
    // nontrivial reduction. For example:
    //
    //    R -> X Y
    //    X -> x
    //    Y -> y
    //
    // In this case, X and Y are both reducible, so "X Y" is reducible and thus
    // R is reducible.
    foreach ($productions as $production) {
      $can_reduce = true;
      foreach ($production as $symbol) {
        // NOTE: We don't need to check for epsilon here, because we would
        // already have determined the rule was reducible if we had an epsilon
        // production.
        if ($symbol == $end) {
          break;
        } else if ($this->isTerminal($symbol)) {
          continue;
        } else if (!$this->isRuleReducible($symbol, $reducible)) {
          $can_reduce = false;
          break;
        }
      }

      if ($can_reduce) {
        // The production contained only terminals and reducible rules, so it
        // is reducible. We're good and don't need to examine remaining
        // productions.
        return true;
      }
    }

    // We didn't find any reducible productions.
    return false;
  }