Re:I'm graduating with a CS degree but I don't feel like I k...
by bad_user on Friday February 04, 2011 @11:02AM
(#2179867)
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 :))
Re:I'm graduating with a CS degree but I don't feel like I k...
by johanbev on Friday February 04, 2011 @11:10AM
(#2179900)
Aaahhh, ofc, now I see why that wouldnt work. Guess I learn something every day :)
Re:I'm graduating with a CS degree but I don't feel like I k...
by stcredzero on Friday February 04, 2011 @10:51AM
(#2179803)
Wouldn't that still be a finite state automata?
The key is the bit about the "recursive call."
Re:I'm graduating with a CS degree but I don't feel like I k...
by cynicalkane on Friday February 04, 2011 @11:56AM
(#2180083)
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.
Re:I'm graduating with a CS degree but I don't feel like I k...
by bad_user on Friday February 04, 2011 @12:50PM
(#2180340)
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.
Re:I'm graduating with a CS degree but I don't feel like I k...
by stcredzero on Friday February 04, 2011 @12:15PM
(#2180182)
Yes, thanks for exposing yet another Comp Sci fundamental tidbit. Any word deriving from "recursive" should be a red flag in this case.
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.