Maximal munch
Disambiguazione – "longest match" rimanda qui. Se stai cercando l'algoritmo di routing, vedi longest prefix match.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[1] riguardante la generazione di codice macchina da parte dei compilatori.
Applicazioni
[modifica | modifica wikitesto]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.[2]
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.[3]
Effetti collaterali
[modifica | modifica wikitesto]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.[4] 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.[5]
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.[6] Ad esempio, compilando con uno standard precedente il C++11, il seguente codice produce un errore di sintassi:
std::vector<std::vector<int>> matrice_11; // Errato in C++03, corretto in C++11.
std::vector<std::vector<int> > matrice_03; // Corretto sia in C++03 sia in C++11.
Alternative
[modifica | modifica wikitesto]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.[7] 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.[8]
Note
[modifica | modifica wikitesto]- ^ R. G. G. Cattell, Formalization and Automatic Derivation of Code Generators, Pittsburgh, Carnegie Mellon University, PhD thesis, 1978.
- ^ Aho et al., p. 168.
- ^ Page, p. 470.
- ^ ISO/IEC 9899:1999, sez. 2.4, Preprocessing Tokens.
- ^ van der Linden, pp. 53-54.
- ^ Vandevoorde.
- ^ Van den Brand et al., p. 26.
- ^ Van Wyk et al., p. 63.
Bibliografia
[modifica | modifica wikitesto]- Alfred V. Aho, Monica S. Lam, Ravi Sethi e Jeffrey D. Ullman, Compilers: Principles, Techniques & Tools, 2nd, Boston, Addison-Wesley, 2007, ISBN 978-0-321-48681-3.
- Daniel Page, Practical Introduction to Computer Architecture[collegamento interrotto], London, Springer, 2009, ISBN 978-1-84882-255-9.
- Mark G.J. Van den Brand, Jeroen Scheerder, Jurgen J. Vinju e Eelco Visser, Disambiguation Filters for Scannerless Generalized LR Parsers [collegamento interrotto], in Lecture Notes in Computer Science, vol. 2304/2002, Berlin/Heidelberg, Springer, 2002, pp. 21–44, DOI:10.1007/3-540-45937-5_12, ISSN 0302-9743.
- Peter Van der Linden, Expert C Programming: Deep C Secrets, Prentice Hall, 1994, ISBN 978-0-13-177429-2.
- Daveed Vandevoorde, Right Angle Brackets, su open-std.org, 14 gennaio 2005. URL consultato il 31 marzo 2010.
- Eric Van Wyk e August Schwerdfeger, Context-Aware Scanning for Parsing Extensible Languages, in GPCE '07: Proceedings of the 6th international conference on Generative programming and component engineering, New York, ACM, 2007, pp. 63–72, DOI:10.1145/1289971.1289983.
