Anubis / Anubis




                                     The Anubis Project

                   A tool for producing fast buffered lexers (version 4). 
                          Copyright (c) Alain Prouté 2008-today. 
     
   Author:             Alain Prouté (2014-09, from previous versions written in 2008 and 2013). 
   Contributions by:   Matthieu Herrmann (2014). 
   Last revision:      2014-09-20


   This is an enhancement of fast_lexer_3.anubis. The differences are as follows:
   
     - The parameter $Aux is no more part of LexingStream. It is introduced separately.
       This has the avantage of being more simple and more flexible. Indeed, we can 
       now have different values for this parameter for multiple lexers plugged on 
       the same lexing stream. 
   
     - The reconstruction of precompiled lexers is automated. Each one is reconstructed
       only if something is changed in the description of the lexer. This is performed
       by using an sha1 hash of the description, which is stored in the first line of the
       generated file. 

   This tool is similar to the Unix tool LEX/FLEX (with some differences, 
   but it is more or less equivalent). If you want to use this tool, you 
   have to add:
   
read lexical_analysis/fast_lexer_4.anubis
   
   into your source file.
   
   Consider a 'source' from which bytes can be read, such as a file, a network connection
   (maybe an SSL connection), a string or a byte array, etc...  There are tools for
   getting the bytes from this source one after the other, but in general we are better
   interested into particular sequences of bytes which are called `tokens'.  As an
   example, if the source is the following string:
   
                                         "344 + 87"
   
   we prefer to read the three 'tokens': "344", "+" and "87" directly (ignoring white
   spaces) rather than the sequence of bytes '3', '4', '4', ' ', '+', ' ', '8' and '7'.

   A 'lexer' is precisely the gadget which will do this job easily and fast (and even
   better than described above).  It uses 'lexing streams', which are buffered for better
   performances, and which can be created from any kind of source of bytes (file,
   connection, byte array, string, etc...).
   
   The lexers can be constructed by this program in two different ways, either statically
   (i.e. at compile time) or dynamically (i.e. at run time). Use the second possibility 
   if the regular expressions (see the definition below) needed for constructing the lexer 
   are not known at compile time. 
   
   
   ---------------------------------- Table of Contents ----------------------------------

   *** (1) Regular expressions. 
      *** (1.1) Description. 
      *** (1.2) Choosing the escape character. 
      *** (1.3) Syntax errors in regular expressions. 
      
   *** (2) Describing a lexer. 
      *** (2.1) Defining a type of tokens. 
      *** (2.2) Output of the lexer. 
      *** (2.3) Returning a token. 
      *** (2.4) Ignoring a token. 
      *** (2.5) Testing if a whole string is a single token.
      *** (2.6) Putting lexer items in the right order. 
      
   *** (3) Lexing streams. 
   
   *** (4) Constructing a lexer. 
      *** (4.1) Construction. 
      *** (4.2) Getting the automaton. 
      *** (4.3) How to use a lexer.
      *** (4.4) Computing a lexer at compile time. 
      
   *** (5) Plugging several lexers on the same input.
   
   ---------------------------------------------------------------------------------------
   
read tools/basis.anubis
read tools/streams.anubis
   
        
   *** (1) Regular expressions. 
   
   
      *** (1.1) Description. 
   
   Regular expressions are character strings which are used for describing particular sets
   of tokens.  Regular expressions are written using 8 bits characters, but some of them
   have a special meaning. They are the following:
   
                                  ( ) [ ] - * + | . $ ^ ?
   
   plus another character, the 'escape character', that you choose yourself.
   Traditionally, the escape character is the backslash: \ .  However this choice creates
   tricky problems because this is also the escape character for Anubis character
   strings. This problem is discussed in another section below.  We recommand to choose
   the character 'sharp': # as the escape character, and we use this character as the
   escape character in our explanations and examples in this file.
   
   All other characters just represent themself.  For example, the regular expression
   'abcd' represents only the token 'abcd'. Note: quotes are just used for 'quoting'. 
   They are not part of the regular expressions and also not part of their interpretations
   as they are shown here. 
   
   Parentheses do not represent anything.  They are just used for delimiting regular
   expressions. For example '(abcd)' represents the same thing as 'abcd'.
   
   The regular expression '[abcd]' represents the 4 tokens: 'a', 'b', 'c' and 'd'. In
   other words, characters between brackets represent all the tokens made of one and only
   one of these characters.  There is a shortcut for ranges of characters.  Instead of
   writting:
   
                                [abcdefghijklmnopqrstuvwxyz]
   
   you may just write '[a-z]'.  For example, the regular expression '[a-zA-Z0-9]'
   represents any token made of one and only one alphanumeric character.
   
   If you add a caret just after the opening bracket, the regular expression represents
   all one byte tokens for all bytes non present within the brackets (i.e.  the
   'complement' in some sens of the previous set).  For example, the regular expression
   '[^a-z]' represents all one byte tokens whose unique character is not a lowercase
   letter.  Note: a byte is any Word8, so that '[^a-z]' also matches characters of code
   above 127.
   
   If 'A' is a regular expression, 'A+' represents any non empty concatenation of tokens
   represented by 'A'.  For example, '[a-z]+' represents any non empty sequence of
   lowercase letters.  Similarly, 'A*' represents all the tokens represented by 'A+', plus
   the empty token (the token made of no character at all).
   
   If 'A' and 'B' are regular expressions, 'AB' is a regular expression representing any
   concatenation of a token represented by 'A' and a token represented by 'B'.  For
   example, 'a+b+' represents any non empty sequence of 'a' followed by any non empty
   sequence of 'b'.  As another example, '[A-Z][A-Za-z]*' represents any sequence of
   letters beginning by an uppercase letter (hence actually non empty).
   
   The escape character quotes the subsequent character.  For example, assuming you have
   chosen '#' as the escape character, the regular expression '#(' represents the token
   made of the single character '('. Of course, this is useful for special characters
   including the escape character itself, which can be quoted as '##'.  However, the
   sequences '#n', '#r' and '#t' represent respectively a line feed, a carriage return and
   a tabulator, not the letters 'n', 'r' and 't'.
   
   If 'A' and 'B' are regular expressions, 'A|B' is a regular expression representing all
   the tokens represented by 'A' and all the tokens represented by 'B'.  For example,
   '(a+)|(b+)' represents all non empty sequences containing either only a's or only b's.
   
   The dot '.' represents any character except the newline character.
      
   If 'A' is a regular expression, 'A?' represents all the tokens represented by 'A' plus
   the empty token.

   
   
   
      *** (1.2) Choosing the escape character. 
   
   As already said above, we recommand to choose the character '#' as the escape
   character.  Let us just compare the two choices '\' and '#'.  The problem with the
   backslash is comming from the fact that the Anubis compiler itself interprets the
   backslash when reading characters strings from your source files. If you choose it as
   the escape character, it is interpreted two consecutive times, and this is maybe quite
   difficult to handle.
   
   Assume that you want to write down a regular expression representing the unique
   sequence made of a single (non interpreted) backslash. If the escape character is '#',
   the regular expression writes (as a character string):
   
      "#\\"
   
   and not "#\", because the Anubis compiler will read this as a non ending character
   string, since the second " is quoted by the backslash. If you choose the backslash as
   the escape character, the same regular expression must be written:
   
      "\\\\"
   
   because this is read by the Anubis compiler as a length two string containing two
   baskslash characters.  The regular expression parser, will interpret this as a quoted
   backslash, so that indeed, this regular expression represents the token made of just
   one backslash character.
   
   As another example, consider the case of a lexer able to recognize the 'mapsto' arrow
   of the Anubis language:
   
                                              |->
   
   If you choose '#' as the escape character, the correct regular expression is:
   
      "#|#->"
   
   since both '|' and '-' are special characters. Now if you choose the backslash as the
   escape character, the correct regular expression is:
   
      "\\|\\->"
   
   because the Anubis compiler will contract double baskslashes into single ones while
   reading the regular expression.
   
   
   Another possibly disturbing situation is the following. How to represent the sequence
   made of a single newline character ? Assuming that '#' has been chosen as the escape
   character, the correct regular expression is:
   
      "#n"
   
   because the Anubis compiler will read that as the two characters string containing '#'
   and 'n', and this sequence will be interpreted as a newline character by the regular
   expression parser. However, the following produces the same effect:
   
      "\n"
   
   Indeed, this is read by the Anubis compiler as the one character string containing only a
   newline, and this is interpreted as a newline by the regular expresssion parser, simply
   because newline is not a special character.
   
   Now if you choose the backslash as the escape character, the two solutions for the same
   problem are:
   
      "\\n"   and   "\n"
   
   
   Despite the fact that it is not impossible to use the baskslash as the escape
   character, it is clearly simpler to use another character. The character '#' is fine
   for this purpose, also because, due to its somewhat 'bold' aspect, it is visualy
   more easily distinguishable from other characters.
   
   You cannot use an already special character (i.e. among: ( ) [ ] - * + | . $ ^ ? ) as
   the escape character.
   
   
   
   
      *** (1.3) Syntax errors in regular expressions. 
   
   When you construct a lexer you provide one or several regular expressions. These
   regular expressions may be syntactically incorrect. For this reason, we have the
   following type classifying the possible errors:
   
public type RegExprError:
   premature_end_of_regexpr,
   unexpected_right_par, 
   unexpected_right_bracket, 
   regexpr_is_empty,
   star_not_following_a_regexpr,
   plus_not_following_a_regexpr,
   question_mark_not_following_a_regexpr,
   non_character_within_brackets,
   misplaced_hyphen,
   misplaced_dollar,
   misplaced_caret,
   misplaced_vbar,
   empty_lexer_description. 

   For your convenience, the function below transforms such an error into a message in
   English.
   
public define String       to_English      (RegExprError e).
   
   
   
   *** (2) Describing a lexer. 
   
      *** (2.1) Defining a type of tokens. 
   
   A single lexer may recognize different sorts of tokens.  For example, a lexer may
   recognize 'symbols' (represented say by the regular expression '[a-zA-Z]+'), and
   integers (represented say by the regular expression '[0-9]+'). The role of the lexer is
   not only to recognize such tokens, but also to return them in such a way that their
   sort is obvious.  For this reason, it is convenient to define a type of tokens with one
   alternative for each sort of token. In the case of our example, this type could be:
   
   type Token: 
      symbol   (Int line, String name),
      integer  (Int line, Int value). 
   
   where 'line' is the line at which the token was found in the source text. Of course, 
   you can replace 'line' by a datum of a more sophisticated type containing informations 
   about the nature of the source (file (including the path) or other) the line, the column 
   or whatever you need. You can also just ignore line numbers and define the above type
   whithout the components 'line'. 
   
   However, if you are also using APG (the Anubis Parser Generator), APG defines this
   type for you. Hence, in most cases, it is preferable to write an APG file first, and
   to define your lexers later on. 
   
   The type of tokens for a given lexer is represented in this file by the type parameter
   '$Token'.
   
   
   
   
   
      *** (2.2) Output of the lexer. 
   
   A lexer returns a datum of type:
   
public type LexerOutput($Token):   
   end_of_input, 
   error            (ByteArray b, Int line, Int col),
   token            ($Token t).   
   
   The lexer returns 'end_of_input' when there is no hope that a next token can be read
   from the input source.  In the case of a file this means that the end of the file has
   been reached. In the case of a network connection, this means that the connection has
   been closed or that time is out. In the case of a string or a byte array, this means
   that the end of the string or byte array has been reached (and that no error occured). 
   If you define a new sort of lexing stream, you have to decide yourself what it means. 
      
   The lexer returns 'error(b,l,c)' when it has read something which cannot be the beginning
   of any acceptable token. More precisely, some bytes have been read from the input, which
   could have been the beginning of a token until the first byte which cannot be part of a
   token.  Next time the lexer will be called, it will continue to read from after this
   sequence.
   
   Notice that the lexer handles a notion of line and column internally (and you can 
   also get the 'offset', i.e. the number of bytes read since the beginning). It increments 
   its line counter at each newline character, and its column counter at each other 
   character (resetting it at 0 in case of a newline). 
   
   The last alternative token($Token) occurs when a (correct) token is recognized. 

   Note: the lexer does not handle multibytes characters (such as utf-8 characters). 
   If you want to scan utf-8 texts you have to design your regular expressions accordingly. 
   More on this below. 
   
   
      *** (2.3) Returning a token. 
   
   When a token is recognized, the lexer has the token at its disposal in the form
   of a byte array. It also has the line and column at which this token begins. In order
   to transform this byte array into a datum of type '$Token' you have to provide a
   function of type '(ByteArray b, LexingTools tools, $Aux aux) -> LexerOutput($Token)'.  
   In the case of our example, if a 'symbol' is to be recognized, the corresponding function
   could be something like this (here we put $Aux = One, because we don't need it):
   
       (ByteArray b, LexingTools t, One u) |-> token(symbol(t.line(unique),to_string(b)))
   
   If an 'integer' is to be recognized, the corresponding function could be:
   
       (ByteArray b, LexingTools t, One u) |-> 
                         if decimal_scan(to_string(b)) is 
                           {
                             failure     then should_not_happen(error(b,0,0)),
                             success(n)  then token(integer(t.line(unique),n))
                           }
   
   Actually, the case `failure' here cannot happen. Indeed, if the token is recognized
   according to the regular expression '[0-9]+', decimal_scan cannot fail. 

   So, in the case of our example (using the type 'Token' above), the lexer may be
   described by the following list of 'lexer items' of type 'List(LexerItem($Token))'. 
   The types 'LexingTools', 'LexerAction' and 'LexerItem' are defined below:
   
      [
        lexer_item("[A-Za-z]+", 
                   return((ByteArray b, LexingTools t, One aux) |-> // 'One' if we don't care about 'aux'
                     token(symbol(to_string(t.line(unique),b))))), 
                     
        lexer_item("[0-9]+", 
                   return((ByteArray b, LexingTools t, One aux) |-> 
                     if decimal_scan(to_string(b)) is 
                                    {
                                      failure     then should_not_happen(error(b,0,0)),
                                      success(n)  then token(integer(t.line(unique),n))
                                    }))
      ]
   
