Homework # 1
due Tuesday, February 3, 2:00 PM

Controversies

On the 'net, find a debate between the proponents of two different languages. Print out an argument from one side and an answer from the other side. Make sure the rebuttal addresses the points argued by the first.

Then, as well as you can, evaluate whether the argument is still valid, or whether the rebuttal demolished the argument, or something in between. I don't want your opinion; I want reasoned evaluation.

Natural Language Grammars

A simple grammar for English may include the following rules:

<S> ::= <NP> <VP>
<NP> ::= <Det> <N>
<Det> ::= a | the
<N> ::= dog | cat | rat
<VP> ::= <V> <NP>
<V> ::= eats | loves | hates

This grammar does not handle the following sentences:

the cat sleeps

the cat by the dog eats the rat in the house

Add new rules to accept these sentences, as well. The new rules should (in principle) accept sentences such as the following:

The cat on the sofa in the house next to the river to the sea sleeps

(``In principle'' here means assume we added the individual words as well.)

Programming Language Grammars

The syntax diagrams in the textbook use arrows. More traditionally, ``railroad diagrams'' use curves to show which direcion is permitted: a train can never take a sharp corner. The following example shows a true ``railroad diagram.''

Cool 2004, the language for which CompSci 654 students are writing a compiler has the following definition for a block:

(The graphic above doesn't look right in the generated HTML; there is a missing semicolon after each declaration, and after the optional declare part is done, it goes down to the begin-end block.) Nonterminals are lowercase words in rectangular boxes. Terminals are either UPPERCASE words in boxes, or literal (quoted) characters in ovals.

• Express this rule as a single production in EBNF. You may use the notation to repeat something one or more times. Warning: `` '' puts a semicolon after every expression, including the last!

• Write it in strict BNF, following the textbook's style. You will need to add new nonterminals, and have several productions. (Our solution has ten productions and adds five intermediate nonterminals.)

  A simple way to convert EBNF to BNF, is to add a new nonterminal $N$ for each parenthesized sequence. Then the new nonterminal gets new rules depending on the parenthesization:

  

          <$N$> ::= $x$ | $x$ <$N$>

  

          <$N$> ::= <empty> | $x$ <$N$>

  

          <$N$> ::= <empty> | $x$

Submitting Your Work

This homework is done on paper only. Turn it in at the beginning of lecture, February 3rd. If you cannot get to lecture ahead of time, please turn it in to my mailbox on the 5th floor of EMS before the deadline.

About this document