Anubis / Anubis

                                     The Anubis Project
   
                        Common Stuff for the Anubis Parser Generator.
   
                               Copyright (c) Alain Proute' 2006.
   
   
   
   Author:  Alain Proute'
   
   Created March 2006
   Revised March 2006
   
  

   This file  contains the public  types and definitions  which are common to  the several
   parts of the Anubis Parser Generator (APG).
   
   
   This is the type of options for APG. 
   
public type APG_Option:
   verbose,
   types, 
   trace,
   time,
   yacc,
   tools,
   force,
   yards. 
   
   

   
public type APG_Symbol_Value:
   symbol_value  (String                      name,
                  String                      value).   // default is "_"
                  
public type APG_Tail_Symbol_Value:
   symbol_value  (String                      name,
                  String                      value),   // default is "_"
   command       (String                      text). 
                  
public type TailItem:    // things that can be in the tail of a grammar rule
   symbol_value  (String                      name, 
                  String                      value), 
   plus          (List(TailItem)              items, 
                  String                      sym, 
                  String                      value),                    
   star          (List(TailItem)              items, 
                  String                      sym, 
                  String                      value),                    
   maybe         (List(TailItem)              items, 
                  String                      sym, 
                  String                      value),
   command       (String                      text).    // command within the body: { <term> }
                  
   
public type APG_Extended_Grammar_Rule:
   grammar_rule  (Word32                      id,   // the grammar reader generates numbers
                  APG_Symbol_Value            head,
                  List(TailItem)              body,
                  Maybe(String)               precedence). 
   
public type APG_Grammar_Rule:
   grammar_rule  (Word32                      id,   // the grammar reader generates numbers
                  APG_Symbol_Value            head,
                  List(APG_Tail_Symbol_Value) body,
                  Maybe(String)               precedence). 
   
   
   
   This type  gathers all  the sorts  of errors which  may occur  during execution  of the
   Anubis Parser Generator.
   
public type APG_Error:
   unexpected_end_of_input                  (Word32 line),
   no_parser_name                           (Word32 line),
   keyword_was_expected                     (Word32 line), 
   unknown_declaration_keyword              (Word32 line, String keyword),
   type_description_expected                (Word32 line),
   tool_description_expected                (Word32 line),
   incorrect_symbol_value                   (Word32 line),
   symbol_expected                          (Word32 line), 
   comma_expected                           (String sort, Word32 line), 
   left_par_expected                        (Word32 line), 
   arrow_expected                           (Word32 line), 
   colon_expected                           (Word32 line),
   cannot_read_after_dollar                 (Word32 line), 
   dollar_not_followed_by_paren             (Word32 line), 
   unexpected_end_of_file_in_command        (Word32 line), 
   consecutive_commands                     (Word32 line), 
   incorrect_rule_precedence                (Word32 line),
   misclosed_rule_precedence                (Word32 line),
   incorrect_end_of_rule                    (Word32 line),
   unexpected_char_after_closing_brace      (Word32 line), 
   bad_end_of_precedence_declaration        (Word32 line),
   bad_end_of_type_declaration              (Word32 line),
   bad_end_of_tool_declaration              (Word32 line),
   bad_end_of_extra_declaration             (Word32 line),
   symbol_has_no_type                       (Word32 line, String symbol),
   symbol_has_no_type                       (String symbol),
   symbol_should_have_value                 (Word32 line, String symbol),
   tool_not_declared                        (String tool_name), 
   not_enough_arguments_in_tool             (APG_Grammar_Rule),
   too_many_arguments_in_tool               (APG_Grammar_Rule),
   bad_argument_type                        (APG_Grammar_Rule,
                                             String arg, 
                                             String actual_type,
                                             String declared_type),
   bad_target_type                          (APG_Grammar_Rule,
                                             String head_type,
                                             String target_type),
   unreadable_tool                          (String tool),
   no_include_file                          (Word32 line, String fname), 
   missing_filename                         (Word32 line). 
  

   
   
   
   
   The function  `en_print` prints in English a  message of type `APG_Error`
   on the standard output.
   
