Anubis / Anubis

                                     The Anubis Project
   
                                  Making a parser automaton.
   
                               Copyright (c) Alain Proute' 2006.
   
   
   
    Author:  Alain Proute'
   
    Created: March 2006
    Revised: April 2006
   
   
   *** Overview.
   
   The  tool in this  file is  part of  the Anubis  Parser Generator  (APG).  It  takes an
   abstract grammar (of  type `APG_Grammar`) and returns an  abstract parser automaton (of
   type `List(APG_State)`).
   
  
read common.anubis   
   
   This function computes a parser automaton from a grammar. 
   
public define (List(FirstEntry),List(APG_State))
   make_APG_automaton
     (
       APG_Grammar        g,
       List(APG_Option)   options
     ). 

   
   --- Thats' all for the public part ! --------------------------------------------------

   
   
   
read tools/basis.anubis   

   ------------------------------- Table of Contents -------------------------------------

   *** [1] Computing 'first'.
      *** [1.1] How to compute 'first'. 
      *** [1.2] 'first' as an association list. 
      *** [1.3] Computing the initial 'first'. 
      *** [1.4] Adding tokens under a key in 'first'. 
      *** [1.5] Using 'first'. 
      *** [1.6] Performing one step of saturation of 'first'.
      *** [1.7] Saturating 'first'. 
      *** [1.8] Testing 'first'. 
   
   *** [2] Making the automaton. 
      *** [2.1] Scenarios, classes, states and definition of the automaton.
      *** [2.2] Getting derived scenarios. 
      *** [2.3] Saturating a set of scenarios. 
      *** [2.4] Inserting a scenario into a set of classes. 
      *** [2.5] Dispatching scenarios into classes. 
      *** [2.6] Computing the successor of a scenario. 
      *** [2.7] Computing the classes of the target state of a class. 
      *** [2.8] Saturating a set of states. 
      *** [2.9] Making the automaton.
      *** [2.10] Computing the transitions. 
      *** [2.11] Testing.
   
   *** [3] Computing lookaheads. 
      *** [3.1] Computing 'v*E'. 
      *** [3.2] Adding the initial lookahead. 
      *** [3.3] Getting all scenarios derived from a scenario. 
      *** [3.4] Finding a state by its id. 
      *** [3.5] Finding the successor of a scenario. 
      *** [3.6] Propagating lookaheads. 
      *** [3.7] Finding the initial scenario. 
      *** [3.8] Computing the lookaheads. 
      *** [3.9] Testing. 
   
   *** [4] The public tool. 
   
   ---------------------------------------------------------------------------------------

   
read read_grammar.anubis   
read tools/streams.anubis   
   
   
   *** [1] Computing 'first'.
   
   We must be able to compute the set of  tokens which may come as the first element in an
   instance of a sequence of grammar symbols.
   
   
   
      *** [1.1] How to compute 'first'. 
   
   Given  a   sequence  'X1...Xn'   of  grammar  symbols   (tokens  and   non  terminals),
   'first(X1...Xn)' is the set of all tokens  which may appear at the first position in an
   instance of 'X1...Xn'. If  the empty sequence may be an instance  of 'X1..Xn', then the
   special 'extended' token "empty" must be in 'first(X1...Xn)'.
   
   For a token 'a', 'first(a)' is just '[a]'. 
   
   For a non terminal 'A', consider a grammar rule with left member 'A':
   
      A -> w
   
   if 'w' is empty, "empty" must be in 'first(A)'. Otherwise, the rule has the form:
   
      A -> Xw
   
   where 'X' is  a grammar symbol. If X is  a token, this token must  be in 'first(A)'. If
   'X' is a non terminal, there are two cases:
   
     - "empty"  is  not  in 'first(X)'.  In  this  case  'first(X)'  must be  included  in
       'first(A)'.
   
     - "empty" is in  'first(X)'. In this case 'first(X) - ["empty"]'  must be included in
       'first(A)', and 'first(w)' must be included in 'first(A)'. 
   
   Finally, if 'X1...Xn' is any  sequence of grammar symbols, 'first(X1...Xn)' is computed
   as follows:
   
     - if 'X1...Xn' is empty (n = 0), 'first(X1...Xn)' is [ ], 
     - otherwise:
         - if "empty" belongs to 'first(X1)', 'first(X1) - ["empty"]' and 'first(X2...Xn)'
           must be included into 'first(X1...Xn)',
         - if  "empty" does no belong  to 'first(X1)', then  'first(X1...Xn)' must contain
           'first(X1)'.
   
   Hence, we see that (again) computing 'first' is a saturation process. 
   
   
   
      *** [1.2] 'first' as an association list. 
   
   We represent  the 'first' function  (which maps a  string to a  list of strings)  as an
   association list. Each element of this list is of type FirstEntry (defined in common.anubis). 
   
   
   
   
      *** [1.3] Computing the initial 'first'. 
   
   Computing first  amounts to start  with an 'initial'  list within which all  values are
   computed  for tokens  and  the  empty list  for  non terminals,  and  to saturate  this
   association list. The initial association list is computed by:
   
define List(FirstEntry)   
   initial_first
     (
       List(String)       tokens,            // list of all tokens 
       List(String)       non_terminals      // list of all non terminals
     ) =
   [first_entry("eof",["eof"])] +
   map((String s) |-> first_entry(s,[s]),tokens) +
   map((String s) |-> first_entry(s,[ ]),non_terminals).
   
   
      *** [1.4] Adding tokens under a key in 'first'. 
   
   The next utility adds a list of token under a given key in a first function. 
   
