title: How recursively lex a char list with multi-letter identifiers and multi-digit ints (lexing in SML)
body: <p>I am coding a lexer in SML. This is my first time working in a fully function language. General recursion is intuitive, but I have a nested recursive function to identify a string identifier, which is identified by starting with a letter (isAlpha) char and consequtive letters and digits. The problem I am having is that the first recursive function (lexer) recurses on the next char every time rather than the first char after the string. I have thought of 2 ways to do this so far: keeping a count and consuming the chars that have already been added to the string, or adding another argument which keeps track of the last char and if both are alphas, then somehow keeping track of them. These are obviously not efficient nor the proper way to implement this. It is driving me crazy and I cannot conceptualize or visualize the solution. Any help would be greatly appreciated.</p>
  <pre><code>exception LexerError;
  
  datatype sign =
      Plus
    | Minus
  ;
  
  datatype atom =
    T
  | NIL
  | Int of int
  | Ident of string
  ;
  
  datatype token =
    Lparen
  | Rparen
  | Dot
  | Sign of sign
  | Atom of atom
  ;
  
  
  (* implement lexid *)
  
  fun lexid (x::xs) = if Char.isAlpha(x) orelse Char.isDigit(x) then (String.str x) ^ lexid(xs)
                      else &quot;&quot;
    | lexid [] = &quot;&quot;
  ;
  
  
  
  
  (* implement lexint NOT COMPLETED*)
  
  fun lexint x = valOf(Int.fromString(String.str x))
  ;
  
  
  (* complete implementation of lexer *)
  fun  lexer (#&quot;.&quot; :: t)  = Dot :: lexer(t)
   |   lexer (#&quot;(&quot; :: t) = Lparen :: lexer(t)
   |   lexer (#&quot;)&quot; :: t) = Rparen :: lexer(t)
   |   lexer (#&quot;p&quot; :: #&quot;l&quot; ::  #&quot;u&quot; ::  #&quot;s&quot; :: t) = Sign(Plus) :: lexer(t)
   |   lexer (#&quot;m&quot; :: #&quot;i&quot; :: #&quot;n&quot; ::  #&quot;u&quot; ::  #&quot;s&quot; :: t) = Sign(Minus) :: lexer(t)
   |   lexer (#&quot;T&quot; :: t) = Atom(T) :: lexer(t)
   |   lexer (#&quot;N&quot; :: #&quot;I&quot; :: #&quot;L&quot; :: t) = Atom(NIL) :: lexer(t)
   |   lexer (#&quot; &quot; :: t) = lexer(t)
   |   lexer (#&quot;\n&quot; :: t) = lexer(t)
   |   lexer (#&quot;\t&quot; :: t) = lexer(t)
   |   lexer (#&quot;\r&quot; :: t) = lexer(t)
   |   lexer (h :: t) =
          if Char.isAlpha(h) then Atom(Ident((lexid (h::t)))) :: lexer(t)
          else if Char.isDigit(h) then Atom(Int((lexint h))) :: lexer(t)
          else Atom(Ident(&quot;test&quot;)) :: lexer(t)
   |   lexer [] = []
  ;
  
  fun print_tokens [] = print(&quot;\n&quot;)
    | print_tokens (Lparen :: t) = (print(&quot;Lparen &quot;); print_tokens(t))
    | print_tokens (Rparen :: t) = (print(&quot;Rparen &quot;); print_tokens(t))
    | print_tokens (Dot :: t) = (print(&quot;Dot &quot;); print_tokens(t))
    | print_tokens (Sign(Plus) :: t) = (print(&quot;Plus &quot;); print_tokens(t))
    | print_tokens (Sign(Minus) :: t) = (print(&quot;Minus &quot;); print_tokens(t))
    | print_tokens (Atom(a) :: t) =
    (case a of
     T =&gt; (print(&quot;Atom(T) &quot;); print_tokens(t))
     | NIL =&gt; (print(&quot;Atom(NIL) &quot;); print_tokens(t))
     | Int i =&gt; (print(&quot;Atom(Int(&quot; ^ Int.toString(i) ^ &quot;)) &quot;); print_tokens(t))
     | Ident s =&gt; (print(&quot;Atom(Ident(&quot; ^ s ^ &quot;)) &quot;); print_tokens(t)))
    ;
  
  
  fun reader(copt: char option, is, l) =
    case copt of
      NONE    =&gt; (TextIO.closeIn is; l)
    | SOME(c) =&gt; reader (TextIO.input1 is, is, (l@[c]))
    ;
  
  val args = CommandLine.arguments();
  val ins = TextIO.openIn(hd(args));
  
  print_tokens(lexer(reader(TextIO.input1 ins, ins, [])));
  
  val _ = OS.Process.exit(OS.Process.success)
  </code></pre>