public define One
   en_print
     (
       APG_Error  e
     ). 
   
   
   
   
   
   This is  the type of (abstract)  grammars.  An object of  this type is  produced by the
   function `read_APG_grammar`  (see `read_grammar.anubis`), and  given as an  argument to
   the function `make_APG_automaton` (see `make_automaton.anubis`). This type is opaque.
   
public type APG_Grammar:...
public type APG_Extended_Grammar:...   

read tools/streams.anubis
   
   

  
   This  type represents states  in the  abstract automaton  as it  is constructed  by the
   function  `make_APG_automaton` (see `make_automaton.anubis`).  The automaton  itself is
   just a list of such states. This is an opaque type. 
   
public type APG_State:...
   
   
   
  
   
read tools/basis.anubis   
   
public type APG_Precedence_Dec:
   left          (Word32 level, List(String)   symbol_names),
   right         (Word32 level, List(String)   symbol_names),
   non_assoc     (Word32 level, List(String)   symbol_names).
   
public type APG_Type_Dec:
   type_dec      (String                      type,
                  List(String)                symbol_names).

public type APG_Tool_Dec:
   tool_dec      (String                      target_type,
                  List(String)                source_types, 
                  List(String)                symbol_names). 
   
public type Extra:
   extra(String type, String name). 
   
public type APG_Extended_Grammar:
   grammar       (String                               preambule,
                  String                               parser_name,
                  List(APG_Precedence_Dec)             precedence_declarations,
                  List(APG_Type_Dec)                   type_declarations,
                  List(APG_Extended_Grammar_Rule)      grammar_rules,
                  Maybe(Extra)                         extra, 
                  String                               postambule). 
   
public type APG_Grammar:
   grammar       (String                      preambule,
                  String                      parser_name,
                  List(APG_Precedence_Dec)    precedence_declarations,
                  List(APG_Type_Dec)          type_declarations,
                  List(APG_Grammar_Rule)      grammar_rules,
                  Maybe(Extra)                extra, 
                  String                      postambule). 
   
public type APG_Transition:
   transition(String       symbol, 
              Word32       target_id). 
    
public type APG_Propagation:
   propagates_to_derived,
   dont_propagate_to_derived.
   
public type APG_Symbol_Act:
   symbol   (String        name),    // grammar symbol appearing in the body of a rule
   command  (String        text).    // immediate command
   
public type APG_Scenario:
   scenario(Word32                      rule_id, 
            String                      head, 
            List(APG_Symbol_Act)        before_dot, 
            List(APG_Symbol_Act)        after_dot,
            APG_Propagation             propagation, 
            Var(Bool)                   has_generated, 
            Var(List(String))           lookaheads_v). 
        
public type APG_Class:  
   class(String                 transition, 
         List(APG_Scenario)     scenarios). 
   
   
public type APG_State:   
   state(Word32                 state_id,
         //Maybe(String)          preaction,  // action $(term) to execute before reading the lookahead
         List(APG_Class)        classes,
         List(APG_Transition)   transitions). 
   
   
         
public define Bool
   less
   (
     APG_Transition  t1,
     APG_Transition  t2
   ) =
   symbol(t1) < symbol(t2). 
         
   Getting all symbol names from a grammar.
   
define List(APG_Symbol_Act)
  names_in
  (
    TailItem    i
  ) =
  if i is 
  {
    symbol_value(name,value)  then [symbol(name)],  
    plus(items,sym,v)         then no_doubles(flat(map(names_in,items))),
    star(items,sym,v)         then no_doubles(flat(map(names_in,items))),
    maybe(items,sym,v)        then no_doubles(flat(map(names_in,items))),
    command(text)             then [command(text)]
  }. 
   
  
public define List(APG_Symbol_Act)
  drop_leading_command    // if any
  (
    List(APG_Symbol_Act)  l
  ) =
  if l is 
  {
    [ ] then [ ], 
    [h . t] then if h is 
      {
        symbol(_)  then l, 
        command(_) then t
      }
  }. 
  
