In LaTeX3, what is the best data type for storing, parsing and outputting free user input?

Question

I'm working on a mini-parser that takes free user input and interprets certain inputs as commands. For example, the parser interprets + as \oplus or [ as "start a pre-configured array with the bracket as a delimiter". The parser would ultimately enable convenient inserting of a certain kind of data-structure used in linguistics (called AVM), for which there is currently no package on CTAN.

The parser is currently based on looping through an input token list (wit \tl_map_inline:nn). But looping through spaces and control sequences from the user input gives me a headache. For example, the user input could contain:

Hello World
\textit{Hello World}

Since \tl_map_inline:nn loops over the items of the token list, the outputs will be come "HelloWorld" and "HelloWorld".

Of course, the protected input

Hello{~}World
{\textit{Hello World}}

will give the desired result, but users are unlikely to type their input in that way. Also, the two inputs above really are quite different: Hello{~}World is a token list with 11 items, but {\textit{Hello World}} has just 1. In the mapping, I'd like to parse the contents of a command like \textit as individual letters, not a single token (because its argument could contain characters that the parser should be sensitive to, like the + mentioned above).

That got me thinking that maybe there is a better way to implement the parser than using a token list and a mapping on it. If the token list is the best way, then what methods are there to:

1. prepare the user input so that spaces will be kept as items? (maybe replace them with ~, but how?)
2. properly forward control sequences to the output and be able to access the tokens their arguments are made of?

In this answer, @egreg suggested receiving the user input as a sequence, splitting that at each space into token lists, and then parsing the token lists (with a space added to the output after every tl). Can this approach be applied to carry along commands in the example of \textit?

(Is it true that the difference between item and token is at the core of the issue?)

---

Here's the bare skeleton of my approach (the actual one also contains a mode switch so that the user can disable replacement of, e.g. [ so that one can still enter commands with optional arguments in the scope of the parser):

\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn

