Volodymyr  Prysiazhniuk Volodymyr Prysiazhniuk - 1 month ago 10
Python Question

How to generate all possible expressions satisfying a grammar

I have a grammar for my application with following expressions:

(FIND, SEARCH, Lookup) [a, the, an, for] ITEM [in, at] (NEST, SHELF, DESK)


Items in round brackets "()" - required, items in square brackets are optional, words without brackets are required.

Simple expressions for me would be:


  • FIND an ITEM at DESK

  • FIND an ITEM in DESK

  • Lookup the ITEM in NEST

  • SEARCH for ITEM at SHELF



Is there any parsing methods or libraries I can use to generate all possible combinations?

Answer Source

Sjoerd's answer points to exrex. Since your expression can be written as a regex this library will do it.

>>> import exrex
>>> list(exrex.generate(r'(FIND|SEARCH|Lookup)( a| the| an| for)? ITEM ( in| at)?( NEST| SHELF| DESK)'))
['FIND ITEM  NEST', 'FIND ITEM  SHELF', 'FIND ITEM  DESK', 'FIND ITEM  in NEST', 'FIND ITEM  in SHELF', 'FIND ITEM  in DESK', 'FIND ITEM  at NEST', 'FIND ITEM  at SHELF', 'FIND ITEM  at DESK', 'FIND a ITEM  NEST', 'FIND a ITEM  SHELF', 'FIND a ITEM  DESK', 'FIND a ITEM  in NEST', 'FIND a ITEM  in SHELF', 'FIND a ITEM  in DESK', 'FIND a ITEM  at NEST', 'FIND a ITEM  at SHELF', 'FIND a ITEM  at DESK', 'FIND the ITEM  NEST', 'FIND the ITEM  SHELF', 'FIND the ITEM  DESK', 'FIND the ITEM  in NEST', 'FIND the ITEM  in SHELF', 'FIND the ITEM  in DESK', 'FIND the ITEM  at NEST', 'FIND the ITEM  at SHELF', 'FIND the ITEM  at DESK', 'FIND an ITEM  NEST', 'FIND an ITEM  SHELF', 'FIND an ITEM  DESK', 'FIND an ITEM  in NEST', 'FIND an ITEM  in SHELF', 'FIND an ITEM  in DESK', 'FIND an ITEM  at NEST', 'FIND an ITEM  at SHELF', 'FIND an ITEM  at DESK', 'FIND for ITEM  NEST', 'FIND for ITEM  SHELF', 'FIND for ITEM  DESK', 'FIND for ITEM  in NEST', 'FIND for ITEM  in SHELF', 'FIND for ITEM  in DESK', 'FIND for ITEM  at NEST', 'FIND for ITEM  at SHELF', 'FIND for ITEM  at DESK', 'SEARCH ITEM  NEST', 'SEARCH ITEM  SHELF', 'SEARCH ITEM  DESK', 'SEARCH ITEM  in NEST', 'SEARCH ITEM  in SHELF', 'SEARCH ITEM  in DESK', 'SEARCH ITEM  at NEST', 'SEARCH ITEM  at SHELF', 'SEARCH ITEM  at DESK', 'SEARCH a ITEM  NEST', 'SEARCH a ITEM  SHELF', 'SEARCH a ITEM  DESK', 'SEARCH a ITEM  in NEST', 'SEARCH a ITEM  in SHELF', 'SEARCH a ITEM  in DESK', 'SEARCH a ITEM  at NEST', 'SEARCH a ITEM  at SHELF', 'SEARCH a ITEM  at DESK', 'SEARCH the ITEM  NEST', 'SEARCH the ITEM  SHELF', 'SEARCH the ITEM  DESK', 'SEARCH the ITEM  in NEST', 'SEARCH the ITEM  in SHELF', 'SEARCH the ITEM  in DESK', 'SEARCH the ITEM  at NEST', 'SEARCH the ITEM  at SHELF', 'SEARCH the ITEM  at DESK', 'SEARCH an ITEM  NEST', 'SEARCH an ITEM  SHELF', 'SEARCH an ITEM  DESK', 'SEARCH an ITEM  in NEST', 'SEARCH an ITEM  in SHELF', 'SEARCH an ITEM  in DESK', 'SEARCH an ITEM  at NEST', 'SEARCH an ITEM  at SHELF', 'SEARCH an ITEM  at DESK', 'SEARCH for ITEM  NEST', 'SEARCH for ITEM  SHELF', 'SEARCH for ITEM  DESK', 'SEARCH for ITEM  in NEST', 'SEARCH for ITEM  in SHELF', 'SEARCH for ITEM  in DESK', 'SEARCH for ITEM  at NEST', 'SEARCH for ITEM  at SHELF', 'SEARCH for ITEM  at DESK', 'Lookup ITEM  NEST', 'Lookup ITEM  SHELF', 'Lookup ITEM  DESK', 'Lookup ITEM  in NEST', 'Lookup ITEM  in SHELF', 'Lookup ITEM  in DESK', 'Lookup ITEM  at NEST', 'Lookup ITEM  at SHELF', 'Lookup ITEM  at DESK', 'Lookup a ITEM  NEST', 'Lookup a ITEM  SHELF', 'Lookup a ITEM  DESK', 'Lookup a ITEM  in NEST', 'Lookup a ITEM  in SHELF', 'Lookup a ITEM  in DESK', 'Lookup a ITEM  at NEST', 'Lookup a ITEM  at SHELF', 'Lookup a ITEM  at DESK', 'Lookup the ITEM  NEST', 'Lookup the ITEM  SHELF', 'Lookup the ITEM  DESK', 'Lookup the ITEM  in NEST', 'Lookup the ITEM  in SHELF', 'Lookup the ITEM  in DESK', 'Lookup the ITEM  at NEST', 'Lookup the ITEM  at SHELF', 'Lookup the ITEM  at DESK', 'Lookup an ITEM  NEST', 'Lookup an ITEM  SHELF', 'Lookup an ITEM  DESK', 'Lookup an ITEM  in NEST', 'Lookup an ITEM  in SHELF', 'Lookup an ITEM  in DESK', 'Lookup an ITEM  at NEST', 'Lookup an ITEM  at SHELF', 'Lookup an ITEM  at DESK', 'Lookup for ITEM  NEST', 'Lookup for ITEM  SHELF', 'Lookup for ITEM  DESK', 'Lookup for ITEM  in NEST', 'Lookup for ITEM  in SHELF', 'Lookup for ITEM  in DESK', 'Lookup for ITEM  at NEST', 'Lookup for ITEM  at SHELF', 'Lookup for ITEM  at DESK']