Regelbundna uttrycksmönster ger ett naturligt, deklarativt sätt att uttrycka begränsningar på halvstrukturerade data och att extrahera relevant information från dem. Det är faktiskt ett centralt inslag i programmeringsspråket Perl, ytor i olika UNIX-verktyg som sed och awk, och har nyligen föreslagits i samband med XML programmeringsspråket XDuce. Eftersom reguljära uttryck kan vara tvetydiga i allmänhet, har olika disambigeringspolitik föreslagits för att få en unik matchande strategi. Vi definierar formellt matchande semantik under både (1) POSIX, och (2) den första och längsta matcha disambigeringsstrategier. Vi visar att den allmänt accepterade metoden för att definiera den längsta matchen i termer av den första matchen och rekursionen inte överensstämmer med den naturliga uppfattningen om den längsta matchen. Vi fortsätter med att lösa problemet med typinferens för båda disambigeringsstrategierna, som består i att beräkna uppsättningen av alla deldelar av indatavärden en underuttryck kan matcha under den givna policyn.
Disambitionspolicyn kan vara subtil och studeras formellt i REF (inklusive POSIX och den första och längsta matchpolicyn).
Type inference for unique pattern matching
{'venue': 'TOPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}