Zoo tutorials: [ SQL | Linux | XML ]

A Gentle Introduction to xml

Deterministic Expressions
With answers

We can nest options, this allows us to specify complicated options - but we must give "deterministic" expressions.

The bar (|) may be used to allow options. A|B means either A or B is permitted. We can use brackets in these regular expressions.

Any of the following is allowed:

The dtd given is correct - but it cannot be used because it is not deterministic.

Non-Deterministic Expession

A non-deterministic expression can be parsed in more than one way. The validator uses a "one symbol look ahead" - if there are two options that start with the same element the validator cannot cope.

Example of a non-deterministic expression

(a,b)|(a,c)

A deterministic equivalent

a,(b|c)

Replace the dtd with a deterministic equivalent.


ValidInvalid
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <!-- United kingdom -->
  <queen>Elizabeth II</queen>
</country>

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <king>Rudolf</king>
  <king>Michael</king>
  <king>Rudolf</king>
  <!--Should not allow three kings -->
</country>

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <!-- France -->
  <president>Sarkozy</president>
</country>

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <president>Robert</president>
  <king>Rudolf</king>
  <!-- Cannot have president and king-->
</country>


<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <!-- Norway -->
  <king>Harald</king>
  <queen>Sonja</queen>
</country>

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <!-- King comes before queen-->
  <queen>Henrietta</queen>
  <king>Rudolf</king>
</country>

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <!-- Nowhere -->
  <king>Andrew</king>
</country>

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE country SYSTEM "country.dtd">
<country>
  <!-- Should have president or monarch-->
</country>