home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / pascal / compcomp / tpyacc / src / lexdfa.pas < prev    next >
Pascal/Delphi Source File  |  1991-04-30  |  2KB  |  57 lines
  1.  
  2. unit LexDFA;
  3.  
  4. (* 2-5-91 AG *)
  5.  
  6. (* Copyright (c) 1990,91 by Albert Graef, Schillerstr. 18,
  7.    6509 Schornsheim/Germany
  8.    All rights reserved *)
  9.  
  10. interface
  11.  
  12. (* DFA table construction. This code, admittedly, is not the most aesthetic,
  13.    but it's quite efficient (and that's the main goal). For further
  14.    explanation, refer to Aho/Sethi/Ullman 1986, Section 3.9. *)
  15.  
  16. procedure makeDFATable;
  17.   (* construct DFA from position table *)
  18.  
  19. implementation
  20.  
  21. uses LexBase, LexTables;
  22.  
  23. procedure makeDFATable;
  24.   var i : Integer;
  25.   begin
  26.     (* initialize start states: *)
  27.     for i := 2 to 2*n_start_states+1 do
  28.       setunion(first_pos_table^[i]^, first_pos_table^[i mod 2]^);
  29.     for i := 0 to 2*n_start_states+1 do
  30.       act_state := newState(first_pos_table^[i]);
  31.     act_state := -1;
  32.     while succ(act_state)<n_states do
  33.       begin
  34.         inc(act_state);
  35.         (* add transitions for active state: *)
  36.         startStateTrans;
  37.         for i := 1 to size(state_table^[act_state].state_pos^) do
  38.           with pos_table^[state_table^[act_state].state_pos^[i]] do
  39.             if pos_type=char_pos then
  40.               addTrans([c], follow_pos)
  41.             else if pos_type=cclass_pos then
  42.               addTrans(cc^, follow_pos)
  43.             else if pos=0 then
  44.               state_table^[act_state].final := true;
  45.         (* assign next states: *)
  46.         for i := state_table^[act_state].trans_lo to n_trans do
  47.           with trans_table^[i] do
  48.             next_state := addState(follow_pos);
  49.         (* merge transitions for the same next state: *)
  50.         mergeTrans;
  51.         (* sort transitions: *)
  52.         sortTrans;
  53.         endStateTrans;
  54.       end;
  55.   end(*makeDFATable*);
  56.  
  57. end(*LexDFA*).