define List(FirstEntry)
   add_first_tokens
     (
       String             key, 
       List(String)       to_be_added,
       List(FirstEntry)   first
     ) =
   if first is 
     {
       [ ] then [ ],     // will never happen since all symbols have entries
       [e1 . other_entries] then 
         if e1 is first_entry(name,l) then
         if key = name
         then [first_entry(key,merge(to_be_added,l)) . other_entries]
         else [e1 . add_first_tokens(key,to_be_added,other_entries)]
     }. 
   
   
      *** [1.5] Using 'first'. 
   
   Getting the value under a given key in a given first function. 
   
define List(String)
   get_first_tokens
     (
       APG_Symbol_Act     key, 
       List(FirstEntry)   first
     ) =
   if first is 
     {
       [ ] then [ ],    // will happen only if key is a command 
       [e1 . other_entries] then
         if e1 is first_entry(name,value) then
         if key = symbol(name)
         then value 
         else get_first_tokens(key,other_entries)
     }.
   
   We need the same one for a sequence of symbols. 
   
define List(String)
   get_first_tokens
     (
       List(APG_Symbol_Act)       sequence,
       List(FirstEntry)           first
     ) =
   if sequence is 
     {
       [ ] then ["empty"], 
       [_X1 . _Xs] then 
         with first_X1 = get_first_tokens(_X1,first), 
         if "empty":first_X1
         then merge(first_X1 - ["empty"],get_first_tokens(_Xs,first))
         else first_X1
     }. 
   
   
   
   
   
      *** [1.6] Performing one step of saturation of 'first'.
   
   In a single step of saturation we use each grammar rule once. 
   
define List(FirstEntry)
   saturate_one_step
     (
       List(FirstEntry)           first, 
       List(APG_Grammar_Rule)     rules
     ) =
   if rules is 
     {
       [ ] then first, 
       [rule1 . other_rules] then
         if rule1 is grammar_rule(id,head,body,prec) then 
         with _A = name(head), 
         if body is 
           {
             [ ] then 
               saturate_one_step(add_first_tokens(_A,["empty"],first),other_rules),
   
             [_X . w] then if _X is 
             {
               symbol_value(nameX,_)  then 
                 with first_X = get_first_tokens(symbol(nameX),first),
                 if "empty":first_X
                 then saturate_one_step(
                        add_first_tokens(_A,
                                         merge(first_X - ["empty"],
                                               get_first_tokens(names_in(w),
                                                                first)),
                                         first),
                        other_rules)
                 else saturate_one_step(
                        add_first_tokens(_A,
                                         first_X,
                                         first),
                        other_rules),
                      
               immcom(_)  then
                 // never two consecutive immediate commands
                 if w is 
                 {
                   [] then 
                     saturate_one_step(add_first_tokens(_A,["empty"],first),other_rules),
                   
                   [_Y . k] then if _Y is 
                     {
                       symbol_value(nameY,_)  then 
                         with first_Y = get_first_tokens(symbol(nameY),first),
                         if "empty":first_Y
                         then saturate_one_step(
                                add_first_tokens(_A,
                                                 merge(first_Y - ["empty"],
                                                       get_first_tokens(names_in(w),
                                                                        first)),
                                                 first),
                                other_rules)
                         else saturate_one_step(
                                add_first_tokens(_A,
                                                 first_Y,
                                                 first),
                                other_rules),
                      
                       immcom(_)  then should_not_happen([])
                     }
                 }
             }                     
           }
     }. 
   
   
   
   
      *** [1.7] Saturating 'first'. 
   
   Now, we saturate 'first' repeatedly until it does no more change. 
   
define List(FirstEntry)
   saturate
     (
       List(FirstEntry)           first, 
       List(APG_Grammar_Rule)     rules
     ) =
   with next = saturate_one_step(first,rules),
   if first = next
   then first
   else saturate(next,rules). 
   

   
   Now, we can compute the first function for a given grammar. 
   
define List(FirstEntry)
   compute_first
     (
       APG_Grammar        g
     ) =
   with      rules = grammar_rules(g), 
           symbols = all_symbols(rules), 
     non_terminals = all_non_terminals(rules), 
            tokens = symbols - non_terminals, 
         ini_first = initial_first(tokens,non_terminals), 
   saturate(ini_first,rules).
   
   
   
   
   
   
      *** [1.8] Testing 'first'. 
   
define One
   print
     (
       FirstEntry   fe
     ) =
   if fe is first_entry(key,value) then
   print("\n   "+key+":        ");
   map_forget((String s) |-> print(s+" "),value). 
     
   
 global define One
   first_function_test
     (
       List(String) args
     ) =
   if read_APG_grammar(make_stream(example_grammar),[]) is 
     {
        error(msg)  then en_print(msg), 
        ok(g)       then 
          with      rules = grammar_rules(g), 
                  symbols = all_symbols(rules), 
            non_terminals = all_non_terminals(rules), 
                   tokens = symbols - non_terminals, 
                ini_first = initial_first(tokens,non_terminals), 
                    first = saturate(ini_first,rules), 
          print("\n\n   First function:");
          map_forget(print,first);
          print("\n\n")
     }.
   
   
   
   

     
     
   
   *** [2] Making the automaton. 
   
      *** [2.1] Scenarios, classes, states and definition of the automaton.
   
   A 'type  1 scenario' is  a gammar rule whose  body has been  split into two parts  by a
   dot. Precisely, if
   
     A -> uv
   
   (where either u or v may be empty) is a grammar rule, then 
   
     A -> u.v
   
   is a type 1 scenario. 
   
