
In the past few units we've used regular expressions to classify or layout sets of strings.

It turns out that grammars can encode all of these regular languages or regular expressions

that we've been working with previously.

Here I've written a grammar for number that's going to recognize

exactly the same language, exactly the same set of strings as the regular expression above.

We can rewrite number to be a digit followed by more digits.

This construction is meant to mimic or get the same idea as this plus.

We need at least one, but we could have some more.

Down here I've just listed out all of the digits longhand.

Well, I haven't on this particular page but you could imagine I could write out

2 through 8 as optional alternate rewrite rules in our grammar.

More digits is where a lot of the action happens.

One possibility is that we have one digit followed by potentially even more,

and another is that we give up.

I could write epsilon. This means more_digits goes to nothing.

For example, down here at the bottom, I have a derivation

starting with number getting to the number 42.

Number goes to digit moredigits, using our first rulerule number one.

Then we're going to turn more digits into digit more_digit, using rule number 2.

Thenoh my gosh, classic professor mistakeyou cannot take me anywhere.

Shwoopoh look. It wraps. That that amazing.

The from digit digit more_digits, we're going to turn more_digits into the empty string,

using rule three. Now we're left with digit digit nothing.

I'm going to turn that second digit into a 2this empty string isn't really there.

Then I'll turn that first digit into a four. Huzzah.