Parsing 3

• Context-Free Grammars
• BNF
• Combinator parsers

Context-Free Grammar

• Language: Set of valid token sequences
• Terminal symbol: Token in the language. Ex: "class" "3.14" "("
• Nonterminal symbol: Symbols in the grammar. Ex. expression
• Production: Rule for replacing a nonterminal by a sequence of nonterminals and terminals

  term ::= factor * term

• Can have more than one production for the same nonterminal

  term ::= factor

• Derivation: Sequence of productions

  term ::= factor * term
    ::= factor * factor * term
    ::= factor * factor * factor

• Context-free: The replacement doesn't depend on the context of the nonterminal

Parse Tree

• Shows derivation process

  

• Not the same as an expression tree!
• Parser: Component that follows derivation process, yielding some actions
• Most common actions: Building an expression tree. (Next lecture)

Grammar Example: List of Numbers

• Want to generate

  (1)
  (1, 24, 4)
  ()

• list ::= "(" contents ")"

• contents ::=
  contents ::= number
  contents ::= number "," contents

• No, that's wrong. We could derive (1, 24, )

Grammar Example: List of Numbers

• Try again

• list ::= "(" contents ")"
  list ::= "(" ")"

• contents ::= number
  contents ::= number "," contents

• Easy to see by induction that contents yields n numbers separated by n - 1 commas

Extended BNF

• Backus-Naur form: Original syntax for grammar rules in Algol-60
• Extended by conveniences for frequently recurring constructs
• Alternatives A | B
• Repetitions
  • 0 or more (A)* or {A}
  • 1 or more (A)+
  • 0 or 1 (A)? or [A]
• For example,

  list = "(" ( number ( "," number )* )? ")"

Parser Generators

• Parser generator: Produces a parser from a given grammar
• Works in conjunction with lexical analyzer
• Examples: yacc, Antlr, JavaCC
• Programmer specifies actions to be taken during parsing
• Far better than writing a parser by hand
• No free lunch: need to know parsing theory to build efficient parsers
• Scala has a built-in “combinator parser”

Combinator Parser

• Each nonterminal becomes a function
• Terminals (strings) and nonterminals (functions) are combined with operators
  • Sequence ~
  • Alternative |
  • 0 or more rep(...)
  • 0 or 1 opt(...)

  class SimpleLanguageParser extends JavaTokenParsers {    
    def expr: Parser[Any] = term ~ opt(("+" | "-") ~ expr)
    def term: Parser[Any] = factor ~ opt(("*" | "/" ) ~ term)
    def factor: Parser[Any] = wholeNumber | "(" ~ expr ~ ")"
  }

• Will replace Parser[Any] with something more useful later

Combinator Parser Result

• String returns itself
• opt(P) returns Option: Some of the result of P, or None
• rep(P) returns List of the results of P
• P ~ Q returns instance of class ~ (similar to a pair)
• For example,

  val parser = new SimpleLanguageParser
  val result = parser.parse(parser.expr, "3 - 4 * 5")

  sets result to

  ((3~None)~Some((-~((4~Some((*~(5~None))))~None))))

• We'll transform this to something more useful in the next lecture
• After changing (x~None) to x, Some(y) to y, and ~ to spaces:

  (3 (- (4 (* 5))))

Lab

• One of you writes the code, the other types up answers
• Switch coder/scribe roles each lab

  ubmit lab work to Sakai.

Step 1

1. Here is the complete application that was discussed in the lecture:

   package parsing3
   
   import scala.util.parsing.combinator._
   
   class SimpleLanguageParser extends JavaTokenParsers {    
     def expr: Parser[Any] = term ~ opt(("+" | "-") ~ expr)
     def term: Parser[Any] = factor ~ opt(("*" | "/" ) ~ term)
     def factor: Parser[Any] = wholeNumber | "(" ~ expr ~ ")"
   }
   
   object Main {
     def main(args: Array[String]) = {
       val parser = new SimpleLanguageParser
       val result = parser.parse(parser.expr, "3 - 4 * 5")
       println(result)
     }
   }

2. Run the application. What is the output?
3. Now change the expression to 3 * 4 - 5. How does the output differ?
4. How does this indicate that the grammer “knows” that multiplication binds more strongly than addition?
5. The factor rule recurses back to the expr rule. Give an example input to the parser that demonstrates this feature. What is your input? What is the output?
6. What happens when you give an illegal input to the parser? What input did you give, and what was the result?

Step 2

1. Add the following function to the SimpleLanguageParser (and not to Main):

   def eval(x : Any) : Int = x match {
     case a ~ Some("+" ~ b) => eval(a) + eval(b)
     case a ~ Some("-" ~ b) => eval(a) - eval(b)
     case a ~ Some("*" ~ b) => eval(a) * eval(b)
     case a ~ Some("/" ~ b) => eval(a) / eval(b)
     case a ~ None => eval(a)
     case a : String => Integer.parseInt(a)
     case "(" ~ a ~ ")" => eval(a)
   }

2. In your main program, print the value computed by parser.eval(result.get). What output do you get when the parser input is 3 - 4 * 5? 3 * 4 - 5?

3. What does the eval function do?
4. Give an input that shows that the last matching rule is necessary. What is your input? What is the output? What result do you get when you comment out the last matching rule?

Step 3

1. Now we want to enhance the language and add support for statements such as

   val x = 3 + 4 * y

   In BNF, this would be

   valdef ::= "val" identifier "=" expr

   Add a valdef type to the combinator parser that represents such a definition. (To see how to parse an identifier, go to the scaladoc of JavaTokenParsers and then click on the source link on the top of the file.)

   What is the type that you added?

2. What do you get when you parse val x = 3 + 4? Hint: Remember to call

   parser.parse(parser.valdef, "val x = 3 + 4")

3. What happens when you parse val x = 3 + 4 * y? (Hint: Look closely at the output. Where is the y? Why?)
4. What do you do to fix the problem? (Hint: Handle variable identifiers at the same level as numbers.)
5. Now what is the parser output?