Maximal munch

From Wikipedia, the free encyclopedia

[edit] Definition

In computer programming, the "maximal munch" principle is the rule that as much of the input as possible should be processed when creating some construct.

For instance, the lexical grammar for many programming languages requires that the next token be built from the maximum number of characters from the input stream (eg, in the C language, the three-character sequence <<= is the single token <<=, and not the three tokens <, < and =, or the two tokens << and =).

[edit] Algorithm

• Starting at the root of the tree, find the largest tile that fits.
• Cover the root node (and others ?) with this tile.
• Repeat for each uncovered subtree.
• Generate the corresponding instruction when the tree is fully covered.