package cs241e.assignments

import cs241e.scanparse._
import Grammars._
import DFAs._

import scala.collection.mutable

/** Parsers for general grammars. */

object Parsing {
  /** Parses the `input` sequence of `Token`s according to the `grammar` using the Cocke-Younger-Kasami algorithm.
    * Specifically, the `kind`s of the `Token`s are considered as the terminals of the grammar, and the
    * `lexeme`s are not used for parsing but are preserved in the resulting parse tree.
    * If the parse is ambiguous, returns an arbitrary one of the possible parse trees.
    * If the `input` is not in the language generated by the grammar, returns `None`.
  def parseCYK(grammar: Grammar, input: IndexedSeq[Token]): Option[Tree] = {
    /** The memoization table: if the string of non-terminals ABC derives the substring of length `length`
      * starting at position `from` of the `input`, then the entry for (Seq("A", "B", "C"), from, length)
      * contains the three parse trees of A, B, and C. If a particular string of non-terminals
      * does not derive a given substring of the `input`, the corresponding table entry is `None`.
    val memo = mutable.Map[(Seq[String], Int, Int), Option[Seq[Tree]]]()

    /** If the string of non-terminals `lhs` derives the substring of length `length`
      * starting at position `from` of the `input`, returns a sequence of the parse trees for the
      * non-terminals in `lhs`.
      * If `lhs` does not derive this substring of the input, returns `None`.
    def recur(lhs: Seq[String], from: Int, length: Int): Option[Seq[Tree]] = { ??? }

    recur(Seq(grammar.start), 0, input.size).map(_.head)

  /** Parses the `input` string of terminals according to the `grammar` using Earley's algorithm.
    * Returns `true` if the `input` string is in the language generated by the `grammar`,
    * `false` otherwise.
    * Note: Optional, for bonus only.
  def parseEarley(grammar: Grammar, input: IndexedSeq[String]): Boolean = { ??? }