10.0.0.21 Git - asn2quickder/blob - asn1ate/parser.py

   1 # Copyright (c) 2013, Schneider Electric Buildings AB
   2 # All rights reserved.
   3 #
   4 # Redistribution and use in source and binary forms, with or without
   5 # modification, are permitted provided that the following conditions are met:
   6 #     * Redistributions of source code must retain the above copyright
   7 #       notice, this list of conditions and the following disclaimer.
   8 #     * Redistributions in binary form must reproduce the above copyright
   9 #       notice, this list of conditions and the following disclaimer in the
  10 #       documentation and/or other materials provided with the distribution.
  11 #     * Neither the name of Schneider Electric Buildings AB nor the
  12 #       names of contributors may be used to endorse or promote products
  13 #       derived from this software without specific prior written permission.
  14 #
  15 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  16 # ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  17 # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18 # DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
  19 # ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  20 # (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  21 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  22 # ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  24 # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25
  26 import re
  27 from copy import copy
  28 from pyparsing import Keyword, Literal, Word, OneOrMore, Combine, Regex, Forward, Optional, Group, Suppress, delimitedList, cStyleComment, nums, alphanums, empty, srange
  29
  30
  31 __all__ = ['parse_asn1', 'AnnotatedToken']
  32
  33
  34 def parse_asn1(asn1_payload):
  35     """ Parse a string containing an ASN.1 module definition
  36     and return a syntax tree in the form of a list of
  37     AnnotatedToken objects.
  38     """
  39     grammar = _build_asn1_grammar()
  40     parse_result = grammar.parseString(asn1_payload)
  41     parse_tree = parse_result.asList()
  42     return parse_tree
  43
  44
  45 def print_parse_tree(node, indent=1):
  46     """ Debugging aid. Dumps a parse tree as returned
  47     from parse_asn1 to stdout in indented tree form.
  48     """
  49     def indented_print(msg):
  50         print(' ' * indent + msg)
  51
  52     if type(node) is AnnotatedToken:
  53         # tagged token
  54         tag, values = node.ty, node.elements
  55         indented_print('%s:' % tag)
  56         print_parse_tree(values, indent + 1)
  57     elif type(node) is list:
  58         # token list
  59         for token in node:
  60             print_parse_tree(token, indent + 1)
  61     else:
  62         # token
  63         indented_print(str(node))
  64
  65
  66 class AnnotatedToken(object):
  67     """ A simple data structure to keep track of a token's
  68     type, identified by a string, and its children.
  69     Children may be other annotated tokens, lists or simple
  70     strings.
  71     """
  72     def __init__(self, token_type, elements):
  73         self.ty = token_type
  74         self.elements = elements
  75
  76     def __str__(self):
  77         return 'T(%s)%s' % (self.ty, self.elements)
  78
  79     __repr__ = __str__
  80
  81
  82 def _build_asn1_grammar():
  83     def build_identifier(prefix_pattern):
  84         identifier_suffix = Optional(Word(srange('[-0-9a-zA-Z]')))
  85         identifier = Combine(Word(srange(prefix_pattern), exact=1) + identifier_suffix)  # todo: more rigorous? trailing hyphens and -- forbidden
  86         return identifier
  87
  88     def braced_list(element_rule):
  89         return Suppress('{') + Group(delimitedList(element_rule)) + Suppress('}')
  90
  91     def annotate(name):
  92         def annotation(t):
  93             return AnnotatedToken(name, t.asList())
  94
  95         return annotation
  96
  97     # Reserved words
  98     DEFINITIONS = Keyword('DEFINITIONS')
  99     BEGIN = Keyword('BEGIN')
 100     END = Keyword('END')
 101     OPTIONAL = Keyword('OPTIONAL')
 102     DEFAULT = Keyword('DEFAULT')
 103     TRUE = Keyword('TRUE')
 104     FALSE = Keyword('FALSE')
 105     UNIVERSAL = Keyword('UNIVERSAL')
 106     APPLICATION = Keyword('APPLICATION')
 107     PRIVATE = Keyword('PRIVATE')
 108     MIN = Keyword('MIN')
 109     MAX = Keyword('MAX')
 110     IMPLICIT = Keyword('IMPLICIT')
 111     EXPLICIT = Keyword('EXPLICIT')
 112     EXPLICIT_TAGS = Keyword('EXPLICIT TAGS')
 113     IMPLICIT_TAGS = Keyword('IMPLICIT TAGS')
 114     AUTOMATIC_TAGS = Keyword('AUTOMATIC TAGS')
 115     EXTENSIBILITY_IMPLIED = Keyword('EXTENSIBILITY IMPLIED')
 116     COMPONENTS_OF = Keyword('COMPONENTS OF')
 117     ELLIPSIS = Keyword('...')
 118     SIZE = Keyword('SIZE')
 119     OF = Keyword('OF')
 120
 121     # Built-in types
 122     SEQUENCE = Keyword('SEQUENCE')
 123     SET = Keyword('SET')
 124     CHOICE = Keyword('CHOICE')
 125     ENUMERATED = Keyword('ENUMERATED')
 126     BIT_STRING = Keyword('BIT STRING')
 127     BOOLEAN = Keyword('BOOLEAN')
 128     REAL = Keyword('REAL')
 129     OCTET_STRING = Keyword('OCTET STRING')
 130     CHARACTER_STRING = Keyword('CHARACTER STRING')
 131     NULL = Keyword('NULL')
 132     INTEGER = Keyword('INTEGER')
 133     OBJECT_IDENTIFIER = Keyword('OBJECT IDENTIFIER')
 134
 135     # Restricted string types
 136     BMPString = Keyword('BMPString')
 137     GeneralString = Keyword('GeneralString')
 138     GraphicString = Keyword('GraphicString')
 139     IA5String =  Keyword('IA5String')
 140     ISO646String = Keyword('ISO646String')
 141     NumericString = Keyword('NumericString')
 142     PrintableString = Keyword('PrintableString')
 143     TeletexString = Keyword('TeletexString')
 144     T61String = Keyword('T61String')
 145     UniversalString = Keyword('UniversalString')
 146     UTF8String = Keyword('UTF8String')
 147     VideotexString = Keyword('VideotexString')
 148     VisibleString = Keyword('VisibleString')
 149
 150     # Literals
 151     number = Word(nums)
 152     signed_number = Combine(Optional('-') + number)  # todo: consider defined values from 18.1
 153     bstring = Literal('\'') + Regex('[01]+') + Literal('\'B')
 154     hstring = Literal('\'') + Regex('[0-9A-F]+') + Literal('\'H')
 155
 156     # Comments
 157     hyphen_comment = Regex(r"--[\s\S]*?(--|$)", flags=re.MULTILINE)
 158     comment = hyphen_comment | cStyleComment
 159
 160     # identifier
 161     identifier = build_identifier('[a-z]')
 162
 163     # references
 164     # these are duplicated to force unique token annotations
 165     valuereference = build_identifier('[a-z]')
 166     typereference = build_identifier('[A-Z]')
 167     module_reference = build_identifier('[A-Z]')
 168
 169     # values
 170     # BUG: These are badly specified and cause the grammar to break if used generally.
 171     # todo: consider more literals from 16.9
 172     real_value = Regex(r'-?\d+(\.\d*)?') # todo: this doesn't really follow the spec
 173     boolean_value = TRUE | FALSE
 174     bitstring_value = bstring | hstring     # todo: consider more forms from 21.9
 175     integer_value = signed_number
 176     null_value = NULL
 177
 178     builtin_value = boolean_value | bitstring_value | real_value | integer_value | null_value
 179     defined_value = valuereference # todo: more options from 13.1
 180     value = builtin_value | defined_value
 181
 182     # tags
 183     class_ = UNIVERSAL | APPLICATION | PRIVATE
 184     class_number = number # todo: consider defined values from 30.1
 185     tag = Suppress('[') + Optional(class_) + class_number + Suppress(']')
 186     tag_default = EXPLICIT_TAGS | IMPLICIT_TAGS | AUTOMATIC_TAGS | empty
 187
 188     # extensions
 189     extension_default = EXTENSIBILITY_IMPLIED | empty
 190
 191     # types
 192     defined_type = Unique(typereference)  # todo: consider other defined types from 13.1
 193     referenced_type = Unique(defined_type)  # todo: consider other ref:d types from 16.3
 194
 195     # Forward-declare these, they can only be fully defined once
 196     # we have all types defined. There are some circular dependencies.
 197     named_type = Forward()
 198     type_ = Forward()
 199
 200     # constraints
 201     # todo: consider the full subtype and general constraint syntax described in 45.*
 202     # but for now, just implement a simple integer value range.
 203     value_range_min = (signed_number | valuereference | MIN)
 204     value_range_max = (signed_number | valuereference | MAX)
 205     value_range_constraint = value_range_min + Suppress('..') + value_range_max
 206     size_constraint = SIZE + Suppress('(') + value_range_constraint + Suppress(')')
 207     constraint = Suppress('(') + value_range_constraint + Suppress(')')
 208     optional_paren_l = Optional(Suppress('('))
 209     optional_paren_r = Optional(Suppress(')'))
 210
 211     # TODO: consider exception syntax from 24.1
 212     extension_marker = Unique(ELLIPSIS)
 213
 214     component_type_optional = named_type + Suppress(OPTIONAL)
 215     component_type_default = named_type + Suppress(DEFAULT) + value
 216     component_type_components_of = Suppress(COMPONENTS_OF) + type_
 217     component_type = component_type_components_of | component_type_optional | component_type_default | named_type
 218
 219     tagged_type = tag + Optional(IMPLICIT | EXPLICIT) + type_
 220
 221     named_number_value = Suppress('(') + signed_number + Suppress(')')
 222     named_number = identifier + named_number_value
 223     enumeration = named_number | identifier
 224
 225     set_type = SET + braced_list(component_type | extension_marker)
 226     sequence_type = SEQUENCE + braced_list(component_type | extension_marker)
 227     sequenceof_type = SEQUENCE + Optional(optional_paren_l + size_constraint + optional_paren_r) + OF + (type_ | named_type)
 228     setof_type = SET + Optional(optional_paren_l + size_constraint + optional_paren_r) + OF + (type_ | named_type)
 229     choice_type = CHOICE + braced_list(named_type | extension_marker)
 230     enumerated_type = ENUMERATED + braced_list(enumeration)
 231     bitstring_type = BIT_STRING + braced_list(named_number)
 232     plain_integer_type = INTEGER
 233     restricted_integer_type = INTEGER + braced_list(named_number)
 234     boolean_type = BOOLEAN
 235     real_type = REAL
 236     null_type = NULL
 237     object_identifier_type = OBJECT_IDENTIFIER
 238     octetstring_type = OCTET_STRING
 239     unrestricted_characterstring_type = CHARACTER_STRING
 240     restricted_characterstring_type = BMPString | GeneralString | \
 241                                       GraphicString | IA5String | \
 242                                       ISO646String | NumericString | \
 243                                       PrintableString | TeletexString | \
 244                                       T61String | UniversalString | \
 245                                       UTF8String | VideotexString | VisibleString
 246     characterstring_type = restricted_characterstring_type | unrestricted_characterstring_type
 247
 248     # todo: consider other builtins from 16.2
 249     simple_type = (boolean_type | null_type | octetstring_type | characterstring_type | real_type | plain_integer_type | object_identifier_type) + Optional(constraint)
 250     constructed_type = choice_type | sequence_type | set_type
 251     value_list_type = restricted_integer_type | enumerated_type
 252     builtin_type = tagged_type | simple_type | constructed_type | sequenceof_type | setof_type | value_list_type | bitstring_type
 253
 254     type_ << (builtin_type | referenced_type)
 255
 256     # BUG: identifier should not be Optional here,
 257     # but our ASN.1 interpreter supports unnamed members,
 258     # and we use them.
 259     named_type << (Optional(identifier) + type_)
 260
 261     # BUG: Trailing semi-colon is not allowed by standard grammar, but our ASN.1 interpreter accepts it
 262     # and we happen to use it.
 263     type_assignment = typereference + '::=' + type_ + Suppress(Optional(';'))
 264     value_assignment = valuereference + type_ + '::=' + value
 265
 266     assignment = type_assignment | value_assignment
 267     assignment_list = OneOrMore(assignment)
 268
 269     module_body = (assignment_list | empty)
 270     module_defaults = Suppress(tag_default + extension_default)  # we don't want these in the AST
 271     module_definition = module_reference + DEFINITIONS + module_defaults + '::=' + BEGIN + module_body + END
 272
 273     module_definition.ignore(comment)
 274
 275     # Mark up the parse results with token tags
 276     identifier.setParseAction(annotate('Identifier'))
 277     named_number_value.setParseAction(annotate('Value'))
 278     tag.setParseAction(annotate('Tag'))
 279     class_.setParseAction(annotate('TagClass'))
 280     class_number.setParseAction(annotate('TagClassNumber'))
 281     type_.setParseAction(annotate('Type'))
 282     simple_type.setParseAction(annotate('SimpleType'))
 283     choice_type.setParseAction(annotate('ChoiceType'))
 284     sequence_type.setParseAction(annotate('SequenceType'))
 285     set_type.setParseAction(annotate('SetType'))
 286     value_list_type.setParseAction(annotate('ValueListType'))
 287     bitstring_type.setParseAction(annotate('BitStringType'))
 288     referenced_type.setParseAction(annotate('ReferencedType'))
 289     sequenceof_type.setParseAction(annotate('SequenceOfType'))
 290     setof_type.setParseAction(annotate('SetOfType'))
 291     named_number.setParseAction(annotate('NamedValue'))
 292     constraint.setParseAction(annotate('Constraint'))
 293     component_type.setParseAction(annotate('ComponentType'))
 294     component_type_optional.setParseAction(annotate('ComponentTypeOptional'))
 295     component_type_default.setParseAction(annotate('ComponentTypeDefault'))
 296     component_type_components_of.setParseAction(annotate('ComponentTypeComponentsOf'))
 297     tagged_type.setParseAction(annotate('TaggedType'))
 298     named_type.setParseAction(annotate('NamedType'))
 299     type_assignment.setParseAction(annotate('TypeAssignment'))
 300     value_assignment.setParseAction(annotate('ValueAssignment'))
 301     valuereference.setParseAction(annotate('ValueReference'))
 302     module_reference.setParseAction(annotate('ModuleReference'))
 303     module_body.setParseAction(annotate('ModuleBody'))
 304     module_definition.setParseAction(annotate('ModuleDefinition'))
 305     extension_marker.setParseAction(annotate('ExtensionMarker'))
 306
 307     return module_definition
 308
 309
 310 def Unique(token):
 311     """ Use to create a distinct name of a production
 312     with the same form as another, e.g.
 313       identifier = build_identifier('[a-z]')
 314       valuereference = build_identifier('[a-z]')
 315     We prefer:
 316       identifier = build_identifier('[a-z]')
 317       valuereference = Unique(identifier)
 318     to avoid duplicating the details of the grammar.
 319     This allows unique parse actions for productions
 320     with the same underlying rules.
 321     """
 322     return copy(token)