public define List(APG_Symbol_Act)
   names_in
   (
     List(APG_Tail_Symbol_Value)  l
   ) =
   if l is 
   {
     [ ]      then [ ], 
     [h . t]  then if h is 
       {
         symbol_value(n,_) then [symbol(n) . names_in(t)],
         command(text)     then [command(text) . names_in(t)]
       }
   }.
  
public define List(String)
  symbols_only
  (
    List(APG_Tail_Symbol_Value) l
  ) =
  if l is 
  {
    [ ] then [ ], 
    [h . t] then if h is 
      {
        symbol_value(name,_)  then [name . symbols_only(t)], 
        command(_)            then symbols_only(t)
      }
  }. 
   
   
   
public define List(String)
  symbols_only
  (
    List(APG_Symbol_Act) l
  ) =
  if l is 
  {
    [ ] then [ ], 
    [h . t] then if h is 
      {
        symbol(name) then [name . symbols_only(t)], 
        command(_)   then symbols_only(t)
      }
  }. 
   
public define List(String)
   all_symbols_aux
     (
       List(APG_Grammar_Rule)   rules
     ) =
   if rules is 
     {
       [ ] then [ ], 
       [rule1 . other_rules] then 
         if rule1 is grammar_rule(_,head,body,_) then          
         no_doubles(merge([name(head)],
               merge(no_doubles(symbols_only(names_in(body))),all_symbols_aux(other_rules))))
     }.
   
     
public define List(String)
   all_symbols
     (
       List(APG_Grammar_Rule)   rules
     ) =
   qsort(all_symbols_aux(rules),string_less). 
   
   
   
   Getting all non terminals from a grammar.
   
public define List(String)
   all_non_terminals
     (
       List(APG_Grammar_Rule)     rules
     ) =
   if rules is
     {
       [ ] then [ ], 
       [rule1 . other_rules] then
         if rule1 is grammar_rule(_,head,_,_) then 
         merge([name(head)],all_non_terminals(other_rules))
     }.
   
   
   Tools for getting unused symbols. 
   
public define List(String)
   tokens_from_type_decs
     (
       List(APG_Type_Dec) decs
     ) =
   if decs is 
   {
     [ ] then [ ], 
     [h . t] then if h is type_dec(_,names) then 
       merge(names,tokens_from_type_decs(t))
   }.
     
public define List(String)
   tokens_from_precs
     (
       List(APG_Precedence_Dec) precs
     ) =
   if precs is 
   {
     [ ] then [ ], 
     [h . t] then 
       merge(symbol_names(h),tokens_from_precs(t)) 
   }. 
     
public type APG_Token:
   used   (String name), 
   unused (String name).     
   
public define Bool
   alphaless
     (
       APG_Token t1,
       APG_Token t2
     ) =
   name(t1) < name(t2).    
      
      
define String
  format
  (
    TailItem  i
  ) =
  if i is
  {
    symbol_value(name,value)  then name+"("+value+")", 
    plus(items,sym,v)         then "{"+concat(map(format,items)," ")+"}+("+sym+","+v+")",  
    star(items,sym,v)         then "{"+concat(map(format,items)," ")+"}*("+sym+","+v+")",  
    maybe(items,sym,v)        then "{"+concat(map(format,items)," ")+"}?("+sym+","+v+")",
    command(text)             then "$("+text+")"
  }. 

define String
  format
  (
    APG_Symbol_Value  i
  ) =
  if i is
  {
    symbol_value(name,value)  then name+"("+value+")", 
  }. 

define String
  format
  (
    APG_Tail_Symbol_Value  i
  ) =
  if i is 
  {
     symbol_value(name,value)  then name+"("+value+")", 
     command(text)             then "$("+text+")"
  }. 
  
  
public define One 
  print
  (
    APG_Symbol_Act s
  ) =
  if s is 
  {
    symbol(x)      then print(x), 
    command(text)  then print("$("+text+")")
  }. 
  