type Scenario1:
   scenario1(Word32                  rule_id,        // id of grammar rule
             String                  head,           // A
             List(APG_Symbol_Act)    before_dot,     // u in reverse order
             List(APG_Symbol_Act)    after_dot).     // v in natural order
      
   A type 1 scenario may have one of the following two forms:
   
     - reducing:     A -> u.              (nothing after the dot)
     - transition:   A -> u.Xv            (at least one symbol after the dot)
   
   A transition scenario  'A -> u.Xv' is called  a 'shifting scenario' if 'X'  is a token,
   and 'restarting  scenario' if  'X' is  a non terminal.   The symbol  'X' is  called the
   'transition' of the scenario. By convention, we say that the 'transition' of a reducing
   scenario is "empty". So the 'transition' is well defined for all scenarios.
   
   Two scenarios are said to be 'parallel' if they have the same transition.
   
   'parallelism' is clearly an equivalence  relation on scenarios. An equivalence class of
   scenarios for this relation is just called a 'class'. A class may be either a 'reducing
   class' (if  it contains  reducing scenarios)  or a 'transition  class' (if  it contains
   transition scenarios).  The  transition which is common to all scenarios  in a class is
   called the transition of the class.
   
type Class1:
   class1(String             transition, 
          List(Scenario1)    scenarios). 
     
   
   A restarting scenario gives rise to 'derived scenarios'. Precisely, if
   
      A -> u.Bv
   
   is a restarting scenario, and if 'B -> w' is a grammar rule, the scenario:
   
      B -> .w
   
   is said to be 'derived' from 'A -> u.Bv' . Notice that if 'w' begins by a non terminal,
   the scenario 'B -> .w' itself has derived scenarios.
  
   A 'type 1 state' is a finite set of classes with distinct transitions. 
   
   A type  1 state  'S' is  said to be  'saturated' is  for any scenario  'I' in  'S', all
   scenarios derived from 'I' are also in 'S'.
   
   A transition scenario 'A -> u.Xv' has a 'successor' which is the following scenario:
   
     A -> uX.v
   
   (i.e. the dot is moved past 'X'). 
   
   Given a saturated type 1 state 'S' and a transition class 'C' for 'X' in 'S', the state
   'S(X)' is defined as the saturation of the state obtained by classifying the successors
   of 'C'.
   
   The 'initial state' is made of the single class:
   
      { S -> .A }
   
   The automaton for  our grammar is the smallest set of  saturated states, which contains
   the saturation  of the initial  scenario and contains  'S(X)' whenever it  contains 'S'
   with transition 'X'.

   Hence, in order to compute the automaton, we need to be able to:
   
     - get the set of derived scenarios for a given non terminal,
     - saturate a set of scenarios, 
     - dispatch a set of scenario into classes, 
     - compute the successor of a scenario, 
     - saturate a set of states. 
   
   
   
   
      *** [2.2] Getting derived scenarios. 
   
   Given a non terminal symbol 'B', we want all derived scenarios corresponding to 'B'. We
   just have to construct a derived scenario for each rule whose head is 'B'.
   
define List(Scenario1)
   derived_scenarios
     (
       String                    _B,      // the non terminal 
       List(APG_Grammar_Rule)    rules    // all rules in the grammar
     ) =
   if rules is 
     {
       [ ] then [ ], 
       [rule1 . other_rules] then 
         if rule1 is grammar_rule(id,head,body,prec) then 
         with    _A = name(head), 
               rest = derived_scenarios(_B,other_rules),
         if _A = _B
         then [scenario1(id,_A,[],names_in(body)) . rest]
         else rest
     }.
      
   
   

      *** [2.3] Saturating a set of scenarios. 
   
   Given a set (actually a list) of  scenarios, we want to add all derived scenarios until
   no more derived  scenario may be added to  the set. We proceed as follows.  We have two
   lists of scenarios:
   
      - those not yet used for saturation, 
      - those already used for saturation.
   
   Of course, we must not try to use the same scenario twice. Hence, we try only those
   scenarios which are  not already used.  For such  a scenario, we get a  list of derived
   scenarios. Those  which are already present  in one of  our lists must be  dropped. The
   others must be added to the list of not already used scenarios.
   
   Furthermore, for a given non terminal 'B', the set of rules whose head is 'B' is always
   the same one. Hence,  it is not necessary to generate derived  scenarios twice with
   the same 'B'. This is why we also keep a list of those 'B' which have been already used
   for creating derived scenarios.
   
define List(Scenario1)
   saturate
     (
       List(Scenario1)           already_used,
       List(String)              already_used_Bs,
       List(Scenario1)           not_yet_used, 
       List(APG_Grammar_Rule)    rules
     ) =
   if not_yet_used is 
     {
       [ ] then already_used, 
       [sc1 . scs] then 
         if sc1 is scenario1(id,head,before_dot,after_dot) then 
         if after_dot is 
           {
             [ ] then saturate([sc1 . already_used],already_used_Bs,scs,rules),
             [sa . v] then 
               if sa is 
               {
                 symbol(_B) then  
                   if _B : already_used_Bs
                   then saturate([sc1 . already_used],already_used_Bs,scs,rules)
                   else with new = derived_scenarios(_B,rules) - already_used - not_yet_used,
                      saturate([sc1 . already_used],[_B . already_used_Bs],new+scs,rules)
                 immcom(_) then if v is 
                   {
                     [ ] then saturate([sc1 . already_used],already_used_Bs,scs,rules),
                     [k . _] then 
                       if k is
                         {
                           symbol(_B) then 
                             if _B : already_used_Bs
                             then saturate([sc1 . already_used],already_used_Bs,scs,rules)
                             else with new = derived_scenarios(_B,rules) - already_used - not_yet_used,
                                saturate([sc1 . already_used],[_B . already_used_Bs],new+scs,rules),
                           immcom(_) then should_not_happen([]) 
                         }
                   }
               }
           }
     }.

   
   
   
      *** [2.4] Inserting a scenario into a set of classes. 
   
   We have  a set of classes  (actually a list), and  a scenario.  We want  to insert this
   scenario into the class corresponding to its transition. If no such class exists, a new
   class is created.
   
