# XPath and XQuery Parsing Strategies

## Editor's Draft 18 January 2005

This version:
  http://www.w3.org/TR/2005/NOTE-xquery-xpath-parsing-2005118/
Latest version:
  http://www.w3.org/TR/xquery-xpath-parsing/
Editor:
  Scott Boag (XSL WG), IBM Research <scott_boag@us.ibm.com>

Copyright © 2005 W3C® (MIT, ERCIM, Keio), All Rights Reserved. W3C liability, trademark and document use rules apply.

## Abstract

This document describes possible strategies for parsing the XPath and XQuery languages, and is provided as a helpfull guide to those who are designing an implementation for these languages, and as background material for the normative EBNF found in the language specifications.

## Status of this Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This document is a W3C Working Group Note. It represents the views of the W3C XQuery Working Group and the W3C XSL Working Group members at the time of publication. There are currently no definate plans to amend this document further, though updates may well track further evolution of the XPath and XQuery specifications. Publication as a Working Group Note does not imply endorsement by the W3C Membership. This is a non-normative document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

Comments about this document should be sent to the W3C XPath/XQuery mailing list, public-qt-comments@w3.org (archived at http://lists.w3.org/Archives/Public/public-qt-comments/), with “[XPath Parsing]” or “[XQuery Parsing]” at the beginning of the subject field.

The patent policy for this document is the 5 February 2004 W3C Patent Policy. Patent disclosures relevant to this specification may be found on the XML Query Working Group's patent disclosure page and the XSL Working Group's patent disclosure page. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) with respect to this specification should disclose the information in accordance with section 6 of the W3C Patent Policy.

## 1 Introduction

The XQuery language is, for the most part [1], a super-set of the smaller XPath language. XPath is designed to be a simple addressing and expression language, while XQuery includes prologue declarations, function, variable, and extension declarations, XML element construction, and advanced iteration constructs. These languages do not contain reserved keywords, which is to say data references in the form of QNames are designed to never overlap with keywords in the language. In order to achieve the combination of expression language, directory-style addressing, prologue declarations, type matching, and XML element construction, the meaning of the tokens are extremely context dependent. For instance, the string `div` may be an element reference, or may be a division operator. Likewise, the `*` might be a wildcard element reference, may be a multiplication operator, or may be a kleene operator.

As illustration, the following is a very unlikely, but legal, XQuery example:

    declare namespace namespace = "http://example.com";
    declare union <union>for gibberish {
       for $for in for return <for>***div div</for>
    }</union>,
    if(if) then then else else- +-++-**-* instance
    of element(*)* * * **---++div- div -div

### 1.1 Structure of Parsers

XPath and XQuery parsers may be either top-down or bottom-up. Traditionally, the parsing process is decomposed into subcomponents:

1. [Definition: Lexical scanner, which assigns symbols known as tokens to units in the input, in essense recognizing the basic words and punctuation of the language. Typically, the lexer uses regular expressions as a specification for how to do this tokenization. The rules that govern the lexical structure of the language, sometimes known as microsyntax, should be simple, regular, and as context-free as possible.]

2. [Definition: Parser, which arranges the tokens into a hierarchical structure. Typically, the parser uses a BNF or variant description (EBNF in the case of XPath/XQuery) as a specification for this parsing.]

Since the tokenization of XPath/XQuery is so context dependent, this breakdown may not be as simple as with other programming languages. Furthermore, the granularity of tokenization is an issue.

### 1.2 Lexical Scanning Strategies

We can speculate on an enumeration of some strategies for implementing a lexical scanner as follows:

1. [Definition: Scan-while-parse scanner. Using this strategy, the parser would evaluate the character stream into tokens, while at the same time branching to the respective hierarchical context. Thus the words can be discovered in context. Complex parsers are typically not built in this fashion, but, given the issue of context sensitivity, this may be a reasonable approach. This would probably be implemented as a hand-constructed recursive-descent parser. ]

2. [Definition: Fuzzy token scanner. Using this strategy, a typical simple lexical scanner is implemented, but the meaning of the tokens are often left somewhat ambiguous. Thus, the word `div` might be assigned the symbol QNameOrKeyword. The words can be disambiguated during the context sensitive parse process. This approach would probably be a hand-constructed, Top-down parser.]

3. [Definition: Two-pass scanner. This is the same as the Fuzzy token scanner, but the ambiguous words can be disambiguated by a second scan, using some rules (probably expressed as a context-free grammar) that reflect the basic structure of the EBNF (call this the three-pass approach). The three-pass approach could conceivably be implemented via a parser constructor program, with the addition of a custom disambiguator in between the lexer and parser. This method could be used for either Top-down or Bottom-up techniques.]

4. [Definition: State-driven scanner. This approach recognizes sets of words only in certain states, each word or punctuation possibly transitioning to a next state. In other words, it implements lexical recognition as transition tables for a push-down automata.]

#### 1.2.1 Token Granularity

In XPath/XQuery, the meaning of a word may often be determined by the words and punctuation ahead of it. Thus, the word `if` is only the "if" keyword if it is followed by a left-parenthesis (ignoring whitespace). Likewise, the word `declare` may be a QName, or may be part of a NamespaceDecl in the prolog, if followed by a `namespace` word. Inversely, `namespace` is determined to be a keyword verses a QName by it's appearance after `declare`. In the XQuery and XPath specifications, in the EBNF appendix, the notation "< ... >" is used to indicate a grouping of terminals that together may help disambiguate the individual symbols.

A scanner might take one of two approaches for assigning token units to the character stream:

- [Definition: Short tokens. Using this approach, `declare namespace` would be considered two tokens, the exact symbols assigned based on lexical look-ahead (and look-behind).] In this case, a parser that has at least a look-ahead of two tokens is required (in particular, a two-token look-ahead should be sufficient for a LALR parser).

- [Definition: Long tokens. Using this approach, `declare namespace` would be considered a single token.] In this case, a parser that has a look-ahead of only one token can be implemented.

### 1.3 Parser Strategies

The general strategies for implementing the parser are as follows:

1. Recursive-descent parser. For our purposes, this term means a hand-constructed, recursive descent parser.

2. [Definition: LL Parser (Left to right, Leftmost derivation, hence LL). ] The XPath/XQuery EBNF is expressed as an LL(1) grammar, so an LL parser can use the EBNF from the specifications fairly directly.

3. [Definition: LALR Parser (Look Ahead Left to right, Rightmost derivation, hence LALR). ] The XPath/XQuery EBNF is expressed as an LL(1) grammar, so an LALR parser must use what is essentially an inverted form of the original EBNF.

## 2 Lexical Processing

### 2.1 Lexical States

