Parsing 2

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)

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 = "[" ( item ( "," item )* )? "]"
```

Give three derivations of this rule http://ActiveLecture.org

Lexical Analysis

Parsing assumes that input stream is already grouped into tokens
Lexical analysis
- Group characters into tokens
- Discard whitespace
Also rule-driven, but rules are much simpler
Usually specified by regular expressions
Example: Decimal number
```
(\d+(\.\d*)?|\d*\.\d+)
```
Here, \d is a decimal digit, \. is a period, and + * ? | are as in EBNF
Give three derivations of this rule http://ActiveLecture.org

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

Check into eCampus in the usual way
Scribe puts in report
Buddy puts in comment with scribe's name

Step 1

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

package lab10

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)
  }
}

Run the application. What is the output?
Now change the expression to 3 * 4 - 5. How does the output differ?
How does this indicate that the grammer “knows” that multiplication binds more strongly than addition?
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?
What happens when you give an illegal input to the parser? What input did you give, and what was the result?

Step 2

Add the following function to the SimpleLanguageParser:

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)
}

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?
What does the eval function do?
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

Now we want to enhance the language and add support for statements such as
```
val x = 3 + 4 * y
```
Add a valdef type to the combinator parser that represents such a definition, and enable identifiers in factor. (Hint: Scaladoc of JavaTokenParsers)
What happens when you parse val x = 3 + 4 * y? What do you do to fix the problem?
Now what is the parser output?