Homework # 1
due Monday, February 2, 11:00 AM

Controversies

On the 'net, find a debate between the proponents of two different languages. Print out an argument (not the whole posting!) from one side and an answer from the other side. Make sure the rebuttal addresses the point(s) argued by the first.

Then, as well as you can, evaluate whether the one 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.''

Consider a hypothetical programming language with the following definition for a ``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. Please put your name and PantherID (email) on the top. Turn the homework in at the beginning of lecture. If you cannot get to lecture ahead of time, please turn it in to my office, EMS 925.

About this document