开发工具:
文件大小: 60kb
下载次数: 0
上传时间: 2019-10-13
详细说明：在编译器的前端设计中，对于LL分析和LR分析作为最重要的实现方式。该算法就是书本上的进一步实现Lets fill in the row for State 0 together. Looking back at our notes above, we see that on A we transition to
State 1 and on a we transition to State 2. Transitions on terminals like a are called " shifts and transitions on
non-terminals like A are marked as"gotos
C
b|+|$
0‖ shift2
go
All of the other entries are blank. So, for example, if we are parsing and we are in State 0 and we see a +, it's a
parse error
Now let's fill in the row for State 1. Checking our notes we see that on S we reduce S+A and we transition
to 3. Once again, a transition on a terminal like is a"shift
AB
shift 3
reduce s→
Now that we've seen all of the possible cell entries( shift, reduce and goto ), let's fill in the rest of the table all at
once. If you're following along at home, fill out the blank table on the previous page without looking at the answer
there alld then check to see if you got it right
B
0‖| shift2
goto 1
shift 3
reduce s→A
reduce A→a
reduce A→a
shift 5
g
reduce e→A+ B reduce A→A+B
reduce B→b
reduce b→b
Great! That table wor ked out perfectly. Sometimes you end up with a cell with two entries. For example, for
some other grammar maybe in State 7 when you see a you want to shift to 8 and reduce Q-E/T. That's called a
shift reduce conflict. There are also reduce/reduce conficts. This table does not have any of those, so the grammar
is LR(1). Convenient, since this is supposed to be an Lr(1) example. -
Now that we have the table, let's practice parsing something. How about the string a+b+b? Take a moment to
verify that it's in the grammar(does anyone actually do that when the book or notes asks them to? i thought not
When we say"parsing here, we're trying to get a derivation for S-a+b+b. LR parsing will give us the reverse
of a right-most derivation by reading the input left to right. Since this grammar is unambiguous(take a moment to
verify that! the right-most derivation is the same as the left-most derivation(it's the only derivation
When we simulate parsing we have to keep track of the Stack and the remaining input. We can use the the dFa
or the Table to figure out what state we are in given the Stack. Each time we perform a reduction we get part of the
derivation
We start in State 0 with nothing on the Stack. The input is a+b+b. We see that on a we shift to State 2. Shift
means"take the first part of the input and put it on the stack
So now were in State 2 with a on the Stack. The input is +6+6. We see that on+ we reduce A -a. Reduce
X Y means"take Y off the top of the stack and put X there instead So we take a off t he top of the stack and
put A there instead. But what state are we in now? One way to find out is to run the DFA on the Stack, starting in
State 0. We see that on A we go to State 1. We could also(equivalently, since they hold the same information)use
the Table and the Stack. Starting inl State 0 on the Table, we see that ol A we goto 1. So anly way you slice it we're
So now were in State 1 with A on the Stack. The input is +b+b. We see that on we shift to State 3. So now
the Stack has A+(where the top of the Stack is on the right) and the input has b+b
So now were in State 3 with A+ on the Stack and b+ b left in the input. We look up( 3, b) in the table and find
that we should shift to state 5. so we take the b from the input and put it on the Stack, leaving us with +b in the
input and A+b on the Stack
Now were in State 5 with A+b on the Stack and +b left in the input. Looking in the table we see that on
we reduce B-b. So we take the b off the top of the stack and replace it with a b, giving us A +B. The input is
unchanged. Where are we now? We have to feed the Stack to the DFA (or the Table) to find out. Starting in State
0, on A we goto State 1 and then on we goto State 3 and then on b we goto State 4. So we're in State 4
Now were in State 4 and we have A+ B on the Stack and +b left in the input. On+ we see that we reduce
A-A+B, so we take A+B off the Stack and put an a there. so now the stack has just A. The input is unchanged
What state are we in? Run the dFa (or the Table) on the Stack starting from State 0. On A we goto State 1,so
that’sit.
Here we are in State 1 with A on the Stack and +b left in the input. The action is"shift 3, so we consume the
and put it on the Stack, giving us A+ on the Stack and b left in the input
So now we're in State 3 with A+ on the Stack and b in the input. On b we shift to State 5. So now we have
A+b on the Stack and S left in the input. We better not do ally Inore shifts, because we dont have any input left to
consume
Now were in State 5 with A+b on the Stack and s in the input. State 5 on S reduces B,b, so we take the
b off the top of the stack and replace it with B. That gives us A+B. What state are we in? Run the dfa (or the
Table)on the Stack. Starting in State 0, on A we goto State 1 and then on we goto State 3 and then on b we
goto State 4. So State 4 it is
Now were in State 4 with A+ b on the Stack and S in the input. We reduce A-A+B, so now the Stack is A
and we should go to State 1.(Why? For a hint, look at what we did in State 4 last time.
Now we're in State 1 with A on the Stack and S in the input. So we reduce S-+A. So now the stack has S and
the input is S. Since s is what we wanted to end up with and we covered all the input. by convention we accept. We
could also have had an explicit "accept somewhere in our Table, but thats not critically important
I hope you had fun with Lr(1) parsing
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
