【編譯原理】龍書(shū)第二章課后題答案

【編譯原理】龍書(shū)第?章課后題答案

Exercis for Section 2.2

2.2.1

Consider the context-free grammar:

S -> S S + | S S * | a

1. Show how the string can be generated by this grammar.

aa+a*

2. Construct a par tree for this string.

3. What language does this grammar generate? Justify your answer.

Answer

1. -> S * -> S + S * -> a + S * -> a a + * -> a a + a *

SSSSS

2.

3. L = {Postfix expression consisting of digits, plus and multiple signs}

2.2.2

What language is generated by the following grammars? In each ca justify your answer.

1. S -> 0 S 1 | 0 1

2. S -> + S S | - S S | a

3. S -> S ( S ) S | ε

4. S -> a S b S | b S a S | ε

1. No

2. No

3. Yes

1. Arithmetic expressions in postfix notation.

2. Left-associative lists of identifiers parated by commas.

3. Right-associative lists of identifiers parated by commas.

1. Proof

Any string derived from the grammar can be considered to be a quence consisting of 11 and 1001, where each

quence element is possibly suffixed with a 0.

Let be the t of positions where is placed. is said to be at position if the first in is at position ,

n1111i111i

where starts at 0 and

i

grows from least significant to most significant bit.

Let be the equivalent t for .

m1001

The sum of any string produced by the grammar is:

sum

= Σ (2 + 2) * 2 + Σ (2 + 2) * 2

nm

10n30m

= Σ 3 * 2 + Σ 9 * 2

nm

nm

This is clearly divisible by 3.

2. No. Consider the string “10101”, which is divisible by 3, but cannot be

derived from the grammar.

Readers eking a more formal proof can read about it below:

Proof:

Every number divisible by 3 can be written in the form . We will consider (though it would be valid to consider

3kk > 0

k

to be an arbitrary integer).

Note that every part of num(11, 1001 and 0) is divisible by 3, if the grammar could generate all the numbers divisible

by 3, we can get a production for binary k from num’s production:

3k = num -> 11 | 1001 | num 0 | num num

k = num/3 -> 01 | 0011 | k 0 | k k

k -> 01 | 0011 | k 0 | k k

It is obvious that any value of that has more than 2 concutive bits t to 1 can never be produced. This can be

k

confirmed by the example given in the beginning:

10101 is 3*7, hence, k = 7 = 111 in binary. Becau 111 has more than 2

concutive 1’s in binary, the grammar will never produce 21.

2.2.6

Construct a context-free grammar for roman numerals.

Note: we just consider a subt of roman numerals which is less than 4k.

Answer

via wikipedia, we can categorize the single roman numerals into 4 groups:

I, II, III | I V | V, V I, V II, V III | I X

then get the production:

digit -> smallDigit | I V | V smallDigit | I X

smallDigit -> I | II | III | ε

and we can find a simple way to map roman to arabic numerals. For example:

XII => X, II => 10 + 2 => 12

CXCIX => C, XC, IX => 100 + 90 + 9 => 199

MDCCCLXXX => M, DCCC, LXXX => 1000 + 800 + 80 => 1880

via the upper two rules, we can derive the production:

romanNum -> thousand hundred ten digit

thousand -> M | MM | MMM | ε

hundred -> smallHundred | C D | D smallHundred | C M

smallHundred -> C | CC | CCC | ε

ten -> smallTen | X L | L smallTen | X C

smallTen -> X | XX | XXX | ε

digit -> smallDigit | I V | V smallDigit | I X

smallDigit -> I | II | III | ε

What language is generated by the following grammars? In each ca justify your answer.

1. S -> 0 S 1 | 0 1

2. S -> + S S | - S S | a

3. S -> S ( S ) S | ε

4. S -> a S b S | b S a S | ε

5. S -> a | S + S | S S | S * | ( S )

Answer

Construct unambiguous context-free grammars for each of

the following languages. In each ca show that your grammar is correct.

1. Arithmetic expressions in postfix notation.

1. Proof

Any string derived from the grammar can be considered to be a quence consisting of 11 and 1001, where each

quence element is possibly suffixed with a 0.

Let be the t of positions where is placed. is said to be at position if the first in is at position ,

n1111i111i

where starts at 0 and

i

grows from least significant to most significant bit.

Let be the equivalent t for .

m1001

The sum of any string produced by the grammar is:

sum

= Σ (2 + 2) * 2 + Σ (2 + 2) * 2

nm

10n30m

= Σ 3 * 2 + Σ 9 * 2

nm

nm

This is clearly divisible by 3.

2. No. Consider the string “10101”, which is divisible by 3, but cannot be

derived from the grammar.

Readers eking a more formal proof can read about it below:

Proof:

Every number divisible by 3 can be written in the form . We will consider (though it would be valid to consider

3kk > 0

k

to be an arbitrary integer).

Note that every part of num(11, 1001 and 0) is divisible by 3, if the grammar could generate all the numbers divisible

by 3, we can get a production for binary k from num’s production:

3k = num -> 11 | 1001 | num 0 | num num

k = num/3 -> 01 | 0011 | k 0 | k k

k -> 01 | 0011 | k 0 | k k

It is obvious that any value of that has more than 2 concutive bits t to 1 can never be produced. This can be

k

confirmed by the example given in the beginning:

10101 is 3*7, hence, k = 7 = 111 in binary. Becau 111 has more than 2

concutive 1’s in binary, the grammar will never produce 21.

2.2.6

Construct a context-free grammar for roman numerals.

Note: we just consider a subt of roman numerals which is less than 4k.

Answer

via wikipedia, we can categorize the single roman numerals into 4 groups:

I, II, III | I V | V, V I, V II, V III | I X

then get the production:

digit -> smallDigit | I V | V smallDigit | I X

2.3.2

num -> thousand hundred ten digit

{ = || || || ;

print()}

thousand -> low { = repeat('M', low.v)}

hundred -> low { = repeat('C', low.v)}

| 4 { = 'CD'}

| high { = 'D' || repeat('X', high.v - 5)}

romanNum -> thousand hundred ten digit {romanNum.v = thousand.v || hundred.v || ten.v || digit.v; print(romanNun.v)}

thousand -> M {thousand.v = 1}

| MM {thousand.v = 2}

| MMM {thousand.v = 3}

| ε {thousand.v = 0}

hundred -> smallHundred {hundred.v = smallHundred.v}

| C D {hundred.v = smallHundred.v}