1.a) Input $ b ( ( a a ) a ) b $
Stack Curr Rest of Input Action
(top at right) Sym
--------------------------------------------------------------------
$ b ( ( a a ) a ) b $ Shift
$ b ( ( a a ) a ) b $ Shift
$ b ( ( a a ) a ) b $ Shift
$ b ( ( a a ) a ) b $ Shift
$ b ( ( a a ) a ) b $ Reduce: M --> a
$ b ( ( M a ) a ) b $ Shift
$ b ( ( M a ) a ) b $ Shift
$ b ( ( M a ) a ) b $ Reduce: L --> M a )
$ b ( ( L a ) b $ Reduce: M --> ( L
$ b ( M a ) b $ Shift
$ b ( M a ) b $ Shift
$ b ( M a ) b $ Reduce: L --> M a )
$ b ( L b $ Reduce: M --> ( L
$ b M b $ Shift
$ b M b $ Reduce: S --> b M b
$ S $ accept
b) Parse tree
S
|
+--------+--------------+
| | |
| M |
| | |
| +-----+ |
| | | |
| | L |
| | | |
| | +--------+--+ |
| | | | | |
| | M | | |
| | | | | |
| | +--+ | | |
| | | | | | |
| | | L | | |
| | | | | | |
| | | +--+--+ | | |
| | | | | | | | |
| | | M | | | | |
| | | | | | | | |
b ( ( a a ) a ) b
c) $ b ( ( ( a a ) a ) a ) b $
S --> b M b --> b ( L b --> b ( M a ) b --> b ( ( L a ) b -->
b ( ( M a ) a ) b --> b ( ( ( L a ) a ) b --> b ( ( ( M a ) a ) a ) b -->
b ( ( ( a a ) a ) a ) b
2.) Shift-Reduce parse of $ id + id * id ^ id $
Stack Curr Rest of Input Action
(top at right) Sym
----------------------------------------------------------------------
$ id + id * id ^ id $ Shift
$ id + id * id ^ id $ Reduce: F --> id
$ F + id * id ^ id $ Reduce: S --> F
$ S + id * id ^ id $ Reduce: T --> S
$ T + id * id ^ id $ Reduce: E --> T
$ E + id * id ^ id $ Shift
$ E + id * id ^ id $ Shift
$ E + id * id ^ id $ Reduce: F --> id
$ E + F * id ^ id $ Reduce: S --> F
$ E + S * id ^ id $ Reduce: T --> S
$ E + T * id ^ id $ Shift
$ E + T * id ^ id $ Shift
$ E + T * id ^ id $ Reduce: F --> id
$ E + T * F ^ id $ Shift
$ E + T * F ^ id $ Shift
$ E + T * F ^ id $ Reduce: F --> id
$ E + T * F ^ F $ Reduce: S --> F
$ E + T * F ^ S $ Reduce: S --> F ^ S
$ E + T * S $ Reduce: T --> T * S
$ E + T $ Reduce: E --> E + T
$ E $ Reduce: P --> E
$ P $ Accept
3.a) RPN of $ 7 + 5 * 4 ^ 3 $ is $7543^*+$
Note: in the answer, operands should in same order as before.
($43^5*7+$ is fine as an answer, except for this condition.)
3.b) Evaluate the RPN: process items left to right. Use a stack.
Push operands. Apply operators to stack and push result.
(Ignore initial $. Final $ marks end, but is otherwise ignored.
This resembles a shift-reduce parse. I chose not to use a
current symbol column.)
Stack Rest of Input Action
(top at right)
----------------------------------------------------------------------
7543^*+$ Push (4 times)
7 5 4 3 ^*+$ Apply ^ to top 2
7 5 64 *+$ Apply * to top 2
7 320 +$ Apply + to top 2
327 $ End of input
(answer is on top of stack)
3.c) RPN of $ 6 * (4 + 3) ^ (2 + 1) + 5 $ is $643+21+^*5+$
($43+21+^6*5+$ would be fine except for the above condition.)
Stack Rest of Input Action
(top at right)
----------------------------------------------------------------------
643+21+^*5+$ Push (3 times)
6 4 3 +21+^*5+$ Apply + to top 2
6 7 21+^*5+$ Push (2 times)
6 7 2 1 +^*5+$ Apply + to top 2
6 7 3 ^*5+$ Apply ^ to top 2
6 343 *5+$ Apply * to top 2
2058 5+$ Push 5
2058 5 +$ Apply + to top 2
2063