Tutorial 2

t2.pdf | t2-sol.pdf

Question 1

Part A For each of the following grammars, describe the language (set of strings) that the grammar generates

1. $$A\rightarrow A\ ":"\ N\ |\ N\\N\rightarrow 0\ |\ 1$$

   The grammar produces any non-empty string of “0” or “1” with colons separating the digits

   $\scriptsize L(G)=\{\text{"0"},\ \text{"1"},\ \text{"0:0"},\ \text{"0:1"},\ \text{"1:0"},\ \text{"1:1"},\ \text{"0:0:0"},\text{"0:0:1"},\ \text{"0:1:0"},\ \text{"0:1:1"},\ \text{"1:0:0"}, \cdots\}$

2. $$A\rightarrow A\ N\ |\ \epsilon\\N\rightarrow 0\ |\ 1$$

   The grammar produces any string of “0” or “1”, including the empty string

   $\scriptsize L(G)=\{"", "0", "1", "00","01","10","11","000","001","010","011","100","101","110","111",\cdots\}$

3. $$A\rightarrow A\ A\ |\ N\\N\rightarrow\ 0\ |\ 1$$

   The grammar produces any non-empty string of “0” or “1”

   $\scriptsize L(G)=\{"0", "1", "00","01","10","11","000","001","010","011","100","101","110","111",\cdots\}$

4. $$A\rightarrow A\ N\ |\ N|\ \epsilon\\N\rightarrow0\ |\ 1$$

   The grammar produces any string of “0” or “1” including the empty string.

   $\scriptsize L(G)=\{"","0", "1", "00","01","10","11","000","001","010","011","100","101","110","111",\cdots\}$

Part B For each of the grammars in Q1a state whether or not the grammar is ambiguous. If the grammar is ambiguous, give a string for which there is more than one parse tree, and show the two different parse trees.

1. The grammar is unambiguous

2. The grammar is unambiguous

3. Ambiguous - Consider the string parsing of the string 000

   

4. Ambiguous - Consider the parsing of the string 0

   

Question 2

Part A Given the grammar $A\rightarrow A\ A\ |\ "("\ A\ ")"\ |\epsilon$, describe the language it generates

This language generates any string of arbitrary set of matched parentheses including the empty string

$\scriptsize\{\epsilon, (), (()), ((())), \cdots,()(),(())(()),((()))((())),\cdots,()()(),(())(())(()),((()))((()))((()))\cdots\}$

Part B Given the grammar $A\rightarrow A\ A\ |\ "("\ A\ ")"\ |\epsilon$, show that the grammar is ambiguous, e.g. consider possible parse trees for the string “()” or even the empty string “”

• Consider the empty string $\epsilon$. There is ambiguity in the way that we parse it

• The image to the right describes the two possible symbols for the empty string $\epsilon$.

• It is also possible to generate a parse tree using the second option in our grammar definition

  

• We could also show that the parse tree of a single set of matched parentheses is ambiguous

  

Question 3

Given the grammar:

$$E\rightarrow E\ "+"\ T\ |\ E\ "-"\ T\ | \ T\\T\rightarrow\ T\ "*"\ F\ |\ F\\F\rightarrow\ "("\ E\ ")"\ |\ \bold{number}$$

write down the leftmost derivations (i.e. expand the leftmost non-terminal in each step), parse trees and abstract syntax trees for the following expressions. You may abbreviate a number token $\bold{number(3)}$ by $\bold{3}$. (a). $3+4+5$

The leftmost derivation is shown below, where the non-terminal symbol being expanded is over-lined.

(b) $3+4*5-6$

(c) $3*(4-5*6)$

(d) $3-(4+5*6)$

Question 4

The following grammar for if-then-else statements is proposed to remedy the dangling-else ambiguity:

Show that it is still ambiguous

• Consider the string

  $$\text{if false then if false then other else if false then other else other}$$

• This string can be parsed as either of the following, in which the braces are not part of the string, but to show grouping:

if false then {
  if false then 
    other
  else {
    if false then 
      other
    else 
      other
  }
}

if false then {
  if false then
    other
  else {
    if false then {
      other
    }
} else
  other
}

Question 5

Unary minus can be added in several ways to the simple arithmetic expression grammar:

$$E \rightarrow E\ "+"\ T\ |\ E\ "-"\ T\ | \ T\\T \rightarrow T\ "*"\ F\ |\ F\\F\rightarrow\ "("\ E\ ")"\ |\ \bold{number}$$

Revise the grammar for each of the cases that follow, so that it satisfies the stated rule.

1. At most one unary minus is allowed in each expression, and it must come at the beginning of an expression

   ✅ $-2-3$
   ✅ $-2-(-3)$
   ❌$2--3$
   

   First Solution

   • We can make a distinction at the top level between an expression that starts with a unary minus (NE) and one that doesn’t (E) - those have similar syntax:

     $$S \rightarrow NE\ |\ E\\ NE\rightarrow NE\ "+"\ T\ |\ E\ "-"\ T\ |\ "-"\ T\\ E\rightarrow E\ "+"\ T\ |\ E\ "-"\ T\ |\ T\\ T\rightarrow T\ "*"\ F\ |\ F\\ F\rightarrow\ "("\ S\ ")"\ |\ \bold{number}$$

   Second Solution

   The tutor had this solution, but the expression with the unary operator on a separate line - this is the same as this solution.

   • An alternative simpler syntax also derives the correct sentence:

     $$E\rightarrow E\ "+"\ T\ |\ E\ "-"\ T\ |\ T\ | "-"T\\ T\rightarrow\ T\ "*"\ F\ |\ F\\ F\rightarrow "("\ E\ ")"\ |\ \bold{number}$$

Note that while both of these grammars derive the same language (set of strings), they produce different parse trees.

2. At most one unary minus is allowed before a number or left parenthesis

   ✅ $-2--3$
   ❌$--2$
   ❌$-2---3$
   

   Sample Solution (Same as Tutor’s Solution)

   $$E\rightarrow E\ "+"\ T\ |\ E\ "-"\ T\ |\ T\ | "-"T\\ T\rightarrow\ T\ "*"\ U\ |\ U\\ U\rightarrow "-"F\ |\ F\\ F\rightarrow "("\ E\ ")"\ |\ \bold{number}$$

3. Arbitrarily many unary minuses are allowed before numbers and left parentheses, so everything above is legal.

   Sample Solution

   $$E\rightarrow E\ "+"\ T\ |\ E\ "-"\ T\ |\ T\\ T\rightarrow T\ "*"\ F\ |\ F\\ F\rightarrow\ "-"\ F\ |\ "("\ E\ ")"\ |\ \bold{number}$$

   Tutor’s Solution

   $$E\rightarrow E\ "+"\ T\ |\ E\ "-"\ T\ |\ T\\ E\rightarrow"-"E\\ T\rightarrow T\ "*"\ F\ |\ F\\ F\rightarrow\ \ "("\ E\ ")"\ |\ \bold{number}$$