How do I parse a string and output it as a tree?

Question
1

I need to write a Scala program which reads a string from the user, and uses either a recursive descent parser or parser combinator to determine if the input string matches the below grammar (i.e., is made up of a’s and b’s), while building a parse tree along the way. And then output the generated tree if the match is successful.

Grammar:

S -> E$
E -> C E2
E2 -> E
E2 -> NIL
C -> ‘a’ | 'b’
I am fairly new to Scala so any reading will be much appreciated, If you have any ideas please let me know how I can implement this, Thank you.

Code I already have:

class MPParser extends JavaTokenParsers{
def c[C] = (“a” | “b”) ^^ {case ch => C(ch)}
}

abstract class MatchTree
case class C(s:String) extends MatchTree

The output should look something like this:

scala> Microproject.main(Array(“ababa”))
input : ababa
[1.6] parsed: S(E(C(a),E(C(b),E(C(a),E(C(b),E(C(a),NIL()))))))

scala> Microproject.main(Array(“ababac”))
input : ababac
[1.6] failure: b' expected butc’ found

ababac
^