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

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

From: Ian Stokes-Rees <ijs@decisionsoft.com>
Date: Thu, 13 Jun 2002 12:22:53 +0100
To: "Lehmann, Steen" <slehmann@silverstream.com>
Cc: "'Jeni Tennison'" <jeni@jenitennison.com>, xmlschema-dev@w3.org
Message-ID: <20020613122249.D9666@decisionsoft.com>

On Thu, Jun 13, 2002 at 12:36:18PM +0200, Lehmann, Steen wrote:
> To also include the containing <sequence> simply repeat the whole graph
> twice, copying every transition out of state 0 to state 4, resulting in
> states 5 to 8 (copies of 1 to 4)
> 
> Now, to turn this NFA into a corresponding DFA we "collapse" the empty
> transitions from each state and copy transitions from states we can reach by
> following empty transitions back to the original state (known as evaluating
> lambda closure). The resulting DFA has no empty transitions, so at each
> state we know immediately if a parsed symbol is legal (there is a transition
> somewhere for that symbol) without a need for backtracking. 

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?

Ian.

-- 
Ian Stokes-Rees, Client Services      DecisionSoft Ltd.
Telephone: +44-1865-203192            http://www.decisionsoft.com
Received on Thursday, 13 June 2002 07:24:05 GMT

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