tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search

RFC 4911

 
 
 

Encoding Instructions for the Robust XML Encoding Rules (RXER)

Part 3 of 4, p. 56 to 74
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 56 
26.  Security Considerations

   ASN.1 compiler implementors should take special care to be thorough
   in checking that the GROUP encoding instruction has been correctly
   used; otherwise, ASN.1 specifications with ambiguous RXER encodings
   could be deployed.

   Ambiguous encodings mean that the abstract value recovered by a
   decoder may differ from the original abstract value that was encoded.
   If that is the case, then a digital signature generated with respect
   to the original abstract value (using a canonical encoding other than
   CRXER) will not be successfully verified by a receiver using the
   decoded abstract value.  Also, an abstract value may have
   security-sensitive fields, and in particular, fields used to grant or
   deny access.  If the decoded abstract value differs from the encoded
   abstract value, then a receiver using the decoded abstract value will
   be applying different security policy than that embodied in the
   original abstract value.

27.  References

27.1.  Normative References

   [BCP14]    Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [URI]      Berners-Lee, T., Fielding, R. and L. Masinter, "Uniform
              Resource Identifiers (URI): Generic Syntax", STD 66, RFC
              3986, January 2005.

   [RXER]     Legg, S. and D. Prager, "Robust XML Encoding Rules (RXER)
              for Abstract Syntax Notation One (ASN.1)", RFC 4910, July
              2007.

   [ASN.X]    Legg, S., "Abstract Syntax Notation X (ASN.X)", RFC 4912,
              July 2007.

Top      Up      ToC       Page 57 
   [X.680]    ITU-T Recommendation X.680 (07/02) | ISO/IEC 8824-1,
              Information technology - Abstract Syntax Notation One
              (ASN.1):  Specification of basic notation.

   [X.680-1]  ITU-T Recommendation X.680 (2002) Amendment 1 (10/03) |
              ISO/IEC 8824-1:2002/Amd 1:2004, Support for EXTENDED-XER.

   [X.683]    ITU-T Recommendation X.683 (07/02) | ISO/IEC 8824-4,
              Information technology - Abstract Syntax Notation One
              (ASN.1):  Parameterization of ASN.1 specifications.

   [XML10]    Bray, T., Paoli, J., Sperberg-McQueen, C., Maler, E. and
              F. Yergeau, "Extensible Markup Language (XML) 1.0 (Fourth
              Edition)", W3C Recommendation,
              http://www.w3.org/TR/2006/REC-xml-20060816, August 2006.

   [XMLNS10]  Bray, T., Hollander, D., Layman, A., and R. Tobin,
              "Namespaces in XML 1.0 (Second Edition)", W3C
              Recommendation,
              http://www.w3.org/TR/2006/REC-xml-names-20060816, August
              2006.

   [XSD1]     Thompson, H., Beech, D., Maloney, M. and N. Mendelsohn,
              "XML Schema Part 1: Structures Second Edition", W3C
              Recommendation,
              http://www.w3.org/TR/2004/REC-xmlschema-1-20041028/,
              October 2004.

   [XSD2]     Biron, P. and A. Malhotra, "XML Schema Part 2: Datatypes
              Second Edition", W3C Recommendation,
              http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/,
              October 2004.

   [RNG]      Clark, J. and M. Makoto, "RELAX NG Tutorial", OASIS
              Committee Specification, http://www.oasis-open.org/
              committees/relax-ng/tutorial-20011203.html, December 2001.

27.2.  Informative References

   [INFOSET]  Cowan, J. and R. Tobin, "XML Information Set (Second
              Edition)", W3C Recommendation, http://www.w3.org/
              TR/2004/REC-xml-infoset-20040204, February 2004.

   [X.690]    ITU-T Recommendation X.690 (07/02) | ISO/IEC 8825-1,
              Information technology - ASN.1 encoding rules:
              Specification of Basic Encoding Rules (BER), Canonical
              Encoding Rules (CER) and Distinguished Encoding Rules
              (DER).

