1

I am creating a simple (context-free) grammar, such as this one:

E -> E + E
E -> E * E
E -> 0
E -> 1

For testing purposes, I would like to generate all expressions from this grammar, up to a certain depth. For example:

# depth 0:
0
1
# depth 1:
0 + 0
0 + 1
1 + 0
1 + 1
0 * 0
0 * 1
1 * 0
1 * 1
# depth 2:
(0 + 0) + 0
...
1 * (1 + 1)
...
(1 + 1) * (1 + 1)
...

What is the easiest way to achieve this in Python? Maybe I can use an existing parsing library (such as ANTLR, PLY, Lark) to help with this?

I have found this similar question, but it refers to a simpler grammar than mine.

Peter
  • 401
  • 1
  • 5
  • 17
  • 1
    Have you tried the simple approach of queuing up every possible transition from every intermediate step? E.g., start with a queue of (E), then enqueue `(E+E, E*E, 1, 0)`, then dequeue E+E, enqueue `(E+E+E, E*E+E, E+E*E, 1+E, 0+E, E+0, E+1)`, repeat forever? – Welbog May 28 '21 at 10:29
  • The easiest way is to use a library indeed. I recommend you do it, specially if you plan to complexify your grammar later. – Lenormju May 28 '21 at 12:19
  • @Welbog That is a neat idea in case I do not find a library for my task, thanks! – Peter May 28 '21 at 14:27
  • @Lenormju I was thinking the same, but I did not find this functionality in any parsing library (maybe I did not use the right search terms). – Peter May 28 '21 at 14:28

1 Answers1

0

You can use a recursive generator function:

import re, itertools as it
s = """
E -> E + E
E -> E * E
E -> 0
E -> 1
"""
g = [((k:=re.findall('\w+|[\*\+]', i))[0], k[1:]) for i in s.split('\n') if i]
o = {a for a, _ in g}
def get_expr(d, s = None):
   if not d:
      for a, b in g:
         if all(i not in o for i in b) and (s is None or a in s):
            yield ' '.join(b)
   else:
      for a, b in g:
         if s is None or a in s:
            r = [[i] if i not in o else get_expr(d-1, s=(s or [])+[i]) for i in b]           
            yield from it.product(*r)

for i in range(3):
   print(list(get_expr(i)))

Output:

