4 ms·

The whole discussion at the end of part 2 feels so strage to me. >using the standard RE, it's impossible to match only DD-MM-YYYY or DDMMYYYY strings without m

The whole discussion at the end of part 2 feels so strage to me. >using the standard RE, it's impossible to match only DD-MM-YYYY or DDMMYYYY strings without matching DD-MMYYYY or DDMM-YYYY, because it's impossible to represent this in DFA form. And then there is the reader comment that finds a DFA for this particular problem but then wonders about another: > now whether one could also accept YYYY-MM-DD/YYYYMMDD format with the same regexps, it might require some sort of deeper magic and back-tracking Regular languages are closed under union and there is even a straightforward translation to regular expressions (the | operator). Am I really missing something here? It has been a long time since I took a compiler course, but I would be damned.

rstuart4133 5y ago
Your not missing anything, of course. They are also closed under difference, ie R0 - R1, which means accept all the strings accepted by R0 that aren't accepted by R1. Its very useful. For example, a variable is a token that isn't a keyword can be written succinctly as: ([a-z_][a-z_0-9]*) - (if|then|else|while|for) Sadly, it was not part of the original re syntaxes so while common now it's not so well known, and the syntax varies wildly. For example, in VIM the above is: [a-z_][a-z_0-9]*$if\|then\|else\|while\|for$\@<! In Python and other pcre based matches like Perl it would be: [a-z_[a-z_][a-z_0-9]*(?<!if|then|else|while|for) They are also closed under conjunction, eg R0 & R1 matches strings that match both R0 and R1. Again it wasn't there in the first re packages and confusingly it (and difference) is called an "assertion" now. But there isn't a lot of difference between them and '|' - they are all just ways of composing regular expressions.
rurban 5y ago
The "impossible to represent in DFA" bit is unclear. It should say "without duplication". Some extended regular expressions are really only representable with backrefs, but not this one. No deeper magic needed, just duplication. A backref only matches the exact occurance, but here we can abstract the months and year variables and do the duplication with variables. In shell syntax just expand ${MM} and ${YYYY}, in C strlcpy the parts together to arrive at [0123][0-9](-(Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)-(19|20)[0-9]{2}|(Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)(19|20)[0-9]{2})

rstuart4133 5y ago

Your not missing anything, of course. They are also closed under difference, ie R0 - R1, which means accept all the strings accepted by R0 that aren't accepted by R1. Its very useful. For example, a variable is a token that isn't a keyword can be written succinctly as: ([a-z_][a-z_0-9]*) - (if|then|else|while|for) Sadly, it was not part of the original re syntaxes so while common now it's not so well known, and the syntax varies wildly. For example, in VIM the above is: [a-z_][a-z_0-9]*$if\|then\|else\|while\|for$\@<! In Python and other pcre based matches like Perl it would be: [a-z_[a-z_][a-z_0-9]*(?<!if|then|else|while|for) They are also closed under conjunction, eg R0 & R1 matches strings that match both R0 and R1. Again it wasn't there in the first re packages and confusingly it (and difference) is called an "assertion" now. But there isn't a lot of difference between them and '|' - they are all just ways of composing regular expressions.

rurban 5y ago

The "impossible to represent in DFA" bit is unclear. It should say "without duplication". Some extended regular expressions are really only representable with backrefs, but not this one. No deeper magic needed, just duplication. A backref only matches the exact occurance, but here we can abstract the months and year variables and do the duplication with variables. In shell syntax just expand ${MM} and ${YYYY}, in C strlcpy the parts together to arrive at [0123][0-9](-(Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)-(19|20)[0-9]{2}|(Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec)(19|20)[0-9]{2})