Top      Up      ToC       Page 58 
Appendix A.  GROUP Encoding Instruction Examples

   This appendix is non-normative.

   This appendix contains examples of both correct and incorrect use of
   the GROUP encoding instruction, determined with respect to the
   grammars derived from the example type definitions.  The productions
   of the grammars are labeled for convenience.  Sets and predicates for
   non-terminals with only one production will be omitted from the
   examples since they never indicate non-determinism.

   The requirements of Section 25.1.2 ("Unique Component Attribution")
   are satisfied by all the examples in this appendix and the appendices
   that follow it.

A.1.  Example 1

   Consider this type definition:

      SEQUENCE {
          one    [GROUP] SEQUENCE {
              two    UTF8String OPTIONAL
          } OPTIONAL,
          three  INTEGER
      }

   The associated grammar is:

      P1:  S ::= one three
      P2:  one ::= two
      P3:  one ::=
      P4:  two ::= "two"
      P5:  two ::=
      P6:  three ::= "three"

   Select Sets have to be evaluated to test the validity of the type
   definition.  The grammar leads to the following sets and predicates:

      First(P2) = { "two" }
      First(P3) = { }
      Preselected(P2) = Preselected(P3) = false
      Empty(P2) = Empty(P3) = true
      Follow(one) = { "three" }
      Select(P2) = First(P2) + Follow(one) = { "two", "three" }
      Select(P3) = First(P3) + Follow(one) = { "three" }

Top      Up      ToC       Page 59 
      First(P4) = { "two" }
      First(P5) = { }
      Preselected(P4) = Preselected(P5) = Empty(P4) = false
      Empty(P5) = true
      Follow(two) = { "three" }
      Select(P4) = First(P4) = { "two" }
      Select(P5) = First(P5) + Follow(two) = { "three" }

   The intersection of Select(P2) and Select(P3) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.  If the RXER encoding of a value of the type does not have a
   child element <two>, then it is not possible to determine whether the
   "one" component is present or absent in the value.

   Now consider this type definition with attributes in the "one"
   component:

      SEQUENCE {
          one    [GROUP] SEQUENCE {
              two    UTF8String OPTIONAL,
              four   [ATTRIBUTE] BOOLEAN,
              five   [ATTRIBUTE] BOOLEAN OPTIONAL
          } OPTIONAL,
          three  INTEGER
      }

   The associated grammar is:

      P1:  S ::= one three
      P2:  one ::= two four five
      P3:  one ::=
      P4:  two ::= "two"
      P5:  two ::=
      P6:  four ::= "@four"
      P7:  five ::= "@five"
      P8:  five ::=
      P9:  three ::= "three"

   This grammar leads to the following sets and predicates:

      First(P2) = { "two" }
      First(P3) = { }
      Preselected(P3) = Empty(P2) = false
      Preselected(P2) = Empty(P3) = true
      Follow(one) = { "three" }
      Select(P2) = { }
      Select(P3) = First(P3) + Follow(one) = { "three" }

Top      Up      ToC       Page 60 
      First(P4) = { "two" }
      First(P5) = { }
      Preselected(P4) = Preselected(P5) = Empty(P4) = false
      Empty(P5) = true
      Follow(two) = { "three" }
      Select(P4) = First(P4) = { "two" }
      Select(P5) = First(P5) + Follow(two) = { "three" }

      First(P7) = { }
      First(P8) = { }
      Preselected(P8) = Empty(P7) = false
      Preselected(P7) = Empty(P8) = true
      Follow(five) = { "three" }
      Select(P7) = { }
      Select(P8) = First(P8) + Follow(five) = { "three" }

   The intersection of Select(P2) and Select(P3) is empty, as is the
   intersection of Select(P4) and Select(P5) and the intersection of
   Select(P7) and Select(P8); hence, the grammar is deterministic, and
   the type definition is valid.  In a correct RXER encoding, the "one"
   component will be present if and only if the "four" attribute is
   present.

A.2.  Example 2

   Consider this type definition:

      CHOICE {
          one    [GROUP] SEQUENCE {
              two    [ATTRIBUTE] BOOLEAN OPTIONAL
          },
          three  INTEGER,
          four   [GROUP] SEQUENCE {
              five   BOOLEAN OPTIONAL
          }
      }

   The associated grammar is:

      P1:  S ::= one
      P2:  S ::= three
      P3:  S ::= four
      P4:  one ::= two
      P5:  two ::= "@two"
      P6:  two ::=
      P7:  three ::= "three"
      P8:  four ::= five
      P9:  five ::= "five"

