Maximal munch

In computer programming and computer science, "maximal munch" or "longest match" is the principle that when creating some construct, as much of the available input as possible should be consumed. It is similar, though not entirely identical, to the concept of a greedy algorithm.

Application

For instance, the lexical syntax of many programming languages requires that tokens be built from the maximum possible number of characters from the input stream. This is done to resolve the problem of inherent ambiguity in commonly used regular expressions such as [a-z]+ (one or more lower-case letters).^[1]

The term has also been used in the field of compilers to describe a process of "tiling" — determining how a structured tree representing a program in an intermediate language should be converted into linear machine code. An entire subtree might be converted into just one machine instruction, and the problem is how to split the tree into non-overlapping "tiles," each representing one machine instruction. An effective strategy is simply to make a tile of the largest subtree possible at any given point, which is called "maximal munch."^[2]

Drawbacks

In some situations, "maximal munch" leads to undesirable or unintuitive outcomes. For example, C++ uses the "angle bracket" characters < and > in the syntax for template specialization, but two consecutive > characters are interpreted as the right-shift operator >>.^[3] Prior to C++11, the following code would produce a parse error, because the right-shift operator token is encountered instead of two right-angle-bracket tokens:

    // This is not valid syntax in standard C++.
    std::vector<std::vector<int>> incorrect;
    // Adding whitespace between the brackets yields the correct parse.
    std::vector<std::vector<int> > correct;

The C++11 standard adopted in August 2011 amended the grammar so that a right-shift token is accepted as synonymous with a pair of right-angle brackets, (as in Java,) which complicates the grammar but allows the continued use of the maximal munch principle.

Alternatives

Programming languages researchers have also responded by replacing or supplementing the principle of maximal munch with other lexical disambiguation tactics. One approach is to utilize "follow restrictions," which instead of directly taking the longest match will put some restrictions on what characters can follow a valid match. For example, stipulating that strings matching [a-z]+ cannot be followed by an alphabetic character achieves the same effect as maximal munch with that regular expression.^[4] Another approach is to keep the principle of maximal munch but make it subordinate to some other principle, such as context (e.g., the right-shift token in Java would not be matched in the context of a template expression, where it is syntactically invalid).^[5]

References

1. ^ Aho et al., 168.
2. ^ Page, 470.
3. ^ Vandevoorde.
4. ^ Van den Brand et al., 26.
5. ^ Van Wyk et al., 63.

Bibliography

• Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2007). Compilers: Principles, Techniques & Tools (2nd ed.). Boston: Addison-Wesley. ISBN 978-0-321-48681-1. 
• Page, Daniel (2009). Practical Introduction to Computer Architecture. London: Springer. ISBN 978-1-84882-255-9. http://www.springerlink.com/content/j10237532887k344/. 
• Van den Brand, Mark G.J.; Scheerder, Jeroen; Vinju, Jurgen J.; Visser, Eelco (2002). "Disambiguation Filters for Scannerless Generalized LR Parsers". Lecture Notes in Computer Science (Berlin/Heidelberg: Springer) 2304/2002: 21–44. doi:10.1007/3-540-45937-5_12. ISSN 0302-9743. http://www.springerlink.com/content/03359k0cerupftfh/. 
• Vandevoorde, Daveed (14 January 2005). "Right Angle Brackets". http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1757.html. Retrieved 31 March 2010. 
• Van Wyk, Eric; Schwerdfeger, August (2007). "Context-Aware Scanning for Parsing Extensible Languages". GPCE '07: Proceedings of the 6th international conference on Generative programming and component engineering (New York: ACM): 63–72. doi:10.1145/1289971.1289983. http://portal.acm.org/citation.cfm?id=1289983&dl=GUIDE,.