define List(Class1)
   insert_scenario
     (
       Scenario1         sc,
       List(Class1)      classes
     ) =
   if sc is scenario1(id,_A,bd,ad) then 
   with transition = if ad is 
                       {
                         [ ]       then "empty", 
                         [_X . l]  then if _X is 
                           {
                             symbol(x)   then x, 
                             immcom(_)  then if l is 
                               {
                                 [ ] then "empty", 
                                 [k . z] then if k is 
                                   {
                                     symbol(y)   then y, 
                                     immcom(_)  then should_not_happen("")
                                        // because no consecutive commands
                                   }
                               }
                           }
                       },
   if classes is 
     {
       [ ] then [class1(transition,[sc])],
   
       [c1 . other_classes] then 
         if c1 is class1(_X,l) then
         if _X = transition
         then [class1(_X,[sc . l]) . other_classes]
         else [c1 . insert_scenario(sc,other_classes)]
     }.

   
   
   
   
   
      *** [2.5] Dispatching scenarios into classes. 
   
   We have a set  of scenarios, and we want to dispatch them  into classes. This is easily
   done using 'insert_scenario'.
   
define List(Class1)
   dispatch
     (
       List(Scenario1)    l
     ) =
   if l is 
     {
       [ ] then [ ], 
       [sc1 . scs] then 
         with rest = dispatch(scs), 
         insert_scenario(sc1,rest)
     }. 
   
   
   
   

      *** [2.6] Computing the successor of a scenario. 
   
   Given  a scenario  which  is assumed  to be  a  transition scenario,  we construct  its
   successor. Precisely if the scenario is:
   
         A -> u.Xv
   
   the successor is:
   
         A -> uX.v
   
define Scenario1
   successor
     (
       Scenario1    sc
     ) =
   if sc is scenario1(id,_A,bd,ad) then 
   if ad is 
     {
       [ ] then should_not_happen(sc),  
       [k . v] then
         if k is 
         {
           symbol(_)   then scenario1(id,_A,[k . bd],v), 
           immcom(_)   then if v is 
             {
               [ ]      then should_not_happen(sc), 
               [h . t]  then scenario1(id,_A,[h , k . bd],t),
             }
         }
     }.
   

   
   

   
      *** [2.7] Computing the classes of the target state of a class. 
   
   Given a  class (which  is supposed to  be a  transition class), we  compute the  set of
   classes of the target state for  this transition. This amounts to replace each scenario
   in the class by its successor, saturate  this set of successors, and dispatch them into
   classes.
   
define List(Class1)
   target
     (
       Class1                     c,
       List(APG_Grammar_Rule)     rules
     ) =
   if c is class1(transition,scenarios) then
   dispatch(saturate([],[],map(successor,scenarios),rules)).
   
   
   
   
   
   
   
      *** [2.8] Saturating a set of states. 
   
   Here  a state  is  just a  set  of  classes, and  is  represented by  a  datum of  type
   'List(Class1)'.  We first need  a tool for dropping the reducing class  (if any) from a
   state. Recall that the transition of this class has name "empty".
   
define List(Class1)
   drop_reducing_class
     (
       List(Class1) l
     ) =
   if l is 
     {
       [ ] then [ ], 
       [c1 . cs] then 
          if c1 is class1(tr,_) then 
          if tr = "empty"
          then cs
          else [c1 . drop_reducing_class(cs)]
     }.
   
   
   Now, we  can saturate a set  of states. We have  two lists of states:  those which have
   already  been  used  for saturation,  and  those  which  have  not  yet been  used  for
   saturation. This is just a loop (terminal recursion) from which we escape when the list
   of not yet used states is empty.
   
   While the  list of not  yet used  states is not  empty, we take  the head of  this list
   (denoted 's1'  below) and construct the target  states for all transitions  in 's1'. We
   drop  from this  list of  new states  all those  states which  have already  been seen,
   i.e. those states which already appear either  in the list of already used states or in
   the list of  not yet used states. The remaining  states are put in the  list of not yet
   used states. The state 's1' is put in the list of already used states. 

   As we construct states, we also want to number them. Hence the following type:
   
type State1:
   state1(Word32            state_id, 
          List(Scenario1)   core,
          List(Class1)      classes). 
   
   
define List(Scenario1)
   get_core
     (
       List(Scenario1)   l
     ) =
   if l is 
     {
       [ ] then [ ], 
       [sc1 . scs] then if sc1 is scenario1(_,head,bd,ad) then 
         if bd is 
           {
             [ ] then if head = "start" 
                      then [sc1 . get_core(scs)]
                      else get_core(scs),
             [_ . _] then [sc1 . get_core(scs)]
           }
     }.
   
define List(Scenario1)
   get_core
     (
       List(Class1)  l
     ) =
   if l is 
     {
       [ ] then [ ], 
       [c1 . cs] then if c1 is class1(_,l1) then 
          get_core(l1) + get_core(cs)
     }.
   
   