Top      Up      ToC       Page 61 
      P10: five ::=

   This grammar leads to the following sets and predicates:

      First(P1) = { }
      First(P2) = { "three" }
      First(P3) = { "five" }
      Preselected(P1) = Preselected(P2) = Preselected(P3) = false
      Empty(P2) = false
      Empty(P1) = Empty(P3) = true
      Follow(S) = { "$" }
      Select(P1) = First(P1) + Follow(S) = { "$" }
      Select(P2) = First(P2) = { "three" }
      Select(P3) = First(P3) + Follow(S) = { "five", "$" }

      First(P5) = { }
      First(P6) = { }
      Preselected(P6) = Empty(P5) = false
      Preselected(P5) = Empty(P6) = true
      Follow(two) = { "$" }
      Select(P5) = { }
      Select(P6) = First(P6) + Follow(two) = { "$" }

      First(P9) = { "five" }
      First(P10) = { }
      Preselected(P9) = Preselected(P10) = Empty(P9) = false
      Empty(P10) = true
      Follow(five) = { "$" }
      Select(P9) = First(P9) = { "five" }
      Select(P10) = First(P10) + Follow(five) = { "$" }

   The intersection of Select(P1) and Select(P3) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.  If the RXER encoding of a value of the type is empty, then it
   is not possible to determine whether the "one" alternative or the
   "four" alternative has been chosen.

   Now consider this slightly different type definition:

      CHOICE {
          one    [GROUP] SEQUENCE {
              two    [ATTRIBUTE] BOOLEAN
          },
          three  INTEGER,
          four   [GROUP] SEQUENCE {
              five   BOOLEAN OPTIONAL
          }
      }

Top      Up      ToC       Page 62 
   The associated grammar is:

      P1:  S ::= one
      P2:  S ::= three
      P3:  S ::= four
      P4:  one ::= two
      P5:  two ::= "@two"
      P6:  three ::= "three"
      P7:  four ::= five
      P8:  five ::= "five"
      P9:  five ::=

   This grammar leads to the following sets and predicates:

      First(P1) = { }
      First(P2) = { "three" }
      First(P3) = { "five" }
      Preselected(P2) = Preselected(P3) = false
      Empty(P1) = Empty(P2) = false
      Preselected(P1) = Empty(P3) = true
      Follow(S) = { "$" }
      Select(P1) = { }
      Select(P2) = First(P2) = { "three" }
      Select(P3) = First(P3) + Follow(S) = { "five", "$" }

      First(P8) = { "five" }
      First(P9) = { }
      Preselected(P8) = Preselected(P9) = Empty(P8) = false
      Empty(P9) = true
      Follow(five) = { "$" }
      Select(P8) = First(P8) = { "five" }
      Select(P9) = First(P9) + Follow(five) = { "$" }

   The intersection of Select(P1) and Select(P2) is empty, the
   intersection of Select(P1) and Select(P3) is empty, the intersection
   of Select(P2) and Select(P3) is empty, and the intersection of
   Select(P8) and Select(P9) is empty; hence, the grammar is
   deterministic, and the type definition is valid.  The "one" and
   "four" alternatives can be distinguished because the "one"
   alternative has a mandatory attribute.

