kernel/src/main/java/org/kframework/parser/inner/kernel/EarleyParser.java
/**
   * Parse a sentence according to the grammar represented by this parser.
   * @param input The sentence to parse.
   * @param source The {@link Source} representing the file the string comes from.
   * @param startLine The line the sentence starts on.
   * @param startColumn The column the sentence starts on.
   * @return A {@link Term} representing the parse forest
   * @throws KEMException if parsing fails
   */
Parse a sentence according to the grammar represented by this parser.
@param input The sentence to parse.
@param source The  Source representing the file the string comes from.
@param startLine The line the sentence starts on.
@param startColumn The column the sentence starts on.
@return A  Term representing the parse forest
@throws KEMException if parsing fails
Parse a sentence according to the grammar represented by this parser . @param input The sentence to parse . @param source The Source representing the file the string comes from . @param startLine The line the sentence starts on . @param startColumn The column the sentence starts on . @return A Term representing the parse forest @throws KEMException if parsing fails
public Term parse(String input, Source source, int startLine, int startColumn) {
    ParserMetadata data = new ParserMetadata(input, scanner, source, startLine, startColumn);
    List<EarleySet> S = new ArrayList<>(data.words.length + 1);
    for (int k = 0; k <= data.words.length; k++) {
      S.add(new EarleySet(k, sorts.size()));
    }
    EarleyState startState = new EarleyState(productions.get(0), 0, 0);
    S.get(0).add(startState, data);
    EarleySet Qprime = new EarleySet(0, sorts.size());
    for (int k = 0; k < data.words.length; k++) {
      EarleySet Q = Qprime;
      Qprime = new EarleySet(k+1, sorts.size());
      for (EarleyState state : S.get(k)) {
        if (state.item != state.prod.items.size() && state.prod.items.get(state.item).isNonTerminal()) {
          predict(S, Q, state, k, data);
        } else {
          complete(S, Q, state, k, data);
        }
      }
      S.get(k).finish();
      for (EarleyState state : Q) {
        scan(S, Qprime, state, k, data);
      }
      if (S.get(k+1).empty() && Q.empty()) {
        parseError(data, k);
      }
    }
    if (S.get(data.words.length).empty()) {
      parseError(data, data.words.length-1);
    }
    return Ambiguity.apply(S.get(data.words.length).states.get(0).parseTree().stream().map(list -> list.get(0)).collect(Collectors.toSet()));
  }
public Term parse ( String input , Source source , int startLine , int startColumn ) { ParserMetadata data = new ParserMetadata ( input , scanner , source , startLine , startColumn ) ; List < EarleySet > S = new ArrayList < > ( data . words . length + 1 ) ; for ( int k = 0 ; k <= data . words . length ; k ++ ) { S . add ( new EarleySet ( k , sorts . size ( ) ) ) ; } EarleyState startState = new EarleyState ( productions . get ( 0 ) , 0 , 0 ) ; S . get ( 0 ) . add ( startState , data ) ; EarleySet Qprime = new EarleySet ( 0 , sorts . size ( ) ) ; for ( int k = 0 ; k < data . words . length ; k ++ ) { EarleySet Q = Qprime ; Qprime = new EarleySet ( k + 1 , sorts . size ( ) ) ; for ( EarleyState state : S . get ( k ) ) { if ( state . item != state . prod . items . size ( ) && state . prod . items . get ( state . item ) . isNonTerminal ( ) ) { predict ( S , Q , state , k , data ) ; } else { complete ( S , Q , state , k , data ) ; } } S . get ( k ) . finish ( ) ; for ( EarleyState state : Q ) { scan ( S , Qprime , state , k , data ) ; } if ( S . get ( k + 1 ) . empty ( ) && Q . empty ( ) ) { parseError ( data , k ) ; } } if ( S . get ( data . words . length ) . empty ( ) ) { parseError ( data , data . words . length - 1 ) ; } return Ambiguity . apply ( S . get ( data . words . length ) . states . get ( 0 ) . parseTree ( ) . stream ( ) . map ( list -> list . get ( 0 ) ) . collect ( Collectors . toSet ( ) ) ) ; }
Parse a sentence according to the grammar represented by this parser.
Parse a sentence according to the grammar represented by this parser .
// compute metadata about sentence // initialize Earley sets // initialize initial state of algorithm // add initial state to S[0] // Q' is initially empty // for each position in the tokenized sentence, compute S[k] and Q // loop through S[k] and process each state, predicting and completing it // state is ready to process a non-terminal, therefore predict // state is finished with a production, therefore complete // states ready to process a terminal are added to Q and thus do not appear in S // loop through Q and process each state, scanning it // this loop condition is a bit tricky because we want to stop at the exact loop iteration that parsing failed // in order to generate the correct error message. Nominally speaking, parsing succeeds if after all loop // iterations, S[data.words.length] contains the state (productions.get(0), 2, 0). However, if S[k+1] is empty and // Q is empty at this point, then Qprime must also be empty. Thus, if k+1==data.words.length, S[data.words.length] // is empty, which means it's a parse error. And if k+1<data.words.length, then in the next loop iteration, // S[k] and Q will both start out empty, which means that no more states can ever be added at any point. As a // result, it will eventually be a parse error. Thus, the following condition is sufficient to prove that a // parse error will occur, and we can therefore report it now. The condition is not necessary, so we check for // a parse error after the outer loop finishes also. // no more states to process, so it must be a parse error // finished parsing successfully, so return the final parse forest