## 04-43 Writing Reductions Solution

• 0:00 - 0:02
Let's go through one way to do this.
• 0:02 - 0:08
Hopefully what we're currently looking at is x goes to ab dot nothing come from j.
• 0:08 - 0:13
Hopefully then, if we look back to chart j where we originally came from,
• 0:13 - 0:19
it will have some rule something go to blah, blah, blah dot x.
• 0:19 - 0:21
This is the important part.
• 0:21 - 0:27
We're reducing goes to ab, so I really hope somebody was looking for an x.
• 0:27 - 0:30
If they were, then that can be one of our reductions.
• 0:30 - 0:35
Once again, we're going to use the phenomenal cosmic power of Python list comprehensions.
• 0:35 - 0:41
In general, we're going to take all of these states that were already in chart j
• 0:41 - 0:43
and just modify them a bit.
• 0:43 - 0:47
Let's call each one of those states in chart j jstate.
• 0:47 - 0:51
Conceptually, what we're going to do is move the red dot over one.
• 0:51 - 0:58
Our return value, the new state we're returning, is going to have this same y that we saw from jstate.
• 0:58 - 1:01
Whatever that is that's still going to be our left-hand side.
• 1:01 - 1:05
Then we want to take whatever jstate had before the dot,
• 1:05 - 1:09
and that corresponds to all of this stuff that I've sort of left out here,
• 1:09 - 1:15
but then add on x, because we're shifting over x, conceptually, as we do the reduction.
• 1:15 - 1:20
Now we want to take everything jstate had after the dot, except we want to remove the x,
• 1:20 - 1:23
because we shifted the red dot over it.
• 1:23 - 1:27
Everything jstate had after the dot was j-state bracket 2.
• 1:27 - 1:30
and we're going to do range selection on that to get rid of the first element.
• 1:30 - 1:33
Then it looks like I can't preplan.
• 1:33 - 1:37
Whatever this k value was, we're just going to leave it alone.
• 1:37 - 1:40
Jstate 3 corresponds to k.
• 1:40 - 1:45
However, we only want to do this if certain conditions hold.
• 1:45 - 1:48
First, cd has to be the empty list which corresponds
• 1:48 - 1:51
to this red dot being as far to the right as possible.
• 1:51 - 1:56
The second thing we have to check for is that this x and that one match exactly.
• 1:56 - 2:03
This x was the first element of jstate 0 1 2, so I'll check to make sure that jstate 2 is not empty.
• 2:03 - 2:07
If this red dot were all the way to the right, there would be nothing there to check for.
• 2:07 - 2:13
If it's not empty, I'm going to check its first character and make sure that matches up with our x.
• 2:13 -
Those are all of the states we bring in as part of doing reductions.
Title:
04-43 Writing Reductions Solution
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
02:17