4 ms·

I agree with the general gist of your post, but I should point out that all finite languages are regular. So while potentially infinite HTML documents cannot be

by nmadden 11y ago

I agree with the general gist of your post, but I should point out that all finite languages are regular. So while potentially infinite HTML documents cannot be parsed by regular expressions, they don't turn up very often.

colanderman 11y ago
You're missing the distinction between a finite language, and an arbitrarily large finite production of an infinite language. No-one cares about "infinite HTML documents". I don't even think the Chomskyan hierarchy concerns itself with languages with "infinite" productions. All you have to worry about is infinite languages -- i.e., languages with arbitrarily large productions. There's a key difference between "infinite" and "arbitrarily large": the latter is quantifiable. While indeed to can build a regular expression to match any finite subset of HTML, it can only match HTML documents up to some fixed size. I can always give you a (finite!) document that is one tag deeper that your regex will choke on. "But recursive parsers have the same issue!" you say. "Their stack will run out of memory at some point!" Yes, but they have a key difference: the amount of stack (memory) they require is bounded by the size of the document. This is not true for a regular expression! In fact, not only would a regular expression to match a given subset of HTML require memory exponentially proportional† to the size of the document, the automata itself would be similarly massive! I really wish someone came up with and promulgated a concise handy built-in ubiquitious equivalent of regular expressions for, say, PEGs. The closest I've seen are DCGs in Prolog. Would make so many parsing problems more easy to do correctly! † It's possible I'm wrong about this since it's early morning and I'm basing this off my intuition rather than a proof. The part about the automata itself being exponential w/r/t the size of the document is definitely true though.
- nmadden 11y ago
  You can't always give me a larger HTML document - eventually you will run out of usable universe. Yes, I should have said 'bounded by some finite maximum size' rather than just finite, but it's not a great leap to see that in reality all documents will be bounded by such a maximum. Finite state automata do indeed need an exponentially larger number of states compared to a pushdown automata, I made no claim as to efficiency. The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation.
  - colanderman 11y ago
    For practical purposes, expressing your language using an exponentially large number of states is, for the very reasons you state, untenable.
    - nmadden 11y ago
      Sure, but that doesn't change the fact that you cannot implement anything at all that accepts more than a regular language. In practice, however you implement it, you will have only implemented something equivalent to some finite state machine (due to the finite memory available to you).
  - minitech 11y ago
    > The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation. This is thoroughly wrong. For “all practical purposes”, you won’t expand a non-regular language into a giant regular one with an emulated state.
    - nmadden 11y ago
      You are confusing regular language with finite state machine. I don't know why there is so much resistance to this. All real machines have bounded memory available to them, thus they can only accept regular languages. Therefore, regular expressions are as powerful as any machine in existence.
      - nmadden 11y ago
        Thinking about this some more, there is no reason that a large number of states has to have a proportional amount of memory. If the states are represented in binary notation (thus needing logarithmic number of bits) and the state transition function is represented as a binary decision diagram then this could be quite compressed indeed.
        minitech 11y ago

by nmadden 11y ago

colanderman 11y ago

You're missing the distinction between a finite language, and an arbitrarily large finite production of an infinite language. No-one cares about "infinite HTML documents". I don't even think the Chomskyan hierarchy concerns itself with languages with "infinite" productions. All you have to worry about is infinite languages -- i.e., languages with arbitrarily large productions. There's a key difference between "infinite" and "arbitrarily large": the latter is quantifiable. While indeed to can build a regular expression to match any finite subset of HTML, it can only match HTML documents up to some fixed size. I can always give you a (finite!) document that is one tag deeper that your regex will choke on. "But recursive parsers have the same issue!" you say. "Their stack will run out of memory at some point!" Yes, but they have a key difference: the amount of stack (memory) they require is bounded by the size of the document. This is not true for a regular expression! In fact, not only would a regular expression to match a given subset of HTML require memory exponentially proportional† to the size of the document, the automata itself would be similarly massive! I really wish someone came up with and promulgated a concise handy built-in ubiquitious equivalent of regular expressions for, say, PEGs. The closest I've seen are DCGs in Prolog. Would make so many parsing problems more easy to do correctly! † It's possible I'm wrong about this since it's early morning and I'm basing this off my intuition rather than a proof. The part about the automata itself being exponential w/r/t the size of the document is definitely true though.

nmadden 11y ago
You can't always give me a larger HTML document - eventually you will run out of usable universe. Yes, I should have said 'bounded by some finite maximum size' rather than just finite, but it's not a great leap to see that in reality all documents will be bounded by such a maximum. Finite state automata do indeed need an exponentially larger number of states compared to a pushdown automata, I made no claim as to efficiency. The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation.
- colanderman 11y ago
  For practical purposes, expressing your language using an exponentially large number of states is, for the very reasons you state, untenable.
  - nmadden 11y ago
    Sure, but that doesn't change the fact that you cannot implement anything at all that accepts more than a regular language. In practice, however you implement it, you will have only implemented something equivalent to some finite state machine (due to the finite memory available to you).
- minitech 11y ago
  > The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation. This is thoroughly wrong. For “all practical purposes”, you won’t expand a non-regular language into a giant regular one with an emulated state.
  - nmadden 11y ago
    You are confusing regular language with finite state machine. I don't know why there is so much resistance to this. All real machines have bounded memory available to them, thus they can only accept regular languages. Therefore, regular expressions are as powerful as any machine in existence.
    - nmadden 11y ago
      Thinking about this some more, there is no reason that a large number of states has to have a proportional amount of memory. If the states are represented in binary notation (thus needing logarithmic number of bits) and the state transition function is represented as a binary decision diagram then this could be quite compressed indeed.
      - minitech 11y ago