define One
   print
     (
       APG_Extended_Grammar_Rule    r
     ) =
   if r is grammar_rule(id,head,body,prec) then 
   print(id+" "+name(head)+"("+value(head)+"): ");
   map_forget((TailItem i) |-> print(format(i)+" "), body);
   if prec is 
     {
       failure then unique,
       success(p) then print("   ["+p+"]")
     };
   print(".\n"). 
   
define One
   print
     (
       APG_Grammar_Rule    r
     ) =
   if r is grammar_rule(id,head,body,prec) then 
   print(id+" "+name(head)+"("+value(head)+"): ");
   map_forget((APG_Tail_Symbol_Value i) |-> print(format(i)+" "), body);
   if prec is 
     {
       failure then unique,
       success(p) then print("   ["+p+"]")
     };
   print(".\n"). 
   
public define One
   en_print
     (
       APG_Error  e
     ) =
   if e is 
     {
       unexpected_end_of_input(Word32 line) then
         print(to_decimal(line)+": Unexpected end of input.\n"),
   
       no_parser_name(Word32 line) then
         print(to_decimal(line)+": No parser name.\n"),
   
       keyword_was_expected(Word32 line) then
         print(to_decimal(line)+": Keyword was expected.\n"),
   
       unknown_declaration_keyword(Word32 line,String keyword) then
         print(to_decimal(line)+": Unknown declaration keyword '"+keyword+"'.\n"),
   
       type_description_expected(Word32 line) then
         print(to_decimal(line)+": Type description expected.\n"),
   
       tool_description_expected(Word32 line) then
         print(to_decimal(line)+": Tool function description expected.\n"),
   
       incorrect_symbol_value(Word32 line) then
         print(to_decimal(line)+": Incorrect symbol value.\n"),
   
       symbol_expected(Word32 line) then
         print(to_decimal(line)+": Symbol expected.\n"),
   
       comma_expected(String sort,Word32 line) then
         print(to_decimal(line)+": Comma expected after '{...}"+sort+"(<symbol>'.\n"),
   
       left_par_expected(Word32 line) then
         print(to_decimal(line)+": Opening parenthese expected.\n"),
   
       arrow_expected(Word32 line) then
         print(to_decimal(line)+": An arrow '->' was expected.\n"),
   
       colon_expected(Word32 line) then
         print(to_decimal(line)+": Colon expected.\n"),
   
       cannot_read_after_dollar(Word32 line) then 
         print(to_decimal(line)+": Cannot read after sign '$'.\n"),
              
       dollar_not_followed_by_paren(Word32 line) then 
         print(to_decimal(line)+": Sign '$' not followed by '('.\n"),
       
       unexpected_end_of_file_in_command(Word32 line) then 
         print(to_decimal(line)+": Unexpected end of file within an immediate command.\n"),         
  
       consecutive_commands(Word32 line) then 
         print(to_decimal(line)+": Consecutive immediate commands are forbidden.\n"),         
  
       incorrect_rule_precedence(Word32 line) then
         print(to_decimal(line)+": Incorrect rule precedence.\n"),
   
       misclosed_rule_precedence(Word32 line) then
         print(to_decimal(line)+": Misclosed rule precedence.\n"),
   
       incorrect_end_of_rule(Word32 line) then
         print(to_decimal(line)+": Incorrect end of rule.\n"),
   
       unexpected_char_after_closing_brace(Word32 line) then
         print(to_decimal(line)+": Unexpected character after closing bracket.\n"),
   
       bad_end_of_precedence_declaration(line) then 
         print(to_decimal(line)+": Incorrect end of precedence declaration.\n"),
   
       bad_end_of_type_declaration(line) then 
         print(to_decimal(line)+": Incorrect end of type declaration.\n"),
   
       bad_end_of_tool_declaration(line) then 
         print(to_decimal(line)+": Incorrect end of tool declaration.\n"),
   
       bad_end_of_extra_declaration(line) then 
         print(to_decimal(line)+": Incorrect end of extra declaration.\n"),
   
       symbol_has_no_type(line,symbol) then 
         print(to_decimal(line)+": Symbol '"+symbol+"' has no declared type.\n"),
   
       symbol_has_no_type(symbol) then 
         print("Symbol '"+symbol+"' has no declared type.\n"),
   
       symbol_should_have_value(line,symbol) then 
         print(to_decimal(line)+": Symbol '"+symbol+"' should have a value.\n")
   
       tool_not_declared(name) then 
         print("Type of tool '"+name+"' not declared.\n")
   
       not_enough_arguments_in_tool(r) then 
         print("Not enough arguments in tool:\n");
         print(r), 
   
       too_many_arguments_in_tool(r) then 
         print("Too many arguments in tool:\n");
         print(r), 
   
       bad_argument_type(r,arg,actual_type,declared_type) then 
         print("Bad argument type: ");
         print(r); 
         print("Argument: "+arg+"\n");
         print("Actual type: "+actual_type+"\n");
         print("Declared type: "+declared_type+"\n"),
   
       bad_target_type(r,head_type,target_type) then 
         print("Bad target type: ");
         print(r);
         print("Type of head: "+head_type+"\n");
         print("Target type: "+target_type+"\n"),
   
       unreadable_tool(s) then 
         print("Unreadable tool: "+s+"\n"),
         
       no_include_file(l,n) then 
         print("File '"+n+"' to be included at line "+l+" cannot be found.\n"),
         
       missing_filename(l) then 
         print("File name not found at line "+l+".\n")
   
   }. 
   
   
