Why is a LALR parser the correct choice for parsing mathematical content? (a question about Approach0)

This questions is about the work A novel similarity-search method for mathematical content in LaTeX markup and its implementation.

The parser used by Wei Zhong is LALR.

Now, supose I have to parse a function $$func(foo)=bar$$.

How is the parser able to understand the "$$func$$" as a whole string representing the name of a funciton and not several constants/variables $$f,u$$ and $$n$$ multiplying the function $$c(foo)=bar$$?

The grammar rules are found on pages 54/55:

• Splitting the text into tokens is the lexer’s job (usually), so check how it’s implemented in this case. Feb 3 at 12:43
• Some functions like $arccos$ or $max$ will be correctly handled by the lexer. Others are potentially problematic, like the above function, where there is a option to omit the dot sign ($.$) for the operation of multiplication. I mean, $func(x)$ might represent a single function or the constants $f$,$u$ and $n$ multiplying the function $c(x)$: $f.u.n.c(x)$. Do you understand my question? Feb 3 at 13:24

As @Dmitry said in a comment, the input is partitioned into tokens by the lexical analyser (or "scanner"), normally generated with (f)lex, and this stream of tokens becomes the input to the parser. The parser does not see the individual characters from the input.

Having said that, I don't believe that the parser can distinguish between different syntactic uses of juxtaposition. n(\pi/2) ($$n(\pi/2)$$) could be the product of $$n$$ with $$\pi/2$$, or it could be the application of the function $$n$$ to the argument $$\pi/2$$. Only semantic context could help the reader distinguish the two uses. (Was $$n$$ previously used as a variable or was it textually defined as a function or predicate?). [Note 1]

Since the goal of the cited thesis is to search a corpus of text for instances of mathematical equations similar to a given query, the precise parse is not required (and perhaps not even useful), so that resolving that ambiguity is not a goal of the project. Consequently, it's probably not a great witness for the question "What is the best parsing framework for parsing mathematical content?" In general, mathematicians tend to tolerate highly ambiguous syntaxes in presentations, relying on the common sense and semantic knowledge of the reader to disambiguate. (Much the same as our approach to human language in general.) But when logic and algebra are analysed theoretically, unambiguous syntaxes are required, and those are normally defined in such a way that they can be parsed with an LALR(1) parser. (Indeed, the usual syntactic definitions are defined recursively leading to the possibility of parsing with a recursive descent parser, which is not as powerful as LALR. But LALR might still be an appropriate pragmatic choice.)

The case of user-defined functions whose names contain more than one character is, perhaps, slightly interesting. LaTeX will always typeset juxtaposed letters in a manner consistent with the juxtaposition being a multiplication. Hence, $$find(\pi/2)$$ (find(\pi/2)) looks quite different from the use of predefined operator like \sin ($$\sin(\pi/2)$$). Note that the latter is written with a backslash; \sin is the keyword, not sin.

In LaTeX, you can define your own math operators with the DeclareMathOperator macro. That lets you write:

\DeclareMathOperator{\find}{find}


after which, you can use \find in your equations, producing $$\DeclareMathOperator{\find}{find}\find(\pi/2)$$. However, this feature is not handled by Wei Zhong's work, presumably because it was not useful for his problem (which does not require accurate parsing). Wei's parser only recognises specific LaTeX macros which have mathematical semantics. (These are listed in Appendix B of the thesis.) It ignores many other macros, more related to typography, as well as any user-defined macros. (Quote from page 37 of the thesis.)

Our lexer omits all LATEX control sequences not matching any pattern of our defined tokens, most of them are considered unrelated to math formula semantics.

Notes:

1. There is no universal convention to chose between $$\textrm{foo}(\pi/2)$$ and $$\textit{foo}(\pi/2)$$ (\textrm{foo} and \textit{foo}, respectively) to represent the application of a function named foo. But, at least in my opinion, $$foo(\pi/2)$$ (foo(\pi/2)) should never be used; the kerning is awful.

Apparently, there is an applicable ISO standard (ISO 80000-2:2019, in case you care) which seems to recommend the use of $$\textrm{foo}(\pi/2)$$ for cases where foo has been defined with a specific meaning. According to that document, cursive text ($$f(x)$$) should be used only for generic functions and variables.

I got the above information from this blog post by Nick Higham, which I found while I was writing this answer. Higham's post references the 2009 version of the standard, and includes a link to a more detailed summary by Claudio Becarri, written in 1997 and referencing a predecessor standard. Those resources are free, unlike the ISO standard, which costs CHF 166, or about five dollars per page.

• It's ISO 80000-2 section 3. Feb 4 at 1:29
• @Pseud: OK, added the document ID, and even a link for readers who have money to burn. Looking at the publicly-available excerpt, it seems like the relevant specifications are in section 4 of the current version.
– rici
Feb 4 at 2:46