define List(State1)
   saturate
     (
       List(State1)            result, 
       List(List(Class1))      already_used, 
       List(List(Class1))      not_yet_used,
       List(APG_Grammar_Rule)  rules,
       Word32                  state_id,
       Bool                    verbose
     ) =
   if not_yet_used is 
     {
       [ ] then reverse(result), 
       [s1 . ss] then
         with transition_classes = drop_reducing_class(s1), 
                         targets = map((Class1 c) |-> target(c,rules),transition_classes), 
                             new = targets - already_used - not_yet_used, 
         saturate([state1(state_id,get_core(s1),s1) . result], 
                  [s1 . already_used],
                  new+ss,
                  rules,
                  state_id+1,
                  verbose)
     }. 
   
   
          
   
   
      *** [2.9] Making the automaton.

   In order to make the complete automaton, we just have to create the initial state, make
   a set with it  and saturate this set. In order to make the  initial state, we must find
   the head (denoted '_A' below) of the first (user) rule of the grammar.
   
define List(State1)
   make_automaton
     (
       List(APG_Grammar_Rule)  rules,
       List(APG_Option)        options
     ) =
   (if verbose : options
    then print("\nMaking the automaton ... "); forget(flush(stdout))
    else unique); 
   with auto = 
     if rules is 
       {
         [ ] then should_not_happen([ ]), 
         [rule1 . _] then //print(show_rule(rule1)); 
                          if rule1 is grammar_rule(id1,_A,_,_) then 
           with initial_state = dispatch(saturate([],
                                                  [],
                                                  [scenario1(0,"start",[],[symbol(name(_A))])],
                                                  rules)), 
           saturate([],[],[initial_state],rules,0,verbose : options)
       },
   (if verbose:options
    then print("Done ("+length(auto)+" states).   ")
    else unique);
   auto. 
   
   
   
   
   
   
      *** [2.10] Computing the transitions. 
   
define One print(Scenario1 s).    
   
define Word32
   find_state_id
     (
       List(Scenario1)     core, 
       List(State1)        auto1
     ) =
   if auto1 is
     {
       [ ] then map_forget(print,core); 
                print("\n"); 
                should_not_happen(0),    // the state is necessarily found
       [s1 . ss] then 
         if s1 is state1(id1,core1,_) then 
         //if core = core1
         if same_set(core,core1)
         then id1
         else find_state_id(core,ss)
     }.
   
   
define List(APG_Transition)
   get_transitions
     (
       List(Class1)    classes,
       List(State1)    auto1
     ) =
   if classes is 
     {
       [ ] then [ ], 
       [c1 . cs] then 
         if c1 is class1(symbol,scenarios) then
         if symbol = "empty"
         then get_transitions(cs,auto1)
         else [transition(symbol,find_state_id(map(successor,scenarios),auto1))
                . get_transitions(cs,auto1)]
     }.
   
   
define Word32
   get_transition
     (
       String                  symbol, 
       List(APG_Transition)    transitions
     ) =
   if transitions is 
     {
       [ ] then should_not_happen(0), 
       [tr1 . trs] then if tr1 is transition(s,n) then 
         if s = symbol 
         then n
         else get_transition(symbol,trs)
     }.
   
   
   
define APG_Propagation
   compute_propagation
     (
       List(APG_Symbol_Act)       after_dot,
       List(String)               non_terminals,
       List(FirstEntry)           first
     ) =
   if after_dot is 
     {
       [ ] then dont_propagate_to_derived, 
       [u . v] then 
         if u is 
         {
           symbol(_Y) then 
             if _Y:non_terminals
             then if "empty":get_first_tokens(v,first)
                  then propagates_to_derived
                  else dont_propagate_to_derived
             else dont_propagate_to_derived
           immcom(_) then if v is 
             {
               [ ] then dont_propagate_to_derived,
               [h . _] then if h is 
                 {
                   symbol(_Z) then 
                     if _Z:non_terminals
                     then if "empty":get_first_tokens(v,first)
                          then propagates_to_derived
                          else dont_propagate_to_derived
                     else dont_propagate_to_derived
                   immcom(_) then should_not_happen(dont_propagate_to_derived)
                 }
             }
         }       
     }. 
   
   
define List(APG_Class)
   to2
     (
       List(Class1)         l,
       List(String)         non_terminals,
       List(FirstEntry)     first
     ) =
   map((Class1 c) |-> if c is class1(sym,scs) then 
          class(sym,map((Scenario1 s) |-> if s is scenario1(id,h,bd,ad) then
            scenario(id,h,bd,ad,
                     compute_propagation(ad,non_terminals,first),
                     var(false), 
                     var([])),scs)),l).

define List(APG_State)
   compute_transitions
     (
       List(State1)        auto1, 
       List(State1)        rest,
       List(APG_State)     so_far,
       List(String)        non_terminals,
       List(FirstEntry)    first
     ) =
   if rest is 
     {
       [ ] then reverse(so_far),
       [s1 . ss] then 
         if s1 is state1(id,core,classes) then
         compute_transitions(auto1,
                             ss,
                             [state(id,to2(classes,non_terminals,first),
                                    get_transitions(classes,auto1))
                              . so_far],
                             non_terminals,first)
     }.
     
   
