Homework # 1
due Thursday, March 8, 2:00 PM

Natural Language Grammars

A simple grammar for Chinese may include the following rules:

<S> ::= <NP> <VP>。
<NP> ::= <N> | <Num> <MW> <N>
<Num> ::= 一 | 两
<MW> ::= 个 | 条 | 只 | 口
<N> ::= 猫 | 狗 | 猪
<VP> ::= <V> <NP>
<V> ::= 吃 | 爱 | 怕

• Give two sentences generated by this grammar.
• This grammar does not handle the following sentence:

  狗前边的一只猫怕狗。

  Add new rules to accept sentences like this, as well as the simple sentences already handled. The new rules should (in principle) accept (overly complex) sentences such as the following:

  猪上边的一条狗上边的一只猫吃老鼠。

  (``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'':

(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. Please put your name and student ID number (学号) on the top. Turn the homework in at the beginning of lecture, March 8th. If you cannot get to lecture ahead of time, please turn it in to my office, 蒙民伟楼 (MMW Building) 312.

About this document