example05

Examples 05, 06, and 09 (Option 1 Scenario)

Based on the 5th shift/reduce conflict, we create the following options for the user:

(* Example 05 *)

             (Option 1)                     |              (Option 2)       
                                            |                       
                PLUS                        |                  IF      
               /    \                       |               /  |  \         
              IF     expr                   |           cexpr expr PLUS      
            /  |  \                         |                      /  \             
        cexpr expr expr                     |                    expr expr
                                            |
  (IF cexpr THEN expr ELSE expr) PLUS expr  |     IF cexpr THEN expr ELSE (expr PLUS expr)

Let's suppose that the user selected Option 1.

We follow the Discota algorithm modified for the context of applying tree automata in language design to learn a tree automaton that encodes the above example.

Step 1: Generate states and specify the start state

Generate states $E_1$ ... $E_k$ based on the height $k$ of tree and add to $Q_5$ along with an empty state $\epsilon$. Set $E_1$ to be the start state. Because there are only two newly generated states, we renamed $E_1$ and $E_2$ to be respectively $X$ and $Y$ for this running example.

• $Q_5$ += ${ X, Y, \epsilon }$
• $S_5$ = ${ X }$

Step 2: Rewrite the example tree as well as the representative sample w.r.t. the newly generated states

With the newly generated states, the selected example tree can be represented as follows:

                PLUS
               /    \ 
              IF2    X
            /  |  \    
           D   Y   Y

   (IF D THEN Y ELSE Y) PLUS X

The representative sample $\mathcal{E}_5$ is now equal to ${+( IF_2 ( D, Y, Y ), X ) }$. Modification of the representative sample is needed for generating the observation table in later step.

Step 3: Add $\varepsilon$-transitions and $()$-transitions based on the parent-child relationship, and $\mathbb{B}$-transition as well as $\mathbb{N}$-transition to the corresponding bottom-most leaf states

Add $\varepsilon$-transitions from each state --- excluding the bottom-most leaf state --- to its direct child state (aka $\varepsilon$-introduction) and $()$-transitions from each state --- excluding the top-most root state --- to its direct parent state. At the same time,

• $\Delta_5$ += ${ X \rightarrow_{ε} Y ; ; \ ;;;;;;;;;;; Y \rightarrow_{()} X }$

Step 4: As for the operators that do not appear in the representative sample, encode transitions with the top-most root state

Out of all the alphabets excluding $()$, $\varepsilon$, $\mathcal{N}$, and , there are 2 operators --- $MUL$ and $IF_1$ --- that do not appear in the representative sample.

Because we do not want to exclude any operators after taking intersection with the automaton from original language, we want to add transitions for the $$

Step 5: Based on the parent-children relations, learn the transitions. Verify the resulting transitions with the Angluin's tree automata-learning framework

Based on the precedences specified by the selected tree-structured example (re-written with $E_1$ and $E_2$, or $X$ and $Y$), following transitions are encoded and added to $\Delta_5$:

• $\Delta_5'$ = ${ X \rightarrow_{+} X ; X ; ; \ ;;;;;;;;;; Y \rightarrow_{IF_2} D ; Y ; Y }$
• $\Delta_5$ += $\Delta_5'$

Step 6: Verify that the learned $\mathcal{A}_5$ through Angluin's learning framework

Next, we verify that the above $\Delta_5'$ combined with $\varepsilon$-transition (i.e., $X \rightarrow_{\varepsilon} Y$) are equivalent to the transitions of the tree automaton learned from the Angluin's algorithm framework. In other words, the tree automaton learned from the is equivalent to the automaton

According to the Angluin's algorithm, an observation table $\mathcal{T}_5$ is constructed by taking subterms of the representative sample $\mathcal{E}_5$ as rows and the set of contexts $F_5$ as columns.

• Rows $S(\mathcal{E}_5)$ (subterms): ${ +(IF_2(D, Y, Y), X), IF_2(D, Y, Y), D, Y, X }$
• Columns $\mathcal{E}_5[◇]$ (contexts): ${ ◇, +(◇, X), +(IF_2(◇, Y, Y), X), +(IF_2(D, ◇, Y), X), +(IF_2(D, Y, ◇), X), +(IF_2(D, Y, Y), ◇) }$

Suppose that a cell indexed by the subterm $t$ and the context $c[◇]$ is $T_L(t, c[◇])$. Then, the content of $T_L(t, c[◇])$ is defined by the following:

$$ T_L(t, c[◇]) = \begin{cases} 1, & \text{if } c[t] \in L'\\ 0, & \text{otherwise}. \end{cases} $$

Here, $L'$ is defined by the below productions and given that we have a top-down tree automaton whose start state is $X$, $c[t] \in L$ if $c[t]$ can be traced back to the start state $X$.

$\Delta_L = {; X \rightarrow_{\varepsilon} Y ; ; \ ;;;;;;;;;;;; X \rightarrow_{+} X ; X ; ; \ ;;;;;;;;;;;; Y \rightarrow_{IF_2} D ; Y ; Y ; }$

With this, we can construct the following observation table $OT_5$:

	$◇$	$+(◇, X)$	$+(IF_2(◇, Y, Y), X)$	$+(IF_2(D, ◇, Y), X)$	$+(IF_2(D, Y, ◇), X)$	$+(IF_2(D, Y, Y), ◇)$
$+(IF_2(D, Y, Y), X)$	1	1	0	0	0	1
$IF_2(D, Y, Y)$	1	1	0	1	1	1
$D$	0	0	1	0	0	0
$Y$	1	1	0	1	1	1
$X$	1	1	0	0	0	1

Let's take a look at some of these contents. For the bold 1s, it is obvious that $c[t] \in L$, as it corresponds to the representative sample.

Consistency of $OT_5$

In order to ensure that this table has reached a fixed point (TODO: rephrase) thus a valid $OT_5$, it is important that this table is consistent, hence a correct $OT_5$.

Step 7: Take intersection of the above tree automaton with the tree automaton of the original language

Rename the states for readability.

Step 8: Convert the disambiguated grammar to corresponding lines in parser.mly

cond_expr:
  | TRUE { Bool true }
  | FALSE { Bool false }
  ;

expr_1: 
  | expr_1 PLUS expr_1 { Plus ($1, $3) }
  | expr_1 MUL expr_1 { Mul ($1, $3) }
  | e = expr_2 { e } (* epsilon-transition *)
  | IF cond_expr THEN expr_1 { If ($2, Then ($4, Else Na)) }
  ;

expr_2:
  | INT  { Int $1 }
  | LPAREN expr_1 RPAREN { Paren $2 }
  | IF cond_expr THEN expr_2 ELSE expr_2 { If ($2, Then ($4, Else $6)) }
  ;

Once the above is encoded, the number of shift/reduce conflicts decreases from 9 to 6. Note that this also resolves the shift/reduce conflict from Example09 (aka, dangling-else ambiguity) along with Example06.