• Many individuals have discussed general problems with me, and many have provided specific material included here: Elaine Brennan, Robin Cover, David Fallside, Michael Hahn, Dave Hollander, Deborah A. Lapeyre, Eve L. Maler, Murray Maloney, Jeni Tennison, Henry S. Thompson, Tommie Usdin, Ann Wrightson
• My colleagues at W3C and in the W3C XML Schema Working Group have educated me long and painfully.
• The slides describing document analysis are adapted from slides developed by Mulberry Technologies; used by kind permission of Mulberry Technologies.

• Information has structure
• Markup is used to make that structure explicit
• XML makes structure explicit by using explicit delimiters on everything

What makes a marked-up document valuable is the added value that the markup brings. Without markup, the computer can't tell that This is Emphasized and This is a Book Title. A human can, and needs to let the computer know.

• Telling the computer what's what
• But wait — what is what?
• What things exist? What kinds of things?
• What relations exist among things?

• You can't model everything (but where to stop?)
• The map is not the territory — and shouldn't be!
• Markup is for communication
• Different people may disagree

• Different names for ‘same’ thing
• Different specificity
  Is this a licensing info a Constract? an Agreement? a License? a License Agreement? a set of Legal arrangements? a set of Conditions? a Policy?
• Different views of who's involved
  “Bob buttered the bread.” “The bread was buttered.” “Bob buttered the bread with a knife.” “Bob buttered the bread with a knife using Land o' Lakes brand.” “At 12:23, Bob buttered the bread with a knife using Land o' Lakes brand.” “Event E247 is an event. The agent was Bob. The patient (object) was the bread. The instrument[1] was some butter (B231). B231 is Land o' Lakes brand butter. The instrument[2] was a knife.”

• It's not always easy or fun
• Pass/fail* ratio is low
• Software pain
• Network effects
• Opportunity cost (time lost)
• You can do it with XHTML (and microformats), or DocBook, or ODF, or UBL, or Atom

• Can be very rewarding
• Competitive advantage
• Software leverage
• Network effects
• Cost of bad fit
• Microformats are also vocabularies
  (which interact with their host vocabularies in intricate ways)
• Often you can't do it with an off the shelf language

• If you design your own vocabulary, what needs to be in it?
• If you use an off-the-shelf language, what parts of it do you need?
• If you adapt (cut down, extend, modify) an off-the-shelf language, what must you omit / add / change?

<poem>
<title>The duck</title>
<author>Ogden Nash</author>
<stanza>
<line>Behold the duck.</line>
<line>It does not cluck.</line>
<line>A cluck it lacks.</line>
<line>It quacks.</line>
</stanza>
<stanza>
<line>It is especially fond</line>
<line>Of a puddle or pond.</line>
<line>When it dines or sups</line>
<line>It bottoms-ups.</line>
</stanza>
</poem>

<poem>
<author>Btqra Anfu</author>
<stanza>
<line>Orubyq gur qhpx.</line>
<line>Vg qbrf abg pyhpx.</line>
<line>N pyhpx vg ynpxf.</line>
<line>Vg dhnpxf.</line>
</stanza>
<title>Gur qhpx</title>
<stanza>
<line>Vg vf rfcrpvnyyl sbaq</line>
<line>Bs n chqqyr be cbaq.</line>
<line>Jura vg qvarf be fhcf</line>
<line>Vg obggbzf-hcf.</line>
</stanza>
</poem>

<cbrz>
<gvgyr>Gur qhpx</gvgyr>
<nhgube>ol Btqra Anfu</nhgube>
<fgnamn>
<yvar>Orubyq gur qhpx.</yvar>
<yvar>Vg qbrf abg pyhpx.</yvar>
<yvar>N pyhpx vg ynpxf.</yvar>
<yvar>Vg dhnpxf.</yvar>
</fgnamn>
<fgnanm>
<yyar>Vg vf rfcrpvnyyl sbaq</yyar>
<yyar>Bs n chqqyr be cbaq.</yyar>
<yyar>Jura vg qvarf be fhcf</yyar>
<yvar>Vg obggbzf-hcf.</yvar>
</fgnanm>
</cbrz>

• Precision
• Explicitness
• Mechanical validation

• Can errors exist? or is every string of bits a possible message?
• Can errors be found ...
  • automatically?
  • by clerical inspection?
  • through inspections by highly trained experts?
