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

From Wiki**3

< Theoretical Aspects of Lexical Analysis
(New page: __NOTOC__ Compute the non-deterministic finite automaton (NFA) by using Thompson's algorithm. Compute the minimal deterministic finite automaton (DFA).<br/>The alphabet is Σ = { a, b }. I...)
 
Line 166: Line 166:
  
 
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).
 
The tree expansion for non-splitting sets has been omitted for simplicity ("a" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).
−
<!--
+
 
−
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 as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.
−
-->
+
 
 +
<graph>
 +
digraph mindfa {
 +
    { node [shape=circle style=invis] s }
 +
  rankdir=LR; ratio=0.5
 +
  node [shape=doublecircle,fixedsize=true,width=0.2,fontsize=10]; 0 13 2 4
 +
  node [shape=circle,fixedsize=true,width=0.2,fontsize=10];
 +
  s -> 0
 +
  0 -> 13 [label="a",fontsize=10]
 +
  0 -> 2 [label="b",fontsize=10]
 +
  13 -> 13 [label="a",fontsize=10]
 +
  2 -> 4 [label="b",fontsize=10]
 +
  4 -> 4 [label="b",fontsize=10]
 +
  fontsize=10
 +
}
 +
</graph>
 +
 
 
== Input Analysis ==
 
== Input Analysis ==
−
<!--
+
 
 
{| cellspacing="2"
 
{| cellspacing="2"
 
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
 
! style="padding-left: 20px; padding-right: 20px; background: wheat;" | I<sub>n</sub>
Line 177: Line 193:
 
|-
 
|-
 
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
 
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>abaabb$</tt>  
+
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aababb$</tt>  
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>baabb$</tt>  
+
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>ababb$</tt>  
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>aabb$</tt>  
+
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>babb$</tt>  
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1'''
+
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T1''' (aa)
 
|-
 
|-
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
 
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
−
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>aabb$</tt>
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>babb$</tt>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | 1
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
 
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>abb$</tt>
 
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>abb$</tt>
−
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T2'''
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T1''' (b)
 
|-
 
|-
 
! style="font-weight: normal; align: center; background: #ffffcc;" | 0
 
! 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; 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;" | 13
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 1
+
! style="font-weight: normal; align: center; background: #ffffcc;" | 13
 
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>bb$</tt>
 
! 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;" | '''T1''' (a)
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 3
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 0
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>b$</tt>
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>bb$</tt>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
 
|-
 
|-
−
! style="font-weight: normal; align: center; background: #ffffcc;" | 4
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 2
−
! style="font-weight: normal; text-align: right; background: #ffffcc;" | <tt>$</tt>
+
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>b$</tt>
−
! style="font-weight: normal; align: center; background: #ffffcc;" | '''T2'''
+
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
 +
|-
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | 4
 +
! style="font-weight: normal; text-align: right; background: #e6e6e6;" | <tt>$</tt>
 +
! style="font-weight: normal; align: center; background: #e6e6e6;" | '''T3''' (bb)
 
|}
 
|}
  
−
The input string ''abaabb'' is, after 9 steps, split into three tokens: '''T1''' (corresponding to lexeme ''ab''), '''T2''' (''a''), and '''T2''' (''abb'').
+
The input string ''aababb'' is, after 10 steps, split into three tokens: '''T1''' (corresponding to lexeme ''aa''), '''T1''' (''b''), '''T1''' (''a''), and '''T3''' (''bb'').
−
-->
+
 
 
[[category:Teaching]]
 
[[category:Teaching]]
 
[[category:Compilers]]
 
[[category:Compilers]]
 
[[en:Theoretical Aspects of Lexical Analysis]]
 
[[en:Theoretical Aspects of Lexical Analysis]]

Revision as of 19:38, 28 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 = { a*|b, a*, b*|a }, input string = aababb

NFA

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


DFA

Determination table for the above NFA:

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

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" transitions for super-state {0, 1, 3}, and "a" and "b" transitions for super-state {1,3}).

Given the minimization tree, the final minimal DFA is as follows. Note that states 2 and 4 cannot be the same since they recognize different tokens.


Input Analysis

In Input In+1 / Token
0 aababb$ 13
13 ababb$ 13
13 babb$ T1 (aa)
0 babb$ 2
2 abb$ T1 (b)
0 abb$ 13
13 bb$ T1 (a)
0 bb$ 2
2 b$ 4
4 $ T3 (bb)

The input string aababb is, after 10 steps, split into three tokens: T1 (corresponding to lexeme aa), T1 (b), T1 (a), and T3 (bb).

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