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

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 UTC