Many lexical scanner generators will allow specifications of tokens that are recognized based on some condition. It is possible to condition the XQuery and XPath token recognition in a lexical scanner in terms of a series of states and transitions between those states.

[Definition: A lexical state is a condition where a defined set of patterns are recognized.] The tables below define the complete lexical rules for [XPath/XQuery]. Each two column table corresponds to a lexical state and lists in the first column the tokens that are recognized when in that state. Any token not listed should result in a syntax error when in that state. When a given token is recognized in the given state, the transition to the next state and/or a lexical action is given in the right column. [Definition: A lexical action is an action that occurs as an side-effect of a pattern recognition.] Following are a list of lexical actions used in the tables:

pushState()

  The current state, before the transition, is pushed onto an abstract stack.

pushState(STATE)

  A STATE parameter is pushed onto an abstract stack.

popState()

  The most recently pushed state is removed from the top of the stack, and becomes the current state.

input_stream.backup(n)

  This is a special action that backs up the character stream by n characters. See the description of the OCCURRENCEINDICATOR state for more information.

(maintain state)

  This simply means that the current state is maintained with no modification.

The lexical states have, in many cases, close connection to the parser productions. However, just because a token is recognized in a certain lexical state, does not mean it will be legal in the current EBNF production.

The lexical states where whitespace has explicit specification are as follows: START_TAG, END_TAG, ELEMENT_CONTENT, XML_COMMENT, PROCESSING_INSTRUCTION, PROCESSING_INSTRUCTION_CONTENT, CDATA_SECTION, QUOT_ATTRIBUTE_CONTENT, and APOS_ATTRIBUTE_CONTENT.

Note:

There is no requirement for a lexer/parser to be implemented in terms of lexical states—these are only a way to specify the behavior. The only requirement is to produce results that are consistent with the results of these tables.

Editorial note |
The following tables were hand-constructed and have not, at the time of this writing, been exhaustively verified against all possible paths that may be legal in the XQuery and XPath EBNFs, which is to say, it is possible they contain bugs.

The DEFAULT State

  This state is for patterns that occur at the beginning of an expression or subexpression.

  Pattern | Transition To State
  --- | ---
  DecimalLiteral, "..", ".", DoubleLiteral, IntegerLiteral, NotNumber, <NCName ":" "*">, QName, ")", <"*" ":" NCName>, "*", StringLiteral, <"declare" "construction">, <"declare" "ordering">, <"declare" "default" "order"> |
  OPERATOR
  <"declare" "default" "collation">, <"declare" "namespace">, <"module" "namespace">, <"declare" "base-uri"> |
  NAMESPACEDECL
  <"declare" "default" "element">, <"declare" "default" "function">, <"import" "schema">, <"import" "module">, <"declare" "copy-namespaces"> |
  NAMESPACEKEYWORD
  "$", <"for" "$">, <"let" "$">, <"some" "$">, <"every" "$"> |
  VARNAME
  <"declare" "variable" "$"> |
  VARNAME
  <")" "as"> |
  ITEMTYPE
  <"element" "(">, <"attribute" "(">, <"schema-element" "(">, <"schema-attribute" "(">, <"comment" "(">, <"text" "(">, <"node" "(">, <"document-node" "("> |
  pushState(OPERATOR)
  KINDTEST
  <"processing-instruction" "("> |
  pushState(OPERATOR)
  KINDTESTFORPI
  "<!--" |
  pushState(OPERATOR)
  XML_COMMENT
  "<?" |
  pushState(OPERATOR)
  PROCESSING_INSTRUCTION
  "<![CDATA[" |
  pushState(OPERATOR)
  CDATA_SECTION
  "<" |
  pushState(OPERATOR)
  START_TAG
  <"declare" "boundary-space"> |
  XMLSPACE_DECL
  "}" |
  popState()
  <"validate" "{">, <"validate" ValidationMode> |
  pushState(OPERATOR)
  DEFAULT
  <"typeswitch" "("> |
  DEFAULT
  <"element" "{">, <"attribute" "{"> |
  pushState(OPERATOR)
  DEFAULT
  <"attribute" QName "{">, <"element" QName "{">, <"document" "{">, <"text" "{">, <"processing-instruction" "{">, <"processing-instruction" NCName "{">, <"comment" "{"> |
  pushState(OPERATOR)
  <"declare" "function"> |
  DEFAULT
  "(:" |
  pushState()
  EXPR_COMMENT
  "{", <"ordered" "{">, <"unordered" "{"> |
  pushState(OPERATOR)
  DEFAULT
  <"xquery" "version"> |
  XQUERYVERSION
  "(#" |
  PRAGMA
  <"declare" "option"> |
  OPTION
  <"at" URILiteral> |
  NAMESPACEDECL
  ";", ",", "(", <QName "(">, <"if" "(">, "-", "+", "//", "/", <"ancestor-or-self" "::">, <"ancestor" "::">, <"attribute" "::">, <"child" "::">, <"descendant-or-self" "::">, <"descendant" "::">, <"following-sibling" "::">, <"following" "::">, <"namespace" "::">, <"parent" "::">, <"preceding-sibling" "::">, <"preceding" "::">, <"self" "::">, "@" |
  DEFAULT

The OPERATOR State

  This state is for patterns that are defined for operators.

  Pattern | Transition To State
  --- | ---
  "{" |
  pushState(OPERATOR)
  DEFAULT
  ";", "then", "else", "external", "and", "at", ":=", ",", "div", "=", "except", "eq", "ge", "gt", "le", "lt", "ne", ">=", ">>", ">", "idiv", "intersect", "in", "is", "[", "<=", "<<", "<", "-", "mod", "*", "!=", <"order" "by">, <"stable" "order" "by">, "or", "+", "return", "satisfies", "//", "/", "to", "union", "|", "where", ("preserve" | "strip"), "ordered", "unordered" |
  DEFAULT
  <"castable" "as">, <"cast" "as"> |
  SINGLETYPE
  <"instance" "of">, <"treat" "as">, "case", "as", <")" "as"> |
  ITEMTYPE
  "}" |
  popState()
  "$", <"for" "$">, <"let" "$"> |
  VARNAME
  "(:" |
  pushState()
  EXPR_COMMENT
  ")", "?", <"empty" "greatest">, <"empty" "least">, "ascending", "descending", "default", "]" |
  OPERATOR
  "collation" |
  URITOOPERATOR
  StringLiteral, NotOperatorKeyword |
  (maintain state)

The XQUERYVERSION State

  This state is for recognition of XQuery version specific keywords.

  Pattern | Transition To State
  --- | ---
  ";" |
  DEFAULT
  StringLiteral, "encoding" |
  XQUERYVERSION

