2 ms·

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 bi

by 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
Interesting idea! Wait, here’s another: maybe you could take your regular grammar that accepts some large number of things that a context-free grammar it’s emulating would accept, and implement it using a stack or something. That would save space and remove the arbitrary restriction.
- nmadden 11y ago
  Well you can keep picking nits about implementation choices, but unless your stack can grow unbounded (because you have unlimited resources) then you haven't implemented a PDA and haven't removed any restriction at all. You've just optimised space usage. If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence.
  - minitech 11y ago
    > If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence. You can build a regular expression to match any HTML document to any fixed depth. Set that to whatever you think “all web browsers” limit HTML nesting to “in practice” – citation very much needed, I don’t believe they do – and voilà! You have produced something absolutely useless and probably several million characters long. I don’t know what you’re arguing. I don’t think you know what you’re arguing either. It’s pointless to continue talking.
    - nmadden 11y ago
      For example, see this old commit setting the WebKit maximum nesting depth to 2048. I am told it is 512 by default today. https://www.mail-archive.com/webkit-changes@lists.webkit.org/msg02599.html https://www.mail-archive.com/webkit-changes@lists.webkit.org... I'm fairly certain all browsers will impose such a limit or risk blowing their stack and crashing. Turns out there are advantages to setting upper bounds after all. Who'da thunk? Regarding the BDD approach, it looks like somebody already implements it with excellent performance and memory characteristics: http://www.cs.rutgers.edu/~vinodg/papers/raid2010/raid2010_slides.pps http://www.cs.rutgers.edu/~vinodg/papers/raid2010/raid2010_s... Of course, the point (if you read back) was not to say that you should use REs for all parsing. Just merely to correct a commonly repeated mistake that 'REs cannot parse HTML'. They can do so just fine.
      - minitech 11y ago
        Ah, okay. That’s much more straightforward. The answer, though, remains that regular expressions that are actually regular cannot parse HTML that is actually HTML. Regular expressions can parse HTML up to a certain depth specified in advance – which is not the definition of HTML.
        nmadden 11y ago
        Now we are definitely going in circles.

by nmadden 11y ago

minitech 11y ago

Interesting idea! Wait, here’s another: maybe you could take your regular grammar that accepts some large number of things that a context-free grammar it’s emulating would accept, and implement it using a stack or something. That would save space and remove the arbitrary restriction.

nmadden 11y ago
Well you can keep picking nits about implementation choices, but unless your stack can grow unbounded (because you have unlimited resources) then you haven't implemented a PDA and haven't removed any restriction at all. You've just optimised space usage. If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence.
- minitech 11y ago
  > If you really believe that regular expressions cannot parse any HTML document in reality (eg given that all web browsers in practice limit the nesting depth of HTML) then please present some evidence. You can build a regular expression to match any HTML document to any fixed depth. Set that to whatever you think “all web browsers” limit HTML nesting to “in practice” – citation very much needed, I don’t believe they do – and voilà! You have produced something absolutely useless and probably several million characters long. I don’t know what you’re arguing. I don’t think you know what you’re arguing either. It’s pointless to continue talking.
  - nmadden 11y ago
    For example, see this old commit setting the WebKit maximum nesting depth to 2048. I am told it is 512 by default today. https://www.mail-archive.com/webkit-changes@lists.webkit.org/msg02599.html https://www.mail-archive.com/webkit-changes@lists.webkit.org... I'm fairly certain all browsers will impose such a limit or risk blowing their stack and crashing. Turns out there are advantages to setting upper bounds after all. Who'da thunk? Regarding the BDD approach, it looks like somebody already implements it with excellent performance and memory characteristics: http://www.cs.rutgers.edu/~vinodg/papers/raid2010/raid2010_slides.pps http://www.cs.rutgers.edu/~vinodg/papers/raid2010/raid2010_s... Of course, the point (if you read back) was not to say that you should use REs for all parsing. Just merely to correct a commonly repeated mistake that 'REs cannot parse HTML'. They can do so just fine.
    - minitech 11y ago
      Ah, okay. That’s much more straightforward. The answer, though, remains that regular expressions that are actually regular cannot parse HTML that is actually HTML. Regular expressions can parse HTML up to a certain depth specified in advance – which is not the definition of HTML.
      - nmadden 11y ago
        Now we are definitely going in circles.