W3C home > Mailing lists > Public > xmlschema-dev@w3.org > June 2002

Re: Ambiguous content models -- allowed or disallowed by XSDL?

From: Henry S. Thompson <ht@cogsci.ed.ac.uk>
Date: 13 Jun 2002 13:02:52 +0100
To: Ian Stokes-Rees <ijs@decisionsoft.com>
Cc: "Lehmann, Steen" <slehmann@silverstream.com>, "'Jeni Tennison'" <jeni@jenitennison.com>, xmlschema-dev@w3.org
Message-ID: <f5bbsaf5qtv.fsf@cogsci.ed.ac.uk>

Ian Stokes-Rees <ijs@decisionsoft.com> writes:

> Without working it out in detail, my guess is that you get exponential
> growth in the number of required states if you have multiple nested
> ambiguous content models.  In practical terms, while it would be
> theoretically possible, it is my guess that either the implementation or
> the operation (execution) of a parser which allowed this would be
> difficult.  Is that a fair assessment?

As I said in my post, yes, unfolding the numeric loops is expensive,
but only at compile time (i.e. contentModel->DFA).  Using the unfolded 
DFA is blindingly fast.

ht
-- 
  Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
          W3C Fellow 1999--2002, part-time member of W3C Team
     2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
	    Fax: (44) 131 650-4587, e-mail: ht@cogsci.ed.ac.uk
		     URL: http://www.ltg.ed.ac.uk/~ht/
 [mail really from me _always_ has this .sig -- mail without it is forged spam]
Received on Thursday, 13 June 2002 08:03:03 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 11 January 2011 00:14:31 GMT