W3C home > Mailing lists > Public > www-svg@w3.org > April 2000

Re: Comma delimited lists in SVG

From: Dan Connolly <connolly@w3.org>
Date: Sun, 09 Apr 2000 02:39:24 -0500
Message-ID: <38F033AC.C720936F@w3.org>
To: Chris Lilley <chris@w3.org>
CC: www-svg@w3.org
Chris Lilley wrote:
> 
> Dan Connolly wrote:
> 
> > If you're willing to live with a restriction that your EBNF is
> > a regular grammar, and hence can be converted to a regular expression,
> > you *can* do that with schemas.
> 
> That might be OK if the EBNF can be converted to regexp automatically.
> Maintaining regexps is something I am not willing to get into, but
> auto-converted EBNF should be OK.

Done. It's 10K!

http://www.w3.org/XML/2000/04schema-hacking/svg-path/,svg-re

I started with the SVG grammar, but discovered there
was recursion in there; stuff like:
	digit-sequence:
	digit
	| digit digit-sequence

This recursion can be removed pretty much trivially, but you
should check my work to be sure:

resulting grammar:
	http://www.w3.org/XML/2000/04schema-hacking/svg-path/svg-path-gram
,v file with original and diffs:
	http://www.w3.org/XML/2000/04schema-hacking/svg-path/svg-path-gram,v

the (pretty nasty! but less than 2 page) perl hack that converts from
the grammar to the regexp is:

	http://www.w3.org/XML/2000/04schema-hacking/svg-path/bnf2re.pl

I suspect there are some optimizations still available.
I haven't tested the regexp at all. Sorry, it's late.

Oh... I represented
	#x20 | #x9 | #xD | #xA
using perl's \s ; that's probably not exactly right, but it was
easier on the eyes during debugging.

[...]

> > hmm... seems to be
> >         \s*{[Mn]\s*{coord-pair}(,\s*{lineto-argument-sequence})?}*\s*
> 
> OK so as this progresses we get the entire thing built up on one line as
> one regexp. What would be the performance implications of that huge and
> hairy expression? EBNF at least allows the normal computer programming
> practice of divide and conquer. Does regexp in effect require "the whole
> program in a single function"?

On the contrary.. regexps are one of the most highly optimized
mechanisms around. Even a 10K regexp should "compile"
to something lightning-fast. Hmm... the compilation might
take some time.


-- 
Dan Connolly, W3C http://www.w3.org/People/Connolly/
Received on Sunday, 9 April 2000 03:41:01 GMT

This archive was generated by hypermail 2.3.1 : Friday, 8 March 2013 15:54:18 GMT