Grammar Analysis and Context-Free Language Exercises

Hexadecimal Integer Grammar Analysis

Consider the following grammar for hexadecimal integers:

• <hex literal> ::= 0x<number>
• <number> ::= <number><number> | <digit>
• <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F

The string 0xF3 is an element of the language generated by this grammar.

Derivation Sequences and Parse Trees

1. How many distinct derivation sequences exist for this string?

There exist 6 distinct derivation sequences:

• <hex literal> ⇒ 0x<number> ⇒ 0x<number><number> ⇒ 0x<digit><number> ⇒ 0x<digit><digit> ⇒ 0xF<digit> ⇒ 0xF3
• <hex literal> ⇒ 0x<number> ⇒ 0x<number><number> ⇒ 0x<number><digit> ⇒ 0x<digit><digit> ⇒ 0xF<digit> ⇒ 0xF3
• <hex literal> ⇒ 0x<number> ⇒ 0x<number><number> ⇒ 0x<digit><number> ⇒ 0x<digit><digit> ⇒ 0x<digit>3 ⇒ 0xF3
• <hex literal> ⇒ 0x<number> ⇒ 0x<number><number> ⇒ 0x<number><digit> ⇒ 0x<digit><digit> ⇒ 0x<digit>3 ⇒ 0xF3
• <hex literal> ⇒ 0x<number> ⇒ 0x<number><number> ⇒ 0x<digit><number> ⇒ 0xF<number> ⇒ 0xF<digit> ⇒ 0xF3
• <hex literal> ⇒ 0x<number> ⇒ 0x<number><number> ⇒ 0x<number><digit> ⇒ 0x<number>3 ⇒ 0x<digit>3 ⇒ 0xF3

2. How many distinct parse trees exist for this string?

There is one parse tree. (Show all parse trees: in this case, only one exists).

Ambiguity in Conditional Statement Grammars

Consider the following grammar with the starting non-terminal <stmt>:

• <stmt> ::= if ( <cond> ) <expr> else <expr>
• <expr> ::= INTCONST | ( <expr> + <expr> )
• <cond> ::= <expr> < <expr> | <expr> == <expr> | <cond> && <cond> | ! ( <cond> ) | ( <cond> )

Justifying Grammar Ambiguity

Is the grammar ambiguous?

Yes. For example, there are two parse trees for the string: if (0 < 1 && 2 < 3 && 4 < 5) 6 else 7.

Language Recognition and Grammar Modifications

Suppose we modify the grammar from the previous problem by adding one more production alternative for <cond>:

<cond> ::= <expr> < <expr> | <expr> == <expr> | <cond> && <cond> | ! ( <cond> ) | ( <cond> ) | <expr>

Comparing Language Recognition

Does this grammar recognize the same language as the previous one?

No. For example, only the second grammar recognizes the string: if (33) 4 else 1.

Alternating Strings: Regular Expressions and CFGs

Consider a language of strings of alternating a's and b's starting with a:

L = {ε, a, ab, aba, abab, ababa, ...}

Part A: Regular Expression

Write a regular expression that recognizes L:

(ab)*a?

Part B: Context-Free Grammar

Write a context-free grammar that recognizes L:

• <start> ::= ε
• | a b <start>
• | a

Part C: Parse Tree for "aba"

Draw a parse tree for aba using your grammar from Part B. (If your grammar is ambiguous and allows multiple parse trees for aba, just draw one of them.)

The grammar is non-ambiguous, so there is only one parse tree.