public type LexingTools:
  tools
  (
    One -> Int        line,      // getting the current line
    One -> Int        column,    // getting the current column
    One -> Int        offset,    // getting the current offset (bytes read since the very beginning of the input)
    Int -> One        back,      // going back n characters (if possible)
    One -> One        belt,      // ``back to end of last token''
    One -> One        bept       // ``back to end of penultimate token''
  ).    
  
  The 'belt' and 'bept' tool can be used for putting the lexer back into its state just after the 
  last or penultimate token was (successfully) read. 
  
  For 'belt' to work as stated above, at least one token must have been successfully read from the
  very beginning. If no token has been read, the lexing stream will just return to the very initial
  state. 
  
  Similarly, 'bept' works as stated above if at least two tokens have been successfully read since the
  very beginning. If only one token has been read, 'bept' will return to the state just after this token
  was read. If no token has been read, 'bept' will return to the very initial state. 
  
  'bept' is useful in case we have to switch from one lexer to another 
  and a lookahead token is already read. The text after the end of the penultimate token must be reread 
  by another lexer, because the lookahead token just read in this case was not read by the right lexer 
  and is consequently meaningless. 
  
   
public type LexerAction($Token,$Aux):
   ignore,                                                        // ignore the token (no action)
   return((ByteArray                   token,             
           LexingTools                 tools,
           $Aux                        aux) -> LexerOutput($Token)),  // return the token using this function
   return(((Int s,Int e) -> ByteArray  extract,    // extract token from buffer (start/end relative to token)
           Int                         length,     // length of token
           LexingTools                 tools,
           $Aux                        aux) -> LexerOutput($Token)).  // idem but allowing to extract part of
                                                                      // the token 
                                                                  
   The third alternative in 'LexerAction($Token,$Aux)' is a variant of the second one. Instead of extracting
   the token from the buffer, the function provides tools for extracting a part of the token. The argument 
   'length' is the total length of the token. The function 'extract' enables to extract the part of the token
   located between positions 's' (included) and 'e' (not included), relative to the token. For example, 
   extract(0,length) gives the whole token. 
                                                                  
                                                                  
public type LexerItem($Token,$Aux):
  lexer_item(String                        regular_expression,
             LexerAction($Token,$Aux)      action),
  lexer_item(ByteArray                     literal,
             LexerAction($Token,$Aux)      action).

   The second alternative in 'LexerItem' is used for recognizing a sequence which may contain
   any character (Word8) including 0, but it is taken literally, not as a regular expression
   (i.e. it represents only itself). 

   Notice that you can also write a lexer item recognizing something that you consider as
   faulty. In this case, it is not faulty from the point of view of the lexer, but you are
   free to return a 'faulty token' if you have an alternative such as 'faulty_token(...)'
   in your type 'Token'. This may be interesting for refining the lexical error messages
   for the users of your program.
   
   
   
   
      *** (2.4) Ignoring a token. 
   
   If you don't provide a function in a lexer item (using 'ignore' instead of 'return'),
   the recognized token is just ignored and the lexer tries to read the next token. For example, 
   this may be used for ignoring white spaces. 
   
   If you want to ignore a token and neverthelesss execute an action, use the 'return'
   alternative and discard the token instead of returning it to the parser. 
   

   
      *** (2.5) Testing if a whole string is a single token.
   
   Notice that the most common use of a lexer is to call it repeatedly until it returns
   'end_of_input'. However, in some circumstances, we want to check for example if a whole
   string matches a regular expression. In this case the lexer is called a first time, and
   if it returns a token it must be called a second time in order to check that it has
   reached the end of the input, i.e. that it returns 'end_of_input'. 
   
   
   
      *** (2.6) Putting lexer items in the right order. 
   
   The order of the lexer items in a lexer description can be important.  The lexer can
   behave differently if this order is changed.  Indeed, consider the following lexer
   description (assuming that the type 'Token' has an alternative named 'a'):
   
      [
        lexer_item("a",   return((ByteArray b, LexingTools t, One u) |-> token(a))),
        lexer_item("#n",  ignore),
        lexer_item(".",   ignore)
      ]
   
   In other words, we want all occurences of the letter 'a' and ignore anything
   else. Notice that the regular expression "." also matches the letter 'a'. Hence, 'a' is
   matched by both regular expressions. So, if the lexer finds an 'a', what must it do ?
   Return the token 'a' or ignore this 'a' ?
   
   In the case of our example, the lexer returns the token 'a'. This is just because, in
   case several lexer items match the same sequence, the first one in the list is used for
   either returning or ignoring.  If you reverse the above list, the lexer ignores all
   letters, including 'a'.
   
   
   
   
   *** (3) Lexing streams. 
   
   A lexer recognizes tokens by reading characters from some input. The actual input may
   be either a file, a network connection, a string, a byte array, or anything able to
   provide characters.  From any of the above and many more you can construct a 'lexing stream'.
   
public type LexingStream:...    (an opaque type, except if you need a new sort of lexing stream)


   Creating (opening) a lexing stream.
   
   We provide the following tools for contructing a lexing stream. You can create more
   such tools. 
   
   From a byte array: 
public define LexingStream                make_lexing_stream(String         preambule, 
                                                             ByteArray      b).  
   
   From a character string:
public define LexingStream                make_lexing_stream(String         preambule, 
                                                             String         s). 
   
   From a file or network connection:
public define Maybe(LexingStream)         make_lexing_stream(String         preambule, 
                                                             RStream        stream,
                                                             Int            buffer_size,
                                                             Int            timeout).
   
   A variant of the previous one: 
public define Maybe(LexingStream)         make_lexing_stream(String         preambule, 
                                                             RWStream       stream,
                                                             Int            buffer_size,
                                                             Int            timeout).
   
   From an SSL connection: 
