regexp, string manipulations for tokenizer/parser

[rhaertel80]

I'm trying to use regular expressions in a tokenizer/parser I am writing. I basically need to test if a string matches a regular expression, starting at a certain index. Since this is a parser it must be efficient.

It would be tempting to try: preg_match($buffer, $pattern, $matches, PREG_OFFSET_CAPTURE, $index) with a pattern such as "/^[\w]+/". However, the document explains that this will not work (and I confirmed this).

The obvious answer would be to take the substr, but I'm worried about the efficiency of this operation as it will happen for almost every character in the string to match against. Without knowing for sure, I'll bet that each substr operation copies the (necessary) contents of the parent array--too much overhead for my application.

In C/C++, one might try passing the address of the start of the substring, i.e. (in C syntax) preg_match(&buffer[index], pattern, matches). I'm new to PHP, but I'm pretty sure this is not possible. Can anyone confirm this?

I also thought of using array_pop to permanently discard elements of the string (in which case index is no longer necessary). This doesn't appear to be legal in PHP either. Is there a way of accomplishing this (while keeping the string--otherwise I can't do regular expression matching).

Are there any other ways of doing this short of writing my own regular expression compiler?

Thanks in advance,
Robbie

[Weedpacket]

Just some thoughts:

Can tokens spread across multiple lines (eg. multiline strings, comments)? If no, then reading the input one line at a time would make a significant saving on internal storage (shortening the string with substr() would be easily feasible). If yes, then while reading, you could switch between several modes based on individual characters as they appear (I've seen a '"', I'll just keep buffering until I see another '"') and make one larger string out of all that (Seeing as this effectively scans the multiline token anyway, you could store it at this point and replace it in the rest of the code by some sort of placeholder, to be substituted for the original after it has been isolated from it surroundings.)

Extending the above; any characters that are flagged as whitespace? preg_split() each line on those and further reduce the size of the strings that have to go through regexp/substring matching. One especially convenient pattern to split on may be '/\b/', depending on the language.

Explicit tokens? Use strpos('return', $string)===0 to see if $string starts with "return" - then matching reduces to the task of seeing if the seventh character in the string is part of the same token or not. If not, then the token is "return". This would be much faster than a regexp match.

Basically it's breaking down one big string into a stream of smaller ones without actually damaging any tokens in the process (which is where character-by-character scanning gets ugly); ideally while the code is being read so that there never is an explicit "big string" (as soon as preg_split() has executed, for example, you would have both the original string and an array of pieces; I'm not certain, but I'm pretty sure that PHP will store the pieces as individual strings instead of as offsets/length pairs referencing the original).