4 ms·

This only works if you have a single type of parenthesis. Is that applicable to regex expressions in general that only ()’s can nest?

gpm 7y ago
As typically defined academically, yes. In the real world things might be more complex, but I think it would hold true for many implementations. Academically a regex is a string of of: - character literals - "epsilon" characters (meaning empty string) - "+" characters (which means either what we see before the + or what we see after the +, in real-world regex these are usually represented as | instead of + as well as used implicitly in constructs like [a-zA-Z]) - "*" characters (same meaning as in real-world regex) - And parentheses to allow controlling the order of operations
- Piskvorrr 7y ago
  In other words, "if we build a state machine which is different from a regex, it will perform differently than a regex would." That's trivially true, but is it interesting beyond restating "there is no Silver Bullet"?
  - gpm 7y ago
    Technically we aren't discussing the regex itself here but the syntax for defining a regex. You could use a different syntax for defining the same regex, and that syntax could have different properties. For instance you could use parantheses like racket where "(...)" and "[...]" have the same meaning, but "(...]" is not well formed syntax (if I remember my racket correctly). Using such a syntax to define regex a counter would no longer suffice to decide if a string is a regex.
deleted 7y ago
[deleted]
jessaustin 7y ago
You could have a stack of (paren-type, integer) pairs. If the paren has a different type than the top pair on the stack (or the stack is empty), push a new pair with the integer set to one. If the integer goes to zero, pop the pair. At the end of the expression, you have to have an empty stack.

4 ms·

This only works if you have a single type of parenthesis. Is that applicable to regex expressions in general that only ()’s can nest?

by dyarosla 7y ago

gpm 7y ago
As typically defined academically, yes. In the real world things might be more complex, but I think it would hold true for many implementations. Academically a regex is a string of of: - character literals - "epsilon" characters (meaning empty string) - "+" characters (which means either what we see before the + or what we see after the +, in real-world regex these are usually represented as | instead of + as well as used implicitly in constructs like [a-zA-Z]) - "*" characters (same meaning as in real-world regex) - And parentheses to allow controlling the order of operations
- Piskvorrr 7y ago
  In other words, "if we build a state machine which is different from a regex, it will perform differently than a regex would." That's trivially true, but is it interesting beyond restating "there is no Silver Bullet"?
  - gpm 7y ago
    Technically we aren't discussing the regex itself here but the syntax for defining a regex. You could use a different syntax for defining the same regex, and that syntax could have different properties. For instance you could use parantheses like racket where "(...)" and "[...]" have the same meaning, but "(...]" is not well formed syntax (if I remember my racket correctly). Using such a syntax to define regex a counter would no longer suffice to decide if a string is a regex.
deleted 7y ago
[deleted]
jessaustin 7y ago
You could have a stack of (paren-type, integer) pairs. If the paren has a different type than the top pair on the stack (or the stack is empty), push a new pair with the integer set to one. If the integer goes to zero, pop the pair. At the end of the expression, you have to have an empty stack.