public define Maybe(LexingStream)         make_lexing_stream(String         preambule, 
                                                             SSL_Connection stream,
                                                             Int            buffer_size,
                                                             Int            timeout).
      
   The 'preambule' is a string which is read before the input itself is read. 
   In some sens, the preambule is appended at the beginning of the input. Use the empty string
   if you don't need to append a preambule. The typical preambule is "#n", which allows
   to recognize the beginning of a line (including the first one) as what follows
   a line feed. 

   In the case of a file or network connection (argument of type 'RStream',
   'RWStream', 'SSL_Connection') byte arrays are used for buffering the input. The
   size of these buffers must be provided as an argument.  The choice has no
   incidence on the behavior of the lexer (but cannot be 0 or negative, otherwise
   'failure' is returned), except with respect to performances, and the lexer can still
   return tokens longer than this size.  The timeout is in seconds and used each time the
   buffer is reloaded from the actual input.  When time is out, the lexer gives up as if
   the end of the input was reached. 

   'make_lexing_stream' returns 'failure' if a read error or timeout occurs because when
   the lexing stream is created, the buffer is immediatly loaded for the first time.
   
   In the case of a byte array or a string, the situation is much simpler. The buffer is
   the byte array or the string itself, no time out is needed and the result has no
   'Maybe'.
   
   If you need another kind of lexing stream, have a look at the private part of this
   file, in particular at the actual definition of type 'LexingStream($Aux)', and write down
   another such function (in a file of yours within which you put a 'transmit
   lexical_analysis/fast_lexer_4.anubis', and that you 'read' instead of the present file).



   
   *** (4) Constructing a lexer. 

      *** (4.1) Construction. 
   
   In order to construct a lexer at run time (from a lexer description) use the following:
   
public define Result(RegExprError, 
                     (LexingStream,$Aux) -> One -> LexerOutput($Token))
   make_lexer
     (
       List(LexerItem($Token,$Aux))   lexer_description,
       Word8                          escape_char               // '#' recommanded here
     ).
      
   Thus, a lexer is constructed (if no error occurs) as a function of type:
   
                         LexingStream($Aux) -> (One -> LexerOutput($Token))

   Don't worry about this ``two stages'' function. How to use it is explained below. 
   
   
   
   
      *** (4.2) Getting the automaton. 
      
   This section is only for those who want to see the automaton produced by this program. 
   It is not required for using fast_lexer_4.  
   
   You may want to have a look at the automaton produced by 'make_lexer'.  You may also
   want to use a tool like Graphviz for producing a representation of this automaton.

   The ``deterministic finite automaton'' (DFA) is presented as a list of 'states'.  Each
   state is either accepting, rejecting or ignoring. Each state has a name (of type
   Word16), and a list of transitions. Accepting states also have the corresponding
   'action'.
   
   Each  transition has a  'label' and  the name  of a  state (the  target state  for this
   transition). 
   
public type DFA_label:   
   char(Word8). 
   
   Transitions are defined as:
   
public type DFA_transition:
   transition(DFA_label    label, 
              Word16       target_name). 

   States are defined as:
   
public type DFA_state($Token,$Aux):
  rejecting   (Word16                                               name, 
               List(DFA_transition)                                 transitions), 
    
  accepting   (Word16                                               name, 
               List(DFA_transition)                                 transitions, 
               Int                                                  action_rank, 
               (ByteArray,LexingTools,$Aux) -> LexerOutput($Token)  action),
   
  accepting   (Word16                                               name, 
               List(DFA_transition)                                 transitions, 
               Int                                                  action_rank, 
               ((Int,Int) -> ByteArray,Int,LexingTools,$Aux) -> LexerOutput($Token)  action),
   
  ignoring    (Word16                                               name,
               List(DFA_transition)                                 transitions).
   
   
   
   In order to produce the lexer and get the automaton at the same time, use the following
   variant of 'make_lexer':
   
public define Result(RegExprError, 
                     ((LexingStream,$Aux) -> One -> LexerOutput($Token),     // the lexer
                      List(DFA_state($Token,$Aux))))                        // the automaton
   make_lexer_and_automaton
     (
       List(LexerItem($Token,$Aux))   lexer_description,
       Word8                          escape_char
     ).
   
   
   You can also get a Graphviz source with one of these: 
   
public define One 
  dump_dfa_graphviz       // produces the file 'lexer_name.dot' in the given directory
  ( 
    List(DFA_state($Token, $Aux))         dfa, 
    String                                lexer_name,
    String                                directory
  ). 
      
public define One 
  dump_dfa_graphviz       // dumps the Graphviz text to an output stream
  ( 
    List(DFA_state($Token, $Aux))         dfa, 
    String                                lexer_name, 
    Stream                                output
  ). 
   
   
   
   
   
      *** (4.3) How to use a lexer.
   
   Applying the function of type 'LexingStream -> One -> LexerOutput($Token)' returned by
   'make_lexer' to a lexing stream is understood as 'plugging' the lexer onto this lexing
   stream. The result is a function of type:
   
                                      One -> LexerOutput($Token)
   
   to be used repeatedly until it returns 'end_of_input'.
   
   
   
   
      *** (4.4) Computing a lexer at compile time. 
      
   If you do as explained above, your lexers are constructed at run time. If the 
   lexer description is already known at compile time, it is preferable to construct
   the lexer at compile time. In order to do that, write the following into your
   source file: 
   
   global define One 
     precompile_my_lexers  // of course, you can choose another name here
     (
       List(String) _      // not used
     ) =
     make_precompiled_lexer(lexer_name_1,lexer_description_1,'#'); 
     ...
     make_precompiled_lexer(lexer_name_n,lexer_description_n,'#'). 
     
   execute anbexec precompile_my_lexers
   
   This creates 'n' Anubis source files whose names are 'lexer_name_1.anubis', etc...
   within a subdirectory (of the current directory) named 'generated', which is created
   if needed. This execution prints error messages (if any) on the standard output. 
   
   The function 'make_precompiled_lexer' is declared as follows: 
   
public define One
  make_precompiled_lexer
  (
    String                         lexer_name, 
    List(LexerItem($Token,$Aux))   lexer_description,
    Word8                          escape_char    
  ). 

  If you want to create the target files in another directory than 'generated', use
  the variant below: 
  
public define One
  make_precompiled_lexer
  (
    String                         directory,  // where the file must be created
    String                         lexer_name, 
    List(LexerItem($Token,$Aux))   lexer_description,
    Word8                          escape_char    
  ). 

   
   Each generated file contains a precompiled fast lexer in lexical form, but you 
   don't even need to have a look at it. In order to get your lexer in the form of 
   a function of type: 
   
        LexingStream($Aux) -> (One -> LexerOutput($Token))
   
   as above, just write this: 
   
   read generated/lexer_name_1.anubis      (in order to have the precompiled version of the lexer)
   
   and, at the place in your program where you want to have your lexer:
   
      retrieve_lexer(lexer_description_1,lexer_name_1)
   
   The function 'retrieve_lexer' is declared as follows:
      
public define (LexingStream,$Aux) -> (One -> LexerOutput($Token))
  retrieve_lexer
  (
    List(LexerItem($Token,$Aux))       lexer_description, 
    (List(Int),PrecompiledFastLexer)   p    // the datum defined in the generated file
  ). 
   
   At this moment no error can happen if the file 'lexer_name_1.anubis' did not contain
   any error (this automatically generated file should not contain any error, anyway). 
   
   
   *** (5) Plugging several lexers on the same input. 
   
   It is often the case that we have to use several lexers on the same input. This is
   equivalent to saying that we have only one lexer on this input but with several
   different 'states' in the sens of LEX/FLEX.  In our system there is no notion of
   'state' for lexers, but several lexers can use the same lexing stream concurrently.
   You can plug them to the same lexing stream, and use them repeatedly in any order
   depending on the sort of thing you want to read from the stream. In picture, you
   can have this: 
   
                                         +---------+
                                  .----->| lexer 1 |-->-.
                                  |      +---------+    |
              +---------------+   |      +---------+    |     +--------+
     input -->| Lexing stream |---+----->| lexer 2 |----+---->| parser |--> 
              +---------------+   |      +---------+    |     +--------+
                                  |      +---------+    |
                                  `----->| lexer 3 |-->-'
                                         +---------+
                                         
   But you can also have this: 
   
                                         +---------+     +----------+
                                  .----->| lexer 1 |-->--| parser 1 |--.
                                  |      +---------+     +----------+  |
              +---------------+   |      +---------+               +---v---------+
     input -->| Lexing stream |---+----->| lexer 2 |-------------->| main parser |--> 
              +---------------+   |      +---------+               +---^---------+
                                  |      +---------+     +----------+  |
                                  `----->| lexer 3 |-->--| parser 3 |--'
                                         +---------+     +----------+ 
    
   which is a better solution, because it avoids the need for lexer switching. See the 
   APG documentation for knowing how a parser can call another parser. 
                                         
   As an example of the first solution above, consider the case of the Anubis language 
   syntax (that you know very well for sure). We need at least two lexers, one (say 
   the 'off' lexer) for reading outside any paragraph and another one (say the 'in' 
   lexer) for reading within the paragraphs. Here we illustrate only how the lexer 
   is changed from 'off' to 'in' when we encounter a key words like 'define', 'public' 
   or 'type' in the leftmost column. Remark that in order to recognize the beginning 
   of a line we use the prefix "\n" in 'make_lexing_stream' so that '#n' represents the 
   beginning of a line for the lexer, even if this line is the first one. 
   
   First of all, define a type like this one: 
   
   type LexerState: 
      off, 
      in. 
      
   The lexer item of the 'off' lexer for recognizing 'define' at the beginning of a 
   line can be:
      
      lexer_item("#ndefine", 
                 return((ByteArray b, Int line, Int col, LexerState -> One change_lexer) |->
                     change_lexer(in); token(...)))   
      
   Here, 'change_lexer' is a function of type 'LexerState -> One', which plays the role
   if the macro BEGIN of FLEX. The effet of 'change_lexer(in);' is to put 'in' into a 
   dynamic variable, say 'lexer_state_v' of type 'Var(LexerState)'. Hence, the function 
   'change_lexer' can be defined as: 
   
                          (LexerState s) |-> lexer_state_v <- s
      
   Now, asuming that we are reading the input from a string (say 'text'), the lexing 
   stream can be created as follows: 
   
      with    lexer_state_v = var((LexerState)off),      // 'off' is the 'initial' lexer
              lexing_stream = make_lexing_stream("\n",
                                                 text,
                                                 (LexerState s) |-> lexer_state_v <- s), 
                                                 
   Of course, this is not enough because the lexer you really want is a 'global' lexer 
   performing both 'off' and 'in' reading. You can define it as follows (just after the 
   above). Here we assume that the two lexers 'off_lexer' and 'in_lexer' have
   already been constructed by 'make_lexer'. 
   
             // plug the two lexers on the same lexing stream:
               with  pluged_off = off_lexer(lexing_stream), 
                      pluged_in = in_lexer(lexing_stream),
               
             // construct the global lexer
               global_lexer = (One _) |-> if *lexer_state_v is  
                                            {
                                              // call the right one depending on the 'state'
                                              off   then pluged_off(unique),
                                              in    then pluged_in(unique)
                                            }, 
                                            
             // at this point you can proceed with 'global_lexer'
             // for example give it (after some result type conversion) 
             // as an argument to an APG parser. 
                      
             Enjoy !
                


      
               
   --- That's all for the public part ! --------------------------------------------------   
   
   
   
   
   
   -------------------------------- Table of Contents ------------------------------------
   
   *** [1] Parsing regular expressions. 
      *** [1.1] Regular expressions. 
      *** [1.2] Basic regular expressions. 
      *** [1.3] 'Extended' characters. 
      *** [1.4] Getting the next (extended) character from the regular expression. 
      *** [1.5] Tools. 
         *** [1.5.1] Creating a range of consecutive characters.
         *** [1.5.2] Computing the complement of a set of characters. 
         *** [1.5.3] Concatenating a list of regular expression (in reverse order).  
         *** [1.5.4] Reading a 'choice' of characters. 
         *** [1.5.5] Reading a complemented 'choice' of characters. 
         *** [1.5.6] Reading a 'choice' (general case). 
      *** [1.6] Reading a regular expression. 
         *** [1.6.1] Right delimiters. 
         *** [1.6.2] Recursive reading. 
         *** [1.6.3] The tool for parsing regular expressions. 
      *** [1.7] Transforming a regular expression into a basic one.    
         *** [1.7.1] Expanding a 'choice' of characters. 
         *** [1.7.2] The tool for converting to basic.
      *** [1.8] Formating error messages into English.
      *** [1.1] The type 'LexingStream'. 
      *** [1.2] How a lexing stream is used. 
      *** [2.2] Constructing lexing streams. 
         *** [2.2.1] From a byte array. 
         *** [2.2.2] From a string. 
         *** [2.2.3] From a read only stream. 
         *** [2.2.4] From a read/write stream. 
         *** [2.2.5] From an SSL connection. 
   *** [2] Using lexing streams.
      *** [2.3] Counting lines and columns. 
      *** [2.3] Reading the next token. 
   *** [3] Constructing the automaton. 
      *** [3.1] Pre-labels. 
      *** [3.2] Decorating basic regular expressions. 
      *** [3.3] Computing the follow table. 
      *** [3.5] Renaming the states of the DFA.
      *** [3.5] Making the DFA.
      *** [3.6] Translating a DFA into a fast lexer description. 
   *** [4] Constructing the lexer. 
      *** [4.1] Plugging a lexer to a lexing stream. 
   *** [5] Graphviz formatting.
      *** [5.1] Formatting tools.
      *** [5.2] Transition grouping.
      *** [5.3] State dumping.
      *** [5.4] DFA to graphviz.
      
   ---------------------------------------------------------------------------------------
   
   

read system/convert.anubis
   
   

   *** [1] Parsing regular expressions. 
   
   
      *** [1.1] Regular expressions. 
   
   Regular expressions are formalized as follows.
   
public type RegExpr:
   char(Word8),                 // a
   choice(List(Word8)),         // [abc]
   plus(RegExpr),               // a+
   star(RegExpr),               // a*
   cat(RegExpr,RegExpr),        // ab
   or(RegExpr,RegExpr),         // (a|b)
   dot,                         // . 
   question_mark(RegExpr).      // a? 

   
   
      *** [1.2] Basic regular expressions. 
   
   Basic regular expressions are enough for representing all regular expressions. In other
   words any regular expression is equivalent to a basic regular expression. Furthermore,
   at some point of the construction of lexers we have to handle 'actions'. We introduce
   them here even if we generate them only later.
   
type LexerRankAction($Token,$Aux):
   ignore,   
   return(Int rk, (ByteArray,LexingTools,$Aux) -> LexerOutput($Token)), 
   return(Int rk, ((Int,Int) -> ByteArray,Int,LexingTools,$Aux) -> LexerOutput($Token)).
   
   
public type BasicRegExpr($Token,$Aux):
   char(Word8), 
   star(BasicRegExpr($Token,$Aux)),
   or(BasicRegExpr($Token,$Aux),BasicRegExpr($Token,$Aux)),
   cat(BasicRegExpr($Token,$Aux),BasicRegExpr($Token,$Aux)),
   epsilon,                           // matches the empty sequence of characters
   action(LexerRankAction($Token,$Aux)). 
   
   The role of 'epsilon', which matches only the empty lexeme, is to provide a
   representation for the empty choice '[]', and for regular expressions of the form 'A?',
   which are translated into 'or(A,epsilon)'.
   

   
      *** [1.3] 'Extended' characters. 

   'Extended' characters (used in regular expressions) are defined (and classified) as
   follows.
   
type ExChar:
   left_par,               // (
   right_par,              // )
   left_bracket,           // [
   right_bracket,          // ]
   star,                   // *
   plus,                   // +
   or,                     // |
   dot,                    // .
   caret,                  // ^
   hyphen,                 // -
   question_mark,          // ?
   char(Word8).            // a, b, c, ...

   
   
   
      *** [1.4] Getting the next (extended) character from the regular expression. 
  
   The next function  reads an extended character from the  regular expression. It returns
   'failure' as it encounters the end of the string.
   
define Maybe(ExChar)  
  next_exchar
    (
      Stream        s,
      Word8         escape_char,
    ) =
  if read_byte(s) is 
    {
      failure then failure,  
      success(c) then 
        if c = escape_char
        then if read_byte(s) is
               {
                 failure then failure, 
                 success(d) then 
                 if d = 'n' then success(char('\n')) else
                 if d = 'r' then success(char('\r')) else
                 if d = 't' then success(char('\t')) else
                 success(char(d))
               }
        else if c = '(' then success(left_par)
        else if c = ')' then success(right_par)
        else if c = '[' then success(left_bracket)
        else if c = ']' then success(right_bracket)
        else if c = '|' then success(or)
        else if c = '*' then success(star)
        else if c = '+' then success(plus)
        else if c = '.' then success(dot)
        else if c = '^' then success(caret)
        else if c = '-' then success(hyphen)
        else if c = '?' then success(question_mark)
        else success(char(c))
    }. 

   
   
   
   
   
      *** [1.5] Tools. 
   
         *** [1.5.1] Creating a range of consecutive characters.
   
   Given a first character and a last character, create the list of all characters between
   these two (included).

   Beware ! The following is buggy because if z =  255, we never have z +< a and we get an
   infinite loop.
   
 define List(Word8)
  range
    (
      Word8 a, 
      Word8 z
    ) =
  if z +< a then [ ] else [a . range(a+1,z)]. 


   Here is the good version:
   
define List(Word8)
  range
    (
      Word8 a, 
      Word8 z
    ) =
  if z +< a then [ ] else 
  if a = 255 then [255]     /* here we have a = 255 and z >=+ a, hence also z = 255 */
  else [a . range(a+1,z)]. 

   

   
   
         *** [1.5.2] Computing the complement of a set of characters. 
   
   Compute the  'complement' of a  choice, i.e.  the list of  all characters which  do not
   belong to the given choice. 
   
define List(Word8)
  complement_choice
    (
      List(Word8)  l,           /* the given choice of characters */
      List(Word8)  result,      /* a 'local variable' */
      Word32       n            /* another 'local variable' */
    ) = 
  if n = -1 then result else
  with c = truncate_to_Word8(n), 
  if member(l,c)
  then complement_choice(l,result,n-1)
  else complement_choice(l,[c . result],n-1). 
   
   
   
   
   
         *** [1.5.3] Concatenating a list of regular expressions (in reverse order).  
   
   Concatenate a (non empty) list of RegExpr in reverse order:

define RegExpr
  cat_list
    (
      RegExpr last,
      List(RegExpr) others
    ) =
  if others is
    {
      [ ] then last, 
      [h . t] then cat(cat_list(h,t),last)
    }.


   
   
         *** [1.5.4] Reading a 'choice' of characters. 
   
   Reading a 'choice', i.e. the characters within square brackets. 
   
define Result(RegExprError,List(Word8))
  read_choice
    (
      Stream        s,
      Word8         escape_char, 
      List(Word8)   already_read
    ) = 
   if next_exchar(s,escape_char) is 
     {
       failure then error(premature_end_of_regexpr), 
       success(x) then 
         if x is right_bracket then ok(already_read) else
         if x is char(c) then read_choice(s,escape_char,[c . already_read]) else
         if x is hyphen then 
           if already_read is 
             {
               [ ] then error(misplaced_hyphen),
               [a . others] then 
                 if next_exchar(s,escape_char) is 
                   {
                     failure then error(premature_end_of_regexpr),
                     success(y) then 
                       if y is char(z) 
                       then read_choice(s,escape_char,append(range(a,z),others)) 
                       else error(non_character_within_brackets)
                   }
             }
         else error(non_character_within_brackets)
     }. 


   
   
   
         *** [1.5.5] Reading a complemented 'choice' of characters. 
   
   The same one but giving the complement of the 'choice'. 
   
define Result(RegExprError,List(Word8))
  read_counter_choice
    (
      Stream        s,
      Word8         escape_char,
      List(Word8)   already_read
    ) =
  if read_choice(s,escape_char,already_read) is
    {
      error(msg) then error(msg),
      ok(l) then ok(complement_choice(l,[],255))
    }. 

   
   
   
         *** [1.5.6] Reading a 'choice' (general case). 
   
   The following function is  called when a left bracket has been  read. It reads extended
   characters until the right bracket is found.

define Result(RegExprError,List(Word8))
  read_within_brackets
    (
      Stream        s,
      Word8         escape_char
    ) =
  if next_exchar(s,escape_char) is 
    {
      failure then error(premature_end_of_regexpr),
      success(x) then 
        if x = caret 
        then read_counter_choice(s,escape_char,[])
        else if x is char(c) then read_choice(s,escape_char,[c]) 
                             else error(non_character_within_brackets)
    }. 


   
   
   
   
      *** [1.6] Reading a regular expression. 
  
         *** [1.6.1] Right delimiters. 
   
type RightDelimiter:
   right_par,
   end_of_regexpr. 
   
   
   
   
         *** [1.6.2] Recursive reading. 
   
define Result(RegExprError,RegExpr)
  read_regexpr
    (
      Stream          s,
      Word8           escape_char,
      List(RegExpr)   already_read,
      RightDelimiter  delim
    ) =  
  if next_exchar(s,escape_char) is 
    {
      failure then 
        if delim is
          {
            right_par then 
              error(premature_end_of_regexpr), 

            end_of_regexpr then 
       if already_read is 
                {
                  [ ] then error(regexpr_is_empty),
                  [last . others] then 
                     ok(cat_list(last,others)) 
                }
          },
   
      success(ec) then 
        if ec is 
          {
            left_par then 
              if read_regexpr(s,escape_char,[],right_par) is
                {
                  error(msg) then 
                    error(msg), 

                  ok(r1) then 
                    read_regexpr(s,escape_char,[r1 . already_read],delim)  
                },

            right_par then 
              if delim is
                {
                  right_par then 
                    if already_read is
                      {
                        [ ] then 
                          error(unexpected_right_par), 
      
                        [last . others] then 
                          ok(cat_list(last,others))
                      },

                  end_of_regexpr then 
                    error(unexpected_right_par)
                },
 
            left_bracket then 
              if read_within_brackets(s,escape_char) is 
                {
                  error(msg) then error(msg), 
 
                  ok(r1) then if already_read is 
                    {
                      [ ] then 
                        read_regexpr(s,escape_char,[choice(r1)],delim),

                      [last . others] then 
                        read_regexpr(s,escape_char,[choice(r1),last . others],delim)
                    }           
                },

            right_bracket then 
              error(unexpected_right_bracket), 

            star then 
              if already_read is
                {
                  [ ] then
                    error(star_not_following_a_regexpr), 

                  [last . others] then 
                    read_regexpr(s,escape_char,[star(last) . others],delim)
                },

            plus then 
              if already_read is
                {
                  [ ] then
                    error(plus_not_following_a_regexpr), 

                  [last . others] then 
                    read_regexpr(s,escape_char,[plus(last) . others],delim)
                },

            or then 
              if read_regexpr(s,escape_char,[],delim) is
                {
                  error(msg) then error(msg), 

                  ok(r1) then 
                    if already_read is
                      { 
                        [ ]      then error(misplaced_vbar),
                        [h . t]  then 
                          ok(or(cat_list(h,t),r1))
                      }
                },
   
            dot then 
              read_regexpr(s,escape_char,[dot . already_read], delim),

            caret then 
              error(misplaced_caret), 
   
            hyphen then 
              error(misplaced_hyphen),

            question_mark then 
              if already_read is
                {
                  [ ] then
                    error(question_mark_not_following_a_regexpr), 
      
                  [last . others] then 
                    read_regexpr(s,escape_char,[question_mark(last) . others],delim)
                },

            char(c) then 
             read_regexpr(s,escape_char,[char(c) . already_read], delim)
          }
    }.

   

   
    Debugging tools:
define String
   format
   (
     List(Word8)  l
   ) =
   concat(map((Word8 c) |-> to_decimal(c) ,l)," ").
   
define String
   format
   (
     RegExpr e
   ) =
   if e is 
   {
     char(Word8 _0)              then "char("+constant_string(1,_0)+")",
     choice(List(Word8) _0)      then "choice("+format(_0)+")",
     plus(RegExpr _0)            then "plus("+format(_0)+")",
     star(RegExpr _0)            then "star("+format(_0)+")",
     cat(RegExpr _0,RegExpr _1)  then "cat("+format(_0)+","+format(_1)+")",
     or(RegExpr _0,RegExpr _1)   then "or("+format(_0)+","+format(_1)+")",
     dot                         then "dot",
     question_mark(RegExpr _0)   then "question_mark("+format(_0)+")"
   }. 
         
         
         *** [1.6.3] The tool for parsing regular expressions. 
         
      
public define Result(RegExprError,RegExpr)
  parse_regular_expression
    (
      Stream          s,
      Word8           escape_char
    ) =  
   if read_regexpr(s,escape_char,[],end_of_regexpr) is 
     {
       error(msg)  then error(msg), 
       ok(re)      then //print("["+format(re)+"]\n"); 
                        ok(re)
     }.
   
   
   
      *** [1.7] Transforming a regular expression into a basic one.    
      
         *** [1.7.1] Expanding a 'choice' of characters. 
   
   Given list of characters (a  'choice sequence'), compute the correponding basic regular
   expression.
   
define BasicRegExpr($Token,$Aux)
  expand_choice
    (
      List(Word8) l
    ) = 
  if l is 
    {
      [ ] then epsilon,
      [h . t] then 
        if t is [ ] then char(h) else
        or(char(h),expand_choice(t))
    }.

   
   
         *** [1.7.2] The tool for converting to basic.

   Convert a regular expression to a basic one.

public define BasicRegExpr($Token,$Aux) to_basic(
    RegExpr r
  ) =
  if r is
  {
    char(c)                then char(c),
    choice(l)              then expand_choice(l),
    plus(r1)               then with br = to_basic(r1), cat(br,star(br)),
    star(r1)               then star(to_basic(r1)),
    cat(r1,r2)             then cat(to_basic(r1),to_basic(r2)),
    or(r1,r2)              then or(to_basic(r1),to_basic(r2)),
    dot                    then expand_choice(append(range(0,'\n'-1), range('\n'+1,255))),
    question_mark(r1)      then or(epsilon,to_basic(r1))
  }.

   Convert a byte array to a a basic regular expression.
public define BasicRegExpr($Token,$Aux) to_basic(
    ByteArray                 ba
  ) =
  with l = length(ba),
  if l = 0
  then should_not_happen(char(0))
  else with conv = (Int idx, BasicRegExpr($Token, $Aux) re) |-rec->
    if nth(idx, ba) is
    {
      failure     then re
      success(s)  then rec(idx-1, cat(char(s), re))
    },
  conv(l-1, char(force_nth(l-1, ba)))
  .

      *** [1.8] Formating error messages into English.

public define String
   to_English
     (
       RegExprError  e
     ) =
  if e is
    {
      premature_end_of_regexpr              then "Premature end of regular expression.",
      unexpected_right_par                  then "Unexpected right parenthese.",
      unexpected_right_bracket              then "Unexpected right bracket.",
      regexpr_is_empty                      then "Regular expression is empty.",
      star_not_following_a_regexpr          then "Found '*' not following any regular expression.",
      plus_not_following_a_regexpr          then "Found '+' not following any regular expression.",
      question_mark_not_following_a_regexpr then "Found '?' not following any regular expression.",
      non_character_within_brackets         then "Non character within brackets.",
      misplaced_hyphen                      then "Misplaced '-'.",
      misplaced_dollar                      then "Misplaced '$'.",
      misplaced_caret                       then "Misplaced '^'.",
      misplaced_vbar                        then "Misplaced '|'.",
      empty_lexer_description               then "Empty lexer description."
    }. 
   
      
      
   
   
   
       


      *** [1.1] The type 'LexingStream'. 
      
   A lexing stream provides tools which are adhoc for using low level fast lexers as
   defined in section 13 of predefined.anubis.
      
   The type below records the information needed to come back to the state just after the 
   last or penultimate token was read. 
   
type TokenState:
  tstate 
    (
      Int         current,
      Int         line,
      Int         col
    ).      
   
   There is a ``penultimate token'' when at least two token has been successfully read since the 
   creation of the lexing stream. If it is not the case, the value of the ``penultimate state''
   defaults to the state after the very first token was read or to the very initial state if no
   tokan was read.
   
   When the buffer is reloaded, part of the current buffer is kept. One reason for this is that
   when we encounter the end of the buffer it can be the case that we are currently reading a token
   which can continue after the reloading. Hence, we must keep the end of the previous buffer. 
   Another reason is that we must always be able to come back to the state after the reading
   of the penultimate token. This second condition entails the first one because the end of the 
   penultimate token (or very beginning of stream) is always before the starting position of
   the token we are currently reading. 
   
   We must keep the above information twice. Indeed, consider the case of three successive tokens
   in the source text: 
    
        token1 token2 token3
   
   If we are currently reading token3 (after token1 and token2 have been successfully read), 
   the position after the penultimate token is the end of token1 (because token2 is the last 
   successfully read token). At the moment token3 is successfully read, we can forget
   about token1, and token2 becomes the penultimate token. For this reason, we must keep
   state informations for token1 and token2, the last two tokens successfully read.
   
   
public type LexingStream:
   lexing_stream
     (
       Var(ByteArray)               buffer_v,         // the current buffer
       Var(Int)                     token_start_v,    // start of token being currently read
       Var(Int)                     current_v,        // current position of reading in buffer
       Var(FastLexerLastAccepted)   last_accept_v,    // last accepting position (if any)
       Var(TokenState)              last_tok_v,       // state after the last successful reading of a token 
       Var(TokenState)              penult_tok_v,     // state after the penultimate successful reading of a token
       One -> Maybe(One)            reload_buffer,    // command for loading the sequel in the buffer
       Var(Int)                     line_v,           // line counter
       Var(Int)                     column_v,         // column counter
       Var(Int)                     past_bytes_v,     // number of bytes of past input which are no more in buffer
       LexingTools                  tools
     ).

   The variable 'past_bytes_v' contains the number of bytes which have been read by the lexing stream
   since the very beginning (the creation of the lexing stream), and which are no more present in
   the buffer because of reloading operations. 
     
   The function below can be used for debugging purpose:
   
public define One
   show
   (
     LexingStream  ls
   ) =
   if ls is lexing_stream(buffer_v,
                          token_start_v,
                          current_v,
                          last_accept_v,
                          last_tok_v,
                          penult_tok_v,
                          reload_buffer,
                          line_v,
                          column_v,
                          past_bytes_v,
                          tools)  then 
     print("Lexing stream:\n"); 
     print("  buffer at token_start = \""+to_string(extract(*buffer_v,*token_start_v,(*token_start_v)+80))+" ...\"\n");
     print("  token_start = "+*token_start_v+"\n"); 
     print("  current - token_start = "+(*current_v-*token_start_v)+"\n"); 
     print("  past_bytes  = "+*past_bytes_v+"\n").  
     
     A variant:
     
define One
   show
   (
     Var(ByteArray)           buffer_v, 
     Var(Int)                 token_start_v, 
     Var(Int)                 current_v
   ) = 
     print("Lexing stream:\n"); 
     print("  buffer at token_start = \""+to_string(extract(*buffer_v,*token_start_v,(*token_start_v)+80))+" ...\"\n");
     print("  token_start = "+*token_start_v+"\n"); 
     print("  current - token_start = "+(*current_v-*token_start_v)+"\n"). 
     
      
      *** [1.2] How a lexing stream is used. 
   
   Since the source text is read by chunks (except if the source is a byte array or a
   string), a token may begin near the end of a chunk and continue into the next chunk. For
   example the source text can be:
   
                                "This is the source text."
   
   and the first chunk can be:
   
                                "This is the sou"
   
   In this case, the token 'source' will be read in two steps (or more steps in the case
   of a very long token). Here we assume that we read symbols (regular expression:
   "[A-Za-z]+") and ignore anything else. After the first 3 symbols 'This', 'is' and 'the'
   are read, we are on the point to read the symbol 'source'. The low level fast
   lexer is called with the following parameters:

                                            current_v  (*current_v = 11)
                                            |
                                            v
                                "This is the sou"   
                                 ^           ^
                                 |           |
                     offsets:    0           12
   
       - The current reading position is on the white space just before 'sou' (this is 11
         in this example, the position of the first byte after the token 'the').
       - The current state is state 0, because we want to read a new token.
   
   The low level lexer ignores the white space and reads 'sou'. It returns:
   
                                 accepted(s,at_end_of_input,12,15)
   
   which means that it has recognized the symbol 'sou' between positions 12 (included) and
   15 (not included), that it has reached the end of the buffer, and that the lexer is
   currently in state 's'.
   
   At that point, we need to reload the buffer, but we must keep the end of the current
   buffer. We proceed as follows. 
   
       - We compute the number of byte that we will not keep. This will be the value of
         'dropped'. This is the new starting position returned by the low level lexer. In
         the case of the example, dropped = 12.
   
       - We extract from the buffer what we want to keep, i.e. the tail of the buffer
         starting at 'dropped'. In the case of the example, we keep "sou". 
   
       - We read a new chunk, say "rce text." and concatenate it with what we have
         kept. This makes the new buffer. In the case of the example, this is:
   
                                       "source text."
   
       - We continue reading the token 'source'. To that end, we call the low level lexer
         with the following parameters:
   
           -- the new current buffer "source text."
   
           -- last accepted: (s,3), because 'sou' has been accepted in state 's' and
              ends at offset 3 within the new buffer,

           -- current_v receives the value 3, because 'sou' is already read, 
           
           -- token_start_v receives the value 0, because the token we are currently 
              reading begins at offset 0. 
   
           -- restart in state s, because we want to try to read the sequel of 'sou'. 
   
   Notice that if the low level lexer had returned 'rejected(s,at_end_of_input,12,15)'
   instead of 'accepted(s,at_end_of_input,12,15)', the scenario is the same one except
   that last accepted will be 'none'.
   
   The low level lexer will now return 'accepted(s,not_at_end_of_input,0,6)', meaning that
   it has recognized the token 'source' between positions 0 (included) and 6 (not
   included) within the new buffer. In that case, we extract the token from the buffer and
   return it. The new starting and current positions are 6, i.e. *token_start_v = *current_v =
   6.
   
   
   
      *** [2.2] Constructing lexing streams. 
      
   Making the lexing tools from variables. 
      
define LexingTools
  make_tools
  (
    Var(Int)                     token_start_v,    // actually not used in this function
    Var(Int)                     current_v, 
    Var(Int)                     line_v,
    Var(Int)                     col_v,
    Var(Int)                     past_v,
    Var(TokenState)              last_tok_v,
    Var(TokenState)              penult_tok_v,
    Var(FastLexerLastAccepted)   last_accept_v
  ) =      
  tools(
    // get current line:
    (One _) |-> *line_v,
    
    // get current column:
    (One _) |-> *col_v,
    
    // get current offset:
    // This is the number of bytes which are no more in the buffer plus the current position.
    (One _) |-> *past_v + *current_v,
    
    // go back one char:
    // don't go beyond the beginning of the buffer
    (Int n) |-> current_v <- max(*current_v - n, 0),
    
    // comming back to the state just after the last token was read
    (One _) |-> if *last_tok_v is tstate(cur,l,c) then  
                current_v <- cur; 
                line_v <- l; 
                col_v <- c;
                last_accept_v <- none, 
    
    // comming back to the state just after the penultimate token was read
    (One _) |-> if *penult_tok_v is tstate(cur,l,c) then 
                current_v <- cur; 
                line_v <- l; 
                col_v <- c;
                last_tok_v <- *penult_tok_v; 
                last_accept_v <- none
       ). 

   
         *** [2.2.1] From a byte array. 
   
public define LexingStream
   make_lexing_stream
     (
       String      preambule, 
       ByteArray   b
     ) = 
   with    b1_v = var(if length(preambule) = 0 then b else to_byte_array(preambule)+b),
  token_start_v = var((Int)0),  
      current_v = var((Int)0), 
         line_v = var((Int)0), 
          col_v = var((Int)0), 
         past_v = var((Int)0), 
     last_tok_v = var(tstate(0,0,0)), 
   penult_tok_v = var(tstate(0,0,0)), 
  last_accept_v = var((FastLexerLastAccepted)none), 
   lexing_stream(b1_v,                       // buffer
                 token_start_v,              // starting position
                 current_v,                  // current position
                 last_accept_v,              // last accepting position
                 last_tok_v,                 // last token state
                 penult_tok_v,               // penultimate token state
                 (One u) |-> failure,        // buffer is never reloaded
                 line_v,                     // current line
                 col_v,                      // current column
                 past_v,                     // past bytes (will remain always 0 in this case)
                 make_tools(token_start_v,current_v,line_v,col_v,past_v,last_tok_v,penult_tok_v,last_accept_v)). 
   

   
         *** [2.2.2] From a string. 
   
public define LexingStream
   make_lexing_stream
     (
       String preambule, 
       String s
     ) =
   make_lexing_stream(preambule,to_byte_array(s)).
   
   
   
   
         *** [2.2.3] From a read only stream. 
      
public define Maybe(LexingStream)
   make_lexing_stream
     (
       String   preambule, 
       RStream  stream,
       Int      buffer_size,
       Int      timeout
     ) = 
   if buffer_size < 1 then failure else
   if read(stream,buffer_size,timeout) is 
     {
       error        then failure, 
       timeout      then failure, 
       ok(buffer)   then 
       //print("First buffer: ["+to_string(buffer)+"]\n");
         with   buffer_v         = var(if length(preambule) = 0 then buffer else to_byte_array(preambule)+buffer), 
                token_start_v    = var((Int)0), 
                current_v        = var((Int)0), 
                last_accepted_v  = var((FastLexerLastAccepted)none),
                last_tok_v       = var(tstate(0,0,0)), 
                penult_tok_v     = var(tstate(0,0,0)), 
                line_v           = var((Int)0),
                col_v            = var((Int)0),
                past_bytes_v     = var((Int)0), 
                reload_buffer    = (One _) |-> 
                  if read(stream,buffer_size,timeout) is 
                    {
                      error      then failure, 
                      timeout    then failure, 
                      ok(more)   then 
                        if length(more) = 0   
                        then failure
                        else show(buffer_v,token_start_v,current_v);
                             (with old_buffer = *buffer_v, 
                                   old_length = length(old_buffer), 
                                   dropped    = // number of bytes dropped from old buffer
                                     min(min(current(*penult_tok_v),current(*last_tok_v)),*token_start_v), 
         //print("Keeping this from previous buffer: ["+to_string(extract(old_buffer,dropped,old_length))+"]\n");
                              buffer_v <- extract(old_buffer,dropped,old_length)+more; 
         //print("New buffer: ["+to_string(*buffer_v)+"] size: "+to_decimal(length(*buffer_v))+"\n");
                              token_start_v <- *token_start_v - dropped; 
         //print("Next token starting position: "+to_decimal(*token_start_v)+"\n");
                              // if old_length /= *current_v then alert else
                              current_v <- *current_v - dropped; 
         //print("New current reading position: "+to_decimal(*current_v)+"\n");
                              past_bytes_v <- *past_bytes_v + dropped; 
                              last_tok_v <- (if *last_tok_v is tstate(cur,l,c) then tstate(cur - dropped,l,c));
                              penult_tok_v <- (if *penult_tok_v is tstate(cur,l,c) then tstate(cur - dropped,l,c));
                              last_accepted_v <-
                                if *last_accepted_v is 
                                  {
                                    none       then none, 
                                    last(s,a)  then last(s,a - dropped)
                                  };
                              /* values of 'line_v' and 'col_v' do not change */
                              show(buffer_v,token_start_v,current_v);
                              success(unique))
                    }, 
         success(lexing_stream(buffer_v,
                               token_start_v,
                               current_v,
                               last_accepted_v,
                               last_tok_v, 
                               penult_tok_v, 
                               reload_buffer,
                               line_v,
                               col_v,
                               past_bytes_v, 
                               make_tools(token_start_v,current_v,line_v,col_v,past_bytes_v,last_tok_v,penult_tok_v,last_accepted_v)))
     }.
   
   
   
   
         *** [2.2.4] From a read/write stream. 
   
public define Maybe(LexingStream)
   make_lexing_stream
     (
       String    preambule, 
       RWStream  stream,
       Int       buffer_size,
       Int       timeout
     ) = 
   make_lexing_stream(preambule,weaken(stream),buffer_size,timeout). 
   
   
   
   
         *** [2.2.5] From an SSL connection. 
   

public define Maybe(LexingStream)
   make_lexing_stream
     (
       String           preambule, 
       SSL_Connection   stream,
       Int              buffer_size,
       Int              timeout
     ) = 
   if buffer_size < 1 then failure else
   if (Maybe(ByteArray))read(stream,buffer_size,timeout) is 
     {
       failure           then failure, 
       success(buffer)   then 
         with   buffer_v         = var(if length(preambule) = 0 then buffer else to_byte_array(preambule)+buffer), 
                token_start_v    = var((Int)0), 
                current_v        = var((Int)0), 
                last_accepted_v  = var((FastLexerLastAccepted)none),
                last_tok_v       = var(tstate(0,0,0)),
                penult_tok_v     = var(tstate(0,0,0)),
                line_v           = var((Int)0),
                col_v            = var((Int)0),
                past_bytes_v     = var((Int)0), 
                reload_buffer    = (One _) |-> 
                  if (Maybe(ByteArray))read(stream,buffer_size,timeout) is 
                    {
                      failure        then failure, 
                      success(more)  then 
                        if length(more) = 0   
                        then failure
                        else (with old_buffer = *buffer_v, 
                                   old_length = length(old_buffer), 
                                   dropped    = // number of bytes dropped from old buffer
                                     min(min(current(*penult_tok_v),current(*last_tok_v)),*token_start_v), 
                                   
                              buffer_v <- extract(old_buffer,dropped,old_length)+more; 
                              token_start_v <- *token_start_v - dropped; 
                              current_v <- old_length - dropped; 
                              past_bytes_v <- *past_bytes_v + dropped; 
                              last_tok_v <- (if *last_tok_v is tstate(cur,l,c) then tstate(cur - dropped,l,c));
                              penult_tok_v <- (if *penult_tok_v is tstate(cur,l,c) then tstate(cur - dropped,l,c));
                              last_accepted_v <-
                                if *last_accepted_v is 
                                  {
                                    none       then none, 
                                    last(s,a)  then last(s,a - dropped)
                                  };
                              /* values of 'line_v' and 'col_v' do not change */
                              success(unique))
                    }, 
         success(lexing_stream(buffer_v,
                               token_start_v,
                               current_v,
                               last_accepted_v,
                               last_tok_v,
                               penult_tok_v,
                               reload_buffer,
                               line_v,
                               col_v,
                               past_bytes_v, 
                               make_tools(token_start_v,current_v,line_v,col_v,past_bytes_v,last_tok_v,penult_tok_v,last_accepted_v)))
     }.
   
   
public define Int
  offset
  (
    LexingStream  ls
  ) =
  *past_bytes_v(ls) + *current_v(ls). 
  
   
   
   *** [2] Using lexing streams.
   
   
      *** [2.3] Counting lines and columns. 
   
   The line and column counters should always indicate the line and column of the first
   byte in the next token to be read. In other words, they are updated each time 'token_start_v'
   is updated. The updating of these 3 variables is performed by a single function. But we
   first need an auxiliary function:
   
define (Int, Int, Int)              // returns new (start,line,col)
   compute_start_line_col
     (
       ByteArray     buffer, 
       Int           old_start,     // current value of token_start_v
       Int           new_start,     // new value of token_start_v
       Int           line,          // current line
       Int           col            // current column
     ) =
   //print("old_start = "+old_start+"\n"); 
   if old_start >= new_start then //print("======== new col: "+col+"\n");
           (new_start,line,col) else
   with c = force_nth(old_start,buffer), 
   if ((c >> 6) = 2)   
     /*
         Required for reading UTF-8 strings ('col' is not incremented). 
         In an UFT-8 sequence the first byte has one of the forms 0xxxxxxx or 11xxxxxx. 
         All subsequent bytes have the form 10xxxxxx. Since we count only the first one, 
         we don't count bytes 'c' such that (c >> 6) = 2, but we count all other bytes.  
     */
   then compute_start_line_col(buffer,old_start+1,new_start,line,col)
   else if c = '\n'
        then compute_start_line_col(buffer,old_start+1,new_start,line+1,0)
        else compute_start_line_col(buffer,old_start+1,new_start,line,col+1). 
   
define One
   update_start_line_col
     (
       ByteArray     buffer, 
       Int           new_start, 
       Var(Int)      token_start_v, 
       Var(Int)      line_v, 
       Var(Int)      col_v
     ) =
   //print("new_start = "+new_start+"\n"); 
   if compute_start_line_col(buffer,*token_start_v,new_start,*line_v,*col_v) is (s,l,c) then 
   token_start_v <- s; 
   line_v <- l; 
   col_v <- c. 
   
   
   
   
   
   
      *** [2.3] Reading the next token. 


   We are now ready to write the function reading the next token from a lexing stream using
   a given low level lexer.
   
public define LexerOutput($Token)
   read_next_token
     (
       (ByteArray,FastLexerLastAccepted,Int,Int,Word16) -> FastLexerOutput    low_level_lexer,
       LexingStream                                                           lstream,
       Word16                                                                 starting_state,
       MVar(LexerAction($Token,$Aux))                                         actions,
       $Aux                                                                   aux
     ) =
   if lstream is lexing_stream(buffer_v,token_start_v,current_v,last_accept_v,last_tok_v,penult_tok_v,reload_buffer,
                               line_v,col_v,offset_v,tools) then 
   //print("starting at offset "+to_decimal(*current_v)+" with token start at "+to_decimal(*token_start_v)+"\n"); 
   with lgbuf = length(*buffer_v), 
   if low_level_lexer(*buffer_v,*last_accept_v,*current_v,*token_start_v,starting_state) is 
     {
       rejected(s,start,end) then 
  //print("low level rejected start = "+to_decimal(start)+" end = "+to_decimal(end)+"\n");
         current_v <- end; 
         if end /= lgbuf then 
         (
             /* the lexeme just read must be rejected */
               update_start_line_col(*buffer_v,end,token_start_v,line_v,col_v); 
               last_accept_v <- none; 
               error(extract(*buffer_v,start,end),*line_v,*col_v)
         )
         else
         (
             /* the lexeme may still be accepted after the buffer is reloaded */
             //update_start_line_col(*buffer_v,start,token_start_v,line_v,col_v);
             //print("======== reload 1 (rejected)\n");
             if reload_buffer(unique) is 
               {
                 failure then 
                 /* the buffer cannot be reloaded: we are at the true end of the
                 input. There are still two cases: */
                     if start >= end
                     then end_of_input
                     else error(extract(*buffer_v,start,end),*line_v,*col_v),
   
                 success(_) then 
                 /* the buffer has been reloaded.  We call the low level lexer again in
                 order to read the sequel of the bytes recognized so far (terminal call)
                 */
                   read_next_token(low_level_lexer,lstream,s,actions,aux)
               }
         ),
   
       /* almost the same thing for accepted */
       accepted(s,start,end) then 
       //print("low level accepted start = "+to_decimal(start)+" end = "+to_decimal(end)+"\n");
         last_accept_v <- last(s,end); 
         current_v <- end; 
         // if lgbuf /= length(*buffer_v) then alert else
         if end /= lgbuf then  
         (
             /* the lexeme just read must be accepted: the action is applied */
                
               last_accept_v <- none; 
               if *actions(word32(s,0)) is 
                 {
                   ignore      then show(lstream);
                                    should_not_happen(end_of_input), 
                                    // because the low level lexer doesn't return in this case
                   return(f)  then 
                     // At this point a token is successfully read. 
                     // We must update some variables
                      penult_tok_v <- *last_tok_v; 
                      last_tok_v <- tstate(end,*line_v,*col_v); 
                      with result = f(extract(*buffer_v,start,end),tools,aux),
                        update_start_line_col(*buffer_v,*current_v,token_start_v,line_v,col_v);
                        result, 
                      
                   return(f)  then 
                      penult_tok_v <- *last_tok_v; 
                      last_tok_v <- tstate(end,*line_v,*col_v); 
                      with result = f((Int k, Int l) |-> extract(*buffer_v,start+k,start+l),
                                                 end-start,tools,aux),
                        //print("*token_start_v = "+*token_start_v+"\n"); 
                        //print("*current_v = "+*current_v+"\n");
                        update_start_line_col(*buffer_v,*current_v,token_start_v,line_v,col_v);
                        result
                 }
         )
         else 
         (               
             /* the lexeme may still be accepted after the buffer is reloaded */
             //print("======== reload 2 (accepted)\n");
             if reload_buffer(unique) is 
               {
                 failure then 
                 /* the buffer cannot be reloaded: we are at the true end of the
                 input. There are still two cases: */
                   last_accept_v <- none; 
                   if start >= end
                   then end_of_input
                   else if *actions(word32(s,0)) is 
                     {
                       ignore      then should_not_happen(end_of_input), 
                       return(f)   then penult_tok_v <- *last_tok_v; 
                                        last_tok_v <- tstate(end,*line_v,*col_v); 
                                        with result = f(extract(*buffer_v,start,end),tools,aux),
                                          update_start_line_col(*buffer_v,*current_v,token_start_v,line_v,col_v);
                                          result,
                       return(f)   then penult_tok_v <- *last_tok_v; 
                                        last_tok_v <- tstate(end,*line_v,*col_v); 
                                        with result = f((Int k, Int l) |-> extract(*buffer_v,start+k,start+l),
                                                        end-start,tools,aux),
                                          update_start_line_col(*buffer_v,*current_v,token_start_v,line_v,col_v);
                                          result
                     }, 
                   
                 success(_) then 
                 /* the buffer has been reloaded. We call the low level lexer again in
                 order to read the sequel of the bytes recognized so far (terminal call)
                 */
                   read_next_token(low_level_lexer,lstream,s,actions,aux)
               }
         ),

        ignored_to_end then 
    //print("low level ignored_to_end\n");
             /* we are at end of input buffer */
             //update_start_line_col(*buffer_v,lgbuf,token_start_v,line_v,col_v); 
             current_v <- lgbuf; 
             //print("======== reload 3 (ignored to end)\n"); 
             if reload_buffer(unique) is 
               {
                 failure then 
                 /* the buffer cannot be reloaded: we are at the true end of the
                 input. There are still two cases: */
                    end_of_input, 
     
                 success(_) then 
                 /* the buffer has been reloaded. We call the low level lexer again in
                 order to read the sequel of the bytes recognized so far (terminal call)
                 */
                   read_next_token(low_level_lexer,lstream,0,actions,aux)
               }
     }. 
   
   
      
   
   
   *** [3] Constructing the automaton. 
   
   The description of a lexer is given as a list of 'LexerItem($Token,$Aux)', where the
   parameter '$Token' represents the type of tokens.  Each lexer item is made of a regular
   expression and an action. If the action is 'ignore', the token just read is ignored and
   the lexer tries to read the next one.  Otherwise, the action is applied to the lexeme
   just read, and the result of the action is returned by the lexer.
   
   
   
      
      *** [3.1] Pre-labels. 
   
   These are the labels before the renaming of the DFA.
   
   'Actions' cannot be considered as matching anything in the input. However, in a given
   state, an action may be present among transitions, just meaning that in this state, if
   no transition may be followed, the action must be chosen instead.
   
public type DFA_pre_label($Token,$Aux):
   char(Word8),
   action(LexerRankAction($Token,$Aux)). 

   
   
   
      *** [3.2] Decorating basic regular expressions. 

   Given a basic regular expression, we associate a unique integer to each of its leaves
   (when seen as a tree). Such an integer is called a 'position'.

   Furthermore, we add three decorations to each Basic regular expression:

     - a flag 'nullable', which, when true, means that the regular expression may match
   the empty string,

     - a list of integers, representing all positions which may correspond to the first
   character of a matching string,

     - a list of integers, representing all positions which may correspond to the last
   character in a matching string.

   Actually, these two lists are lists of pairs (Word16,Label), where the label
   corresponds to the position.

type DecoratedBasicRegExpr($Token,$Aux):
  char        (Word8, 
               Word16 pos, 
               Bool nullable, 
               List((Word16,DFA_pre_label($Token,$Aux))) firstpos, 
               List((Word16,DFA_pre_label($Token,$Aux))) lastpos), 
   
  epsilon     (Bool nullable, 
               List((Word16,DFA_pre_label($Token,$Aux))) firstpos, 
               List((Word16,DFA_pre_label($Token,$Aux))) lastpos),
   
  or          (DecoratedBasicRegExpr($Token,$Aux),DecoratedBasicRegExpr($Token,$Aux), 
               Bool nullable, 
               List((Word16,DFA_pre_label($Token,$Aux))) firstpos, 
               List((Word16,DFA_pre_label($Token,$Aux))) lastpos),
   
  cat         (DecoratedBasicRegExpr($Token,$Aux),DecoratedBasicRegExpr($Token,$Aux), 
               Bool nullable, 
               List((Word16,DFA_pre_label($Token,$Aux))) firstpos, 
               List((Word16,DFA_pre_label($Token,$Aux))) lastpos),
   
  star        (DecoratedBasicRegExpr($Token,$Aux), 
               Bool nullable, 
               List((Word16,DFA_pre_label($Token,$Aux))) firstpos, 
               List((Word16,DFA_pre_label($Token,$Aux))) lastpos),
   
  action      (LexerRankAction($Token,$Aux),
               Word16 pos, 
               Bool nullable, 
               List((Word16,DFA_pre_label($Token,$Aux))) firstpos, 
               List((Word16,DFA_pre_label($Token,$Aux))) lastpos). 


   
   The following function adds positions and decorations to a regular expression. Since we
   have to generate position names, we give the first position to be used, and the
   function returns the regular expression (with positions and decorations) and the next
   position free for further use. The computation is simply recursive (there is no 'graph
   walk' to do, only a 'tree walk').


define (DecoratedBasicRegExpr($Token,$Aux),Word16)
  decorate
    (
      BasicRegExpr($Token,$Aux) r, 
      Word16 n
    ) =
  if r is
    {
      char(c) then 
        (char(c,n,false,[(n,char(c))],[(n,char(c))]), n+1), 

      star(r1) then 
        if decorate(r1,n) is (rp1,m) then 
          (star(rp1,
                true,
                firstpos(rp1),
                lastpos(rp1)),m),

      or(r1,r2) then 
        if decorate(r1,n) is (rp1,m) then 
        if decorate(r2,m) is (rp2,l) then 
          (or(rp1,rp2,
              if nullable(rp1) then true else nullable(rp2),
              append(firstpos(rp1),firstpos(rp2)),
              append(lastpos(rp1),lastpos(rp2))),l), 

      cat(r1,r2) then 
        if decorate(r1,n) is (rp1,m) then 
        if decorate(r2,m) is (rp2,l) then 
          (cat(rp1,rp2,
               if nullable(rp1) then nullable(rp2) else false,
               if nullable(rp1) then append(firstpos(rp1),firstpos(rp2)) else firstpos(rp1),
               if nullable(rp2) then append(lastpos(rp1),lastpos(rp2)) else lastpos(rp2)),l), 
   
      epsilon then 
        (epsilon(true,[],[]),n), 

      action(a) then 
        (action(a,n,false,[(n,action(a))],[(n,action(a))]),n+1)
    }. 
   
  
   Notice that the 'firstpos' and 'lastpos' fields in decorated regular expressions are
   always increasingly ordered lists of distinct integers (when ignoring labels), as may
   be easily verified by induction from the previous definition. Hint: when we write

       if decorate(r1,n) is (rp1,m)

   any position i in rp1 is such that n =< i < m.


   
   
 
      *** [3.3] Computing the follow table. 


   A 'follow table' tells us which positions can follow a given position (when scanning a
   string). It also gives the label attached to a position.  Its type is:

type FollowTable($Token,$Aux):
   empty, 
   follow_table(Word16,                                   // position 
                DFA_pre_label($Token,$Aux),               // label
                List(Word16),                             // following positions
                FollowTable($Token,$Aux) next). 
  

   Our lists of Word16s will have to remain increasingly sorted (for the purpose of
   comparison).

   The following function merges two lists sorted in increasing order, so that the result
   is still increasingly sorted.

define List(Word16)
  merge_sorted
    (
      List(Word16) l1,
      List(Word16) l2
    ) =
  if l1 is 
    {
      [ ] then l2, 
      [h1 . t1] then 
        if l2 is
          {
            [ ] then l1,
            [h2 . t2] then 
              if h1 = h2 // avoid duplications
              then [h1 . merge_sorted(t1,t2)]
              else if h1 -< h2
                   then [h1 . merge_sorted(t1,l2)]
                   else [h2 . merge_sorted(l1,t2)]
          }
    }.


   'heads' takes a list of pairs, and returns the list of all heads of these pairs. Remark
   that if we apply 'heads' to either a 'firstpos' or a 'lastpos' datum, we get a list of
   increasingly ordered distinct integers.

define List($T)
  heads
    (
      List(($T,$U)) l
    ) = 
  if l is 
    {
      [ ] then [ ], 
      [h . t] then if h is (u,v) then 
        [u . heads(t)]
    }. 



   Adding entries to a follow table. Given:
    
     - a list of keys (e1,...,ek)       of type (Word16,DFA_pre_label($Token))
     - a list of values (t1,...,tn)     of type (Word16,DFA_pre_label($Token))
     - a A-list of triplets             of type (Word16,DFA_pre_label($Token),List(Word16)), 

   update that A-list, adding keys e1,...,en if they are not already in the A-list, and
   putting each head of ti as a value for each ej. The third element of each triplet (a
   list of integers) should always remain inceasingly sorted, and have distinct elements.

   First, assume there is only one key (and its label) to add:

   
define FollowTable($Token,$Aux)
   add_follow_entry
    ( 
      Word16 key,
      DFA_pre_label($Token,$Aux) c, 
      List((Word16,DFA_pre_label($Token,$Aux))) values,
      FollowTable($Token,$Aux)  previous
    ) =
   if previous is
     {
       empty then follow_table(key,c,heads(values),empty), 
       follow_table(k1,c1,v1,t) then 
         if key = k1
         then follow_table(k1,c1,merge_sorted(heads(values),v1),t)
         else follow_table(k1,c1,v1,add_follow_entry(key,c,values,t))
     }.
   

   Now, add several keys. 

define FollowTable($Token,$Aux)
   add_follow_entries
     (
       List((Word16,DFA_pre_label($Token,$Aux)))    keys, 
       List((Word16,DFA_pre_label($Token,$Aux)))    values,
       FollowTable($Token,$Aux)                     previous
     ) =   
   if keys is 
     {
       [ ] then previous, 
       [k1 . ks] then 
         if k1 is (k,c) then
         add_follow_entries(ks,values,add_follow_entry(k,c,values,previous))
     }. 
   
   Appending two follow tables (it is assumed that they have no key in common).
   
define FollowTable($Token,$Aux)
   append
     (
       FollowTable($Token,$Aux) t1,
       FollowTable($Token,$Aux) t2
     ) =
   if t1 is 
     {
       empty    then t2,
       follow_table(p,l,n,tail1) then follow_table(p,l,n,append(tail1,t2))
     }. 
   

   Making the follow_table from a decorated basic regular expression.

define FollowTable($Token,$Aux)
  make_follow_table
    (
      DecoratedBasicRegExpr($Token,$Aux) r
    ) = 
  if r is
    {
      char(c,n,nb,fp,lp)        then follow_table(n,char(c),[],empty), 
      epsilon(nb,fp,lp)         then empty, 
      or(r1,r2,nb,fp,lp)        then append(make_follow_table(r1),make_follow_table(r2)),
      /* we can use append because r1 and r2 cannot share a
         key. */

      cat(r1,r2,nb,fp,lp)       then 
        with   t = append(make_follow_table(r1),make_follow_table(r2)), 
              /* same remark on append */ 
              l1 = lastpos(r1),
              f2 = firstpos(r2),
                add_follow_entries(l1,f2,t),

      star(r1,nb,fp,lp)         then
        with   t = make_follow_table(r1),
               f = firstpos(r1),
               l = lastpos(r1),
                add_follow_entries(l,f,t),
   
      action(a,n,nb,fb,lp)      then follow_table(n,action(a),[],empty)
    }. 





   Finding an entry in a follow table. 

define (Word16,DFA_pre_label($Token,$Aux),List(Word16))
  follow_table_entry
    (
      Word16 p, 
      FollowTable($Token,$Aux)  l
    ) = 
  if l is 
    {
      empty then should_not_happen((0,char(0),[])),   // we should always find it
      follow_table(n,c,pos,t) then 
        if p = n
        then (n,c,pos)
        else follow_table_entry(p,t)
    }. 
   
   
   
   
   Names of states in the DFA are primarily increasingly sorted lists of Word16s. They are
   transformed into Word16 when the DFA is renamed (see below). A transition is just a
   pair made of a label and a state name.

type DFA_pre_transition($Token,$Aux):
  transition(DFA_pre_label($Token,$Aux)         label, 
             List(Word16)                       target_name). 


   A state is made of a state name and a list of transitions.

type DFA_pre_state($Token,$Aux):
  state(List(Word16)                                  name, 
        Maybe(List(DFA_pre_transition($Token,$Aux)))  transitions). 


   The reason why the field 'transitions' has a 'Maybe' is that we may consider
   'incomplete' states, which did not yet receive their transitions.

   Note: A DFA is not a tree in general, but a graph. This is the reason why states have
   names. Since we cannot construct circular data in Anubis, the presence of names allows
   nevertheless the construction of graphs (including circularities).  However, we cannot
   refer directly to a state, but only to its name.

   We explain now how the automaton is constructed for a decorated basic regular
   expression 'r'.

   First of all, there is an initial state, whose name is firstpos(r). What it means is
   that in this state, we expect to read a character corresponding to one of these
   positions.

   More generally, for any state 's', the name of the state is the list of all positions
   which may match the next character to be read from the input.

   Since, we don't care about unreachable states, we construct the automaton, starting
   with the initial state, and adding all the states required by the transitions, until no
   more state may be added. Of course, this process terminates, since the set of all
   possible state names is obviously finite (its cardinal is at most 2^p, where p is the
   number of positions in r).

   For a given state, with name [p_1,...,pk], the transitions are given by the labels of
   p_1,...,p_k.  Nevertheless, several positions may have the same label. Hence, for a
   given label, let q_1,...,q_j be those among p_1,...,p_k which have this label. The
   target state for the corresponding transition is obtained by taking all the positions
   which may follow one of q_1,...,q_j.

   That's all ! 


   Empty state names. What does it mean that the name of a state is empty ? This means
   that reaching this state produces an error. Indeed, a state accepts a string if and
   only if it contains a position labelled by an action, and has transitions to other
   states if and only if it contains a position labelled by a character (or
   'end_of_file').

   A state which contains an action is an accepting state. Nevertheless, it may also have
   transitions. Hence, the lexer may eventually accept a longer sequence. But following
   the transitions may also lead to an error.  Hence the lexer must always keep the most
   recently found solution, and use it (if it exists) if it enters a dead end (and in that
   case, there is no error at all).

   When using a solution, the lexer must also apply the action. This action must have been
   saved by the lexer.  Hence it is necessary to number actions, and to create a function
   for each action.




   Given a state name [p_1,...,p_k], and the follow table, the function
   'prepare_transitions' produces a list of pairs
 
           (a , l)

   where 'a' is a label, and 'l' the list of all positions with label 'a' which may follow
   one of p1,...,pk. We need an auxiliary function 'insert'.


   
   
   
define List(DFA_pre_transition($Token,$Aux))
  insert
    (
      DFA_pre_label($Token,$Aux)                    c, 
      List(Word16)                                  l, 
      List(DFA_pre_transition($Token,$Aux))         q
    ) =
  if q is
    {
      [ ] then [transition(c,l)],
      [h . t] then 
        if h is transition(c1,l1) then 
        if c = c1
        then [transition(c,merge_sorted(l,l1)) . t]
        else [h . insert(c,l,t)]
    }.
    

define List(DFA_pre_transition($Token,$Aux))
  prepare_transitions
    (
      List(Word16)               name, 
      FollowTable($Token,$Aux)   ft
    ) =
  if name is 
    {
      [ ] then [ ], 
      [p1 . p_others] then 
        if follow_table_entry(p1,ft) is (p,c,l) then 
        with q = prepare_transitions(p_others,ft), 
          insert(c,l,q)
    }. 




   Now, we compute our DFA, i.e a list of DFA_pre_state($Token)s. We begin with only one
   state in the list.  The name of this state is firstpos(r), and it has not yet received
   its transitions. In other words, it is:

           state(firstpos(r),failure)

   Then, we enter an 'infinite' loop. At each pass, we look for a state which did not yet
   receive its transitions. If there is no such state, the DFA is ready (and we exit the
   loop). Otherwise, we add its transitions to the state, and this may create new states
   (without their transitions) in the DFA.

   We need a function to separate (if possible) an incomplete state from a list of states:

define Maybe((DFA_pre_state($Token,$Aux),List(DFA_pre_state($Token,$Aux))))
  separate_incomplete_state
    (
      List(DFA_pre_state($Token,$Aux)) l
    ) =
  if l is 
    {
      [ ] then failure, 
      [s1 . so] then 
        if transitions(s1) is 
          {
            failure then 
              success((s1,so)),
            success(_) then 
              if separate_incomplete_state(so) is
                {
                  failure then failure, 
                  success(p) then if p is (i,m) then 
                    success((i,[s1 . m]))
                }
          }
    }. 


   We need a function to extract the list of target names from a list of transitions.

define List(List(Word16))
  get_targets
    (
      List(DFA_pre_transition($Token,$Aux)) l
    ) =
  if l is 
    {
      [ ] then [ ], 
      [h . t] then if h is transition(n,target) then 
        [target . get_targets(t)]
    }.


   We need a predicate to test if a list of states contains a state of a given name.

define Bool
  is_state_name_in
    (
      List(DFA_pre_state($Token,$Aux)) l,
      List(Word16) n                        // sorted list of integers
    ) =
  if l is 
    {
      [ ] then false, 
      [h . t] then 
        if h is state(m,tr) then 
        if n = m       // comparing sorted lists of integers
        then true
        else is_state_name_in(t,n)
    }. 


   We need a function to add new states to a list of states. The new states are given in
   the form of a list of state names and are added without their transitions.

define List(DFA_pre_state($Token,$Aux))
  add_new_states
    (
      List(List(Word16)) names, 
      List(DFA_pre_state($Token,$Aux)) states
    ) =
  if names is 
    {
      [ ] then states, 
      [h . t] then 
        if is_state_name_in(states,h) 
        then add_new_states(t,states)
        else add_new_states(t,[state(h,failure) . states])
    }. 



   We need a function to complete a state which did not yet receive its transitions.

define List(DFA_pre_state($Token,$Aux))
  complete_state
    (
      DFA_pre_state($Token,$Aux) i,        // incomplete state
      List(DFA_pre_state($Token,$Aux)) o,  // other states
      FollowTable($Token,$Aux) ft
    ) =
  with trans = prepare_transitions(name(i),ft),
       targets = get_targets(trans), 
       add_new_states(targets,[state(name(i),success(trans)) . o]). 
     

   Now, here is our 'infinite' loop. 

define List(DFA_pre_state($Token,$Aux))
  make_DFA_pre
    (
      List(DFA_pre_state($Token,$Aux)) l,
      FollowTable($Token,$Aux) ft
    ) =
  if separate_incomplete_state(l) is
    {
      failure then l, // the DFA is ready

      success(p) then if p is (s,o) then  
        with new = complete_state(s,o,ft), 
          make_DFA_pre(new,ft)
    }. 





      *** [3.5] Renaming the states of the DFA.

   Names of states in our DFA are lists of integers. We need to replace them by integers.

   From a DFA whose state names are lists of integers, we create a list of pairs (old,new)
   where new is a new name (an integer) and old an old name (a list of integers).

define List((List(Word16),Word16))    // an association list
  name_list
    (
      List(DFA_pre_state($Token,$Aux)) l,
      Word16 first_new_name
    ) = 
  if l is 
    {
      [ ] then [ ],
      [h . t] then 
        if h is state(old_name,tr) then 
          [(old_name,first_new_name) . name_list(t,first_new_name+1)]
    }.

   
   Given an old name and our association list, we can get the new name.

define Word16
  get_new_name
    (
      List(Word16) old_name,
      List((List(Word16),Word16)) nlist
    ) =
  if nlist is
    {
      [ ] then should_not_happen(0),   // the new name should always exist
      [h . t] then if h is (o,n) then 
        if old_name = o 
        then n
        else get_new_name(old_name,t)
    }. 


   Now, we rename all transitions in a given state. At the same time we separate actual
   transitions from actions. This is why the following function returns a pair made of a
   list of transitions, and maybe an action. Since the action is of type:
   
                                       LexerRankAction($Token)
   
   the non mandatory action is of type:
   
                                   Maybe(LexerRankAction($Token))
   
   
define (List(DFA_transition),Maybe(LexerRankAction($Token,$Aux)))
   rename
     (
       List(DFA_pre_transition($Token,$Aux)) l,
       List((List(Word16),Word16)) nlist 
     ) =
   if l is 
     {
       [ ] then ([ ],failure), 
       [h . t] then 
         if rename(t,nlist) is (trs,mbmba) then 
         if h is transition(pre_label,target) then 
         if pre_label is 
           {
             char(c)            then 
               ([transition(char(c),get_new_name(target,nlist)) . trs],mbmba),
             action(mba)        then if mbmba is
               {
                 failure       then (trs,success(mba)),
                 success(x)    then // two actions in the same state: choose the first one.
                                    (trs,success(x))
               }
           }
     }.
   

   Now, we rename all the states.

define List(DFA_state($Token,$Aux))
  rename
    (
      List(DFA_pre_state($Token,$Aux)) l,
      List((List(Word16),Word16)) nlist
    ) =
  if l is 
    {
      [ ] then [ ],
      [h . t] then 
        if h is state(old_name,mbtrans) then 
          if mbtrans is 
            {
              failure then should_not_happen([]), // pre-states must have been completed
              success(trans) then 
                if rename(trans,nlist) is (trs,mbmba) then 
                if mbmba is 
                  {
                    failure then 
                      [rejecting(get_new_name(old_name,nlist),trs) . rename(t,nlist)]
                    success(LexerRankAction($Token,$Aux) mba) then if mba is 
                      {
                        ignore then 
                          [ignoring(get_new_name(old_name,nlist),trs) . rename(t,nlist)],
                        return(rk,a) then 
                          [accepting(get_new_name(old_name,nlist),trs,rk,a) . rename(t,nlist)],
                        return(rk,a) then 
                          [accepting(get_new_name(old_name,nlist),trs,rk,a) . rename(t,nlist)]
                      }
                  }
            }
    }.


   
   
   

      *** [3.5] Making the DFA.

define LexerRankAction($Token,$Aux)
  add_rank
  (
    LexerAction($Token,$Aux)   a, 
    Int                        rank
  ) =
  if a is 
  {
    ignore    then ignore, 
    return(f) then return(rank,f),
    return(f) then return(rank,f)
  }. 
                                

define Result(RegExprError,BasicRegExpr($Token,$Aux))
  prepare_global_regexpr
  (
    List(LexerItem($Token,$Aux))  lexer_description,
    Word8                         escape_char, 
    Int                           action_rank
  ) =
  if lexer_description is
  {
    [ ]      then error(empty_lexer_description),
    [h . t]  then if h is
    {
      lexer_item(re,a) then if parse_regular_expression(make_stream(re),escape_char) is
      {
        error(msg)  then error(msg),
        ok(re1)     then if t is
        {
          [ ]      then ok(cat(to_basic(re1), action(add_rank(a,action_rank)))),
          [_ . _]  then if prepare_global_regexpr(t, escape_char,action_rank+1) is
          {
            error(msg)  then error(msg),
            ok(p)       then ok(or(cat(to_basic(re1),action(add_rank(a,action_rank))),p))
          }
        }
      },

      lexer_item(ba, a) then if t is
      {
        [ ]      then ok(cat(to_basic(ba),action(add_rank(a,action_rank)))),
        [_ . _]  then if prepare_global_regexpr(t, escape_char,action_rank+1) is
        {
          error(msg)  then error(msg),
          ok(p)       then ok(or(cat(to_basic(ba),action(add_rank(a,action_rank))),p))
        }
      }
    }
  }.



public define Result(RegExprError,List(DFA_state($Token,$Aux)))   
   make_DFA
     (
       List(LexerItem($Token,$Aux))  lexer_description,
       Word8                         escape_char
     ) =
   if prepare_global_regexpr(lexer_description,escape_char,0) is 
     {
       error(msg) then error(msg), 
       ok(re) then if decorate(re,0) is (br,_) then 
         with dfa = reverse(make_DFA_pre([state(heads(firstpos(br)),failure)],
                                         make_follow_table(br))), 
         ok(rename(dfa,name_list(dfa,0)))
     }. 
   
   
   
   

      *** [3.6] Translating a DFA into a fast lexer description. 
   
   The types 'FastLexerTransition' and 'FastLexerState' is defined in 'predefined.anubis'
   section 13.
   
define List(FastLexerTransition)   
   to_fast_lexer_transitions
     (
       List(DFA_transition) l
     ) =
   if l is 
     {
       [ ] then [ ],
       [h . t] then if h is transition(label,target) then 
         [if label is 
            {
              char(c)            then transition(c,target)
            } . to_fast_lexer_transitions(t)]
     }.
   
   
public define List(FastLexerState)   
   to_fast_lexer_description
     (
       List(DFA_state($Token,$Aux))   l
     ) =
   if l is 
     {
       [ ] then [ ], 
       [h . t] then  [if h is 
         {
           rejecting(n,trs)        then rejecting(to_fast_lexer_transitions(trs))
           accepting(n,trs,rk,a)   then accepting(to_fast_lexer_transitions(trs))
           accepting(n,trs,rk,a)   then accepting(to_fast_lexer_transitions(trs))
           ignoring (n,trs)        then ignoring(to_fast_lexer_transitions(trs))
         } . to_fast_lexer_description(t)]
     }. 
   
   
     
      
   
   
   *** [4] Constructing the lexer. 
   
   The low  level fast  lexer (see  'predefined.anubis', section 13)  does not  care about
   actions. Hence, we  must manage actions in  parallel. To this end we  use the following
   type:
   
                               MVar(LexerAction($Token,$Aux))
   
   The  action for  state  'n' (assumed  to be  an  accepting state or ingoring state with 
   action because the  multiple
   variable is  never used for  rejecting states)  is the value  stored in slot  'n'.  The
   default value is 'ignore' meaning 'ignore this token and read the next one'. Otherwise,
   the function is  applied to the lexeme just  read, and the lexer returns  the result of
   this function.

   The multiple variable is filled up by:
   
define One
   fill_actions
     (
       List(DFA_state($Token,$Aux))                                 dfa,
       MVar(LexerAction($Token,$Aux))                               v
     ) =
   if dfa is 
     {
       [ ] then unique, 
       [h . t] then 
         if h is 
           {
             rejecting(name,trs)           then unique, 
             accepting(name,trs,rk,action) then v(word32(name,0)) <- return(action),
             accepting(name,trs,rk,action) then v(word32(name,0)) <- return(action),
             ignoring (name,trs)           then unique
           }; 
         fill_actions(t,v)
     }. 
   
   
   Making the multiple variable for actions is performed by:
   
define Word16
   truncate_to_Word16
     (
       Int x
     ) =
   if truncate_to_Word32(x) is word32(l,_) then l. 
   
   
public define MVar(LexerAction($Token,$Aux))
   get_actions
     (
       List(DFA_state($Token,$Aux))  dfa
     ) = 
   with ns = length(dfa),      // total number of states
         v = mvar(truncate_to_Word32(ns), 
                  (LexerAction($Token,$Aux))ignore),    /* fake action to be replaced just below */
     fill_actions(dfa,v); v.
   
   
   
   
   
   
      *** [4.1] Plugging a lexer to a lexing stream. 
   
define One -> LexerOutput($Token)
   plug_lexer
     (
       LexingStream                                                       stream, 
       (ByteArray                   input, 
        FastLexerLastAccepted       last_accepted, 
        Int                         position, 
        Int                         token_start, 
        Word16                      starting_state) -> FastLexerOutput    lexer, 
       MVar(LexerAction($Token,$Aux))                                     actions,
       $Aux                                                               aux
     ) = 
   (One _) |-> read_next_token(lexer,stream,0,actions,aux).
   
   
   
   
   
   
   Finally, the tool for making a lexer. 
   
public define Result(RegExprError, (LexingStream,$Aux)-> One -> LexerOutput($Token))
   make_lexer
     (
       List(LexerItem($Token,$Aux))   lexer_description,
       Word8                          escape_char
     ) =
   if make_DFA(lexer_description,escape_char) is 
     {
       error(msg) then error(msg), 
       ok(List(DFA_state($Token,$Aux)) dfa) then 
         with actions = get_actions(dfa),
         if make_fast_lexer(to_fast_lexer_description(dfa)) is 
           {
             unknown_state(n) then should_not_happen(error(empty_lexer_description)),    // cannot happen
             too_many_states  then should_not_happen(error(empty_lexer_description)), 
             ok(fl) then 
               ok((LexingStream ls,$Aux aux) |-> plug_lexer(ls,fl,actions,aux))
           }
     }.


define One
  dump
  (
    WStream     f, 
    ByteArray   b,
    Word32      i
  ) =
  if nth(to_Int(i),b) is 
  {
    failure    then unique, 
    success(c) then
      print(f,"0x"+to_hexa(c)); 
      (if to_Int(i)+1 /= length(b) then print(f,", ") else unique); 
      (if ((i+1)&15) = 0 then print(f,"\n   ") else unique);   
    dump(f,b,i+1)
  }. 

define One
  dump
  (
    WStream      f, 
    List(Int)    l, 
    Int          i
  ) =
  if l is 
  {
    [ ] then unique, 
    [h . t] then 
      print(f,to_decimal(h)); 
      (if t is [] then unique else print(f,", "));
      (if ((i+1)&15) = 0 then print(f,"\n     ") else unique);  
      dump(f,t,i+1)
  }.

define One
  dump
  (
    WStream                  f,
    List(DFA_transition)     l,
    Word32                   i
  ) =
  if l is 
  {
    [ ]      then if (i&15) = 15 then unique else print(f,"\n"),  
    [h . t]  then if h is transition(label,target_name) then 
      if label is char(c) then 
      print(f," '"+implode([c])+"'>"+to_decimal(target_name)); 
      (if (i&15) = 15 then print(f,"\n") else unique);
      dump(f,t,i+1)
  }.

define One
  dump
  (
    WStream                        f, 
    List(DFA_state($Token,$Aux))   dfa
  ) =
  if dfa is
  {
    [ ]      then unique, 
    [h . t]  then if h is 
    {
      rejecting(name,transitions)  then 
        print(f,"\n --- state "+to_decimal(name)+" (rejecting) ---\n"); 
        dump(f,transitions,0), 
        
      accepting(name,transitions,action_rank,action)  then 
        print(f,"\n --- state "+to_decimal(name)+" (accepting with action number "+to_decimal(action_rank)+") ---\n"); 
        dump(f,transitions,0), 

      accepting(name,transitions,action_rank,action)  then 
        print(f,"\n --- state "+to_decimal(name)+" (accepting with action number "+to_decimal(action_rank)+") ---\n"); 
        dump(f,transitions,0), 

      ignoring(name,transitions)  then 
        print(f,"\n --- state "+to_decimal(name)+" (ignoring no action) ---\n"); 
        dump(f,transitions,0)
    };
    dump(f,t)
  }.

define One
  dump
  (
    WStream                        f, 
    String                         lexer_name, 
    List(Int)                      actions_ranks, 
    PrecompiledFastLexer           l,
    List(DFA_state($Token,$Aux))   dfa
  ) = 
  if l is precompiled_fast_lexer(fba,sba) then
  print(f,"\n   This file was automatically generated by 'fast_lexer_4.anubis'.\n"); 
  print(f,"   Don't modify it in any manner.\n"); 
  print(f,"\n   The (deterministic) automaton has "+to_decimal(length(actions_ranks))+" states.\n"); 
  //dump(f,dfa); 
  print(f,"\npublic define (List(Int),PrecompiledFastLexer)\n"); 
  print(f,"  "+lexer_name+" =\n"); 
  print(f,"  (["); 
  dump(f,actions_ranks,0); 
  print(f,"],\n  precompiled_fast_lexer(\n  {");
  dump(f,fba,0); 
  print(f,"},\n  {"); 
  dump(f,sba,0); 
  print(f,"})).\n\n ").


define List(Int)
  actions_ranks
  (
    List(DFA_state($Token,$Aux))   dfa
  ) =
  if dfa is
  {
    [ ] then [ ], 
    [h . t] then if h is 
     {
       rejecting(name,transitions)              then [-1   . actions_ranks(t)], 
       accepting(name,transitions,rank,action)  then [rank . actions_ranks(t)], 
       accepting(name,transitions,rank,action)  then [rank . actions_ranks(t)], 
       ignoring(name,transitions)               then [-1   . actions_ranks(t)]
     }
  }. 
  
  
   Get a characteristic serializable datum from a lexer description (used to avoid
   reconstructing the lexer when the description did not change). The signature is 
   changed if any of the regular expressions is changed or if their order is changed
   or if the sort of action is changed (this last point ensures that the list of 
   action sorts/ranks remains correct in the generated file). 
define List(ByteArray)
   extract_regexprs
   (
     List(LexerItem($Token,$Aux))  l
   ) = 
   with asign = (LexerAction($Token,$Aux) a) |-> if a is 
     {
       ignore      then "(*i)",     // something which is illegal as a regular expression
       return(_0)  then "(*r1)",
       return(_0)  then "(*r2)"
     },
   map((LexerItem($Token,$Aux) i) |-> if i is 
           {
             lexer_item(regular_expression,action)  then to_byte_array(regular_expression+asign(action)), 
             lexer_item(literal,action)             then literal+to_byte_array(asign(action))
           },l).
           

           
public define One
  make_precompiled_lexer_aux
  (
    String                         signature,
    String                         directory, 
    String                         lexer_name, 
    List(LexerItem($Token,$Aux))   lexer_description,
    Word8                          escape_char    
  ) =  
  with file_name = directory/lexer_name+".anubis", 
  if file(file_name,new) is 
  {
    failure       then print("Cannot create file '"+file_name+"'.\n"), 
    success(file) then
      print(weaken(file),"   "+signature+"\n\n"); 
      if make_DFA(lexer_description,escape_char) is 
      {
        error(msg) then print(to_English(msg)+"\n"), 
        ok(List(DFA_state($Token,$Aux)) dfa) then 
          if precompile_fast_lexer(to_fast_lexer_description(dfa)) is 
          {
            unknown_state(s)  then should_not_happen(unique),
            too_many_states   then should_not_happen(unique), 
            ok(pfl)           then dump(weaken(file),lexer_name,actions_ranks(dfa),pfl,dfa)          
          }
      } 
  }.
  

define Maybe(String)
   read_signature
   (
     String file_name
   ) =
   if file(file_name,read) is 
   {
     failure     then failure,
     success(f)  then if read(f,43,10) is     // read the first 3 (blanks) + 40 (sha1 hash) characters
       {
         error    then failure, 
         timeout  then failure, 
         ok(ba)   then success(to_string(extract(ba,3,43))) 
       }
   }.
  
public define One
  make_precompiled_lexer
  (
    String                         directory, 
    String                         lexer_name, 
    List(LexerItem($Token,$Aux))   lexer_description,
    Word8                          escape_char    
  ) =  
  // avoid to reconstruct the lexer if not needed
  with signature = to_hexa(sha1(extract_regexprs(lexer_description))),
       file_name = directory/lexer_name+".anubis", 
           do_it = (One u) |-> 
             print("Creating '"+file_name+"'. Please wait ... "); forget(flush(stdout)); 
             make_precompiled_lexer_aux(signature,directory,lexer_name,lexer_description,escape_char);
             print("Done.\n"); forget(flush(stdout)),
  if read_signature(file_name) is 
  {
    failure    then do_it(unique), 
    success(s) then if s = signature
                    then unique
                    else do_it(unique)
  }. 
  
  
public define One
  make_precompiled_lexer
  (
    String                         lexer_name, 
    List(LexerItem($Token,$Aux))   lexer_description,
    Word8                          escape_char    
  ) =
  forget((String)make_directory("generated"));
  make_precompiled_lexer("generated",lexer_name,lexer_description,escape_char). 

  
define LexerAction($Token,$Aux)
  get_action_by_rank
  (
    List(LexerItem($Token,$Aux))    items,
    Int                             rank
  ) =
  if items is 
    {
      [ ]      then should_not_happen(ignore), 
      [h . t]  then 
        if rank = 0
        then if h is 
          {
            lexer_item(regular_expression,action)  then action, 
            lexer_item(ba,action)                  then action
          }
        else get_action_by_rank(t,rank-1) 
    }.
  
define One
  fill_actions
  (
    List(Int)                       ranks, 
    List(LexerItem($Token,$Aux))    items,
    MVar(LexerAction($Token,$Aux))  v, 
    Word32                          i
  ) =
  if ranks is 
  {
    [ ] then unique, 
    [h . t] then 
      (if h = -1
       then unique
       else v(i) <- get_action_by_rank(items,h));  
      fill_actions(t,items,v,i+1)
  }.
  
define MVar(LexerAction($Token,$Aux))
  get_actions
  (
    List(Int)                      ranks,     // of actions in lexer description
    List(LexerItem($Token,$Aux))   items, 
  ) =
  with ns = length(ranks),     // total number of states
        v = mvar(truncate_to_Word32(ns),
                 (LexerAction($Token,$Aux))ignore), 
    fill_actions(ranks,items,v,0); v. 
  
public define (LexingStream,$Aux) -> One -> LexerOutput($Token)
  retrieve_lexer
  (
    List(LexerItem($Token,$Aux))               lexer_description,
    (List(Int),PrecompiledFastLexer)           p
  ) =
  if p is (actions_ranks,pfl) then 
  with fl = retrieve_fast_lexer(pfl), 
  actions = get_actions(actions_ranks,lexer_description), 
  (LexingStream ls, $Aux aux) |-> plug_lexer(ls,fl,actions,aux). 
  
  
 
public define Result(RegExprError, 
                     ((LexingStream,$Aux) -> One -> LexerOutput($Token),     // the lexer
                       List(DFA_state($Token,$Aux))))                        // the automaton
   make_lexer_and_automaton
     (
       List(LexerItem($Token,$Aux))   lexer_description,
       Word8                          escape_char
     ) =
   if make_DFA(lexer_description,escape_char) is 
     {
       error(msg) then error(msg), 
       ok(List(DFA_state($Token,$Aux)) dfa) then 
         with actions = get_actions(dfa), 
         if make_fast_lexer(to_fast_lexer_description(dfa)) is 
           {
             unknown_state(n) then should_not_happen(error(empty_lexer_description)),    // cannot happen
             too_many_states  then should_not_happen(error(empty_lexer_description)), 
             ok(fl) then ok(((LexingStream ls, $Aux aux) |-> plug_lexer(ls,fl,actions,aux),dfa))
           }
     }.




   *** [5] Graphviz formatting.

read tools/graphviz.anubis
read tools/2-4tree.anubis




      *** [5.1] Formatting tools.

define List(Word8) graphviz_format(Word8 c) =
  if member(c,"-[]")  then  ['\\','\\',c]
  else if c = '\\'    then  ['\','\',' ']
  else if c = '\n'    then  ['\','\','n']
  else if c = '\r'    then  ['\','\','r']
  else if c = ' '     then  ['\','\','_']
  else if c = '\"'    then  ['\"',c]
  else [c].

define List(Word8) label_chars(DFA_label label) = if label is char(c) then graphviz_format(c).




      *** [5.2] Transition grouping.
        
   In each state, we may have several transitions to the same target state. We need to group them into a single
   transition, with all labels concatenated.

type TransitionGroup:
  group(  List(Word8)   labels,         // A label is a list of Word8 (type C 'char')
          Word16        target_name)    // The "name" of the target
  .

    For a given state with several transition, insert the current transition "t" into the group of transition targting
  the same target state
define List(TransitionGroup) insert_transition(
    DFA_transition           t,   // The transition to put in a group
    List(TransitionGroup)    l    // The list of existing groups
  ) =
  if l is
  {
    // No group of transition found for that target: create a new one
    [ ] then if t is transition(label, target_name) then [ group(label_chars(label), target_name) ],

    // Search the right group. If found, insert the transition.
    [head . tail] then
      if head is group(labels, tn) then
      if t is transition(label, target_name) then
      if tn = target_name // Same target group ?
        then [group( append(label_chars(label), labels), tn) . tail]  // Yes: Insert the label into the list of labels
        else [head . insert_transition(t, tail)]                      // No: continue searching
  }.

    For a list of transitions (from the same state), create a list of transition group.
define List(TransitionGroup) group_transitions(List(DFA_transition) l) = if l is
  {
    [ ]        then [ ],
    [t1 . ts]  then with others = group_transitions(ts), insert_transition(t1,others)
  }.

  
  
  
  
      *** [5.3] State dumping.

define GResult dump_all_states(
    List(DFA_state($Token, $Aux))   states,
    GResult                         base_graph
  ) =
  // --- Dump all the states here first.
  if fold_left(states, (new_tree(bt24cmp_us),base_graph), ((TreeKV(Word16, GResult), GResult) tuple, DFA_state($Token, $Aux) s)|->
    with state_name = name(s),
    with col = if s is
    {
      rejecting(_, _)        then color("red")
      accepting(_, _, _, _)  then color("green")
      accepting(_, _, _, _)  then color("green")
      ignoring(_, _)         then color("blue")
    },
    if tuple is (tkv, baseg) then
    // Dump the state itself
    with stateg = add_node(baseg, [ label("state_"+to_decimal(state_name)), col]),
    // Record the state
    with dic    = insert(state_name, stateg, tkv),
    (dic, stateg)
  ) is (dic_node, state_graph) then
  // --- Dump the transition:
  fold_left(states, state_graph, (GResult stateg, DFA_state($Token, $Aux) s)|->
    with groups = group_transitions(transitions(s)),
    with state_node = (if get(name(s), dic_node) is success(n) then n else should_not_happen(add_node(stateg))),
    // Dump the group of transitions
    fold_left(groups, stateg, (GResult transig, TransitionGroup tg)|->
      if tg is group(chars, target_name) then
      with target_node = (if get(target_name, dic_node) is success(n) then n else should_not_happen(add_node(stateg))),
      add_edge(transig, state_node, target_node, label(implode(chars)))
    )
  ).
  
  
  
  
      *** [5.4] DFA to graphviz.
        
define One print(Stream s, String t) = forget(write_string(s,t)).

    Output the DFA, on a stream
public define One dump_dfa_graphviz(
    List(DFA_state($Token, $Aux))   dfa,
    String                          lexer_name,
    Stream                          output
  ) =
  // Create a new empty Non-strict, directed, named graph
  with base = graph( none, digraph, some(lexer_name)),
  with graph = dump_all_states(dfa, base),
  print(output, to_dot(graph))
  .

    Output the DFA, create the file. Helper for the above function.
public define One dump_dfa_graphviz(
    List(DFA_state($Token, $Aux))   dfa,          // The DFA to output
    String                          lexer_name,   // Name of the lexer
    String                          dir           // Directory of output
  ) =
  with fn = dir/lexer_name+".dot",
  if file(fn,new) is
  {
    failure     then print("Cannot create file '"+fn+"'.\n"),
    success(f)  then dump_dfa_graphviz(dfa,lexer_name,make_stream(f))
  }.



   The following is added for compatibility with previous usages:
public define macro LexerItem($Token,$Aux)
   raw_lexer_item
   (
     ByteArray                  ba,
     LexerAction($Token,$Aux)   a
   ) =
   lexer_item(ba,a).