The NAMESPACEDECL State

  This state occurs inside of a namespace declaration, and is needed to recognize a NCName that is to be used as the prefix, as opposed to allowing a QName to occur. (Otherwise, the difference between NCName and QName are ambiguous.)

  Pattern | Transition To State
  --- | ---
  URILiteral, ",", <"at" URILiteral> |
  NAMESPACEDECL
  "(:" |
  pushState()
  EXPR_COMMENT
  "=", NCName |
  NAMESPACEDECL
  ";" |
  DEFAULT

The URITOOPERATOR State

  XXXX

  Pattern | Transition To State
  --- | ---
  URILiteral |
  OPERATOR

The NAMESPACEKEYWORD State

  This state occurs at places where the keyword "namespace" is expected, which would otherwise be ambiguous compared to a QName. QNames can not occur in this state.

  Pattern | Transition To State
  --- | ---
  URILiteral |
  NAMESPACEDECL
  "inherit", "no-inherit" |
  DEFAULT
  "namespace" |
  NAMESPACEDECL
  "(:" |
  pushState()
  EXPR_COMMENT
  <"default" "element">, "preserve", "no-preserve", "," |
  NAMESPACEKEYWORD

The XMLSPACE_DECL State

  This state occurs at places where the keywords "preserve" and "strip" is expected to support "declare xmlspace". QNames can not occur in this state.

  Pattern | Transition To State
  --- | ---
  "preserve", "strip" |
  DEFAULT
  "(:" |
  pushState()
  EXPR_COMMENT

The SINGLETYPE State

  This state distinguishes tokens that can occur only inside the SingleType production.

  Pattern | Transition To State
  --- | ---
  QName |
  OPERATOR
  "(:" |
  pushState()
  EXPR_COMMENT

The ITEMTYPE State

  This state distinguishes tokens that can occur only inside the ItemType production.

  Pattern | Transition To State
  --- | ---
  "$" |
  VARNAME
  <"empty" "(" ")">, QName |
  OPERATOR
  "(:" |
  pushState()
  EXPR_COMMENT
  <"element" "(">, <"attribute" "(">, <"schema-element" "(">, <"schema-attribute" "(">, <"comment" "(">, <"text" "(">, <"node" "(">, <"document-node" "("> |
  pushState(OCCURRENCEINDICATOR)
  KINDTEST
  <"processing-instruction" "("> |
  pushState(OCCURRENCEINDICATOR)
  KINDTESTFORPI
  QName, <"item" "(" ")"> |
  OCCURRENCEINDICATOR
  "(#" |
  PRAGMA
  ";", "then", "else" |
  DEFAULT
  <"at" URILiteral> |
  NAMESPACEDECL
  "external", "and", "at", ":=", ",", "div", "=", "except", "eq", "ge", "gt", "le", "lt", "ne", ">=", ">>", ">", "idiv", "intersect", "in", "is", "[", "(", "<=", "<<", "<", "-", "mod", "!=", <"order" "by">, <"stable" "order" "by">, "or", "return", "satisfies", "to", "union", "|", "where" |
  DEFAULT
  <"castable" "as">, <"cast" "as"> |
  SINGLETYPE
  <"instance" "of">, <"treat" "as">, "case", "as", <")" "as"> |
  ITEMTYPE

The KINDTEST State

  Pattern | Transition To State
  --- | ---
  "{" |
  pushState(OPERATOR)
  DEFAULT
  ")" |
  popState()
  "*", QName |
  CLOSEKINDTEST
  <"element" "(">, <"schema-element" "("> |
  pushState(KINDTEST)
  KINDTEST
  "(:" |
  pushState()
  EXPR_COMMENT

The KINDTESTFORPI State

  Pattern | Transition To State
  --- | ---
  ")" |
  popState()
  "(:" |
  pushState()
  EXPR_COMMENT
  NCName, StringLiteral |
  KINDTESTFORPI

The CLOSEKINDTEST State

  Pattern | Transition To State
  --- | ---
  ")" |
  popState()
  "," |
  KINDTEST
  "{" |
  pushState(OPERATOR)
  DEFAULT
  "?" |
  CLOSEKINDTEST
  "(:" |
  pushState()
  EXPR_COMMENT

The OCCURRENCEINDICATOR State

  This special state is needed to distinguish occurrence indicators that appear in the SequenceType production. For instance, compare "foo instance of baz*" to "baz*foo". In the first case, the "*" is interpreted as an occurrence indicator, and in the second case, it must be interpreted as a multiplication operator. But, when in the OCCURRENCEINDICATOR state, if anything else other than "?", "*", and "+", those symbols must be interpreted in the OPERATOR state. For instance, this would occur with the expression "foo instance of baz and $x", with the operator "and". This backing up of the lexical characters in order to reset the state, is symbolized by the notation "input_stream.backup(1)". NotOccurrenceIndicator is a special symbol for any character that is not an occurrence indicator.

  Pattern | Transition To State
  --- | ---
  [NotOccurrenceIndicator] |
  input_stream.backup(1)
  OPERATOR
  "?", "*", "+" |
  OPERATOR
  "(:" |
  pushState()
  EXPR_COMMENT

The OPTION State

  xxxx

  Pattern | Transition To State
  --- | ---
  QName |
  DEFAULT

The PRAGMA State

  xxxx

  Pattern | Transition To State
  --- | ---
  QName |
  PRAGMACONTENTS

The PRAGMACONTENTS State

  xxxx

  Pattern | Transition To State
  --- | ---
  "#)" |
  OPERATOR
  ";" |
  DEFAULT
  StringLiteral |
  OPERATOR
  S, Char |
  (maintain state)

The VARNAME State

  This state differentiates variable names from qualified names. This allows only the pattern of a QName to be recognized when otherwise ambiguities could occur.

  Pattern | Transition To State
  --- | ---
  VarName |
  OPERATOR
  "(:" |
  pushState()
  EXPR_COMMENT

The START_TAG State

  This state allows attributes in the native XML syntax, and marks the beginning of an element construction. Element constructors also push the current state, popping it at the conclusion of an end tag. In the START_TAG state, the string ">" is recognized as a token which is associated with the transition to the original state.

  Pattern | Transition To State
  --- | ---
  "/>" |
  popState()
  ">" |
  ELEMENT_CONTENT
  '"' |
  QUOT_ATTRIBUTE_CONTENT
  "'" |
  APOS_ATTRIBUTE_CONTENT
  "=" |
  START_TAG
  S, QName |
  (maintain state)

