4 ms·

I'm going to play devil's advocate here, and point out that you can actually construct the proper automaton where the transition conditions are decided by regul

I'm going to play devil's advocate here, and point out that you can actually construct the proper automaton where the transition conditions are decided by regular expressions. It might work like this: some programmer working on the project realizes something can't be parsed in a finite state machine, and 'cleverly' separates out one batch of regular expressions into a loop/recursive call. Repeat until the programmers are satisfied with the number of conditions they can handle. I've seen software that was actually written like this. Fortunately, the language it was designed to parse was pretty simple.

stcredzero 16y ago
I'm going to play devil's advocate here, and point out that you can actually construct the proper automaton where the transition conditions are decided by regular expressions. It might work like this: some programmer working on the project realizes something can't be parsed in a finite state machine, and 'cleverly' separates out one batch of regular expressions into a loop/recursive call In this case, you've created an "Augmented Transition Network" which is equivalent in power to a stack machine or a Context Free Grammar. Is this really playing devil's advocate? That would imply setting up something that isn't a straw man whose solution isn't basic automata theory. This also gives you an idea of how broken the project was, since my understanding is that they'd fix "that particular bug" and keep writing more regular expressions.
- cynicalkane 16y ago
  The implication was that the project couldn't succeed because the management didn't understand basic automata theory, and insisted the programmers use only regular expressions. Presumably the regular expressions were being invoked by a Turing-complete programming language. Unless management decided that Turing-complete programming languages were not allowed, as well.
  - stcredzero 16y ago
    Amazing how often Turing-complete programming languages aren't utilized to their full potential. (And for the record, no I wasn't on that project. I have a CS degree and I remember automata.)
johanbev 16y ago
Wouldn't that still be a finite state automata? You can create a submachine representing the regular expression transition conditions, and just attach that at the state you wanted, resulting in a finite state machine. Of course this doesn't hold when you are talking about non-standard regular expressions, and it's probably a nice feature to have when creating the automata, but IMHO it still sounds like a silly idea when CFG-tools like ANTLR and YACC are available.
- stcredzero 16y ago
  Wouldn't that still be a finite state automata? The key is the bit about the "recursive call."
  - cynicalkane 16y ago
    It doesn't have to be recursive. Iteration can also be non-finite-state. In fact, all recursive programs can be transformed to iterative ones.
    - stcredzero 16y ago
      Yes, thanks for exposing yet another Comp Sci fundamental tidbit. Any word deriving from "recursive" should be a red flag in this case.
    - bad_user 16y ago
      Actually recursion in CS is equivalent to using a stack that keeps intermediate values and that grows in relation to the input. If you've got an algorithm that does that, then it cannot be called "iterative". I.e. backtracking is recursive, no matter how you implement it. In school textbooks they do differentiate between "recursive" and "iterative" backtracking, to teach you how to get rid of the call-stack and manage your own. But that's another story.
- bad_user 16y ago
  Wouldn't that still be a finite state automata? He mentioned recursion, so no :-) I also hate working with ANTLR/YACC ... heavy, hard to start with, steep learning curve. These tools are designed for industrial-strength compilers, where performance / flexibility matters. And PEGs are better than CFGs (that's teeshirt material right there :))

stcredzero 16y ago

I'm going to play devil's advocate here, and point out that you can actually construct the proper automaton where the transition conditions are decided by regular expressions. It might work like this: some programmer working on the project realizes something can't be parsed in a finite state machine, and 'cleverly' separates out one batch of regular expressions into a loop/recursive call In this case, you've created an "Augmented Transition Network" which is equivalent in power to a stack machine or a Context Free Grammar. Is this really playing devil's advocate? That would imply setting up something that isn't a straw man whose solution isn't basic automata theory. This also gives you an idea of how broken the project was, since my understanding is that they'd fix "that particular bug" and keep writing more regular expressions.

cynicalkane 16y ago
The implication was that the project couldn't succeed because the management didn't understand basic automata theory, and insisted the programmers use only regular expressions. Presumably the regular expressions were being invoked by a Turing-complete programming language. Unless management decided that Turing-complete programming languages were not allowed, as well.
- stcredzero 16y ago
  Amazing how often Turing-complete programming languages aren't utilized to their full potential. (And for the record, no I wasn't on that project. I have a CS degree and I remember automata.)

johanbev 16y ago

Wouldn't that still be a finite state automata? You can create a submachine representing the regular expression transition conditions, and just attach that at the state you wanted, resulting in a finite state machine. Of course this doesn't hold when you are talking about non-standard regular expressions, and it's probably a nice feature to have when creating the automata, but IMHO it still sounds like a silly idea when CFG-tools like ANTLR and YACC are available.

stcredzero 16y ago
Wouldn't that still be a finite state automata? The key is the bit about the "recursive call."
- cynicalkane 16y ago
  It doesn't have to be recursive. Iteration can also be non-finite-state. In fact, all recursive programs can be transformed to iterative ones.
  - stcredzero 16y ago
    Yes, thanks for exposing yet another Comp Sci fundamental tidbit. Any word deriving from "recursive" should be a red flag in this case.
  - bad_user 16y ago
    Actually recursion in CS is equivalent to using a stack that keeps intermediate values and that grows in relation to the input. If you've got an algorithm that does that, then it cannot be called "iterative". I.e. backtracking is recursive, no matter how you implement it. In school textbooks they do differentiate between "recursive" and "iterative" backtracking, to teach you how to get rid of the call-stack and manage your own. But that's another story.
bad_user 16y ago
Wouldn't that still be a finite state automata? He mentioned recursion, so no :-) I also hate working with ANTLR/YACC ... heavy, hard to start with, steep learning curve. These tools are designed for industrial-strength compilers, where performance / flexibility matters. And PEGs are better than CFGs (that's teeshirt material right there :))