\NewDocumentCommand{\parse}{+m}{    
    \avm_parse:n { #1 }
}
\tl_new:N \l_avm_output_tl
\cs_new:Nn \avm_parse:n {
    \tl_clear:N \l_avm_output_tl
    \tl_map_inline:nn {#1} {
        \tl_put_right:Nn \l_avm_output_tl {##1}
    }
        \tl_use:N \l_avm_output_tl
}
\ExplSyntaxOff  
\begin{document}
    \noindent
    \parse{Hello World}\\
    \parse{\textit{Hello World}}\\
    \parse{Hello{~}World}\\ 
    \parse{{\textit{Hello{~}World}}}
\end{document}

Answer 1

It's possible to parse the entire token list while preserving spaces and groups, but it's a lot more work than "normal" \tl_map_inline:nn parsing (see here for a more complete explanation). The issue is that \tl_map_inline:nn, as its documentation in interface3 says, does not iterate on tokens, but on items, and it removes outer braces. All of XX, X X, X{X}, and {XX}{XX} are lists of two items (in the last one, each item has two tokens). This space and brace removal happens at a low level of TeX because when it grabs an argument, all of \next X, \next{X} and \next <spaces>X grab X as argument: this is what defines an item.

To iterate on proper tokens, you need to specifically check for the case of spaces and braces. expl3 has three conditional functions, \tl_if_head_is_space:n(TF) to check whether the first token in the argument token list is a space, \tl_if_head_is_group:n(TF) for the case of a grouped list of tokens, and \tl_if_head_is_N_type:n(TF) for all other cases. This allows you to process the argument token list conditionally for spaces and groups, and thus preserve them in the process. This method is also used by expl3's \text_uppercase:n (former \tl_upper_case:n), \tl_count_tokens:n, \tl_reverse:n, and a few others.

Here I defined the \avm_parse:n function so that it iterates on each token of the argument, and in case the token is of N-type, it checks if the current token is a + or a [ (using \str_case:nnF) and calls the appropriate function to process each case. You can change the definition of \__avm_special_plus: and \__avm_special_lbrack:w to do what you expect (I made the + produce \ensuremath{\oplus} and [<tokens>] produce \textbf{<tokens>} (and also parse the <tokens> with \avm_parse:n).

Here's the code:

\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn
\NewExpandableDocumentCommand {\parse} {+m}
  { \avm_parse:n {#1} }
\cs_new:Npn \avm_parse:n #1
  { \exp_args:No \exp_not:o { \__avm_parse:n {#1} } }
\cs_new:Npn \__avm_parse:n #1
  {
    \exp:w
      \group_align_safe_begin:
        \__avm_parse_loop:w #1
          \q_recursion_tail \q_recursion_stop
        \__avm_result:n { }
  }
\cs_new:Npn \__avm_end:w \__avm_result:n #1
  {
      \group_align_safe_end:
    \exp_end:
    #1
  }
\cs_new:Npn \__avm_parse_loop:w #1 \q_recursion_stop
  {
    \tl_if_head_is_N_type:nTF {#1}
      { \__avm_N_type:N }
      {
        \tl_if_head_is_group:nTF {#1}
          { \__avm_group:nw }
          { \__avm_space:w }
      }
    #1 \q_recursion_stop
  }
\cs_new:Npn \__avm_N_type:N #1
  {
    \quark_if_recursion_tail_stop_do:Nn #1
      { \__avm_end:w }
    \__avm_parse_specials:N #1
  }
\cs_new:Npn \__avm_parse_specials:N #1
  {
    \str_case:nnF {#1}
      {
        { + }{ \__avm_special_plus: }
        { [ }{ \__avm_special_lbrack:w }
      }
      { \__avm_non_special:N #1 }
  }
\cs_new:Npn \__avm_group:nw #1
  { \exp_args:NNo \exp_args:No \__avm_group:n { \__avm_parse:n {#1} } }
\cs_new:Npn \__avm_group:n #1 { \__avm_add_result:nw { {#1} } }
\exp_last_unbraced:NNo
\cs_new:Npn \__avm_space:w \c_space_tl { \__avm_add_result:nw { ~ } }
\cs_new:Npn \__avm_add_result:nw #1 #2 \q_recursion_stop \__avm_result:n #3
  { \__avm_parse_loop:w #2 \q_recursion_stop \__avm_result:n {#3 #1} }
\cs_new:Npn \__avm_non_special:N #1 { \__avm_add_result:nw {#1} }
%
\cs_new:Npn \__avm_special_plus:
  { \__avm_add_result:nw { \ensuremath { \oplus } } }
\cs_new:Npn \__avm_special_lbrack:w #1 ]
  {
    \exp_args:No \__avm_add_result:nw
      { \exp:w \exp_args:NNf \exp_end: \textbf { \avm_parse:n {#1} } }
  }
\ExplSyntaxOff
\begin{document}
\noindent
\parse{Hello World}\\
\parse{\textit{Hello World}}\\
\parse{Hello{~}World}\\
\parse{{\textit{Hello{~}World}}}\\
\parse{Hello [World]}\\
\parse{\textit{Hell[o W]orld}}\\
\parse{Hell[o{~+}W]orld}\\
\end{document}

and the output of the examples:

Answer 2

I find the recursion approach understandable, but somewhat harder to understand than the analysis function family; and it's not easy to preserve the charcode of {}.

_{Remark: In the simple cases, if a regex replacement suffices, just use that. Also it's faster.}

Alternative approaches include

• use regex to temporarily replace all space with some placeholder, process, then replace back.
• tokcycle or etl package.

An example of using \tl_analysis_map_inline _{needless to say, in real code don't redefine important LaTeX macros such as \f, \a etc.}:

\ExplSyntaxOn
\def \f #1 {
    \tl_build_begin:N \a
    \tl_analysis_map_inline:nn {#1} {
        \int_compare:nNnTF {##2} = {`[} {
            \tl_build_put_right:Nn \a {
                \iftrue \noexpand\textbf{ \else } \fi  % this will x-expand to '\textbf{'
            }
        } {
            \int_compare:nNnTF {##2} = {`]} {
                \tl_build_put_right:Nn \a {
                    \iffalse { \else } \fi  % this will x-expand to '}'
                }
            } {
                \int_compare:nNnTF {##2} = {`+} {
                    \tl_build_put_right:Nn \a { $\noexpand \oplus$ }
                } {
                    \tl_build_put_right:Nn \a {##1}
                }
            }
        }
    }
    \tl_build_end:N \a
    \tl_set:Nx \a {\a}
}

\ExplSyntaxOff
\f{a [Hello + world] b}
\a

The method to build partially-unbalanced intermediate token list is also demonstrated in the answer. (see explanation in my other answer here)

The output is , and the token list content after being processed is .

The disadvantage of this method however, is that it's necessary to manually count the number of open braces and close braces if you want to either

• grab an item, or
• only operate on the top level.

(while tokcycle package can do that automatically, but it ignores charcode of {})