Parsers Talk Notes

ambiguity-example.txt

S ::= S S S
    | S S
    | 'a'


aaaaaaaaaaaaaaaaaaaaaaaaaaaaa

O(n^3)

bnf-example.txt

E ::= E '+' E
    | E '-' E
    | \d+

1 + 2 + 3

derivative-parsing-example.scala

/*
 * e ::= e '*' e
 *     | e '/' e
 *     | '(' e ')'
 *     | '1'
 */

 ////////////////////////////////////////////////////////


 . 1 * 1 / 1

 /*
 * e ::= . e '*' e
 *     | . e '/' e
 *     | . '(' e ')'
 *     | . '1'
 */


 1 . * 1 / 1

 /*
  * e ::= '1' . '*' e
  *     | '1' . '/' e
  *     | '1' .
  */


 1 * . 1 / 1

 /*
  * e ::= '1' '*' . e
  */


1 * 1 . / 1

 /*
  * e ::= '1' '*' '1' . '*' e
  *     | '1' '*' '1' . '/' e
  *     | '1' '*' '1' .
  */


1 * 1 / . 1

 /*
  * e ::= '1' '*' '1' '/' . e
  */


1 * 1 / 1 .

 /*
  * e ::= '1' '*' '1' '/' '1' . '*' e
  *     | '1' '*' '1' '/' '1' . '/' e
  *     | '1' '*' '1' '/' '1' .
  */

lalr-example.scala

/*
 * e ::= e '*' t
 *     | e '/' t
 *     | t
 *
 * t ::= '(' e ')'
 *     | '1'
 */

def recognize(chars: List[Char]): (Boolean, List[Char]) =
  state0(chars)

/*
 * e ::= . e '*' t
 *     | . e '/' t
 *     | . t
 *
 * t ::= . '(' e ')'
 *     | . '1'
 */
def state0(chars: List[Char]) = chars match {
  case '(' :: tail =>
    val back @ (result, tail2) = state2(tail)

    if (result)
      state6(tail2)   // shift t
    else
      back

  case '1' :: tail =>
    val back @ (result, tail2) = state5(tail)

    if (result)
      state6(tail2)   // shift t
    else
      back

  case _ => (false, Nil)
}

/*
 * t ::= . '(' e ')'
 *     | . '1'
 */
def state1(chars: List[Char]) = chars match {
  case '(' :: tail => state2(tail)
  case '1' :: tail => state5(tail)
  case _ => (false, Nil)
}

/*
 * t ::= '(' . e ')'
 */
def state2(chars: List[Char]) = {
  val back @ (result, tail) = state0(chars)

  if (result)
    state3(tail)
  else
    back
}

/*
 * t ::= '(' e . ')'
 */
def state3(chars: List[Char]) = chars match {
  case ')' :: tail => state4(tail)
  case _ => (false, Nil)
}

/*
 * t ::= '(' e ')' .
 */
def state4(chars: List[Char]) = (true, chars)

/*
 * t ::= '1' .
 */
def state5(chars: List[Char]) = (true, chars)

/*
 * e ::= . e '*' t
 *     | . e '/' t
 *     | t .
 */
def state6(chars: List[Char]) = chars match {
  case ('*' | '/') :: _ => state7(chars)
  case Nil => (true, chars)
  case _ => (false, Nil)
}

/*
 * e ::= e . '*' t
 *     | e . '/' t
 */
def state7(chars: List[Char]) = chars match {
  case '*' :: tail => state8(tail)
  case '/' :: tail => state9(tail)
  case _ => (false, Nil)
}

/*
 * e ::= e '*' . t
 *     | e '/' . t
 */
def state8(chars: List[Char]) = {
  val back @ (result, tail) = state1(tail)

  if (back)
    state9(tail)
  else
    back
}

/*
 * e ::= . e '*' t
 *     | . e '/' t

 * e ::= e '*' t .
 *     | e '/' t .
 */
def state9(chars: List[Char]) = chars match {
  case ('*' | '/') :: _ => state7(chars)
  case Nil => (true, chars)
  case _ => (false, Nil)
}

rd-example.scala

/*
 * e ::= t '*' e
 *     | t '/' e
 *     | t
 *
 * t ::= '(' e ')'
 *     | '1'
 */

def recognize(chars: List[Char]): (Boolean, List[Char]) =
  parseE(chars)

def parseE(chars: List[Char]) = {
  val back @ (result, tail2) = parseT(chars)

  if (back)
    parseETail(tail2)
  else
    (false, Nil)
}

def parseETail(chars: List[Char]) = chars match {
  case '*' :: tail => parseE(tail)
  case '/' :: tail => parseE(tail)
  case Nil => (true, Nil)
  case _ => (false, Nil)
}

def parseT(chars: List[Char]) = chars match {
  case '(' :: tail =>
    val back @ (result, tail2) = parseE(tail)

    if (back)
      parseTTail(tail2)
    else
      (false, Nil)

  case '1' :: tail => (true, tail)
  case _ => (false, Nil)
}

def parseTTail(chars: List[Char]) = chars match {
  case ')' :: tail => (true, tail)
  case _ => (false, Nil)
}