Split View: [컴파일러] 05. 유한 오토마타와 어휘 분석기 구현

Regular Expression <=> NFA <=> DFA

- NFA: Simple to construct but complex to execute
- DFA: Complex to construct but fast to execute

         a
    +--------+
    |        |
    v    a   |    b         b
--> 0 -----> 1 -----> 2 -----> ((3))
    |
    +--b--+
    |     |
    +<----+

State |  a      |  b
-----+--------+--------
  0  | {0, 1} | {0}
  1  | -      | {2}
  2  | -      | {3}
  3  | -      | -

Input: "aabb"

Possible paths:
  0 -a-> 0 -a-> 0 -b-> 0 -b-> 0  (not accepting state)
  0 -a-> 0 -a-> 1 -b-> 2 -b-> 3  (accepting state!) -> Accept
  0 -a-> 1 (no transition for next a) -> Fail

         b
    +--------+
    |        |
    v    a   |    b         b
--> 0 -----> 1 -----> 2 -----> ((3))
    ^        |        |
    |   b    |   a    |   a
    +--------+        |
    |                 |
    +-----------------+

State |  a  |  b
-----+-----+-----
  0  |  1  |  0
  1  |  1  |  2
  2  |  1  |  3
  3  |  1  |  0

public boolean simulate(DFA dfa, String input) {
    int state = dfa.startState;

    for (char ch : input.toCharArray()) {
        state = dfa.transition[state][ch];
        if (state == DFA.ERROR) {
            return false;  // Error state
        }
    }

    return dfa.isAccepting(state);
}

1. Single character a:
   (i) --a--> ((f))

2. Epsilon:
   (i) --epsilon--> ((f))

              epsilon     NFA(r)     epsilon
          +----------> (i_r) ...> (f_r) ----------+
          |                                        |
   (i) ---+                                        +---> ((f))
          |                                        |
          +----------> (i_s) ...> (f_s) ----------+
              epsilon     NFA(s)     epsilon

   (i_r) --> NFA(r) --> (f_r/i_s) --> NFA(s) --> ((f_s))

                    epsilon
              +-------------------+
              |                   |
   (i) --epsilon--> (i_r) --> NFA(r) --> (f_r) --epsilon--> ((f))
     |                                                        ^
     +-------------------epsilon------------------------------+

Step 1: NFA for a
   (2) --a--> (3)

Step 2: NFA for b
   (4) --b--> (5)

Step 3: NFA for a|b
   (1) --eps--> (2) --a--> (3) --eps--> (6)
   (1) --eps--> (4) --b--> (5) --eps--> (6)

Step 4: NFA for (a|b)*
   (0) --eps--> (1) --...--> (6) --eps--> (7)
   (0) --eps--> (7)
   (6) --eps--> (1)

Step 5: Complete (a|b)*abb
   ... --eps--> (7) --a--> (8) --b--> (9) --b--> ((10))

epsilon-closure(s): Set of all states reachable from state s via epsilon transitions only
epsilon-closure(T): Union of epsilon-closure for each state in state set T
move(T, a): Set of states reachable from state set T via transitions on input a

Add epsilon-closure(s0) to Dstates and mark as "unprocessed"

while (unprocessed state T exists in Dstates) do
    Mark T as "processed"
    for (each input symbol a) do
        U = epsilon-closure(move(T, a))
        if (U is not in Dstates)
            Add U to Dstates and mark as "unprocessed"
        Dtran[T, a] = U
    end for
end while

NFA states: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
NFA start: 0, NFA accept: 10

DFA state A = epsilon-closure(0) = {0, 1, 2, 4, 7}
  move(A, a) = {3, 8}
  epsilon-closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B
  move(A, b) = {5}
  epsilon-closure({5}) = {1, 2, 4, 5, 6, 7} = C

DFA state B = {1, 2, 3, 4, 6, 7, 8}
  move(B, a) = {3, 8}  -> B
  move(B, b) = {5, 9}
  epsilon-closure({5, 9}) = {1, 2, 4, 5, 6, 7, 9} = D

DFA state C = {1, 2, 4, 5, 6, 7}
  move(C, a) = {3, 8}  -> B
  move(C, b) = {5}     -> C

DFA state D = {1, 2, 4, 5, 6, 7, 9}
  move(D, a) = {3, 8}  -> B
  move(D, b) = {5, 10}
  epsilon-closure({5, 10}) = {1, 2, 4, 5, 6, 7, 10} = E

DFA state E = {1, 2, 4, 5, 6, 7, 10}  (contains 10 -> accepting state)
  move(E, a) = {3, 8}  -> B
  move(E, b) = {5}     -> C

State |  a  |  b  | Accept?
-----+-----+-----+--------
  A  |  B  |  C  |  X
  B  |  B  |  D  |  X
  C  |  B  |  C  |  X
  D  |  B  |  E  |  X
  E  |  B  |  C  |  O

1. Initial partition: {accepting states}, {non-accepting states}

2. Repeat: examine each group, and within the same group,
   separate states that transition to different groups for some input

3. Terminate when no more splits are possible

Initial partition:
  G1 = {A, B, C, D}  (non-accepting)
  G2 = {E}           (accepting)

Checking input 'b':
  A -> C (G1), B -> D (G1), C -> C (G1), D -> E (G2)
  D goes to a different group, so split!

New partition:
  G1 = {A, B, C}
  G3 = {D}
  G2 = {E}

Checking input 'b':
  A -> C (G1), B -> D (G3), C -> C (G1)
  Split B!

Final partition:
  {A, C}, {B}, {D}, {E}

Declarations
%%
Translation Rules
%%
Auxiliary Functions

%{
#include <stdio.h>
#include "y.tab.h"
%}

digit    [0-9]
letter   [a-zA-Z]

%%

if          { return IF; }
else        { return ELSE; }
while       { return WHILE; }

{letter}({letter}|{digit})*  { return ID; }
{digit}+                      { return NUM; }

"+"         { return PLUS; }
"-"         { return MINUS; }
"*"         { return TIMES; }
"/"         { return DIVIDE; }
"="         { return ASSIGN; }
"=="        { return EQ; }
"<"         { return LT; }
"<="        { return LE; }

"("         { return LPAREN; }
")"         { return RPAREN; }
";"         { return SEMI; }

[ \t\n]+    { /* ignore whitespace */ }
.           { printf("Unexpected: %s\n", yytext); }

%%

Lex Specification (.l file)
       |
       v
  +----------+
  |   Lex    |  (Lex Compiler)
  +----------+
       |
       v
  lex.yy.c (C Source Code)
       |
       v
  +----------+
  | C Compiler|
  +----------+
       |
       v
  Lexical Analyzer (Executable)

nullable rules:
  epsilon node     -> true
  position i node  -> false
  cat(c1, c2) node -> nullable(c1) AND nullable(c2)
  or(c1, c2) node  -> nullable(c1) OR nullable(c2)
  star(c1) node    -> true