The ELEMENT_CONTENT State

  This state allows XML-like content, without these characters being misinterpreted as expressions. The character "{" marks a transition to the DEFAULT state, i.e. the start of an embedded expression, and the "}" character pops back to the ELEMENT_CONTENT state. To allow curly braces to be used as character content, a double left or right curly brace is interpreted as a single curly brace character. The string "</" is interpreted as the beginning of an end tag, which is associated with a transition to the END_TAG state.

  Pattern | Transition To State
  --- | ---
  "</" |
  END_TAG
  "{" |
  pushState()
  DEFAULT
  "<!--" |
  pushState()
  XML_COMMENT
  "<?" |
  pushState()
  PROCESSING_INSTRUCTION
  "<![CDATA[" |
  pushState()
  CDATA_SECTION
  "<" |
  pushState()
  START_TAG
  ElementContentChar |
  ELEMENT_CONTENT
  PredefinedEntityRef, CharRef, "{{", "}}" |
  (maintain state)

The END_TAG State

  When the end tag is terminated, the state is popped to the state that was pushed at the start of the corresponding start tag.

  Pattern | Transition To State
  --- | ---
  ">" |
  popState()
  S, QName |
  (maintain state)

The XML_COMMENT State

  The "<--" token marks the beginning of an XML Comment, and the "-->" token marks the end. This allows no special interpretation of other characters in this state.

  Pattern | Transition To State
  --- | ---
  "-->" |
  popState()
  (Char - '-'), <'-' (Char - '-')> |
  XML_COMMENT

The EXPR_COMMENT State

  The "(:" token marks the beginning of an expression Comment, and the ":)" token marks the end. This allows no special interpretation of other characters in this state.

  Pattern | Transition To State
  --- | ---
  ":)" |
  popState()
  "(:" |
  pushState()
  EXPR_COMMENT
  Char |
  (maintain state)

The PROCESSING_INSTRUCTION State

  In this state, only patterns that are legal in a processing instruction name are recognized.

  Pattern | Transition To State
  --- | ---
  S |
  PROCESSING_INSTRUCTION_CONTENT
  "?>" |
  popState()
  PITarget |
  PROCESSING_INSTRUCTION

The PROCESSING_INSTRUCTION_CONTENT State

  In this state, only characters are that are legal in processing instruction content are recognized.

  Pattern | Transition To State
  --- | ---
  "?>" |
  popState()
  Char |
  PROCESSING_INSTRUCTION_CONTENT

The CDATA_SECTION State

  In this state, only lexemes that are legal in a CDATA section are recognized.

  Pattern | Transition To State
  --- | ---
  "]]>" |
  popState()
  Char |
  CDATA_SECTION

The QUOT_ATTRIBUTE_CONTENT State

  This state allows content legal for attributes. The character "{" marks a transition to the DEFAULT state, i.e. the start of an embedded expression, and the "}" character pops back to the original state. To allow curly braces to be used as character content, a double left or right curly brace is interpreted as a single curly brace character. This state is the same as APOS_ATTRIBUTE_CONTENT, except that apostrophes are allowed without escaping, and an unescaped quote marks the end of the state.

  Pattern | Transition To State
  --- | ---
  '"' |
  START_TAG
  "{" |
  pushState()
  DEFAULT
  EscapeQuot, QuotAttrContentChar |
  QUOT_ATTRIBUTE_CONTENT
  PredefinedEntityRef, CharRef, "{{", "}}" |
  (maintain state)

The APOS_ATTRIBUTE_CONTENT State

  This state is the same as QUOT_ATTRIBUTE_CONTENT, except that quotes are allowed, and an unescaped apostrophe marks the end of the state.

  Pattern | Transition To State
  --- | ---
  "'" |
  START_TAG
  "{" |
  pushState()
  DEFAULT
  EscapeApos, AposAttrContentChar |
  APOS_ATTRIBUTE_CONTENT
  PredefinedEntityRef, CharRef, "{{", "}}" |
  (maintain state)

## 3 Error Reporting and Recovery

Editorial note |
To be done at a later date.

## A XPath/XQuery Grammar

### A.1 EBNF

For convenience, the basic EBNF of the XPath/XQuery grammar is reproduced here. For further details please consult the respective specifications.

Editorial note |
Need to add more....

The following grammar uses the same simple Extended Backus-Naur Form (EBNF) notation as [XML 1.0] with the following minor differences. The notation "< ... >" is used to indicate a grouping of terminals that together may help disambiguate the individual symbols. To help readability, this "< ... >" notation is absent in the EBNF in the main body of this document. This appendix is the normative version of the EBNF.

Comments on grammar productions are between '/*' and '*/' symbols - please note that these comments are normative. A 'gn:' prefix means a 'Grammar Note', and is meant as a clarification for parsing rules, and is explained in XXXXX. A 'ws:' prefix explains the whitespace rules for the production, the details of which are explained in XXXXX.

Editorial note |
make XXXXX link to external specs