define List(APG_State)
   compute_transitions
     (
       List(State1)        auto1, 
       List(State1)        rest,
       List(APG_State)     so_far,
       List(APG_Option)    options,
       List(String)        non_terminals,
       List(FirstEntry)    first
     ) =
   (if verbose:options
    then print("\nComputing transitions ... "); forget(flush(stdout))
    else unique); 
   with result = compute_transitions(auto1,rest,so_far,non_terminals,first),
   (if verbose:options
    then print("Done.  ")
    else unique);
   result. 
   
   
   
   
      *** [2.11] Testing.
   
   We make  a test of  the above 'make_automaton'  function, using the example  grammar in
   'read_grammar.anubis'. 
   
define One
   print
     (
       Scenario1  sc
     ) =
   if sc is scenario1(id,head,bd,ad) then 
   print("\n   ["+right_pad(id,4)+"] "); 
   print(right_pad(head+":",14)); 
   map_forget((APG_Symbol_Act s) |-> print(s); print(" "),reverse(bd));
   print(". ");
   map_forget((APG_Symbol_Act s) |-> print(s); print(" "),ad).  
   
define One
   print
     (
       APG_Scenario  sc
     ) =
   if sc is scenario(id,head,bd,ad,prop,hg,l) then 
   print("\n   ["+right_pad(id,4)+"] "); 
   print(right_pad(head+":",14)); 
   map_forget((APG_Symbol_Act s) |-> print(s); print(" "),reverse(bd));
   print(". ");
   map_forget((APG_Symbol_Act s) |-> print(s); print(" "),ad);
   print("\n      { "); 
   map_forget((String s) |-> print(s+" "),*l);
   print("}"). 
   
define One
   print
     (
       Class1   c
     ) =
   if c is class1(tr,l) then 
   map_forget(print,l).
   
define One
   print
     (
       APG_Class   c
     ) =
   if c is class(tr,l) then 
   map_forget(print,l).
   
define One
   print
     (
       State1    s
     ) =
   if s is state1(state_id,core,classes) then 
   print("\n\n   === state "+state_id+" ================================="); 
   map_forget(print,core);
   print("\n   -----------"); 
   map_forget(print,classes).
   
   
define One
   print
     (
       APG_Transition   t
     ) =
   if t is transition(symbol,state_id) then 
   print("\n   "+right_pad(symbol,16)+"     go to state "+state_id). 
   
   
define One
   print
     (
       APG_State    s
     ) =
   if s is state(state_id,classes,trans) then 
   print("\n\n   === state "+state_id+" ================================="); 
   map_forget(print,classes);
   print("\n");
   map_forget(print,trans);
   print("\n"). 
   
   
   
 global define One
   automaton_test_1
     (
       List(String) args
     ) =
   if read_APG_grammar(make_stream(example_grammar),[]) is 
     {
        error(msg)  then en_print(msg), 
        ok(g)       then 
          with auto1 = make_automaton(grammar_rules(g),[verbose]), 
               auto2 = compute_transitions(auto1,auto1,[],[verbose]), 
          map_forget(print,auto2);
          print("\n\n")
     }.

   
   
   
   
   
   
   
 
   *** [3] Computing lookaheads. 
   
   When the automaton has  reached a state with a non empty  reducing class, it may choose
   to  reduce using  a  grammar  rule. Decision  is  based on  which  token  will be  read
   next. Some tokens are acceptable for a reduction, some are not.  By definition, the set
   of 'lookaheads' for a  reducing scenario is the set of tokens  which are acceptables as
   next to be read in a reducing state.
   
   Computing  the set  of lookaheads  for  each reducing  scenario is  again a  saturation
   process.   Actually, we  must associate  a  set of  lookaheads to  all scenarios,  even
   transition  scenarios, because  they are  used for  the computation  of  lookaheads for
   reducing scenarios.
   
   Lookaheads 'propagate' from  a scenario to another scenario  according to the following
   two rules:
   
     (1) If 'A  -> u.Bv' is  a restarting  scenario with set  of lookaheads 'E',  then all
   scenarios derived from this one (hence in the same state), i.e. of the form:
   
        B -> .w
   
   must have all elements of 'v*E' (defined below) in their set of lookaheads. 

   'v*E' is the set of all tokens which may come first in an instance of 'va' for some 'a'
   in 'E'.  Hence, in order to compute  'v*E', we compute 'first(va)' for each 'a' in 'E',
   and make the reunion. Notice that if 'v' is empty, 'v*E' is 'E'. When we compute 'v*E',
   'E' is never empty.
   
     (2) If 'A -> u.Xv'  is any transition scenario with set of  lookaheads 'E', then it's
   successor (in the target state for this transition)
   
        A -> uX.v
   
   has all elements of 'E' in its set of lookaheads. 
   
   Each scenario propagates its lookaheads to its derived scenarios (in the same state) if
   any, and to its successor (in the same or in another state) if any.  If the propagation
   does not change  the set of lookaheads of  the second scenario, it is  not necessary to
   propagate  again  from this  scenario.  Hence, we  just  need  to propagate  lookaheads
   recursively starting from the initial scenario (which belongs to state 0):
   
        start -> .A
   
   for which the set of lookaheads is ["eof"]. 
   
   We must also consider immediate actions (written $(<action>) in a grammar rule) as 
   transparent. 
   
   
     
   
      *** [3.1] Computing 'v*E'. 
   
define List(String)
   v_star_E
     (
       List(APG_Symbol_Act)        v,
       List(String)                _E,
       List(FirstEntry)            first
     ) =
   if _E is 
     {
       [ ] then [ ], 
       [a . others] then
         merge(get_first_tokens(v+[symbol(a)],first),v_star_E(v,others,first))
     }.
   
   
   
   
   
      *** [3.2] Adding the initial lookahead. 
   
