Formal Language Processing in Scala, Solutions to Part 1
July 29th, 2008 | In ScalaHere are the solutions to the exercises from part one.
1.1
programUnit = statement* statement = "print" expression expression = numericLit ( ( "+" | "*" ) numericLit )*
1.2 & 1.3
There is a left-recursive solution:
programUnit = ( programUnit "print" expression )?
And a right-recursive one:
programUnit = ( "print" expression programUnit )?
1.4
programUnit = ( "print" expression )* expression = term ( "+" term )* term = factor ( "*" factor )* factor = numericLit
1.5
Again there is a left-recursive solution:
programUnit = ( programUnit "print" expression )? expression = ( expression "+" )? term term = ( term "*" )? factor factor = numericLit
And a right-recursive one:
programUnit = ( "print" expression programUnit )? expression = term ( "+" expression )? term = factor ( "*" term )? factor = numericLit
1.6
Change the definition of “factor” to:
factor = numericLit | ( "(" expression ")" )
This works for both, the left- and right-recursive version.
2.
The parser uses the right-recursive version of the grammar. You could implement the iterative version in a similar fashion. You could not implement the left-recursive version in a recursive-descent parser. Recursing without consuming any tokens would lead to an endless loop.