[1] | `XPath` | ::= | `Expr`
[2] | `Module` | ::= | `VersionDecl? (MainModule | LibraryModule)`
[3] | `VersionDecl` | ::= | `<"xquery" "version"> StringLiteral ("encoding" StringLiteral)? Separator`
[4] | `MainModule` | ::= | `Prolog QueryBody`
[5] | `LibraryModule` | ::= | `ModuleDecl Prolog`
[6] | `ModuleDecl` | ::= | `<"module" "namespace"> NCName "=" URILiteral Separator`
[7] | `Prolog` | ::= | `(Setter Separator)* ((Import | NamespaceDecl | DefaultNamespaceDecl) Separator)* ((VarDecl | FunctionDecl | OptionDecl) Separator)*`
[8] | `Setter` | ::= | `BoundarySpaceDecl | DefaultCollationDecl | BaseURIDecl | ConstructionDecl | OrderingModeDecl | EmptyOrderDecl | CopyNamespacesDecl`
[9] | `Import` | ::= | `SchemaImport | ModuleImport`
[10] | `Separator` | ::= | `";"`
[11] | `NamespaceDecl` | ::= | `<"declare" "namespace"> NCName "=" URILiteral`
[12] | `BoundarySpaceDecl` | ::= | `<"declare" "boundary-space"> ("preserve" | "strip")`
[13] | `DefaultNamespaceDecl` | ::= | `(<"declare" "default" "element"> | <"declare" "default" "function">) "namespace" URILiteral`
[14] | `OptionDecl` | ::= | `<"declare" "option"> QName StringLiteral`
[15] | `OrderingModeDecl` | ::= | `<"declare" "ordering"> ("ordered" | "unordered")`
[16] | `EmptyOrderDecl` | ::= | `<"declare" "default" "order"> (<"empty" "greatest"> | <"empty" "least">)`
[17] | `CopyNamespacesDecl` | ::= | `<"declare" "copy-namespaces"> PreserveMode "," InheritMode`
[18] | `PreserveMode` | ::= | `"preserve" | "no-preserve"`
[19] | `InheritMode` | ::= | `"inherit" | "no-inherit"`
[20] | `DefaultCollationDecl` | ::= | `<"declare" "default" "collation"> URILiteral`
[21] | `BaseURIDecl` | ::= | `<"declare" "base-uri"> URILiteral`
[22] | `SchemaImport` | ::= | `<"import" "schema"> SchemaPrefix? URILiteral (<"at" URILiteral> ("," URILiteral)*)?`
[23] | `SchemaPrefix` | ::= | `("namespace" NCName "=") | (<"default" "element"> "namespace")`
[24] | `ModuleImport` | ::= | `<"import" "module"> ("namespace" NCName "=")? URILiteral (<"at" URILiteral> ("," URILiteral)*)?`
[25] | `VarDecl` | ::= | `<"declare" "variable" "$"> VarName TypeDeclaration? ((":=" ExprSingle) | "external")`
[26] | `ConstructionDecl` | ::= | `<"declare" "construction"> ("preserve" | "strip")`
[27] | `FunctionDecl` | ::= | `<"declare" "function"> <QName "("> ParamList? (")" | (<")" "as"> SequenceType)) (EnclosedExpr | "external")`
[28] | `ParamList` | ::= | `Param ("," Param)*`
[29] | `Param` | ::= | `"$" VarName TypeDeclaration?`
[30] | `EnclosedExpr` | ::= | `"{" Expr "}"`
[31] | `QueryBody` | ::= | `Expr`
[32] | `Expr` | ::= | `ExprSingle ("," ExprSingle)*`
[33] | `ExprSingle` | ::= | `FLWORExpr | ForExpr | QuantifiedExpr | TypeswitchExpr | IfExpr | OrExpr`
[34] | `FLWORExpr` | ::= | `(ForClause | LetClause)+ WhereClause? OrderByClause? "return" ExprSingle`
[35] | `ForExpr` | ::= | `SimpleForClause "return" ExprSingle`
[36] | `ForClause` | ::= | `<"for" "$"> VarName TypeDeclaration? PositionalVar? "in" ExprSingle ("," "$" VarName TypeDeclaration? PositionalVar? "in" ExprSingle)*`
[37] | `PositionalVar` | ::= | `"at" "$" VarName`
[38] | `SimpleForClause` | ::= | `<"for" "$"> VarName "in" ExprSingle ("," "$" VarName "in" ExprSingle)*`
[39] | `LetClause` | ::= | `<"let" "$"> VarName TypeDeclaration? ":=" ExprSingle ("," "$" VarName TypeDeclaration? ":=" ExprSingle)*`
[40] | `WhereClause` | ::= | `"where" ExprSingle`
[41] | `OrderByClause` | ::= | `(<"order" "by"> | <"stable" "order" "by">) OrderSpecList`
[42] | `OrderSpecList` | ::= | `OrderSpec ("," OrderSpec)*`
[43] | `OrderSpec` | ::= | `ExprSingle OrderModifier`
[44] | `OrderModifier` | ::= | `("ascending" | "descending")? (<"empty" "greatest"> | <"empty" "least">)? ("collation" URILiteral)?`
[45] | `QuantifiedExpr` | ::= | `(<"some" "$"> | <"every" "$">) VarName TypeDeclaration? "in" ExprSingle ("," "$" VarName TypeDeclaration? "in" ExprSingle)* "satisfies" ExprSingle`
[46] | `TypeswitchExpr` | ::= | `<"typeswitch" "("> Expr ")" CaseClause+ "default" ("$" VarName)? "return" ExprSingle`
[47] | `CaseClause` | ::= | `"case" ("$" VarName "as")? SequenceType "return" ExprSingle`
[48] | `IfExpr` | ::= | `<"if" "("> Expr ")" "then" ExprSingle "else" ExprSingle`
[49] | `OrExpr` | ::= | `AndExpr ( "or" AndExpr )*`
[50] | `AndExpr` | ::= | `ComparisonExpr ( "and" ComparisonExpr )*`
[51] | `ComparisonExpr` | ::= | `RangeExpr ( (ValueComp | GeneralComp | NodeComp) RangeExpr )?`
[52] | `RangeExpr` | ::= | `AdditiveExpr ( "to" AdditiveExpr )?`
[53] | `AdditiveExpr` | ::= | `MultiplicativeExpr ( ("+" | "-") MultiplicativeExpr )*`
[54] | `MultiplicativeExpr` | ::= | `UnionExpr ( ("*" | "div" | "idiv" | "mod") UnionExpr )*`
[55] | `UnionExpr` | ::= | `IntersectExceptExpr ( ("union" | "|") IntersectExceptExpr )*`
[56] | `IntersectExceptExpr` | ::= | `InstanceofExpr ( ("intersect" | "except") InstanceofExpr )*`
[57] | `InstanceofExpr` | ::= | `TreatExpr ( <"instance" "of"> SequenceType )?`
[58] | `TreatExpr` | ::= | `CastableExpr ( <"treat" "as"> SequenceType )?`
[59] | `CastableExpr` | ::= | `CastExpr ( <"castable" "as"> SingleType )?`
[60] | `CastExpr` | ::= | `UnaryExpr ( <"cast" "as"> SingleType )?`
[61] | `UnaryExpr` | ::= | `("-" | "+")* ValueExpr`
[62] | `ValueExpr` | ::= | `ValidateExpr | PathExpr | ExtensionExpr`
[63] | `GeneralComp` | ::= | `"=" | "!=" | "<" | "<=" | ">" | ">="` | /* gn: lt */
[64] | `ValueComp` | ::= | `"eq" | "ne" | "lt" | "le" | "gt" | "ge"`
[65] | `NodeComp` | ::= | `"is" | "<<" | ">>"`
[66] | `ValidateExpr` | ::= | `(<"validate" "{"> | (<"validate" ValidationMode> "{")) Expr "}"` | /* gn: validate */
[67] | `ExtensionExpr` | ::= | `Pragma+ "{" Expr? "}"`
[68] | `Pragma` | ::= | `"(#" S? QName PragmaContents "#)"` | /* ws: explicit */
[69] | `PragmaContents` | ::= | `(Char* - (Char* '#)' Char*))`
[70] | `PathExpr` | ::= | `("/" RelativePathExpr?) | ("//" RelativePathExpr) | RelativePathExpr` | /* gn: leading-lone-slash */
[71] | `RelativePathExpr` | ::= | `StepExpr (("/" | "//") StepExpr)*`
[72] | `StepExpr` | ::= | `AxisStep | FilterExpr`
[73] | `AxisStep` | ::= | `(ForwardStep | ReverseStep) PredicateList`
[74] | `ForwardStep` | ::= | `(ForwardAxis NodeTest) | AbbrevForwardStep`
[75] | `ForwardAxis` | ::= | `<"child" "::"> | <"descendant" "::"> | <"attribute" "::"> | <"self" "::"> | <"descendant-or-self" "::"> | <"following-sibling" "::"> | <"following" "::"> | <"namespace" "::">`
[76] | `AbbrevForwardStep` | ::= | `"@"? NodeTest`
[77] | `ReverseStep` | ::= | `(ReverseAxis NodeTest) | AbbrevReverseStep`
[78] | `ReverseAxis` | ::= | `<"parent" "::"> | <"ancestor" "::"> | <"preceding-sibling" "::"> | <"preceding" "::"> | <"ancestor-or-self" "::">`
[79] | `AbbrevReverseStep` | ::= | `".."`
[80] | `NodeTest` | ::= | `KindTest | NameTest`
[81] | `NameTest` | ::= | `QName | Wildcard`
[82] | `Wildcard` | ::= | `"*" | <NCName ":" "*"> | <"*" ":" NCName>` | /* ws: explicit */
[83] | `FilterExpr` | ::= | `PrimaryExpr PredicateList`
[84] | `PredicateList` | ::= | `Predicate*`
[85] | `Predicate` | ::= | `"[" Expr "]"`
[86] | `PrimaryExpr` | ::= | `Literal | VarRef | ParenthesizedExpr | ContextItemExpr | FunctionCall | Constructor | OrderedExpr | UnorderedExpr`
[87] | `Literal` | ::= | `NumericLiteral | StringLiteral`
[88] | `NumericLiteral` | ::= | `IntegerLiteral | DecimalLiteral | DoubleLiteral`
[89] | `VarRef` | ::= | `"$" VarName`
[90] | `ParenthesizedExpr` | ::= | `"(" Expr? ")"`
[91] | `ContextItemExpr` | ::= | `"."`
[92] | `OrderedExpr` | ::= | `<"ordered" "{"> Expr "}"`
[93] | `UnorderedExpr` | ::= | `<"unordered" "{"> Expr "}"`
[94] | `FunctionCall` | ::= | `<QName "("> (ExprSingle ("," ExprSingle)*)? ")"` | /* gn: parens */
|  |  |  | /* gn: reserved-function-names */
[95] | `Constructor` | ::= | `DirectConstructor | ComputedConstructor`
[96] | `DirectConstructor` | ::= | `DirElemConstructor | DirCommentConstructor | DirPIConstructor`
[97] | `DirElemConstructor` | ::= | `"<" QName DirAttributeList ("/>" | (">" DirElemContent* "</" QName S? ">"))` | /* ws: explicit */
|  |  |  | /* gn: lt */
[98] | `DirAttributeList` | ::= | `(S (QName S? "=" S? DirAttributeValue)?)*` | /* ws: explicit */
[99] | `DirAttributeValue` | ::= | `('"' (EscapeQuot | QuotAttrValueContent)* '"') | ("'" (EscapeApos | AposAttrValueContent)* "'")` | /* ws: explicit */
[100] | `QuotAttrValueContent` | ::= | `QuotAttrContentChar | CommonContent`
[101] | `AposAttrValueContent` | ::= | `AposAttrContentChar | CommonContent`
[102] | `DirElemContent` | ::= | `DirectConstructor | ElementContentChar | CDataSection | CommonContent`
[103] | `CommonContent` | ::= | `PredefinedEntityRef | CharRef | "{{" | "}}" | EnclosedExpr`
[104] | `DirCommentConstructor` | ::= | `"<!--" DirCommentContents "-->"` | /* ws: explicit */
[105] | `DirCommentContents` | ::= | `((Char - '-') | <'-' (Char - '-')>)*` | /* ws: explicit */
[106] | `DirPIConstructor` | ::= | `"<?" PITarget (S DirPIContents)? "?>"` | /* ws: explicit */
[107] | `DirPIContents` | ::= | `(Char* - (Char* '?>' Char*))` | /* ws: explicit */
[108] | `CDataSection` | ::= | `"<![CDATA[" CDataSectionContents "]]>"` | /* ws: explicit */
[109] | `CDataSectionContents` | ::= | `(Char* - (Char* ']]>' Char*))` | /* ws: explicit */
[110] | `ComputedConstructor` | ::= | `CompDocConstructor | CompElemConstructor | CompAttrConstructor | CompTextConstructor | CompCommentConstructor | CompPIConstructor`
[111] | `CompDocConstructor` | ::= | `<"document" "{"> Expr "}"`
[112] | `CompElemConstructor` | ::= | `(<"element" QName "{"> | (<"element" "{"> Expr "}" "{")) ContentExpr? "}"`
[113] | `ContentExpr` | ::= | `Expr`
[114] | `CompAttrConstructor` | ::= | `(<"attribute" QName "{"> | (<"attribute" "{"> Expr "}" "{")) Expr? "}"`
[115] | `CompTextConstructor` | ::= | `<"text" "{"> Expr "}"`
[116] | `CompCommentConstructor` | ::= | `<"comment" "{"> Expr "}"`
[117] | `CompPIConstructor` | ::= | `(<"processing-instruction" NCName "{"> | (<"processing-instruction" "{"> Expr "}" "{")) Expr? "}"`
[118] | `SingleType` | ::= | `AtomicType "?"?`
[119] | `TypeDeclaration` | ::= | `"as" SequenceType`
[120] | `SequenceType` | ::= | `(ItemType OccurrenceIndicator?) | <"empty" "(" ")">`
[121] | `OccurrenceIndicator` | ::= | `"?" | "*" | "+"` | /* gn: occurrence-indicators */
[122] | `ItemType` | ::= | `AtomicType | KindTest | <"item" "(" ")">`
[123] | `AtomicType` | ::= | `QName`
[124] | `KindTest` | ::= | `DocumentTest | ElementTest | AttributeTest | SchemaElementTest | SchemaAttributeTest | PITest | CommentTest | TextTest | AnyKindTest`
[125] | `AnyKindTest` | ::= | `<"node" "("> ")"`
[126] | `DocumentTest` | ::= | `<"document-node" "("> (ElementTest | SchemaElementTest)? ")"`
[127] | `TextTest` | ::= | `<"text" "("> ")"`
[128] | `CommentTest` | ::= | `<"comment" "("> ")"`
[129] | `PITest` | ::= | `<"processing-instruction" "("> (NCName | StringLiteral)? ")"`
[130] | `AttributeTest` | ::= | `<"attribute" "("> (AttribNameOrWildcard ("," TypeName)?)? ")"`
[131] | `AttribNameOrWildcard` | ::= | `AttributeName | "*"`
[132] | `SchemaAttributeTest` | ::= | `<"schema-attribute" "("> AttributeDeclaration ")"`
[133] | `AttributeDeclaration` | ::= | `AttributeName`
[134] | `ElementTest` | ::= | `<"element" "("> (ElementNameOrWildcard ("," TypeName "?"?)?)? ")"`
[135] | `ElementNameOrWildcard` | ::= | `ElementName | "*"`
[136] | `SchemaElementTest` | ::= | `<"schema-element" "("> ElementDeclaration ")"`
[137] | `ElementDeclaration` | ::= | `ElementName`
[138] | `AttributeName` | ::= | `QName`
[139] | `ElementName` | ::= | `QName`
[140] | `TypeName` | ::= | `QName`

