Re: Do XML Schema processors do backtracking?

(Roger: isn't this kinda a repeat of your thread
http://lists.xml.org/archives/xml-dev/201311/msg00000.html  ?)

No. DTDs and XSD are designed to be LL(k) (presumably LL(1)  or have I
fogotten it) so no backtracking is required for element content models.
(For keyrefs and assertions, the grammar characterisation really does not
fit. No-one would attempt to implement XPaths as a grammar, anyway,  I
think.) A simple recursive descent parser is all that is needed.

For DTDs, the ambiguity rule prevents the need for backtracking.  For XSD,
the Unique Particle Attribution rule does similar. If you grammar ever
presents you with a choice of

But RELAX NG schemas are not necessarily ll(k) so they may indeed need
backtracking. However, an alternative technique called Partial Evaluation
(which continuously rewrites the grammar as you go) is what everyone uses
AFAIK.

 For XML attribute validation, and for XSD ALL content groupings, I think
implementers choose some evaluation methods that go outside ll(k) to
prevent combinatorial explosion: but this is an optimization technique
rather than a necessary class of grammar.

There has been a lot of developments in grammar theory and parser
implementation in the last 20 years. For example, PEG grammars are a class
that is quite convenient for expressing XML with less lexical handwaving.

Rick



On Tue, 19 Apr 2022, 9:33 pm Roger L Costello, <[email protected]> wrote:

> Hi Folks,
>
> I am reading a compiler book [1] and it says this:
>
> "An important practical criterion is that a parser should not backtrack.
> At all stages it should operate deterministically. A number of authors have
> described backtracking parsers, but those are rarely used in practice. It
> is difficult to undo semantic actions carried out by the parser as is
> necessary if it has to backtrack."
>
> Do XML Schema processors do backtracking? For instance, if the XML
> document has this:
>
> <name>John Doe</name>
>
> and the XML Schema has this choice:
>
> <xs:choice>
>     <xs:element name="id" type="xs:int" />
>     <xs:element name="name" type="xs:string" />
> </xs:choice>
>
> Does the XML Schema processor try the first branch of the choice,
> backtrack, and then try the second branch?
>
> /Roger
>
>
> [1] Introduction to Compiling Techniques by J.R. Bennett, see bottom of
> page 80.
>
> _______________________________________________________________________
>
> XML-DEV is a publicly archived, unmoderated list hosted by OASIS
> to support XML implementation and development. To minimize
> spam in the archives, you must subscribe before posting.
>
> [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
> Or unsubscribe: [email protected]
> subscribe: [email protected]
> List archive: http://lists.xml.org/archives/xml-dev/
> List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
>
>