equal
deleted
inserted
replaced
70 expressions. They can be used for a very simple regular expression |
70 expressions. They can be used for a very simple regular expression |
71 matching algorithm. Sulzmann and Lu cleverly extended this algorithm |
71 matching algorithm. Sulzmann and Lu cleverly extended this algorithm |
72 in order to deal with POSIX matching, which is the underlying |
72 in order to deal with POSIX matching, which is the underlying |
73 disambiguation strategy for regular expressions needed in lexers. |
73 disambiguation strategy for regular expressions needed in lexers. |
74 Their algorithm generates POSIX values which encode the information of |
74 Their algorithm generates POSIX values which encode the information of |
75 \emph{how} a regular expression matched a string---that is, which part |
75 \emph{how} a regular expression matches a string---that is, which part |
76 of the string is matched by which part of the regular expression. In |
76 of the string is matched by which part of the regular expression. In |
77 this paper we give our inductive definition of what a POSIX value is |
77 this paper we give our inductive definition of what a POSIX value is |
78 and show $(i)$ that such a value is unique (for given regular |
78 and show $(i)$ that such a value is unique (for given regular |
79 expression and string being matched) and $(ii)$ that Sulzmann and Lu's |
79 expression and string being matched) and $(ii)$ that Sulzmann and Lu's |
80 algorithm always generates such a value (provided that the regular |
80 algorithm always generates such a value (provided that the regular |