• Is the cost of undetected errors ...
  • trivial?
  • small?
  • large?
  • catastrophic?

• Cobol, Fortan I (before BNF)
• LaTeX, GML
• HTML*

• Distinguish
  • Valid
  • Invalid

• Test:
  • Member of set of valid messages?
  • No?

• Language as set of sentences
• Grammar as definition of that set
  • Numerous ad hoc rules
  • Generative grammars (since 1956)

1. Take a set of rewrite rules of the form left-hand-side = right-hand-side.
2. Put a start symbol (e.g. expression) into a buffer.
3. Choose some symbol* in your buffer.
4. Find it on the left hand side of a rule.
5. In your buffer, erase the symbol and insert the right hand side of the rule.
6. Any symbols left?
   • If yes, then go to step 3.
   • If not, you're done. The contents of your buffer are a sentence in the language defined by the grammar given by the rules of step 1, the start symbol, and the sets of terminal and non-terminal symbols.

expression = number operator number
operator = '+'
operator = '-'
number = DIGIT 
number = number DIGIT
number = '(' expression ')'
DIGIT = '0' 
DIGIT = '1' 
DIGIT = '2'  
... 
DIGIT = '9'

• Simple mechanism
• Easy to reason about
• Reversible* (given sequence of characters, is there a derivation for it?)
  • Recognition
  • Parsing

• Documents have grammars, too
  • document = front body back
  • purchase-order = billing-info shipping-info details
• In XML,
  • Structure is clear even without schema
  • Schemas help check correctness
  • Contrast schemas for databases (or SGML)

Separating the valid from invalid.

Sheep on the right, goats on the left.

And a great gulf shall be established between them.

• Waterloo grammar: anything goes anywhere, as long as it's declared
• Single-element vocabulary
  • Every element named “e”
  • Distinguish by type attribute
  • Often proposed as a ‘reductio ad absurdum’...
  • ... but consider Microsoft's Office format

• the ones with all the necessary information
• the ones which convey meaning to the application
• the ones the software knows how to process correctly
• the ones the stylesheet knows how to handle gracefully

• I agree to accept any valid document.
• You agree to send only valid documents.
• The software promises to process valid documents correctly.
• We promise not to invoke the software on invalid documents.
• The stylesheet can be checked to make sure it handles all valid documents.

• a schema, and
• an input XML document

• an output document annotated with type information and validation results, the post-schema-validation infoset, or PSVI

1. identify the element to validate (often the root element of a document);
2. find or construct a schema;
3. check the validity of that element and its descendants;
4. annotate the input infoset with validity and type information.

• valid, invalid, not known
• fully validated, not validated at all, partially validated
• validation information on each element and attribute

• numbers: decimal, float, double, integer, int, positiveInteger, negativeInteger, ...
• dates and times: dateTime, date, time, gYearMonth, gYear, gMonthDay, gMonth, gDay
• durations
• binary data: hexBinary, base64binary
• boolean
• Unicode strings
• miscellaneous: anyURI, QName, NOTATION

• min- and maxInclusive, -Exclusive
• enumeration of values
• length (absolute, minimum, maximum)
• totalDigits, fractionDigits
• pattern (constrains the lexical space)

 <xsd:simpleType name="grade">
  <xsd:restriction base="xsd:integer">
   <xsd:minInclusive value="0"/>
   <xsd:maxInclusive value="100"/>
  </xsd:restriction>
 </xsd:simpleType>

<xsd:element name="orderDate" type="xsd:date"/>
<xsd:element name="partnumber" type="my:partnum"/>

<my:shipDate xsi:type="xsd:date">2006-12-04</my:shipDate>

• content model: What child elements can elements of this type have, in what order, with what types?
• attributes: What attributes can elements of this type have, with what types?
• global and local elements
• global and local types
• wildcards

<xsd:complexType name="address">
  <xsd:sequence>
    <xsd:element name="name"   type="xsd:string"/>
    <xsd:element name="street" type="xsd:string"/>
    <xsd:element name="city"   type="xsd:string"/>
    <xsd:element name="state"  type="my:state-or-province"/>
    <xsd:element name="zip"    type="my:zipcode"/>
  </xsd:sequence>
</xsd:complexType>