Formal Language Processing in Scala, Solutions to Part 2
August 5th, 2008 | In ScalaHere are the solutions to the exercises from part 2.
1.
rep1 can be defined in terms of rep by first applying the parser for the repeated element once and then calling rep.
def rep1(p: (List[Any] => Option[List[Any]]))(
l:List[Any]): Option[List[Any]] = p(l) match {
case None => None
case Some(rest) => rep(p)(rest)
}
2.1
def asteriskOrPlus(l:List[Any]): Option[List[Any]] = l match {
case "*" :: rest => Some(rest)
case "+" :: rest => Some(rest)
case _ => None
}
2.2
def asterisk(l:List[Any]): Option[List[Any]] = l match {
case "*" :: rest => Some(rest)
case _ => None
}
def plus(l:List[Any]): Option[List[Any]] = l match {
case "+" :: rest => Some(rest)
case _ => None
}
def asteriskOrPlus(l:List[Any]): Option[List[Any]] = asterisk(l) match {
case r @ Some(rest) => r
case None => plus(l)
}
2.3
def lift(str:String)(l:List[Any]): Option[List[Any]] = l match {
case s :: rest if(s == str) => Some(rest)
case _ => None
}
Notice the “if” clause. Using “case str :: rest => …” would introduce a new str variable which shadows the existing one instead of matching against the existing variable.
2.4
def choice(a: (List[Any] => Option[List[Any]]),
b: (List[Any] => Option[List[Any]]))(
l:List[Any]): Option[List[Any]] = a(l) match {
case r @ Some(rest) => r
case None => b(l)
}