3 ms·

Your semantics for question marks are wrong. Question marks matching zero or one characters are the semantics for IBM/Microsoft command interpreters, for reaso

by JdeBP 10y ago

Your semantics for question marks are wrong. Question marks matching zero or one characters are the semantics for IBM/Microsoft command interpreters, for reasons that go back all of the way to CP/M. (Strictly speaking the original semantics amounted to, because of the 8.3 field padding, question marks matching a character, the end of the string, or zero characters if immediately before the dot.) In POSIX, question marks match exactly one character, always. There's no need for backtracking. * http://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_13_01 http://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3...

E6300 10y ago
HN screwed up my comment. It's not supposed to be "question mark, a, question mark, a, ...". I meant to write "question mark, a, star, question mark, a, star, ...".
- JdeBP 10y ago
  That would be backtracking caused by those stars, not by the question marks. Hacker News didn't screw up the part where you wrote "wouldn't be able to handle question marks".
  - E6300 10y ago
    A pattern like "star a star a star a star" can be handled by the algorithm described in the article: > Consider the pattern "a star bx star cy star d". If we end the first star at the first bx, we have the rest of the name to find the cy and then the d. Using any later bx can only remove choices for cy and d; it cannot lead to a successful match that using the first bx missed. So we should implement a star bx star cy star d without any second-guessing, as “find a leading a, then find the earliest bx after that, then find the earliest cy after that, then find a trailing d, or else give up.” This algorithm doesn't work if the pattern has question marks.
    - rsc 10y ago
      Yes it does.
  - E6300 10y ago
    I made a type in my previous response. I wrote "can be handled" instead of "can't be handled". The algorithm described can't handle that case.

by JdeBP 10y ago

E6300 10y ago

HN screwed up my comment. It's not supposed to be "question mark, a, question mark, a, ...". I meant to write "question mark, a, star, question mark, a, star, ...".

JdeBP 10y ago
That would be backtracking caused by those stars, not by the question marks. Hacker News didn't screw up the part where you wrote "wouldn't be able to handle question marks".
- E6300 10y ago
  A pattern like "star a star a star a star" can be handled by the algorithm described in the article: > Consider the pattern "a star bx star cy star d". If we end the first star at the first bx, we have the rest of the name to find the cy and then the d. Using any later bx can only remove choices for cy and d; it cannot lead to a successful match that using the first bx missed. So we should implement a star bx star cy star d without any second-guessing, as “find a leading a, then find the earliest bx after that, then find the earliest cy after that, then find a trailing d, or else give up.” This algorithm doesn't work if the pattern has question marks.
  - rsc 10y ago
    Yes it does.
- E6300 10y ago
  I made a type in my previous response. I wrote "can be handled" instead of "can't be handled". The algorithm described can't handle that case.