Difference between revisions of "Theoretical Aspects of Lexical Analysis/Exercise 5"

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(New page: Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). The alphabet is Σ = { a, b }. Indicate the nu...)
 
Line 119: Line 119:
 
|}
 
|}
  
−
 
+
Graphically, the DFA is represented as follows:
−
{| width="100%"
 
−
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |Graphically, the DFA is represented as follows:
 
  
 
<graph>
 
<graph>
Line 133: Line 131:
 
   0 -> 2 [label="b",fontsize=10]
 
   0 -> 2 [label="b",fontsize=10]
 
   1 -> 3 [label="b",fontsize=10]
 
   1 -> 3 [label="b",fontsize=10]
−
  3 -> 1 [label="a",fontsize=10]
 
 
   3 -> 4 [label="b",fontsize=10]
 
   3 -> 4 [label="b",fontsize=10]
 
   4 -> 4 [label="b",fontsize=10]
 
   4 -> 4 [label="b",fontsize=10]
Line 161: Line 158:
  
 
Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).
 
Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).
−
<!--
+
 
−
<graph>
+
=== Input Analysis ===
−
digraph dfamin {
+
 
−
    { node [shape=circle style=invis] s }
+
{| cellspacing="2"
−
  rankdir=LR; ratio=0.5
+
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
−
  node [shape=doublecircle,fixedsize=true,width=0.4,fontsize=10]; 456
+
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | Input
−
  node [shape=circle,fixedsize=true,width=0.3,fontsize=10];
+
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n+1</sub> / Token
−
  s -> 02
+
|-
−
  02 -> 1 [label="a",fontsize=10]
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
−
  02 -> 02 [label="b",fontsize=10]
+
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abaabb$</tt>
−
  1 -> 1  [label="a",fontsize=10]
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
−
  1 -> 3  [label="b",fontsize=10]
+
|-
−
  3 -> 1 [label="a",fontsize=10]
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
−
  3 -> 456 [label="b",fontsize=10]
+
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>baabb$</tt>
−
  456 -> 456 [label="a",fontsize=10]
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
−
  456 -> 456 [label="b",fontsize=10]
+
|-
−
  fontsize=10
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
−
  //label="DFA for (a|b)*abb(a|b)*"
+
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aabb$</tt>
−
}
+
! style="font-weight: normal; align: center; background: #ffffcc;" | T1
−
</graph>
+
|-
−
-->
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
−
! style="text-align: left; font-weight:normal; vertical-align: top; width: 50%;" |  
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>aabb$</tt>
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
 +
|-
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
 +
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>abb$</tt>
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | T1
 +
|-
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
 +
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abb$</tt>
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
 +
|-
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
 +
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bb$</tt>
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
 +
|-
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
 +
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>b$</tt>
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
 +
|-
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
 +
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
 +
! style="font-weight: normal; align: center; background: #ffffcc;" | T2
 
|}
 
|}
 +
 +
The input string ''abaabb'' is, after 9 steps, split into three tokens: T1 (corresponding to lexeme ''ab''), T1 (''a''), and T2 (''abb'').
  
 
[[category:Teaching]]
 
[[category:Teaching]]
 
[[category:Compilers]]
 
[[category:Compilers]]
 
[[en:Theoretical Aspects of Lexical Analysis]]
 
[[en:Theoretical Aspects of Lexical Analysis]]

Revision as of 05:54, 22 March 2009

Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA). The alphabet is Σ = { a, b }. Indicate the number of processing steps for the given input string.

  • G = { ab, ab*, a|b }, input string = abaabb

Solution

NFA

The following is the result of applying Thompson's algorithm. State 3 recognizes the first expression (token T1); state 8 recognizes token T2; and state 14 recognizes token T3.


DFA

Determination table for the above NFA:

In α∈Σ move(In, α) ε-closure(move(In, α)) In+1 = ε-closure(move(In, α))
- - 0 0, 1, 4, 9, 10, 12 0
0 a 2, 5, 11 2, 5, 6, 8, 11, 14 1 (T2)
0 b 13 13, 14 2 (T3)
1 a - - -
1 b 3, 7 3, 6, 7, 8 3 (T1)
2 a - - -
2 b - - -
3 a - - -
3 b 7 6, 7, 8 4 (T2)
4 a - - -
4 b 7 6, 7, 8 4 (T2)

Graphically, the DFA is represented as follows:


The minimization tree is as follows. Note that before considering transition behavior, states are split according to the token they recognize.


The tree expansion for non-splitting sets has been omitted for simplicity ("a" transition for final states {1, 4}).

Given the minimization tree, the final minimal DFA is exactly the same as the original DFA (all leaf sets are singular).

Input Analysis

In Input In+1 / Token
0 abaabb$ 1
1 baabb$ 3
3 aabb$ T1
0 aabb$ 1
1 abb$ T1
0 abb$ 1
1 bb$ 3
3 b$ 4
4 $ T2

The input string abaabb is, after 9 steps, split into three tokens: T1 (corresponding to lexeme ab), T1 (a), and T2 (abb).

Retrieved from "https://web.tecnico.ulisboa.pt/~david.matos/w/pt/index.php?title=Theoretical_Aspects_of_Lexical_Analysis/Exercise_5&oldid=3061"