ebnf.py 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  1. # This module tries to implement ISO 14977 standard with pyparsing.
  2. # pyparsing version 1.1 or greater is required.
  3. # ISO 14977 standardize The Extended Backus-Naur Form(EBNF) syntax.
  4. # You can read a final draft version here:
  5. # https://www.cl.cam.ac.uk/~mgk25/iso-ebnf.html
  6. #
  7. # Submitted 2004 by Seo Sanghyeon
  8. #
  9. from pyparsing import *
  10. all_names = '''
  11. integer
  12. meta_identifier
  13. terminal_string
  14. optional_sequence
  15. repeated_sequence
  16. grouped_sequence
  17. syntactic_primary
  18. syntactic_factor
  19. syntactic_term
  20. single_definition
  21. definitions_list
  22. syntax_rule
  23. syntax
  24. '''.split()
  25. integer = Word(nums)
  26. meta_identifier = Word(alphas, alphanums + '_')
  27. terminal_string = Suppress("'") + CharsNotIn("'") + Suppress("'") ^ \
  28. Suppress('"') + CharsNotIn('"') + Suppress('"')
  29. definitions_list = Forward()
  30. optional_sequence = Suppress('[') + definitions_list + Suppress(']')
  31. repeated_sequence = Suppress('{') + definitions_list + Suppress('}')
  32. grouped_sequence = Suppress('(') + definitions_list + Suppress(')')
  33. syntactic_primary = optional_sequence ^ repeated_sequence ^ \
  34. grouped_sequence ^ meta_identifier ^ terminal_string
  35. syntactic_factor = Optional(integer + Suppress('*')) + syntactic_primary
  36. syntactic_term = syntactic_factor + Optional(Suppress('-') + syntactic_factor)
  37. single_definition = delimitedList(syntactic_term, ',')
  38. definitions_list << delimitedList(single_definition, '|')
  39. syntax_rule = meta_identifier + Suppress('=') + definitions_list + \
  40. Suppress(';')
  41. ebnfComment = ( "(*" +
  42. ZeroOrMore( CharsNotIn("*") | ( "*" + ~Literal(")") ) ) +
  43. "*)" ).streamline().setName("ebnfComment")
  44. syntax = OneOrMore(syntax_rule)
  45. syntax.ignore(ebnfComment)
  46. def do_integer(str, loc, toks):
  47. return int(toks[0])
  48. def do_meta_identifier(str, loc, toks):
  49. if toks[0] in symbol_table:
  50. return symbol_table[toks[0]]
  51. else:
  52. forward_count.value += 1
  53. symbol_table[toks[0]] = Forward()
  54. return symbol_table[toks[0]]
  55. def do_terminal_string(str, loc, toks):
  56. return Literal(toks[0])
  57. def do_optional_sequence(str, loc, toks):
  58. return Optional(toks[0])
  59. def do_repeated_sequence(str, loc, toks):
  60. return ZeroOrMore(toks[0])
  61. def do_grouped_sequence(str, loc, toks):
  62. return Group(toks[0])
  63. def do_syntactic_primary(str, loc, toks):
  64. return toks[0]
  65. def do_syntactic_factor(str, loc, toks):
  66. if len(toks) == 2:
  67. # integer * syntactic_primary
  68. return And([toks[1]] * toks[0])
  69. else:
  70. # syntactic_primary
  71. return [ toks[0] ]
  72. def do_syntactic_term(str, loc, toks):
  73. if len(toks) == 2:
  74. # syntactic_factor - syntactic_factor
  75. return NotAny(toks[1]) + toks[0]
  76. else:
  77. # syntactic_factor
  78. return [ toks[0] ]
  79. def do_single_definition(str, loc, toks):
  80. toks = toks.asList()
  81. if len(toks) > 1:
  82. # syntactic_term , syntactic_term , ...
  83. return And(toks)
  84. else:
  85. # syntactic_term
  86. return [ toks[0] ]
  87. def do_definitions_list(str, loc, toks):
  88. toks = toks.asList()
  89. if len(toks) > 1:
  90. # single_definition | single_definition | ...
  91. return Or(toks)
  92. else:
  93. # single_definition
  94. return [ toks[0] ]
  95. def do_syntax_rule(str, loc, toks):
  96. # meta_identifier = definitions_list ;
  97. assert toks[0].expr is None, "Duplicate definition"
  98. forward_count.value -= 1
  99. toks[0] << toks[1]
  100. return [ toks[0] ]
  101. def do_syntax(str, loc, toks):
  102. # syntax_rule syntax_rule ...
  103. return symbol_table
  104. symbol_table = {}
  105. class forward_count:
  106. pass
  107. forward_count.value = 0
  108. for name in all_names:
  109. expr = vars()[name]
  110. action = vars()['do_' + name]
  111. expr.setName(name)
  112. expr.setParseAction(action)
  113. #~ expr.setDebug()
  114. def parse(ebnf, given_table={}):
  115. symbol_table.clear()
  116. symbol_table.update(given_table)
  117. forward_count.value = 0
  118. table = syntax.parseString(ebnf)[0]
  119. assert forward_count.value == 0, "Missing definition"
  120. for name in table:
  121. expr = table[name]
  122. expr.setName(name)
  123. #~ expr.setDebug()
  124. return table