Top      Up      ToC       Page 63 
A.3.  Example 3

   Consider this type definition:

      SEQUENCE {
          one  [GROUP] CHOICE {
              two    [ATTRIBUTE] BOOLEAN,
              three  [GROUP] SEQUENCE OF number INTEGER
          } OPTIONAL
      }

   The associated grammar is:

      P1:  S ::= one
      P2:  one ::= two
      P3:  one ::= three
      P4:  one ::=
      P5:  two ::= "@two"
      P6:  three ::= number three
      P7:  three ::=
      P8:  number ::= "number"

   This grammar leads to the following sets and predicates:

      First(P2) = { }
      First(P3) = { "number" }
      First(P4) = { }
      Preselected(P3) = Preselected(P4) = Empty(P2) = false
      Preselected(P2) = Empty(P3) = Empty(P4) = true
      Follow(one) = { "$" }
      Select(P2) = { }
      Select(P3) = First(P3) + Follow(one) = { "number", "$" }
      Select(P4) = First(P4) + Follow(one) = { "$" }

      First(P6) = { "number" }
      First(P7) = { }
      Preselected(P6) = Preselected(P7) = Empty(P6) = false
      Empty(P7) = true
      Follow(three) = { "$" }
      Select(P6) = First(P6) = { "number" }
      Select(P7) = First(P7) + Follow(three) = { "$" }

   The intersection of Select(P3) and Select(P4) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.  If the RXER encoding of a value of the type is empty, then it
   is not possible to determine whether the "one" component is absent or
   the empty "three" alternative has been chosen.

Top      Up      ToC       Page 64 
A.4.  Example 4

   Consider this type definition:

      SEQUENCE {
          one  [GROUP] CHOICE {
              two    [ATTRIBUTE] BOOLEAN,
              three  [ATTRIBUTE] BOOLEAN
          } OPTIONAL
      }

   The associated grammar is:

      P1:  S ::= one
      P2:  one ::= two
      P3:  one ::= three
      P4:  one ::=
      P5:  two ::= "@two"
      P6:  three ::= "@three"

   This grammar leads to the following sets and predicates:

      First(P2) = { }
      First(P3) = { }
      First(P4) = { }
      Preselected(P4) = Empty(P2) = Empty(P3) = false
      Preselected(P2) = Preselected(P3) = Empty(P4) = true
      Follow(one) = { "$" }
      Select(P2) = { }
      Select(P3) = { }
      Select(P4) = First(P4) + Follow(one) = { "$" }

   The intersection of Select(P2) and Select(P3) is empty, the
   intersection of Select(P2) and Select(P4) is empty, and the
   intersection of Select(P3) and Select(P4) is empty; hence, the
   grammar is deterministic, and the type definition is valid.

A.5.  Example 5

   Consider this type definition:

      SEQUENCE {
          one  [GROUP] SEQUENCE OF number INTEGER OPTIONAL
      }

Top      Up      ToC       Page 65 
   The associated grammar is:

      P1:  S ::= one
      P2:  one ::= number one
      P3:  one ::=
      P4:  one ::=
      P5:  number ::= "number"

   P3 is generated during the processing of the SEQUENCE OF type.  P4 is
   generated because the "one" component is optional.

   This grammar leads to the following sets and predicates:

      First(P2) = { "number" }
      First(P3) = { }
      First(P4) = { }
      Preselected(P2) = Preselected(P3) = Preselected(P4) = false
      Empty(P2) = false
      Empty(P3) = Empty(P4) = true
      Follow(one) = { "$" }
      Select(P2) = First(P2) = { "number" }
      Select(P3) = First(P3) + Follow(one) = { "$" }
      Select(P4) = First(P4) + Follow(one) = { "$" }

   The intersection of Select(P3) and Select(P4) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.  If the RXER encoding of a value of the type does not have any
   <number> child elements, then it is not possible to determine whether
   the "one" component is present or absent in the value.

   Consider this similar type definition with a SIZE constraint:

      SEQUENCE {
          one  [GROUP] SEQUENCE SIZE(1..MAX) OF number INTEGER OPTIONAL
      }

   The associated grammar is:

      P1:  S ::= one
      P2:  one ::= number one'
      P3:  one' ::= number one'
      P4:  one' ::=
      P5:  one ::=
      P6:  number ::= "number"

