title: Maximal munch
text: # Maximal munch
  
  In informatica si definisce maximal munch (in lingua inglese può tradursi come massima ingestione) o longest match (corrispondenza più lunga) un procedimento che ad ogni iterazione, tra diverse alternative possibili, sceglie quella che consuma la maggior quantità di input.
  
  Un riferimento alla locuzione si trova già in una tesi di dottorato del 1978 presso l'Università Carnegie Mellon riguardante la generazione di codice macchina da parte dei compilatori.
  
  ## Applicazioni
  
  Molte regex hanno diversi possibili match sullo stesso input (ad esempio [a-z]+ in abcde può individuare a, ab, abc, abcd o abcde), per cui tipicamente i regex matcher per impostazione predefinita restituiscono la più lunga corrispondenza possibile. Nella compilazione e traduzione del codice, molti lexer costruiscono i token usando il maggior numero possibile di caratteri dallo stream di input.
  
  Nel processo di selezione delle istruzioni l'espressione è usata per indicare un metodo di tiling, ovvero un procedimento per convertire in codice macchina un albero che descrive un programma in rappresentazione intermedia. Un intero sottoalbero può essere convertito in una sola istruzione, e il problema consiste nel suddividere l'albero in tile che non si sovrappongono, ognuna delle quali rappresenta una istruzione macchina. Una strategia efficace, detta appunto maximal munch, consiste nel creare una tile con il più ampio sottoalbero possibile ad ogni iterazione.
  
  ## Effetti collaterali
  
  Il maximal munch, analogamente agli algoritmi greedy, non è sempre la soluzione ottimale, e può avere effetti collaterali o indesiderati. Ad esempio, lo standard ISO C prevede che nel preprocessing ogni token debba essere generato con la più lunga sequenza di caratteri che costituisce un token valido, anche se questo comporta il fallimento dell'analisi lessicale. Come conseguenza, l'istruzione x=y/*z; (senza spazi) dove x e y sono variabili int e z è un puntatore a int può causare un errore sintattico, in quanto /* viene interpretato come l'apertura di un commento (che può andare a chiudersi sul tag di chiusura di un commento successivo, se presente, in quanto in C i commenti non si annidano), nonostante la stessa istruzione con l'aggiunta degli spazi rappresenti una divisione di y per il valore di ritorno dell'operatore che dereferenzia il puntatore z.
  
  Un esempio analogo in C++ è legato alle parentesi angolate < e > nella sintassi dei template. Se sono presenti due template annidati, i compilatori precedenti lo standard C++11 interpretano la sequenza di caratteri >> come l'operatore di shift binario verso destra, per cui le due parentesi di chiusura devono necessariamente essere separate da uno spazio. Ad esempio, compilando con uno standard precedente il C++11, il seguente codice produce un errore di sintassi:
  
  ## Alternative
  
  Un approccio alternativo al maximal munch è l'impiego di "follow restrictions", che non prendono direttamente la corrispondenza più lunga ma valutano alcune restrizioni su cosa può seguire dopo una corrispondenza valida. Ad esempio, stabilire che una corrispondenza valida della regex [a-z]+ non può essere seguita da una lettera ASCII minuscola ha lo stesso effetto del maximal munch. Un altro approccio prevede di mantenere il principio di maximal munch, ma subordinato ad un altro principio, come il contesto: in questo modo, ad esempio, l'operatore di shift a destra in Java non è ambiguo con due parentesi angolari chiuse nella sintassi dei generics.
  
  