UNB/ CS/ David Bremner/ teaching/ cs3613/ tutorials/ CS3613 Tutorial 4

Introduction

In this assignment you will use the ragg parser toolkit to parse transcripts of encounters with dogs. These are represented as strings containing "wag", "growl", "bark", "slobber", and "bite", separated by whitespace. Each encounter is ended with a ’.’; an example input follows:

slobber slobber.
wag wag slobber. growl bark.
growl bark bite.

You should have help on ragg in drracket, under "Help -> Racket Documentation -> Miscellaneous Libraries".

Structure of solutions.

Unlike in your assignments, you will need to use multiple files for this tutorial. You can download the lexer

Write your parser in a second file starting with #lang ragg, and use the two of them from a third driver file like the following. Note that we're using plai, not plai-typed. Also notice you need to use some custom error handling code, rather than test/exn.

#lang plai

(require "grammar-1.rkt")
(require "lexer.rkt")

(define (string->sexpr str)
  (syntax->datum (parse (tokenize-string str))))

(define (catch-parse-error str)
  (with-handlers ([exn:fail? (lambda (v) 'fail)])
    (string->sexpr str)))

(test  
 (string->sexpr "bark bark.")
 '(dog (sentence (angry (before-bite "bark" "bark")) ".")))

(test (catch-parse-error "bite.") 'fail)

1. Happy Dog, Angry Dog

In this question you should construct BNF grammar that enforces the following rules:

  1. Every dog encountered is either happy or angry.
  2. A happy dog always slobbers at least once.
  3. A happy dog may wag several times before slobbering, but once it starts slobbering, it stops wagging.
  4. An angry dog may growl several times before barking, but once it starts barking, it stops growling.
  5. An angry dog does not necessarily bite, but it always growls or barks before biting.

The examples in the introduction are all valid for these rules. Here some examples of invalid encounters.

bite.
bark wag.
growl bark growl.

Here is the beginning of a solution

dog: sentence +

sentence: happy "." | angry "."

Add tests to your driver to test each of the 5 rules given above.

2. To every Slobber a Wag

As an extra challenge, modify your first grammar to enforce the additional rule that the number of wags and slobbers of any happy dog is exactly equal. For this question "wag wag slobber slobber." is valid, but "wag slobber slobber." and "wag wag slobber." are not.