define One
   add_initial_lookahead
     (
       List(APG_Scenario)    scs
     ) =
   if scs is 
     {
       [ ] then unique, 
       [sc1 . others] then 
         if sc1 is scenario(_,head,bd,ad,prop,hg,lh_v) then 
         if (head = "start" & bd = [])
         then lh_v <- ["eof"]
         else add_initial_lookahead(others)
     }.
   
   
define One
   add_initial_lookahead
     (
       List(APG_State)    auto
     ) =
   if auto is 
     {
       [ ] then should_not_happen(unique), 
       [s1 . others] then 
         if s1 is state(id,classes,transitions) then 
         if id = 0
         then map_forget((APG_Class c) |-> add_initial_lookahead(scenarios(c)),classes)
         else add_initial_lookahead(others)
     }.
   

   
      *** [3.3] Getting all scenarios derived from a scenario. 
   
define List(APG_Scenario)   
   get_derived_scenarios
     (
       String               _B,
       List(APG_Scenario)   scs
     ) =
   if scs is 
     {
       [ ] then [ ], 
       [sc1 . others] then 
         if sc1 is scenario(_,head,bd,_,_,_,_) then 
         if (head = _B & bd = [])
         then [sc1 . get_derived_scenarios(_B,others)]
         else get_derived_scenarios(_B,others)
     }.
   
define List(APG_Scenario)   
   get_derived_scenarios
     (
       String            _B,
       List(APG_Class)   classes
     ) =
   if classes is 
     {
       [ ] then [ ], 
       [c1 . others] then 
         if c1 is class(_,scs) then 
         get_derived_scenarios(_B,scs) + get_derived_scenarios(_B,others)
     }.
   
define List((APG_Scenario,APG_State))   
   get_derived_scenario_and_state
     (
       APG_Scenario     sc, 
       APG_State        st
     ) =
   if sc is scenario(_,_,bd,ad,_,_,_) then 
   if symbols_only(ad) is 
     {
       [ ] then [ ], 
       [_B . v] then
         map((APG_Scenario d) |-> (d,st),get_derived_scenarios(_B,classes(st)))
     }. 
   
   
   
      *** [3.4] Finding a state by its id. 
   
define APG_State
   find_state
     (
       Word32             state_id,
       List(APG_State)    auto
     ) =
   if auto is 
     {
       [ ] then should_not_happen(state(0,[],[])), 
       [s1 . others] then 
         if s1 is state(id,_,_) then 
         if id = state_id
         then s1
         else find_state(state_id,others)
     }.
   
   
   
      *** [3.5] Finding the successor of a scenario. 
   
define Maybe(APG_Scenario)
   find_successor
     (
       Word32                        rule_id,
       List(APG_Symbol_Act)          after_dot,
       List(APG_Scenario)            scs
     ) = 
   if scs is 
     {
       [ ] then failure, 
       [sc1 . others] then 
         if sc1 is scenario(id,_,_,ad,_,_,_) then
         if rule_id = id & after_dot = ad
         then success(sc1) 
         else find_successor(rule_id,after_dot,others)
     }.
   
define APG_Scenario
   find_successor
     (
       Word32                    rule_id,
       List(APG_Symbol_Act)      after_dot,
       List(APG_Class)           classes
     ) = 
   if classes is 
     {
       [ ] then should_not_happen(scenario(0,"",[],[],propagates_to_derived,
                       var(false),var([]))), 
       [c1 . others] then 
         if find_successor(rule_id,after_dot,scenarios(c1)) is
           {
             failure     then find_successor(rule_id,after_dot,others)
             success(s)  then s
           }
     }.
   
define List((APG_Scenario,APG_State))
   get_successor_and_state
     (
       APG_Scenario       from, 
       APG_State          source, 
       List(APG_State)    auto
     ) =
   if from is scenario(rule_id,_,bd,ad,prop,hg,lh_v) then 
   if symbols_only(ad) is 
     {
       [ ] then [ ], // no successor for a reducing scenario
       [_X . v] then 
         if source is state(_,_,transitions) then 
         with target = find_state(get_transition(_X,transitions),auto), 
           if drop_leading_command(ad) is 
           {
             [ ] then should_not_happen([]),
             [_ . t] then 
                [(find_successor(rule_id,t,classes(target)),target)]
           }
     }. 
   
   
   
   
   
   
      *** [3.6] Propagating lookaheads. 
   
   We have a pair of cross recursive functions. 
   
define One
   propagate_lookaheads // forward declaration
     (
       APG_Scenario        from,    // the (transition) scenario from which propagation starts
       APG_State           current, // the state to which 'from' belongs
       List(APG_State)     auto,    // the automaton
       List(FirstEntry)    first,
       Bool                verbose
     ). 
     
   
