Best way to parse a string in C/C++

[earlofqb]

Just a quick question for you that came up whilst designing a game:

What is the best way for a beginner to parse a string in C/C++ (either one, the game isn't even started yet. If it helps you at all, I do lean towards writing it in C++ however)?

[earlofqb]

Hello? Anyone?

So far the "best" method I've found includes looping through the string until you hit a null character ("") and throwing a pointer at that spot. Then you repeat for all the spaces (put a pointer at the beginning of each new word). It seems to me this is terribly ineffective, even if pointers use up relatively small amounts of memory to point to things.

So, anyone (Mik, Ild? Stroustrup even?)?

[Ildûrest]

All I can say is, it is dependent on what it is you're actually parsing and what you need to get out of it, but I'll assume it's a kind of text-adventurey thing.

In which case you could just parse it one cute character at a time. Each new character narrows down the list of possibilities; if you hit a space you've got to have just covered a complete word that matches your dictionary somewhere. Then start on the next word.

All you really need is a nice structure containing pointers into your dictionary thing (pointers that get filled in as each word is parsed). Everything typed must have a verb, some verbs need direct objects, some verbs need indirect objects, and of course you may wish to add numbers and "wildcards" into the mix.

Just to recap - as you parse you find everything starting with the word so far; each new letter narrows down the possibilities. Hitting a space checks if you've got a match; if you do then you store a pointer to the entry for that particular word. If there's no match you of course inform the user that they were not understood. And of course a few words have grammatical function like "with". I know that isn't the whole story but it's close enough for now.

Oh yes, and in case it wasn't clear - the string will only be scanned once and you never need to go back.


C style strings are unbeatable for copy/output speed. But for concatenation and most string manipulation, they get slow and bulky, which of course grows more severe with size. (For error and status messages C strings are perfect.)

By "C style string" of course I mean something which is manipulated with strcpy() and printf() and all the standard print functions that expect null-terminated character arrays.

- I am not referring to all character pointers. (char *) is a very useful little thing and can be used for making your own type of string suited to the occasion - my usual choice is one pointer to the start and one to the end. (Yes, and of course there's the C++ string class)

Yeah, anyway. Too tired to rant any more.

[earlofqb]

No!!! I need more!!! More ranting, please!

Anyway, I just bought C++ for Dummies, we'll see if it'll help (oddly enough, they had C for Dummies, but the thing costs twice as much. Sort of remniscient of the Hitchiker's Guide paradox: buy something worthless because it's cheaper ). I have C++ next semester, so I'll use that as my "official" excuse for buying a worthless book. Hopefully I'll also learn something there...

[Mikrondel]

Ranting? OK

>UNLOCK DOOR WITH RED KEY
>OPEN DOOR

In this case, unlock takes a direct object (door) and indirect object (red key), using the word "with" to indicate the indirect object. The word RED qualifies the key. If you only have one key in your inventory, "KEY" might be enough, but once you have more you need the qualifier.

In terms of parsing; the next thing after the verb becomes part of the direct object; if you hit WITH then everything after that becomes part of the indirect object. But as both can be composed of multiple words, you need to store all the words they might need, and the parser needs to figure out what kind of word it just read so that you can decide how it fits into the sentence structure. To add more features you might want to recognise IN/INTO (PUT BRICK INTO CHUTE) and so forth, though very few verbs will take this kind of object.

And then we come to:
OPEN DOOR WITH RED KEY

This should work the same as above, but in this case OPEN takes an object while above it didn't. (Though that's not the parser's concern.)