kernel/src/main/java/org/kframework/parser/inner/kernel/EarleyParser.java
/**
   * Perform the "Predict" step of the Earley algorithm.
   *
   * @param S The {@link EarleySet EarleySets} for completion and prediction
   * @param Q The {@link EarleySet} for scanning
   * @param state The {@link EarleyState} to process
   * @param k the current end-index being parsed
   * @param data The {@link ParserMetadata} about the sentence being parsed
   */
Perform the "Predict" step of the Earley algorithm.
Perform the " Predict " step of the Earley algorithm .
private void predict(List<EarleySet> S, EarleySet Q, EarleyState state, int k, ParserMetadata data) {
    EarleyNonTerminal nt = (EarleyNonTerminal)state.prod.items.get(state.item);
    if (nullable.get(nt.sort) || first[nt.sort].get(data.words[k].kind)) {
      List<EarleyProduction> prods = predictor.get(nt.sort);
      for (EarleyProduction next : prods) {
        if (next.items.size() != 0 && !next.items.get(0).isNonTerminal()) {
          EarleyTerminal t = (EarleyTerminal)next.items.get(0);
          if (t.kind == data.words[k].kind) {
            EarleyState nextState = new EarleyState(next, 0, k);
            Q.add(nextState, data);
          }
        } else {
          EarleyState nextState = new EarleyState(next, 0, k);
          S.get(k).add(nextState, data);
        }
      }
    }
    if (nullable.get(nt.sort)) {
      EarleyState nextState = new EarleyState(state.prod, state.item+1, state.start);
      nextState.parseTree = new HashSet<>();
      wrapAndAppend(nt.sort, k, nextState, state, S.get(k));
      addStateToSet(S, Q, state, nextState, k, data);
    }
  }
private void predict ( List < EarleySet > S , EarleySet Q , EarleyState state , int k , ParserMetadata data ) { EarleyNonTerminal nt = ( EarleyNonTerminal ) state . prod . items . get ( state . item ) ; if ( nullable . get ( nt . sort ) || first [ nt . sort ] . get ( data . words [ k ] . kind ) ) { List < EarleyProduction > prods = predictor . get ( nt . sort ) ; for ( EarleyProduction next : prods ) { if ( next . items . size ( ) != 0 && ! next . items . get ( 0 ) . isNonTerminal ( ) ) { EarleyTerminal t = ( EarleyTerminal ) next . items . get ( 0 ) ; if ( t . kind == data . words [ k ] . kind ) { EarleyState nextState = new EarleyState ( next , 0 , k ) ; Q . add ( nextState , data ) ; } } else { EarleyState nextState = new EarleyState ( next , 0 , k ) ; S . get ( k ) . add ( nextState , data ) ; } } } if ( nullable . get ( nt . sort ) ) { EarleyState nextState = new EarleyState ( state . prod , state . item + 1 , state . start ) ; nextState . parseTree = new HashSet < > ( ) ; wrapAndAppend ( nt . sort , k , nextState , state , S . get ( k ) ) ; addStateToSet ( S , Q , state , nextState , k , data ) ; } }
Perform the "Predict" step of the Earley algorithm.
Perform the " Predict " step of the Earley algorithm .
// first, use lookahead to check if we need to predict this sort at all // for each production for the sort being predicted, add it to the appropriate set // if it's a terminal, add it to be scanned only if the next token matches // if it matches, add (next, 0, k) to Q // state is either now complete or at a non-terminal, therefore add it to S[k] // non-terminal is nullable, so complete the state by advancing past the nullable sort. // see Aycock and Horspool