invRegex.py 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257
  1. #
  2. # invRegex.py
  3. #
  4. # Copyright 2008, Paul McGuire
  5. #
  6. # pyparsing script to expand a regular expression into all possible matching strings
  7. # Supports:
  8. # - {n} and {m,n} repetition, but not unbounded + or * repetition
  9. # - ? optional elements
  10. # - [] character ranges
  11. # - () grouping
  12. # - | alternation
  13. #
  14. __all__ = ["count","invert"]
  15. from pyparsing import (Literal, oneOf, printables, ParserElement, Combine,
  16. SkipTo, infixNotation, ParseFatalException, Word, nums, opAssoc,
  17. Suppress, ParseResults, srange)
  18. class CharacterRangeEmitter(object):
  19. def __init__(self,chars):
  20. # remove duplicate chars in character range, but preserve original order
  21. seen = set()
  22. self.charset = "".join( seen.add(c) or c for c in chars if c not in seen )
  23. def __str__(self):
  24. return '['+self.charset+']'
  25. def __repr__(self):
  26. return '['+self.charset+']'
  27. def makeGenerator(self):
  28. def genChars():
  29. for s in self.charset:
  30. yield s
  31. return genChars
  32. class OptionalEmitter(object):
  33. def __init__(self,expr):
  34. self.expr = expr
  35. def makeGenerator(self):
  36. def optionalGen():
  37. yield ""
  38. for s in self.expr.makeGenerator()():
  39. yield s
  40. return optionalGen
  41. class DotEmitter(object):
  42. def makeGenerator(self):
  43. def dotGen():
  44. for c in printables:
  45. yield c
  46. return dotGen
  47. class GroupEmitter(object):
  48. def __init__(self,exprs):
  49. self.exprs = ParseResults(exprs)
  50. def makeGenerator(self):
  51. def groupGen():
  52. def recurseList(elist):
  53. if len(elist)==1:
  54. for s in elist[0].makeGenerator()():
  55. yield s
  56. else:
  57. for s in elist[0].makeGenerator()():
  58. for s2 in recurseList(elist[1:]):
  59. yield s + s2
  60. if self.exprs:
  61. for s in recurseList(self.exprs):
  62. yield s
  63. return groupGen
  64. class AlternativeEmitter(object):
  65. def __init__(self,exprs):
  66. self.exprs = exprs
  67. def makeGenerator(self):
  68. def altGen():
  69. for e in self.exprs:
  70. for s in e.makeGenerator()():
  71. yield s
  72. return altGen
  73. class LiteralEmitter(object):
  74. def __init__(self,lit):
  75. self.lit = lit
  76. def __str__(self):
  77. return "Lit:"+self.lit
  78. def __repr__(self):
  79. return "Lit:"+self.lit
  80. def makeGenerator(self):
  81. def litGen():
  82. yield self.lit
  83. return litGen
  84. def handleRange(toks):
  85. return CharacterRangeEmitter(srange(toks[0]))
  86. def handleRepetition(toks):
  87. toks=toks[0]
  88. if toks[1] in "*+":
  89. raise ParseFatalException("",0,"unbounded repetition operators not supported")
  90. if toks[1] == "?":
  91. return OptionalEmitter(toks[0])
  92. if "count" in toks:
  93. return GroupEmitter([toks[0]] * int(toks.count))
  94. if "minCount" in toks:
  95. mincount = int(toks.minCount)
  96. maxcount = int(toks.maxCount)
  97. optcount = maxcount - mincount
  98. if optcount:
  99. opt = OptionalEmitter(toks[0])
  100. for i in range(1,optcount):
  101. opt = OptionalEmitter(GroupEmitter([toks[0],opt]))
  102. return GroupEmitter([toks[0]] * mincount + [opt])
  103. else:
  104. return [toks[0]] * mincount
  105. def handleLiteral(toks):
  106. lit = ""
  107. for t in toks:
  108. if t[0] == "\\":
  109. if t[1] == "t":
  110. lit += '\t'
  111. else:
  112. lit += t[1]
  113. else:
  114. lit += t
  115. return LiteralEmitter(lit)
  116. def handleMacro(toks):
  117. macroChar = toks[0][1]
  118. if macroChar == "d":
  119. return CharacterRangeEmitter("0123456789")
  120. elif macroChar == "w":
  121. return CharacterRangeEmitter(srange("[A-Za-z0-9_]"))
  122. elif macroChar == "s":
  123. return LiteralEmitter(" ")
  124. else:
  125. raise ParseFatalException("",0,"unsupported macro character (" + macroChar + ")")
  126. def handleSequence(toks):
  127. return GroupEmitter(toks[0])
  128. def handleDot():
  129. return CharacterRangeEmitter(printables)
  130. def handleAlternative(toks):
  131. return AlternativeEmitter(toks[0])
  132. _parser = None
  133. def parser():
  134. global _parser
  135. if _parser is None:
  136. ParserElement.setDefaultWhitespaceChars("")
  137. lbrack,rbrack,lbrace,rbrace,lparen,rparen,colon,qmark = map(Literal,"[]{}():?")
  138. reMacro = Combine("\\" + oneOf(list("dws")))
  139. escapedChar = ~reMacro + Combine("\\" + oneOf(list(printables)))
  140. reLiteralChar = "".join(c for c in printables if c not in r"\[]{}().*?+|") + " \t"
  141. reRange = Combine(lbrack + SkipTo(rbrack,ignore=escapedChar) + rbrack)
  142. reLiteral = ( escapedChar | oneOf(list(reLiteralChar)) )
  143. reNonCaptureGroup = Suppress("?:")
  144. reDot = Literal(".")
  145. repetition = (
  146. ( lbrace + Word(nums)("count") + rbrace ) |
  147. ( lbrace + Word(nums)("minCount")+","+ Word(nums)("maxCount") + rbrace ) |
  148. oneOf(list("*+?"))
  149. )
  150. reRange.setParseAction(handleRange)
  151. reLiteral.setParseAction(handleLiteral)
  152. reMacro.setParseAction(handleMacro)
  153. reDot.setParseAction(handleDot)
  154. reTerm = ( reLiteral | reRange | reMacro | reDot | reNonCaptureGroup)
  155. reExpr = infixNotation( reTerm,
  156. [
  157. (repetition, 1, opAssoc.LEFT, handleRepetition),
  158. (None, 2, opAssoc.LEFT, handleSequence),
  159. (Suppress('|'), 2, opAssoc.LEFT, handleAlternative),
  160. ]
  161. )
  162. _parser = reExpr
  163. return _parser
  164. def count(gen):
  165. """Simple function to count the number of elements returned by a generator."""
  166. return sum(1 for _ in gen)
  167. def invert(regex):
  168. r"""Call this routine as a generator to return all the strings that
  169. match the input regular expression.
  170. for s in invert(r"[A-Z]{3}\d{3}"):
  171. print s
  172. """
  173. invReGenerator = GroupEmitter(parser().parseString(regex)).makeGenerator()
  174. return invReGenerator()
  175. def main():
  176. tests = r"""
  177. [A-EA]
  178. [A-D]*
  179. [A-D]{3}
  180. X[A-C]{3}Y
  181. X[A-C]{3}\(
  182. X\d
  183. foobar\d\d
  184. foobar{2}
  185. foobar{2,9}
  186. fooba[rz]{2}
  187. (foobar){2}
  188. ([01]\d)|(2[0-5])
  189. (?:[01]\d)|(2[0-5])
  190. ([01]\d\d)|(2[0-4]\d)|(25[0-5])
  191. [A-C]{1,2}
  192. [A-C]{0,3}
  193. [A-C]\s[A-C]\s[A-C]
  194. [A-C]\s?[A-C][A-C]
  195. [A-C]\s([A-C][A-C])
  196. [A-C]\s([A-C][A-C])?
  197. [A-C]{2}\d{2}
  198. @|TH[12]
  199. @(@|TH[12])?
  200. @(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9]))?
  201. @(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9])|OH(1[0-9]?|2[0-9]?|30?|[4-9]))?
  202. (([ECMP]|HA|AK)[SD]|HS)T
  203. [A-CV]{2}
  204. A[cglmrstu]|B[aehikr]?|C[adeflmorsu]?|D[bsy]|E[rsu]|F[emr]?|G[ade]|H[efgos]?|I[nr]?|Kr?|L[airu]|M[dgnot]|N[abdeiop]?|Os?|P[abdmortu]?|R[abefghnu]|S[bcegimnr]?|T[abcehilm]|Uu[bhopqst]|U|V|W|Xe|Yb?|Z[nr]
  205. (a|b)|(x|y)
  206. (a|b) (x|y)
  207. [ABCDEFG](?:#|##|b|bb)?(?:maj|min|m|sus|aug|dim)?[0-9]?(?:/[ABCDEFG](?:#|##|b|bb)?)?
  208. (Fri|Mon|S(atur|un)|T(hur|ue)s|Wednes)day
  209. A(pril|ugust)|((Dec|Nov|Sept)em|Octo)ber|(Febr|Jan)uary|Ju(ly|ne)|Ma(rch|y)
  210. """.split('\n')
  211. for t in tests:
  212. t = t.strip()
  213. if not t: continue
  214. print('-'*50)
  215. print(t)
  216. try:
  217. num = count(invert(t))
  218. print(num)
  219. maxprint = 30
  220. for s in invert(t):
  221. print(s)
  222. maxprint -= 1
  223. if not maxprint:
  224. break
  225. except ParseFatalException as pfe:
  226. print(pfe.msg)
  227. print('')
  228. continue
  229. print('')
  230. if __name__ == "__main__":
  231. main()