Question

Now that you know a bit about BNF's, try writing a grammar (productions) for the "language" of a phone number, which consists of:

• three digits enclosed in parentheses - the first digit cannot be "0" (zero)
• followed by three digits - the first digit cannot be "0" (zero)
• followed by a "-" (dash)
• followed by four digits

So, (757)530-4601 is a valid phone number. All the following numbers are invalidaccording to this grammar:

• 757-530-4601 (area code is not in parentheses)
• (757)530.4601 (missing dash after the exchange)
• (919)-555-5555 (stray dash after area code)
• (019)555-5555 (area code cannot start with zero)
• and so on

Once you have a grammar, write down:

• the derivation of one correct phone number - give both the sequence of substitutions and the parse tree representation

• the attempted derivation of one incorrect phone number - list the sequence of substitutions OR draw the parse tree until the derivation "breaks." Write a note explaining why the derivation can go no further.

Answer 1

Grammar for the language of a phone number:

S -> (N)N-M

N -> DZZ

M -> ZZZZ

Z -> 0|D

D -> 1|2|3|4|5|6|7|8|9

where S, N, M, D, Z are non-terminals. and (,),-,0,1,2,3,4,5,6,7,8,9 are terminals and S is the start symbol.

S is the phone number, N is the 3 digit number not begin with 0, M is 4 digit number and Z corresponds digits including 0 and D corresponds digits excluding 0.

The derivation of correct phone number using parse tree method:

(757)530-4601

using sequence substitution method (top down method):

S

=> (N)N-M    // rule 1

=> (DZZ)DZZ-ZZZZ // rule 2 and 3

=> (7DD)5D0-DD0D // rule 3 and 4

=> (757)530-4601 // rule 4

Now test for an incorrect phone number:

(019)555-5555

In case of incorrect phone number the derivation can't go further because while expanding N the first non-terminal is D which corresponds to digit but not zero. where in phone number left N begins with 0(zero). Here there is no rule we can apply.

Hence derivation should be terminated with error.