define One
   propagate_lookaheads
     (
       APG_Scenario        from,    // the (transition) scenario from which propagation starts
       APG_State           source,  // the state to which 'from' belongs
       APG_Scenario        to  ,    // the scenario to which lookaheads are propagated
       APG_State           target,  // the state to which 'to' belongs
       List(APG_State)     auto,    // the whole automaton
       List(FirstEntry)    first,   // the 'first' function
       Bool                verbose
     ) =
   with id1 = state_id(source), id2 = state_id(target), 
   if from is scenario(_,_,bd1,ad1,prop1,hg1,lh1_v) then 
   with tail_ad1 = if drop_all_commands(ad1) is 
        { 
          [ ] then should_not_happen([]),      // ad1 cannot be empty
          [_ . t] then t
        }, 
   if to   is scenario(_,_,bd2,ad2,prop2,hg2,lh2_v) then 
   with previous = *lh2_v, 
   if drop_all_commands(bd2) is 
     {
       [ ]     then // 'to' is a derived scenario
         //(if *lh1_v = [] then should_not_happen(unique) else unique);  
         // *lh1_v is never empty
         lh2_v <- merge(v_star_E(tail_ad1,*lh1_v,first),
                        previous),
   
       [_ . _] then // 'to' is a successor scenario
         lh2_v <- merge(*lh1_v,
                        previous)
     };
   if length(*lh2_v) = length(previous)
   then unique // stop propagation if nothing changed in 'to'
   else if drop_all_commands(ad2) is 
          {
            [ ] then unique,  // reducing scenarios don't propagate
            [_ . _] then propagate_lookaheads(to,target,auto,first,verbose)
          }. 
   
define One
   propagate_lookaheads
     (
       APG_Scenario        from,    // the (transition) scenario from which propagation starts
       APG_State           current, // the state to which 'from' belongs
       List(APG_State)     auto,    // the automaton
       List(FirstEntry)    first,
       Bool                verbose
     ) =
   if from is scenario(id,h,bd1,ad1,prop1,hg1_v,lh1_v) then 
   with next_scenarios = if prop1 is 
            {
              propagates_to_derived then (get_derived_scenario_and_state(from,current)),
              dont_propagate_to_derived then
                if *hg1_v
                then [ ]
                else (hg1_v <- true; get_derived_scenario_and_state(from,current)),
            } 
            + get_successor_and_state(from,current,auto), 
   map_forget(((APG_Scenario,APG_State) p) |-> if p is (sc,st) then 
                  propagate_lookaheads(from,current,sc,st,auto,first,verbose),
              next_scenarios). 
   
   
   
   
   
      *** [3.7] Finding the initial scenario. 
   
define Maybe(APG_Scenario)
   initial_scenario
     (
       List(APG_Scenario) l
     ) =
   if l is 
     {
       [ ] then failure, 
       [sc1 . others] then 
         if sc1 is scenario(id,head,_,_,_,_,_) then 
         if (id = 0 & head = "start")
         then success(sc1)
         else initial_scenario(others)
     }.
   
define APG_Scenario
   initial_scenario
     (
       List(APG_Class)   c
     ) =
   if c is 
     {
       [ ] then should_not_happen(scenario(0,"",[],[],propagates_to_derived,
                       var(false),var([]))), 
       [c1 . others] then 
         if initial_scenario(scenarios(c1)) is 
           {
             failure then initial_scenario(others), 
             success(s) then s
           }
     }.
   
   
   
   
   
   
      *** [3.8] Computing the lookaheads. 
   
define List(APG_State)
   compute_lookaheads
     (
       List(APG_State)      auto,
       APG_Grammar          g,
       List(APG_Option)     options,
       List(FirstEntry)     first
     ) =
   (if verbose:options
    then print("\nPropagating lookaheads ... "); forget(flush(stdout))
    else unique); 
   add_initial_lookahead(auto); 
   with state_0 = find_state(0,auto), 
   propagate_lookaheads(initial_scenario(classes(state_0)),
                        state_0,
                        auto,
                        first,
                        verbose:options);
   (if verbose:options
    then print("Done.  ")
    else unique);    
   auto. 
   
   
   
   
   
      *** [3.9] Testing. 
   
 global define One
   automaton_test_2
     (
       List(String) args
     ) =
   if read_APG_grammar(make_stream(example_grammar),[]) is 
     {
        error(msg)  then en_print(msg), 
        ok(g)       then 
          with auto1 = make_automaton(grammar_rules(g),[verbose]), 
               auto2 = compute_transitions(auto1,auto1,[],[verbose]), 
                auto = compute_lookaheads(auto2,g,[verbose]),
          map_forget(print,auto);
          print("\n\n")
     }.


   
   *** [4] The public tool. 
   
 public define List(APG_State)
   make_APG_automaton
     (
       APG_Grammar         g,
       List(APG_Option)    options
     ) =
   with non_terminals = all_non_terminals(grammar_rules(g)), 
                first = if time:options
                        then show_time("compute_first: ",(One u) |-> compute_first(g))
                        else compute_first(g), 
   //map_forget(print,first); 
   with auto1 = make_automaton(grammar_rules(g),options),
   with auto2 = compute_transitions(auto1,auto1,[],options,non_terminals,first),
   compute_lookaheads(auto2,g,options,first).
   
   
public define (List(FirstEntry),List(APG_State))
   make_APG_automaton
     (
       APG_Grammar         g,
       List(APG_Option)    options
     ) =   
   with non_terminals = all_non_terminals(grammar_rules(g)), 
   if time:options
   then 
     (
     with  first = show_time("compute_first: ",      
                             (One u) |-> compute_first(g)),
           auto1 = show_time("make_automaton: ",     
                             (One u) |-> make_automaton(grammar_rules(g),options)),
           auto2 = show_time("compute_transitions: ",
                             (One u) |-> compute_transitions(auto1,auto1,[],options,non_terminals,first)),
           (first,show_time("compute_lookaheads: ",
                             (One u) |-> compute_lookaheads(auto2,g,options,first)))
     )
   else
     (
     with first = compute_first(g), 
          auto1 = make_automaton(grammar_rules(g),options),
          auto2 = compute_transitions(auto1,auto1,[],options,non_terminals,first),
          (first,compute_lookaheads(auto2,g,options,first))
     ).