 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Algorithmic Forays Part 2 |
|
 |
Kentaro Member since: 11/28/2002 From: Canada |
|||
 Posted - 3/29/2004 9:19:43 PM |
||||
| Ummmm... the example of the FSM that recognizes xy* is incorrect. An example of a string not in the language of xy* that is accepted by the example FSM is "xyyxx" (follow the diagram and see). This is because of the way the transition function is defined in the diagram. I can't draw a diagram so I'll give the correct state transitions in terms of ordered pairs... (0, 'x') -> 1 (1, 'y') -> 1 All other (undefined) transitions cause the machine to "die" and not accept the string. This could be defined in terms of a dead state (call it 2) where (2, a) -> 2 for a an element of the alphabet of the FSM. Over the centuries, mankind has tried many ways of combating the forces of evil...prayer, fasting, good works and so on. Up until Doom, no one seemed to have thought about the double-barrel shotgun. Eat leaden death, demon... -- Terry Pratchett |
||||
|
||||
|
Aprosenf Member since: 5/8/2001 From: USA |
|||
|
Posted - 3/29/2004 10:58:59 PM |
||||
| Yeah, the diagram actually represents (y*xy*x)*y*xy*. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 3/30/2004 5:54:19 AM |
||||
| Great work on explaining the basics behind a interpreter/compiler. I haven't read the entire article, so, I may have overlooked, but you should tell ppl that what you're doing has already been done millions of times, and that there are really good implementations of lexical and grammatical scanners arounf (lex/flex/bison/yacc). It's good to know the principles behind a tool to better use it, but warn ppl to not to reinvent the weel. just my 2 cents |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 3/30/2004 5:59:16 AM |
||||
| Are those usable in any language? What about people programming in, say Visual Basic, who want to implement parsing of this sort? |
||||
|
||||
|
BitMaster Member since: 8/9/2000 From: Cologne, Germany |
|||
|
Posted - 3/30/2004 6:11:08 AM |
||||
| (f)lex, yacc and bison generate C or (halfheartedly) C++ code. Java has JavaCC. AntLR is implemented for several languages, including C++ and Java. There are probably regex parsers and grammar generators out for every language, but these are the ones I know and used. |
||||
|
||||
|
spur4444 Member since: 3/9/2004 From: Haifa, Holy Land |
|||
|
Posted - 3/30/2004 1:39:08 PM |
||||
| Thanks for spotting the mistake. I already fixed the article and sent the updated version to GameDev. Hope they'll upload it soon. Guys, I'm not trying to compete with Lex, Perl or grep here. I want to demonstrate how FSMs work, what uses they have and how to implement them. As a side effect, I think the articles serve as a nice introduction to regular expressions and how those "tick". |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 3/31/2004 5:58:23 AM |
||||
| Hi again, I was not bashing your work. As I (and you) said, its a great source for understanding FSMs. I was only telling you that you should refer compiler compilers, interpreters and parsers in your article for two reasons: 1 - it allows ppl who want to understand the "behind the scenes" of these tools, to know that your articles talk about it. 2 - it allows ppl who first came in contact with FSM machines, that there are great tools that explore this subject. Just my two cents, DC |
||||
|
||||
 |
davepermen GDNet+ Member since: 3/31/2000 From: Augst, Switzerland |
|||
|
Posted - 3/31/2004 6:10:31 AM |
||||
| i knew yet fsm. but thanks a lot for the regex part. i never grasped regex so far, how it works, and how to use. you helped me yet quite a bit, can't wait for the next one. If that's not the help you're after then you're going to have to explain the problem better than what you have. - joanusdmentia davepermen.net |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 4/1/2004 1:25:57 AM |
||||
| Aside from parsing tools, the standard C library has some regular expression support. Check out regex.h and the functions regcomp() and regexec(). With these tools you can basically write your own grep program in under a dozen lines of code. I would recommend using these instead of building a finite state minutes from scratch. It's faster to code, less error-prone, and a FSM is built when regcomp is called, so it runs fairly fast. |
||||
|
||||
 |
Fruny Moderator Member since: 11/16/2001 From: Paris, France |
|||
|
Posted - 4/1/2004 7:32:27 PM |
||||
quote: It's not part of the standard C library, but of the GNU platform, just like conio.h is part of the DOS platform. “Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” — Brian W. Kernighan |
||||
|
||||
|
spur4444 Member since: 3/9/2004 From: Haifa, Holy Land |
|||
|
Posted - 4/2/2004 5:22:29 AM |
||||
quote: Hello there, 1) As far as I know, this code is not part of the standard C library. There are, however, free and high level regexp libraries for C++ and C online. 2) My goal is to explain how these things work on the inside. I could use libraries to parse regexes, but then I could also use Lex or Perl and just get over with it. This is obviously not my goal :-) |
||||
|
||||
|
Aprosenf Member since: 5/8/2001 From: USA |
|||
|
Posted - 4/2/2004 2:25:35 PM |
||||
| I hate to be a killjoy, but the updated FSM is still not entirely correct. It now represents y*xy*, not xy*. To make it represent xy*, you'd have to change the (y that goes from node 0 to node 0) to (y that goes from node 0 to node 2). |
||||
|
||||
|
spur4444 Member since: 3/9/2004 From: Haifa, Holy Land |
|||
|
Posted - 4/11/2004 12:54:17 AM |
||||
| Thanks a lot ! |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 4/16/2004 2:21:48 PM |
||||
.... still waiting on part 3; that's where the good stuffs at.  |
||||
|
||||
|
Seriema Member since: 6/15/2001 From: Stockholm, Sweden |
|||
 Posted - 11/9/2004 11:51:56 AM |
||||
| Hi! I'm finally getting around to read these articles :) I usually just comment the code, heh bad habit :P So here it is: bool is_final_state(fsm_state state) { return (state == 3) ? true : false; } O_o hehe that's like: if true return true, elseif false return false :P just return state==3; But in move() you could use the ? : quite nicely. Just look at all the case's. case 0: if (input == 'a') { return 1; } else if (input == 'b') { return 0; } break; --- could easily become case 0 : return (input == 'a') ? 1 : 0; break; You did assert for any other char, so it can only be 'a' or 'b'. No need to be extra careful with that. (even though this is like the above, you're not returning a bool. and even though true==1 and false==0, I prefer to use int's to be explicit) bool recognize(string str) { if (str == "") return false; You should check string::empty(), i.e. if( str.empty() ) return false; Otherwise it was nice. Maybe a bit short, since many articles have several chapters when covering a topic you've split it into several articles. I would prefer to see one about regex/FSM artcile of 3+ sections/chapters than split amongst several articles. But maybe that's just me :) See ya in the other articles, have to get to nr 6 which is the newest at the moment ;) [ ThumbView: Adds thumbnail support for DDS, PCX, TGA and 16 other imagetypes for Windows XP Explorer. ] [ Chocolate peanuts: Brazilian recipe for home made chocolate covered peanuts. Pure coding pleasure. ] |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 2/11/2005 7:24:27 PM |
||||
| Is it or just me or the (a|b)*abb FSM would also come to an early end if the expression was abbabb ? Curious |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
