Ruby Programming Language :: Partial Regular Expression Matching


	Partial Regular Expression Matching I would like to identify partial matching of a regular expression, for a stream of input, as described in the pcrepartial(3) manpage. Is this possible with ruby Regexp, or would I have to wrap (a piece of) pcre? (or implement my own regular expression engine, hah!) As an aside, what I am really trying to do is write a lexer that works on stream input, and can decide whether any of the eligible tokens match before reading EOF (which may be a long, long way off both in bytes and time). If you can think of another approach (that still uses regexes) that'd work too. Thanks 1. http://www.gammon.com.au/pcre/pcrepartial.html On Tue, May 22, 2007 at 03:20:04PM +0900, Hans Fugal wrote: > I would like to identify partial matching of a regular expression, for a > stream of input, as described in the pcrepartial(3) manpage. Is this > possible with ruby Regexp, or would I have to wrap (a piece of) pcre? > (or implement my own regular expression engine, hah!) It looks like someone has wrapped pcre already: http://raa.ruby-lang.org/project/pcre/ but that's quite old so you might need to fiddle with it a bit. > As an aside, what I am really trying to do is write a lexer that works > on stream input, and can decide whether any of the eligible tokens match > before reading EOF (which may be a long, long way off both in bytes and > time). If you can think of another approach (that still uses regexes) > that'd work too. Well, you can use regexps to distinguish a complete token from a partial one, simply by checking if it is followed by a character which is not part of the token. A little care is needed to handle EOF correctly - at worst you could just stick a sentinel character onto the end. A simple example, which matches (\w+) and (\s+) as tokens: require 'stringio' stream = StringIO.new("wibble bibble boing") token = "" chunk = stream.read(1) token << chunk if chunk loop do case token when /\A\w+/ match = $& when /\A\s+/ match = $& else puts "Syntax error here! " + token.inspect break end if match.size < token.size or chunk.nil? puts "Match token: " + token.slice!(0,match.size).inspect break if chunk.nil? else #puts "Partial match: " + token.inspect chunk = stream.read(1) token << chunk if chunk end end This should also work if you use, say, read(4096) instead of read(1), so it ought to be pretty efficient. Regards, Brian. - Hide quoted text - Brian Candler wrote: >> As an aside, what I am really trying to do is write a lexer that works >> on stream input, and can decide whether any of the eligible tokens match >> before reading EOF (which may be a long, long way off both in bytes and >> time). If you can think of another approach (that still uses regexes) >> that'd work too. > Well, you can use regexps to distinguish a complete token from a partial > one, simply by checking if it is followed by a character which is not part > of the token. A little care is needed to handle EOF correctly - at worst you > could just stick a sentinel character onto the end. > A simple example, which matches (\w+) and (\s+) as tokens: > require 'stringio' > stream = StringIO.new("wibble bibble boing") > token = "" > chunk = stream.read(1) > token << chunk if chunk > loop do > case token > when /\A\w+/ > match = $& > when /\A\s+/ > match = $& > else > puts "Syntax error here! " + token.inspect > break > end > if match.size < token.size or chunk.nil? > puts "Match token: " + token.slice!(0,match.size).inspect > break if chunk.nil? > else > #puts "Partial match: " + token.inspect > chunk = stream.read(1) > token << chunk if chunk > end > end > This should also work if you use, say, read(4096) instead of read(1), so it > ought to be pretty efficient. Well that works for \w+ an \s+, but what if you want to match /01+0/? You'd get a syntax error on 0111 even though it's a valid partial match. On Tue, May 22, 2007 at 03:20:04PM +0900, Hans Fugal wrote: > I would like to identify partial matching of a regular expression, for a > stream of input, as described in the pcrepartial(3) manpage. Is this > possible with ruby Regexp, or would I have to wrap (a piece of) pcre? > (or implement my own regular expression engine, hah!) > As an aside, what I am really trying to do is write a lexer that works > on stream input, and can decide whether any of the eligible tokens match > before reading EOF (which may be a long, long way off both in bytes and > time). If you can think of another approach (that still uses regexes) > that'd work too. Why not use rex? Also StringScanner may be helpful for this. - Hide quoted text - > Thanks > 1. http://www.gammon.com.au/pcre/pcrepartial.html On 5/22/07, Hans Fugal <fug@zianet.com> wrote: > Well that works for \w+ an \s+, but what if you want to match /01+0/? > You'd get a syntax error on 0111 even though it's a valid partial match. Han's I'm not sure I understand your use case. Perhaps you could provide some code as you would write it IF Ruby provided a match_partial method for Regexp. The normal use case for partial re matching is that you are processing interactively accumulated input, and want to check that what the user has typed in so far is a valid prefix for the valid inputs. As far as I can see the best way to do that with the current Ruby regexp engine is to write a regexp which fully matches all prefixes $ cat part_mat.rb full_pat = /^01+0/ part_pat = /^((0\|01+)0?)?$/ (%w(0 01 010 0100 011 0110 01100) << "").each do \|str\| m = part_pat.match(str) if m puts "\"#{str}\" partially matches as \"#{m.string}\"" else puts "\"#{str}\" does not match" end end $ ruby part_mat.rb "0" partially matches as "0" "01" partially matches as "01" "010" partially matches as "010" "0100" does not match "011" partially matches as "011" "0110" partially matches as "0110" "01100" does not match "" partially matches as "" It might be possible to take a regexp and automatically generate another regexp which will match it's prefixes. Might make an interesting rubyquiz. -- Rick DeNatale My blog on Ruby http://talklikeaduck.denhaven2.com/ On Wed, May 23, 2007 at 01:00:04AM +0900, Hans Fugal wrote: > Well that works for \w+ an \s+, but what if you want to match /01+0/? > You'd get a syntax error on 0111 even though it's a valid partial match. OK, I see the problem - it's not detecting the end of the expression, it's saying that this expression might match but only if the right characters were appended to the end of the source. In the general case I think you'd have to turn each RE into one which matches all possible prefixes, perhaps something like /(0(1+(0)?)?)/ # (note ) However, if you can guarantee that no individual valid token is going to be longer than a certain size (let's say 200 characters) then it would be simpler to ensure that you read-ahead at least 200 characters into a buffer and then match against that. Alternatively: perhaps only a few of your token REs have unlimited variable length. Those you can code in the prefix form like that shown above. The remainder (of fixed or limited length) can just be matched in the simple way against a large enough read-ahead buffer. Regards, Brian. () Hmm, this isn't quite right, since it partially matches 011112 as well. You could check for a partial match (i.e. $3 = nil) and allow it only if it consumes the whole string. Alternatively, the RE itself needs to say "must be followed by X or end of string". This works, but it's a bit ugly: /(0(\z\|1+(\z\|0))) I can't think of a better formulation off the top of my head though. Rick DeNatale wrote: > On 5/22/07, Hans Fugal <fug@zianet.com> wrote: >> Well that works for \w+ an \s+, but what if you want to match /01+0/? >> You'd get a syntax error on 0111 even though it's a valid partial match. > Han's I'm not sure I understand your use case. Perhaps you could > provide some code as you would write it IF Ruby provided a > match_partial method for Regexp. It's a thought excercise. I've been fiddling with parser generators, and had an idea for a simple recursive-descent parser that includes the lexer by defining terminals as regexes. Example: # productions expr: term {. expr0 = term .} ( '+' term {. expr0 += term3 .} \| '-' term {. expr0 -= term4 .} )* ; term: fact {. term0 = fact1 .} ( '' fact {. term0 = fact2 .} \| '/' fact {. term0 /= fact3 .} )* ; fact: ['+'] const {. fact0 = const1.to_f .} \| '-' const {. fact0 = -const2.to_f .} \| '(' expr ')' {. fact0 = expr1 .} ; # terminals const: /\d+[\.\d+]/ = '0'; Whether a parser generator or a generic lexer, in order to do the lexing generically from a set of regexes, you need to be able to say "doesn't match" in order to catch syntax errors in a timely manner. It's easy enough if you have all of the input, or "a lot" which is reasonably expected to be longer than any token, or if you can count on tokens not crossing a guard (such as a newline), but in general you need to do partial matching. So the code might look like: r = /\A#{terminals.inject {\|u,r\| Regexp.union(u,r)}}/ until input.eof? if r =~ input # figure out which token and consume/return it elsif r.partial_match(input) # wait for more input end end That may not be the most efficient way, but it gives a good idea. The problem is also applicable for input verification, i.e. in a field on a form, as has been mentioned. - Hide quoted text - On Fri, May 25, 2007 at 11:25:09PM +0900, Hans Fugal wrote: > # productions > expr: term {. expr0 = term .} > ( '+' term {. expr0 += term3 .} > \| '-' term {. expr0 -= term4 .} > )* > ; > term: fact {. term0 = fact1 .} > ( '' fact {. term0 = fact2 .} > \| '/' fact {. term0 /= fact3 .} > )* > ; > fact: ['+'] const {. fact0 = const1.to_f .} > \| '-' const {. fact0 = -const2.to_f .} > \| '(' expr ')' {. fact0 = expr1 .} > ; > # terminals > const: /\d+[\.\d+]/ = '0'; I imagine it should be const: /\d+(\.\d+)?/ > It's easy > enough if you have all of the input, or "a lot" which is reasonably > expected to be longer than any token, or if you can count on tokens not > crossing a guard (such as a newline), but in general you need to do > partial matching. All your tokens above are one character, so a one character lookahead is fine, apart from 'const' If you read your input in 4096 byte blocks, reading a new block when your buffer is less than 4096 bytes full, then you'll have somewhere between 4K and 8K of lookahead. You'd do that for efficiency anyway, I'd hope. So this leaves the case of any terminal regexps which might be required to match more than 4K of data as a single token. If you're parsing a language like that, then I'd agree that having partial matching makes your code a bit simpler. But otherwise, you can write your regexp to match partially: const: /\d+(\.(\d+)?)?/ and if a partial match is detected, keep eating more input as necessary. Note: the worst case is that the entire file consists of a single token - in which case, you will end up reading the whole file into memory anyway. Regards, Brian. - Hide quoted text - Brian Candler wrote: > On Fri, May 25, 2007 at 11:25:09PM +0900, Hans Fugal wrote: >> # productions >> expr: term {. expr0 = term .} >> ( '+' term {. expr0 += term3 .} >> \| '-' term {. expr0 -= term4 .} >> )* >> ; >> term: fact {. term0 = fact1 .} >> ( '' fact {. term0 = fact2 .} >> \| '/' fact {. term0 /= fact3 .} >> )* >> ; >> fact: ['+'] const {. fact0 = const1.to_f .} >> \| '-' const {. fact0 = -const2.to_f .} >> \| '(' expr ')' {. fact0 = expr1 .} >> ; >> # terminals >> const: /\d+[\.\d+]/ = '0'; > I imagine it should be > const: /\d+(\.\d+)?/ Yes, of course. Sorry. >> It's easy >> enough if you have all of the input, or "a lot" which is reasonably >> expected to be longer than any token, or if you can count on tokens not >> crossing a guard (such as a newline), but in general you need to do >> partial matching. > All your tokens above are one character, so a one character lookahead is > fine, apart from 'const' My example is not meant to be pathological. It's not hard to imagine a set of terminal regexes where you need much more than one-character lookahead. > If you read your input in 4096 byte blocks, reading a new block when your > buffer is less than 4096 bytes full, then you'll have somewhere between 4K > and 8K of lookahead. You'd do that for efficiency anyway, I'd hope. When was the last time you typed 4k faster than the computer could process it? The biggest reason for stream parsing is when there's a human on the other end. In practice, you usually wouldn't have trouble assuming newline is never part of a token, because you wouldn't get stdin except after the user presses enter. But that's not entirely a guarantee, and there can be other situations (like a network stream) where that might not be the case. > So this leaves the case of any terminal regexps which might be required to > match more than 4K of data as a single token. If you're parsing a language > like that, then I'd agree that having partial matching makes your code a bit > simpler. But otherwise, you can write your regexp to match partially: > const: /\d+(\.(\d+)?)?/ > and if a partial match is detected, keep eating more input as necessary. Easy enough in a hand-written lexer, but I wouldn't want to ask users of a parser generator to have to provide partial-match regexes. And parsing regexes to discover a partial match regex is not an easy task. On Sun, May 27, 2007 at 12:45:12AM +0900, Hans Fugal wrote: > >If you read your input in 4096 byte blocks, reading a new block when your > >buffer is less than 4096 bytes full, then you'll have somewhere between 4K > >and 8K of lookahead. You'd do that for efficiency anyway, I'd hope. > When was the last time you typed 4k faster than the computer could > process it? The biggest reason for stream parsing is when there's a > human on the other end. OK. So it sounds like the problem is that you need partial matching, because you need to handle parse-as-you-type, rather than parse an existing file presented as a stream. In which case the conclusions seem clear: (1) Find an existing regular expression engine or lexical analyser engine which does what you need. There are several which have been ported to Ruby which you could try. or: (2) Write your own Regular Expression engine. Sorry for stating the obvious. But I can't really see what else you want from this thread. Commiseration that Ruby's built-in regexp engine isn't suitable for your requirements? :-) Regards, Brian. - Hide quoted text - Brian Candler wrote: > On Sun, May 27, 2007 at 12:45:12AM +0900, Hans Fugal wrote: >>> If you read your input in 4096 byte blocks, reading a new block when your >>> buffer is less than 4096 bytes full, then you'll have somewhere between 4K >>> and 8K of lookahead. You'd do that for efficiency anyway, I'd hope. >> When was the last time you typed 4k faster than the computer could >> process it? The biggest reason for stream parsing is when there's a >> human on the other end. > OK. So it sounds like the problem is that you need partial matching, > because you need to handle parse-as-you-type, rather than parse an existing > file presented as a stream. > In which case the conclusions seem clear: > (1) Find an existing regular expression engine or lexical analyser engine > which does what you need. There are several which have been ported to Ruby > which you could try. > or: > (2) Write your own Regular Expression engine. > Sorry for stating the obvious. But I can't really see what else you want > from this thread. Commiseration that Ruby's built-in regexp engine isn't > suitable for your requirements? :-) Sorry that I didn't state the obvious. :) Yes, what I hoped to find from this thread was that I wasn't missing something and that these are really the only two options.