['0', '1']
[('0', '+', '0'), ('0', '+', '1'), ('1', '+', '0'), ('1', '+', '1'), ('0', '*', '0'), ('0', '*', '1'), ('1', '*', '0'), ('1', '*', '1'), ('0',), ('1',)]
[(('0', '+', '0'), '+', ('0', '+', '0')), (('0', '+', '0'), '+', ('0', '+', '1')), (('0', '+', '0'), '+', ('1', '+', '0')), (('0', '+', '0'), '+', ('1', '+', '1')), (('0', '+', '0'), '+', ('0', '*', '0')), (('0', '+', '0'), '+', ('0', '*', '1')), (('0', '+', '0'), '+', ('1', '*', '0')), (('0', '+', '0'), '+', ('1', '*', '1')), (('0', '+', '0'), '+', ('0',)), (('0', '+', '0'), '+', ('1',)), (('0', '+', '1'), '+', ('0', '+', '0')), (('0', '+', '1'), '+', ('0', '+', '1')), (('0', '+', '1'), '+', ('1', '+', '0')), (('0', '+', '1'), '+', ('1', '+', '1')), (('0', '+', '1'), '+', ('0', '*', '0')), (('0', '+', '1'), '+', ('0', '*', '1')), (('0', '+', '1'), '+', ('1', '*', '0')), (('0', '+', '1'), '+', ('1', '*', '1')), (('0', '+', '1'), '+', ('0',)), (('0', '+', '1'), '+', ('1',)), (('1', '+', '0'), '+', ('0', '+', '0')), (('1', '+', '0'), '+', ('0', '+', '1')), (('1', '+', '0'), '+', ('1', '+', '0')), (('1', '+', '0'), '+', ('1', '+', '1')), (('1', '+', '0'), '+', ('0', '*', '0')), (('1', '+', '0'), '+', ('0', '*', '1')), (('1', '+', '0'), '+', ('1', '*', '0')), (('1', '+', '0'), '+', ('1', '*', '1')), (('1', '+', '0'), '+', ('0',)), (('1', '+', '0'), '+', ('1',)), (('1', '+', '1'), '+', ('0', '+', '0')), (('1', '+', '1'), '+', ('0', '+', '1')), (('1', '+', '1'), '+', ('1', '+', '0')), (('1', '+', '1'), '+', ('1', '+', '1')), (('1', '+', '1'), '+', ('0', '*', '0')), (('1', '+', '1'), '+', ('0', '*', '1')), (('1', '+', '1'), '+', ('1', '*', '0')), (('1', '+', '1'), '+', ('1', '*', '1')), (('1', '+', '1'), '+', ('0',)), (('1', '+', '1'), '+', ('1',)), (('0', '*', '0'), '+', ('0', '+', '0')), (('0', '*', '0'), '+', ('0', '+', '1')), (('0', '*', '0'), '+', ('1', '+', '0')), (('0', '*', '0'), '+', ('1', '+', '1')), (('0', '*', '0'), '+', ('0', '*', '0')), (('0', '*', '0'), '+', ('0', '*', '1')), (('0', '*', '0'), '+', ('1', '*', '0')), (('0', '*', '0'), '+', ('1', '*', '1')), (('0', '*', '0'), '+', ('0',)), (('0', '*', '0'), '+', ('1',)), (('0', '*', '1'), '+', ('0', '+', '0')), (('0', '*', '1'), '+', ('0', '+', '1')), (('0', '*', '1'), '+', ('1', '+', '0')), (('0', '*', '1'), '+', ('1', '+', '1')), (('0', '*', '1'), '+', ('0', '*', '0')), (('0', '*', '1'), '+', ('0', '*', '1')), (('0', '*', '1'), '+', ('1', '*', '0')), (('0', '*', '1'), '+', ('1', '*', '1')), (('0', '*', '1'), '+', ('0',)), (('0', '*', '1'), '+', ('1',)), (('1', '*', '0'), '+', ('0', '+', '0')), (('1', '*', '0'), '+', ('0', '+', '1')), (('1', '*', '0'), '+', ('1', '+', '0')), (('1', '*', '0'), '+', ('1', '+', '1')), (('1', '*', '0'), '+', ('0', '*', '0')), (('1', '*', '0'), '+', ('0', '*', '1')), (('1', '*', '0'), '+', ('1', '*', '0')), (('1', '*', '0'), '+', ('1', '*', '1')), (('1', '*', '0'), '+', ('0',)), (('1', '*', '0'), '+', ('1',)), (('1', '*', '1'), '+', ('0', '+', '0')), (('1', '*', '1'), '+', ('0', '+', '1')), (('1', '*', '1'), '+', ('1', '+', '0')), (('1', '*', '1'), '+', ('1', '+', '1')), (('1', '*', '1'), '+', ('0', '*', '0')), (('1', '*', '1'), '+', ('0', '*', '1')), (('1', '*', '1'), '+', ('1', '*', '0')), (('1', '*', '1'), '+', ('1', '*', '1')), (('1', '*', '1'), '+', ('0',)), (('1', '*', '1'), '+', ('1',)), (('0',), '+', ('0', '+', '0')), (('0',), '+', ('0', '+', '1')), (('0',), '+', ('1', '+', '0')), (('0',), '+', ('1', '+', '1')), (('0',), '+', ('0', '*', '0')), (('0',), '+', ('0', '*', '1')), (('0',), '+', ('1', '*', '0')), (('0',), '+', ('1', '*', '1')), (('0',), '+', ('0',)), (('0',), '+', ('1',)), (('1',), '+', ('0', '+', '0')), (('1',), '+', ('0', '+', '1')), (('1',), '+', ('1', '+', '0')), (('1',), '+', ('1', '+', '1')), (('1',), '+', ('0', '*', '0')), (('1',), '+', ('0', '*', '1')), (('1',), '+', ('1', '*', '0')), (('1',), '+', ('1', '*', '1')), (('1',), '+', ('0',)), (('1',), '+', ('1',)), (('0', '+', '0'), '*', ('0', '+', '0')), (('0', '+', '0'), '*', ('0', '+', '1')), (('0', '+', '0'), '*', ('1', '+', '0')), (('0', '+', '0'), '*', ('1', '+', '1')), (('0', '+', '0'), '*', ('0', '*', '0')), (('0', '+', '0'), '*', ('0', '*', '1')), (('0', '+', '0'), '*', ('1', '*', '0')), (('0', '+', '0'), '*', ('1', '*', '1')), (('0', '+', '0'), '*', ('0',)), (('0', '+', '0'), '*', ('1',)), (('0', '+', '1'), '*', ('0', '+', '0')), (('0', '+', '1'), '*', ('0', '+', '1')), (('0', '+', '1'), '*', ('1', '+', '0')), (('0', '+', '1'), '*', ('1', '+', '1')), (('0', '+', '1'), '*', ('0', '*', '0')), (('0', '+', '1'), '*', ('0', '*', '1')), (('0', '+', '1'), '*', ('1', '*', '0')), (('0', '+', '1'), '*', ('1', '*', '1')), (('0', '+', '1'), '*', ('0',)), (('0', '+', '1'), '*', ('1',)), (('1', '+', '0'), '*', ('0', '+', '0')), (('1', '+', '0'), '*', ('0', '+', '1')), (('1', '+', '0'), '*', ('1', '+', '0')), (('1', '+', '0'), '*', ('1', '+', '1')), (('1', '+', '0'), '*', ('0', '*', '0')), (('1', '+', '0'), '*', ('0', '*', '1')), (('1', '+', '0'), '*', ('1', '*', '0')), (('1', '+', '0'), '*', ('1', '*', '1')), (('1', '+', '0'), '*', ('0',)), (('1', '+', '0'), '*', ('1',)), (('1', '+', '1'), '*', ('0', '+', '0')), (('1', '+', '1'), '*', ('0', '+', '1')), (('1', '+', '1'), '*', ('1', '+', '0')), (('1', '+', '1'), '*', ('1', '+', '1')), (('1', '+', '1'), '*', ('0', '*', '0')), (('1', '+', '1'), '*', ('0', '*', '1')), (('1', '+', '1'), '*', ('1', '*', '0')), (('1', '+', '1'), '*', ('1', '*', '1')), (('1', '+', '1'), '*', ('0',)), (('1', '+', '1'), '*', ('1',)), (('0', '*', '0'), '*', ('0', '+', '0')), (('0', '*', '0'), '*', ('0', '+', '1')), (('0', '*', '0'), '*', ('1', '+', '0')), (('0', '*', '0'), '*', ('1', '+', '1')), (('0', '*', '0'), '*', ('0', '*', '0')), (('0', '*', '0'), '*', ('0', '*', '1')), (('0', '*', '0'), '*', ('1', '*', '0')), (('0', '*', '0'), '*', ('1', '*', '1')), (('0', '*', '0'), '*', ('0',)), (('0', '*', '0'), '*', ('1',)), (('0', '*', '1'), '*', ('0', '+', '0')), (('0', '*', '1'), '*', ('0', '+', '1')), (('0', '*', '1'), '*', ('1', '+', '0')), (('0', '*', '1'), '*', ('1', '+', '1')), (('0', '*', '1'), '*', ('0', '*', '0')), (('0', '*', '1'), '*', ('0', '*', '1')), (('0', '*', '1'), '*', ('1', '*', '0')), (('0', '*', '1'), '*', ('1', '*', '1')), (('0', '*', '1'), '*', ('0',)), (('0', '*', '1'), '*', ('1',)), (('1', '*', '0'), '*', ('0', '+', '0')), (('1', '*', '0'), '*', ('0', '+', '1')), (('1', '*', '0'), '*', ('1', '+', '0')), (('1', '*', '0'), '*', ('1', '+', '1')), (('1', '*', '0'), '*', ('0', '*', '0')), (('1', '*', '0'), '*', ('0', '*', '1')), (('1', '*', '0'), '*', ('1', '*', '0')), (('1', '*', '0'), '*', ('1', '*', '1')), (('1', '*', '0'), '*', ('0',)), (('1', '*', '0'), '*', ('1',)), (('1', '*', '1'), '*', ('0', '+', '0')), (('1', '*', '1'), '*', ('0', '+', '1')), (('1', '*', '1'), '*', ('1', '+', '0')), (('1', '*', '1'), '*', ('1', '+', '1')), (('1', '*', '1'), '*', ('0', '*', '0')), (('1', '*', '1'), '*', ('0', '*', '1')), (('1', '*', '1'), '*', ('1', '*', '0')), (('1', '*', '1'), '*', ('1', '*', '1')), (('1', '*', '1'), '*', ('0',)), (('1', '*', '1'), '*', ('1',)), (('0',), '*', ('0', '+', '0')), (('0',), '*', ('0', '+', '1')), (('0',), '*', ('1', '+', '0')), (('0',), '*', ('1', '+', '1')), (('0',), '*', ('0', '*', '0')), (('0',), '*', ('0', '*', '1')), (('0',), '*', ('1', '*', '0')), (('0',), '*', ('1', '*', '1')), (('0',), '*', ('0',)), (('0',), '*', ('1',)), (('1',), '*', ('0', '+', '0')), (('1',), '*', ('0', '+', '1')), (('1',), '*', ('1', '+', '0')), (('1',), '*', ('1', '+', '1')), (('1',), '*', ('0', '*', '0')), (('1',), '*', ('0', '*', '1')), (('1',), '*', ('1', '*', '0')), (('1',), '*', ('1', '*', '1')), (('1',), '*', ('0',)), (('1',), '*', ('1',)), ('0',), ('1',)]
Ajax1234
  • 69,937
  • 8
  • 61
  • 102