public define One print(Stream s, String t) = forget(write_string(s,t)). 

   
   
define One
   print
     (
       Stream               s, 
       APG_Precedence_Dec   d
     ) =
   if d is 
     {
       left(l,names)       then map_forget((String x) |-> print(s,"   "+l+" left        "+x+"\n"),names),
       right(l,names)      then map_forget((String x) |-> print(s,"   "+l+" right       "+x+"\n"),names), 
       non_assoc(l,names)  then map_forget((String x) |-> print(s,"   "+l+" non_assoc   "+x+"\n"),names) 
     }.
   

public define String
   right_pad
     (
       String s, 
       Int    n
     ) =
   with l = length(s), 
   if l >= n
   then s
   else s+constant_string(n-l,' '). 
   
public define String
   right_pad
     (
       Word32  s, 
       Int     n
     ) =
   right_pad(to_decimal(s),n). 
   
   
public define One
  print
  (
    Stream            s, 
    APG_Symbol_Act    x
  ) =
  if x is 
  {
    symbol(a)   then print(s,a), 
    command(t)  then print(s,"$("+t+")") 
  }. 
    
define One
   print
     (
       Stream        s, 
       APG_Type_Dec  d
     ) =
   if d is type_dec(type,names) then 
   map_forget((String x) |-> print(s,"   "+right_pad(type,25)+"   "+x+"\n"),names). 
   
   
define One
   print
     (
       Stream            s, 
       APG_Symbol_Value  sv,
       Bool              pad
     ) =
   if sv is symbol_value(name,value) then 
   with x = name+"("+value+") ", 
   print(s,if pad then right_pad(x,25) else x). 
   
define One
   print
     (
       Stream                 s, 
       APG_Tail_Symbol_Value  sv,
       Bool                   pad
     ) =
   with x = if sv is 
   {
     symbol_value(name,value) then name+"("+value+") ", 
     command(text)            then "$("+text+") "
   }, 
   print(s,if pad then right_pad(x,25) else x). 
   
   
define One 
   print   
     (
       Stream             s, 
       APG_Grammar_Rule   r
     ) =
   if r is grammar_rule(id,head,body,prec) then 
   print(s,right_pad("   ("+id+") ",3)); 
   print(s,head,true); 
   print(s,": "); 
   map_forget((APG_Tail_Symbol_Value sv) |-> print(s,sv,false),body);
   print(s,".\n"). 

   
   This function  prints a  grammar (of  type `APG_Grammar`) on  the standard  output. The
   preambule and postambule are not printed.
   
