Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 4911

Encoding Instructions for the Robust XML Encoding Rules (RXER)

Pages: 91
Experimental
Part 3 of 4 – Pages 56 to 74
First   Prev   Next

Top   ToC   RFC4911 - Page 56   prevText

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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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   ToC   RFC4911 - 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 Section