[141] | `IntegerLiteral` | ::= | `Digits`
[142] | `DecimalLiteral` | ::= | `("." Digits) | (Digits "." [0-9]*)` | /* ws: explicit */
[143] | `DoubleLiteral` | ::= | `(("." Digits) | (Digits ("." [0-9]*)?)) [eE] [+-]? Digits` | /* ws: explicit */
[144] | `URILiteral` | ::= | `StringLiteral`
[145] | `StringLiteral` | ::= | `('"' (PredefinedEntityRef | CharRef | ('"' '"') | [^"&])* '"') | ("'" (PredefinedEntityRef | CharRef | ("'" "'") | [^'&])* "'")` | /* ws: explicit */
[146] | `PITarget` | ::= | `[http://www.w3.org/TR/REC-xml#NT-PITarget]XML` | /* gn: xml-version */
[147] | `VarName` | ::= | `QName`
[148] | `ValidationMode` | ::= | `"lax" | "strict"`
[149] | `Digits` | ::= | `[0-9]+`
[150] | `PredefinedEntityRef` | ::= | `"&" ("lt" | "gt" | "amp" | "quot" | "apos") ";"` | /* ws: explicit */
[151] | `CharRef` | ::= | `[http://www.w3.org/TR/REC-xml#NT-CharRef]XML` | /* gn: xml-version */
[152] | `EscapeQuot` | ::= | `'""'`
[153] | `EscapeApos` | ::= | `"''"`
[154] | `ElementContentChar` | ::= | `Char - [{}<&]`
[155] | `QuotAttrContentChar` | ::= | `Char - ["{}<&]`
[156] | `AposAttrContentChar` | ::= | `Char - ['{}<&]`
[157] | `Comment` | ::= | `"(:" (CommentContents | Comment)* ":)"` | /* ws: explicit */
|  |  |  | /* gn: comments */
[158] | `CommentContents` | ::= | `(Char+ - (Char* ':)' Char*))`
[159] | `QName` | ::= | `[http://www.w3.org/TR/REC-xml-names/#NT-QName]Names` | /* gn: xml-version */
[160] | `NCName` | ::= | `[http://www.w3.org/TR/REC-xml-names/#NT-NCName]Names` | /* gn: xml-version */
[161] | `S` | ::= | `[http://www.w3.org/TR/REC-xml#NT-S]XML` | /* gn: xml-version */
[162] | `Char` | ::= | `[http://www.w3.org/TR/REC-xml#NT-Char]XML` | /* gn: xml-version */