public define One
   print_grammar
     (
       Stream        s, 
       APG_Grammar   g
     ). 
   
public define One
   print_grammar
     (
       Stream                 s, 
       APG_Extended_Grammar   g
     ). 
   
   

public define One
   print_grammar
     (
       Stream        s, 
       APG_Grammar   g
     ) =
   with prints    = (String x) |-> print(s,x), 
   if g is  grammar(preambule,
                    parser_name,
                    precedence_declarations,
                    type_declarations,
                    grammar_rules,
                    mb_extra, 
                    postambule) then
   
      prints("\n   Parser name: "+parser_name+"\n");
   
      prints("\n   Precedence levels and association modes:\n");
      map_forget((APG_Precedence_Dec d) |-> print(s,d),precedence_declarations);
   
      prints("\n   Types of all symbols:\n");
      map_forget((APG_Type_Dec d) |-> print(s,d),type_declarations); 
      // all other symbols have type One by default: 
      print(s,type_dec("One", 
          all_symbols(grammar_rules) - flat(map(symbol_names,type_declarations)))); 
   
      if mb_extra is 
        {
          failure then prints("\n   No Extra data.\n"),
          success(e) then if e is extra(t,n) then 
            prints("\n   Extra data: ("+t+") "+n+"\n")
        };
   
      prints("\n   Grammar rules:\n");
      map_forget((APG_Grammar_Rule r) |-> print(s,r),grammar_rules);
   
      prints("\n").
   



   
   
 public define One
   print_grammar
     (
       Stream                 s, 
       APG_Extended_Grammar   g
     ) =
   with prints = (String x) |-> print(s,x), 
   if g is  grammar(preambule,
                    parser_name,
                    precedence_declarations,
                    type_declarations,
                    grammar_rules,
                    mb_extra, 
                    postambule) then
   
      prints("\nParser name: "+parser_name+"\n");
   
      prints("\nPrecedence levels and association modes:\n");
      map_forget(prints,precedence_declarations);
   
      prints("\nType declarations:\n");
      map_forget(prints,type_declarations); 
   
      if mb_extra is 
        {
          failure then prints("\nNo Extra data.\n"),
          success(e) then if e is extra(t,n) then 
            prints("\nExtra data: ("+t+") "+n+"\n")
        };
   
      prints("\nGrammar rules:\n");
      map_forget(prints,grammar_rules);
   
      prints("\n").
   
   
   
public define One
   print_grammar
     (
       APG_Extended_Grammar   g
     ) = print_grammar(make_stream(stdout),g). 
   
public define One
   print_grammar
     (
       APG_Grammar   g
     ) = print_grammar(make_stream(stdout),g). 
   
   
   
   
   
define Maybe(List($T))
   extract
     (
       $T        x,
       List($T)  l
     ) =
   if l is 
     {
       [ ] then failure, 
       [h . t] then 
         if h = x
         then success(t)
         else if extract(x,t) is 
           {
             failure then failure, 
             success(s) then success([h . s])
           }
     }.
   
   
public define Bool
   same_set
     (
       List($T)    l1,
       List($T)    l2
     ) =
   if l1 is 
     {
       [ ] then l2 = [ ], 
       [h1 . t1] then 
         if extract(h1,l2) is 
           {
             failure then false,
             success(t2) then same_set(t1,t2)
           }
     }. 
   
   
read system/string.anubis
   
public define $T
   show_time
     (
       String       msg, 
       One -> $T    term
     ) =
   with start_time = (UTime)unow, 
            result = term(unique), 
   if unow - start_time is utime(s,m) then 
   print(msg+s+","+zero_pad_n(6,m)+" seconds\n");
   result. 
   
   
public define String
   show_rule
   (
     APG_Extended_Grammar_Rule h
   )=
   if h is grammar_rule(id,head,body,prec) then 
      "("+to_decimal(id)+") "+name(head)+": "+
        concat(map(format,body)," ") + "\n".