Top      Up      ToC       Page 66 
   This grammar leads to the following sets and predicates:

      First(P2) = { "number" }
      First(P5) = { }
      Preselected(P2) = Preselected(P5) = Empty(P2) = false
      Empty(P5) = true
      Follow(one) = { "$" }
      Select(P2) = First(P2) = { "number" }
      Select(P5) = First(P5) + Follow(one) = { "$" }

      First(P3) = { "number" }
      First(P4) = { }
      Preselected(P3) = Preselected(P4) = Empty(P3) = false
      Empty(P4) = true
      Follow(one') = { "$" }
      Select(P3) = First(P3) = { "number" }
      Select(P4) = First(P4) + Follow(one') = { "$" }

   The intersection of Select(P2) and Select(P5) is empty, as is the
   intersection of Select(P3) and Select(P4); hence, the grammar is
   deterministic, and the type definition is valid.  If there are no
   <number> child elements, then the "one" component is necessarily
   absent and there is no ambiguity.

A.6.  Example 6

   Consider this type definition:

      SEQUENCE {
          beginning  [GROUP] List,
          middle     UTF8String OPTIONAL,
          end        [GROUP] List
      }

      List ::= SEQUENCE OF string UTF8String

   The associated grammar is:

      P1:  S ::= beginning middle end
      P2:  beginning ::= string beginning
      P3:  beginning ::=
      P4:  middle ::= "middle"
      P5:  middle ::=
      P6:  end ::= string end
      P7:  end ::=
      P8:  string ::= "string"

Top      Up      ToC       Page 67 
   This grammar leads to the following sets and predicates:

      First(P2) = { "string" }
      First(P3) = { }
      Preselected(P2) = Preselected(P3) = Empty(P2) = false
      Empty(P3) = true
      Follow(beginning) = { "middle", "string", "$" }
      Select(P2) = First(P2) = { "string" }
      Select(P3) = First(P3) + Follow(beginning)
                 = { "middle", "string", "$" }

      First(P4) = { "middle" }
      First(P5) = { }
      Preselected(P4) = Preselected(P5) = Empty(P4) = false
      Empty(P5) = true
      Follow(middle) = { "string", "$" }
      Select(P4) = First(P4) = { "middle" }
      Select(P5) = First(P5) + Follow(middle) = { "string", "$" }

      First(P6) = { "string" }
      First(P7) = { }
      Preselected(P6) = Preselected(P7) = Empty(P6) = false
      Empty(P7) = true
      Follow(end) = { "$" }
      Select(P6) = First(P6) = { "string" }
      Select(P7) = First(P7) + Follow(end) = { "$" }

   The intersection of Select(P2) and Select(P3) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.

   Now consider the following type definition:

      SEQUENCE {
          beginning     [GROUP] List,
          middleAndEnd  [GROUP] SEQUENCE {
              middle        UTF8String,
              end           [GROUP] List
          } OPTIONAL
      }

   The associated grammar is:

      P1:  S ::= beginning middleAndEnd
      P2:  beginning ::= string beginning
      P3:  beginning ::=
      P4:  middleAndEnd ::= middle end
      P5:  middleAndEnd ::=

Top      Up      ToC       Page 68 
      P6:  middle ::= "middle"
      P7:  end ::= string end
      P8:  end ::=
      P9:  string ::= "string"

   This grammar leads to the following sets and predicates:

      First(P2) = { "string" }
      First(P3) = { }
      Preselected(P2) = Preselected(P3) = Empty(P2) = false
      Empty(P3) = true
      Follow(beginning) = { "middle", "$" }
      Select(P2) = First(P2) = { "string" }
      Select(P3) = First(P3) + Follow(beginning) = { "middle", "$" }

      First(P4) = { "middle" }
      First(P5) = { }
      Preselected(P4) = Preselected(P5) = Empty(P4) = false
      Empty(P5) = true
      Follow(middleAndEnd) = { "$" }
      Select(P4) = First(P4) = { "middle" }
      Select(P5) = First(P5) + Follow(middleAndEnd) = { "$" }

      First(P7) = { "string" }
      First(P8) = { }
      Preselected(P7) = Preselected(P8) = Empty(P7) = false
      Empty(P8) = true
      Follow(end) = { "$" }
      Select(P7) = First(P7) = { "string" }
      Select(P8) = First(P8) + Follow(end) = { "$" }

   The intersection of Select(P2) and Select(P3) is empty, as is the
   intersection of Select(P4) and Select(P5) and the intersection of
   Select(P7) and Select(P8); hence, the grammar is deterministic, and
   the type definition is valid.

A.7.  Example 7

   Consider the following type definition:

      SEQUENCE SIZE(1..MAX) OF
          one  [GROUP] SEQUENCE {
              two    INTEGER OPTIONAL
          }

Top      Up      ToC       Page 69 
   The associated grammar is:

      P1:  S ::= one S'
      P2:  S' ::= one S'
      P3:  S' ::=
      P4:  one ::= two
      P5:  two ::= "two"
      P6:  two ::=

   This grammar leads to the following sets and predicates:

      First(P2) = { "two" }
      First(P3) = { }
      Preselected(P2) = Preselected(P3) = false
      Empty(P2) = Empty(P3) = true
      Follow(S') = { "$" }
      Select(P2) = First(P2) + Follow(S') = { "two", "$" }
      Select(P3) = First(P3) + Follow(S') = { "$" }

      First(P5) = { "two" }
      First(P6) = { }
      Preselected(P5) = Preselected(P6) = Empty(P5) = false
      Empty(P6) = true
      Follow(two) = { "two", "$" }
      Select(P5) = First(P5) = { "two" }
      Select(P6) = First(P6) + Follow(two) = { "two", "$" }

   The intersection of Select(P2) and Select(P3) is not empty and the
   intersection of Select(P5) and Select(P6) is not empty; hence, the
   grammar is not deterministic, and the type definition is not valid.
   The encoding of a value of the type contains an indeterminate number
   of empty instances of the component type.

A.8.  Example 8

   Consider the following type definition:

      SEQUENCE OF
          list [GROUP] SEQUENCE SIZE(1..MAX) OF number INTEGER

   The associated grammar is:

      P1:  S ::= list S
      P2:  S ::=
      P3:  list ::= number list'
      P4:  list' ::= number list'
      P5:  list' ::=
      P6:  number ::= "number"

Top      Up      ToC       Page 70 
   This grammar leads to the following sets and predicates:

      First(P1) = { "number" }
      First(P2) = { }
      Preselected(P1) = Preselected(P2) = Empty(P1) = false
      Empty(P2) = true
      Follow(S) = { "$" }
      Select(P1) = First(P1) = { "number" }
      Select(P2) = First(P2) + Follow(S) = { "$" }

      First(P4) = { "number" }
      First(P5) = { }
      Preselected(P4) = Preselected(P5) = Empty(P4) = false
      Empty(P5) = true
      Follow(list') = { "number", "$" }
      Select(P4) = First(P4) = { "number" }
      Select(P5) = First(P5) + Follow(list') = { "number", "$" }

   The intersection of Select(P4) and Select(P5) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.  The type describes a list of lists, but it is not possible
   for a decoder to determine where the outer lists begin and end.

A.9.  Example 9

   Consider the following type definition:

      SEQUENCE OF item [GROUP] SEQUENCE {
          before  [GROUP] OneAndTwo,
          core    UTF8String,
          after   [GROUP] OneAndTwo OPTIONAL
      }

      OneAndTwo ::= SEQUENCE {
          non-core  UTF8String
      }

   The associated grammar is:

      P1:  S ::= item S
      P2:  S ::=
      P3:  item ::= before core after
      P4:  before ::= non-core
      P5:  non-core ::= "non-core"
      P6:  core ::= "core"
      P7:  after ::= non-core
      P8:  after ::=

Top      Up      ToC       Page 71 
   This grammar leads to the following sets and predicates:

      First(P1) = { "non-core" }
      First(P2) = { }
      Preselected(P1) = Preselected(P2) = Empty(P1) = false
      Empty(P2) = true
      Follow(S) = { "$" }
      Select(P1) = First(P1) = { "non-core" }
      Select(P2) = First(P2) + Follow(S) = { "$" }

      First(P7) = { "non-core" }
      First(P8) = { }
      Preselected(P7) = Preselected(P8) = Empty(P7) = false
      Empty(P8) = true
      Follow(after) = { "non-core", "$" }
      Select(P7) = First(P7) = { "non-core" }
      Select(P8) = First(P8) + Follow(after) = { "non-core", "$" }

   The intersection of Select(P7) and Select(P8) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.  There is ambiguity between the end of one item and the start
   of the next.  Without looking ahead in an encoding, it is not
   possible to determine whether a <non-core> element belongs with the
   preceding or following <core> element.

A.10.  Example 10

   Consider the following type definition:

      CHOICE {
          one   [GROUP] List,
          two   [GROUP] SEQUENCE {
              three  [ATTRIBUTE] UTF8String,
              four   [GROUP] List
          }
      }

      List ::= SEQUENCE OF string UTF8String

   The associated grammar is:

      P1:  S ::= one
      P2:  S ::= two
      P3:  one ::= string one
      P4:  one ::=
      P5:  two ::= three four
      P6:  three ::= "@three"
      P7:  four ::= string four

Top      Up      ToC       Page 72 
      P8:  four ::=
      P9:  string ::= "string"

   This grammar leads to the following sets and predicates:

      First(P1) = { "string" }
      First(P2) = { "string" }
      Preselected(P1) = Empty(P2) = false
      Preselected(P2) = Empty(P1) = true
      Follow(S) = { "$" }
      Select(P1) = First(P1) + Follow(S) = { "string", "$" }
      Select(P2) = { }

      First(P3) = { "string" }
      First(P4) = { }
      Preselected(P3) = Preselected(P4) = Empty(P3) = false
      Empty(P4) = true
      Follow(one) = { "$" }
      Select(P3) = First(P3) = { "string" }
      Select(P4) = First(P4) + Follow(one) = { "$" }

      First(P7) = { "string" }
      First(P8) = { }
      Preselected(P7) = Preselected(P8) = Empty(P7) = false
      Empty(P8) = true
      Follow(four) = { "$" }
      Select(P7) = First(P7) = { "string" }
      Select(P8) = First(P8) + Follow(four) = { "$" }

   The intersection of Select(P1) and Select(P2) is empty, as is the
   intersection of Select(P3) and Select(P4) and the intersection of
   Select(P7) and Select(P8); hence, the grammar is deterministic, and
   the type definition is valid.  Although both alternatives of the
   CHOICE can begin with a <string> element, an RXER decoder would use
   the presence of a "three" attribute to decide whether to select or
   disregard the "two" alternative.

   However, an attribute in an extension cannot be used to select
   between alternatives.  Consider the following type definition:

Top      Up      ToC       Page 73 
      [SINGULAR-INSERTIONS] CHOICE {
          one   [GROUP] List,
          ...,
          two   [GROUP] SEQUENCE {
              three  [ATTRIBUTE] UTF8String,
              four   [GROUP] List
          } -- ExtensionAdditionAlternative (E1).
          -- The extension insertion point is here (I1).
      }

      List ::= SEQUENCE OF string UTF8String

   The associated grammar is:

      P1:  S ::= one
      P10: S ::= E1
      P11: S ::= "*"
      P12: E1 ::= two
      P3:  one ::= string one
      P4:  one ::=
      P5:  two ::= three four
      P6:  three ::= "@three"
      P7:  four ::= string four
      P8:  four ::=
      P9:  string ::= "string"

   This grammar leads to the following sets and predicates for P1, P10
   and P11:

      First(P1) = { "string" }
      First(P10) = { "string" }
      First(P11) = { "*" }
      Preselected(P1) = Preselected(P10) = Preselected(P11) = false
      Empty(P10) = Empty(P11) = false
      Empty(P1) = true
      Follow(S) = { "$" }
      Select(P1) = First(P1) + Follow(S) = { "string", "$" }
      Select(P10) = First(P10) = { "string" }
      Select(P11) = First(P11) = { "*" }

   Preselected(P10) evaluates to false because Preselected(P10) is
   evaluated on the base grammar, wherein P10 is rewritten as:

      P10: S ::=

Top      Up      ToC       Page 74 
   The intersection of Select(P1) and Select(P10) is not empty; hence,
   the grammar is not deterministic, and the type definition is not
   valid.  An RXER decoder using the original, unextended version of the
   definition would not know that the "three" attribute selects between
   the "one" alternative and the extension.



(page 74 continued on part 4)

Next RFC Part