# Expanding Exp – Programming Languages

So let’s start coding this up. There’s our first grammar rule, expression goes to expression + expression. Our second grammar rule, very similar but for the minus. All right, so here I actually have quite a bit of Python code, and we’re going to walk through it together, and then you’re going to help me finish it out, so here’s our definition of our grammar. It has 4 rewrite rules, and where I’m going to need your help is given a list of tokens and a grammar, I want to find all possible ways to expand it using those rules. Let me just show you what I mean by that. Here’s our grammar again, and let’s say that we started with “a exp.” I would want us to come out with “a exp + exp,” “a exp – exp,” “a ( exp ),” and “a num.” For each of these possible token positions and for each grammar rule, we removed the starting token and replaced it with the right-hand side of the grammar rule. This is the way we’re going to enumerate all of the valid strings in the grammar. Now, you’ll notice that I’ve made more expressions in many of these cases, so I could go from here and start and expand it again and get a few more strings until eventually I’m full entirely of terminals. I’m going to call the number of times I do this the depth. If we start with a exp and we expand it to depth 1, we get 4 new utterances, 4 new sentences. You’re going to have to help me write that expansion procedure. Down here I’ve got some code to help us print it out. For now, we’re only going to enumerate things up to a depth of 1, and we’re going to start with just expression, and then we’re going to use your expand procedure to make many more utterances, many more sentences starting from expression, probably 4 more, so then we’ll have a total of 5, and then at the end of the day we print them all out. If you do it correctly, this is the output you expect to see, our original sentence, but then it’s been expanded with 4 more, expression + expression, expression – expression, open expression close and num. And in fact, if we go back up here and change this to a exp, the example we worked through in the comments, we get the expected output. A is unchanged because there’s no rewrite rule in our grammar for dealing with it, but a exp becomes a expression + expression, a expression – expression, a open expression close, and a num. Your job, submit via the interpreter the correct definition for the expand procedure so that it does this. Here’s a hint. You’re going to need yield with high probability, and you may also want to end up using list comprehensions. By the way, this is a very tricky quiz. This is not easy to get right the first time, so you should not feel bad if something goes wrong. Give this your all, but it is very difficult compared to what we’ve been up to so far.