### A.2 LALR BNF

Editorial note |
To be done at a later date.

## B References

### B.1 Normative References

ISO/IEC 10646
  ISO (International Organization for Standardization). ISO/IEC 10646-1:2000. Information technology—Universal Multiple-Octet Coded Character Set (UCS)—Part 1: Architecture and Basic Multilingual Plane and ISO/IEC 10646-2:2001. Information technology—Universal Multiple-Octet Coded Character Set (UCS)—Part 2: Supplementary Planes, as, from time to time, amended, replaced by a new edition, or expanded by the addition of new parts. [Geneva]: International Organization for Standardization. (See http://www.iso.ch for the latest version.)
RFC 2119
  S. Bradner. Key Words for use in RFCs to Indicate Requirement Levels. IETF RFC 2119. See http://www.ietf.org/rfc/rfc2119.txt.
RFC2396
  T. Berners-Lee, R. Fielding, and L. Masinter. Uniform Resource Identifiers (URI): Generic Syntax. IETF RFC 2396. See http://www.ietf.org/rfc/rfc2396.txt.
Unicode
  The Unicode Consortium. The Unicode Standard, Version 4.0. Reading, Mass.: Addison-Wesley, 2003, as updated from time to time by the publication of new versions. (See http://www.unicode.org/unicode/standard/versions for the latest version and additional information on versions of the standard and of the Unicode Character Database).
XML 1.0
  World Wide Web Consortium. Extensible Markup Language (XML) 1.0. W3C Recommendation. See http://www.w3.org/TR/2000/REC-xml-20001006
XML 1.1
  World Wide Web Consortium. Extensible Markup Language (XML) 1.1. W3C Recommendation. See http://www.w3.org/TR/xml11/
XML Names
  World Wide Web Consortium. Namespaces in XML. W3C Recommendation. See http://www.w3.org/TR/REC-xml-names/
XML Names 1.1
  World Wide Web Consortium. Namespaces in XML 1.1. W3C Recommendation. See http://www.w3.org/TR/xml-names11/
XML Schema
  World Wide Web Consortium. XML Schema, Parts 0, 1, and 2. W3C Recommendation, 2 May 2001. See http://www.w3.org/TR/2001/REC-xmlschema-0-20010502/, http://www.w3.org/TR/2001/REC-xmlschema-1-20010502/, and http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/.
XQuery 1.0 and XPath 2.0 Data Model
  World Wide Web Consortium. XQuery 1.0 and XPath 2.0 Data Model. W3C Working Draft, 29 Oct 2004. See http://www.w3.org/TR/xpath-datamodel/.
XQuery 1.0 and XPath 2.0 Formal Semantics
  World Wide Web Consortium. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Working Draft, 20 Feb. 2004. See http://www.w3.org/TR/xquery-semantics/.
XQuery 1.0 and XPath 2.0 Functions and Operators
  World Wide Web Consortium. XQuery 1.0 and XPath 2.0 Functions and Operators W3C Working Draft, 20 Oct 2004. See http://www.w3.org/TR/xpath-functions/.
XSLT 2.0 and XQuery 1.0 Serialization
  World Wide Web Consortium. XSLT 2.0 and XQuery 1.0 Serialization. W3C Working Draft, 29 Oct 2004. See http://www.w3.org/TR/xslt-xquery-serialization/.

### B.2 Non-normative References

Uniform Resource Locators (URL)
  Internet Engineering Task Force (IETF). Uniform Resource Locators (URL). Request For Comment No. 1738, Dec. 1994. See http://www.ietf.org/rfc/rfc1738.txt.
Use Case Sample Queries
  Queries from the XQuery 1.0 Use Cases, presented in a single file
XML Query 1.0 Requirements
  World Wide Web Consortium. XML Query 1.0 Requirements. W3C Working Draft, 12 Nov 2003. See http://www.w3.org/TR/xquery-requirements/.
XML Query Use Cases
  World Wide Web Consortium. XML Query Use Cases. W3C Working Draft, 12 Nov. 2003. See http://www.w3.org/TR/xquery-use-cases/.
XPath 2.0
  World Wide Web Consortium. XML Path Language (XPath) Version 2.0. W3C Working Draft, 29 Oct 2004. See http://www.w3.org/TR/xpath20/.
XPath 2.0 Requirements
  World Wide Web Consortium. XPath Requirements Version 2.0. W3C Working Draft 22 August 2003. See http://www.w3.org/TR/xpath20req.
XQuery
  World Wide Web Consortium. XQuery 1.0: An XML Query Language. W3C Working Draft, 29 Oct 2004. See http://www.w3.org/TR/xquery/.
XQuery Sample Queries
  Queries from this document, presented in a single file.
XQueryX 1.0
  World Wide Web Consortium. XQueryX, Version 1.0. W3C Working Draft, 19 Dec 2003. See http://www.w3.org/TR/xqueryx.

  Editorial note |
  As of the date of this publication, XQueryX has not incorporated recent language changes; it will be made consistent with this document in its next edition.

XSLT 2.0
  World Wide Web Consortium. XSL Transformations (XSLT) 2.0. W3C Working Draft. See http://www.w3.org/TR/xslt20/

### B.3 Non-normative Background References

Lorel
  Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, and Janet L. Wiener. The Lorel Query Language for Semistructured Data. International Journal on Digital Libraries, 1(1):68-88, April 1997. See "http://www-db.stanford.edu/~widom/pubs.html
ODMG
  Rick Cattell et al. The Object Database Standard: ODMG-93, Release 1.2. Morgan Kaufmann Publishers, San Francisco, 1996.
Quilt
  Don Chamberlin, Jonathan Robie, and Daniela Florescu. Quilt: an XML Query Language for Heterogeneous Data Sources. In Lecture Notes in Computer Science, Springer-Verlag, Dec. 2000. Also available at http://www.almaden.ibm.com/cs/people/chamberlin/quilt_lncs.pdf. See also http://www.almaden.ibm.com/cs/people/chamberlin/quilt.html.
SQL
  International Organization for Standardization (ISO). Information Technology-Database Language SQL. Standard No. ISO/IEC 9075:2003. (Available from American National Standards Institute, New York, NY 10036, (212) 642-4900.)
XML-QL
  Alin Deutsch, Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A Query Language for XML. See http://www.research.att.com/~mff/files/final.html
XQL
  J. Robie, J. Lapp, D. Schach. XML Query Language (XQL). See http://www.w3.org/TandS/QL/QL98/pp/xql.html.
YATL
  S. Cluet, S. Jacqmin, and J. Simeon. The New YATL: Design and Specifications. Technical Report, INRIA, 1999.

### B.4 Non-normative Informative Material

Character Model
  World Wide Web Consortium. Character Model for the World Wide Web. W3C Working Draft. See http://www.w3.org/TR/charmod/.
Document Object Model
  World Wide Web Consortium. Document Object Model (DOM) Level 3 Core Specification. W3C Recommendation, April 7, 2004. See http://www.w3.org/TR/2004/REC-DOM-Level-3-Core-20040407/.
XML Infoset
  World Wide Web Consortium. XML Information Set. W3C Recommendation 24 October 2001. See http://www.w3.org/TR/xml-infoset/
XPath 1.0
  World Wide Web Consortium. XML Path Language (XPath) Version 1.0. W3C Recommendation, Nov. 16, 1999. See http://www.w3.org/TR/xpath.html
XPointer
  World Wide Web Consortium. XML Pointer Language (XPointer). W3C Last Call Working Draft 8 January 2001. See http://www.w3.org/TR/WD-xptr
XSLT 1.0
  World Wide Web Consortium. XSL Transformations (XSLT) 1.0. W3C Recommendation. See http://www.w3.org/TR/xslt

## C Glossary (Non-Normative)

fuzzy token scanner

  Fuzzy token scanner. Using this strategy, a typical simple lexical scanner is implemented, but the meaning of the tokens are often left somewhat ambiguous. Thus, the word `div` might be assigned the symbol QNameOrKeyword. The words can be disambiguated during the context sensitive parse process. This approach would probably be a hand-constructed, Top-down parser.

LALR Parser

  LALR Parser (Look Ahead Left to right, Rightmost derivation, hence LALR).

lexical action

  A lexical action is an action that occurs as an side-effect of a pattern recognition.

lexical scanner

  Lexical scanner, which assigns symbols known as tokens to units in the input, in essense recognizing the basic words and punctuation of the language. Typically, the lexer uses regular expressions as a specification for how to do this tokenization. The rules that govern the lexical structure of the language, sometimes known as microsyntax, should be simple, regular, and as context-free as possible.

lexical state

  A lexical state is a condition where a defined set of patterns are recognized.

LL Parser

  LL Parser (Left to right, Leftmost derivation, hence LL).

long token

  Long tokens. Using this approach, `declare namespace` would be considered a single token.

parser

  Parser, which arranges the tokens into a hierarchical structure. Typically, the parser uses a BNF or variant description (EBNF in the case of XPath/XQuery) as a specification for this parsing.

Scan-while-parse scanner

  Scan-while-parse scanner. Using this strategy, the parser would evaluate the character stream into tokens, while at the same time branching to the respective hierarchical context. Thus the words can be discovered in context. Complex parsers are typically not built in this fashion, but, given the issue of context sensitivity, this may be a reasonable approach. This would probably be implemented as a hand-constructed recursive-descent parser.

short token

  Short tokens. Using this approach, `declare namespace` would be considered two tokens, the exact symbols assigned based on lexical look-ahead (and look-behind).

state-driven scanner

  State-driven scanner. This approach recognizes sets of words only in certain states, each word or punctuation possibly transitioning to a next state. In other words, it implements lexical recognition as transition tables for a push-down automata.

two-pass scanner

  Two-pass scanner. This is the same as the Fuzzy token scanner, but the ambiguous words can be disambiguated by a second scan, using some rules (probably expressed as a context-free grammar) that reflect the basic structure of the EBNF (call this the three-pass approach). The three-pass approach could conceivably be implemented via a parser constructor program, with the addition of a custom disambiguator in between the lexer and parser. This method could be used for either Top-down or Bottom-up techniques.

## D Revision Log (Non-Normative)

This log records the changes that have been made to this document since the Last Call Draft of 12 November 2003.

### End Notes

[1]

  XQuery does not include the ForExpr production and <"namespace" "::"> axis.