| |
[Below, I didn't ask for the notations in red,
nor did I ask for the parse tree in Problem 2.
I added these to make the material clearer.]
1.a) Input $ b ( ( a a ) a ) b $
Stack Curr Rest of Input Action Reduction
(top at right) Sym Number
---------------------------------------------------------------------------------
$ 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 1
$ b ( ( M a ) a ) b $ Shift
$ b ( ( M a ) a ) b $ Shift
$ b ( ( M a ) a ) b $ Reduce: L --> M a ) 2
$ b ( ( L a ) b $ Reduce: M --> ( L 3
$ b ( M a ) b $ Shift
$ b ( M a ) b $ Shift
$ b ( M a ) b $ Reduce: L --> M a ) 4
$ b ( L b $ Reduce: M --> ( L 5
$ b M b $ Shift
$ b M b $ Reduce: S --> b M b 6
$ S $ accept
b) Parse tree for the above parse, showing each reduction used in order:
S
|6
+--------------+-----+------------------+
| | |
| M |
| |5 |
| +---------+---------+ |
| | | |
| | L |
| | |4 |
| | +---------+----+----+ |
| | | | | |
| | M | | |
| | |3 | | |
| | +----+----+ | | |
| | | | | | |
| | | L | | |
| | | |2 | | |
| | | +----+----+ | | |
| | | | | | | | |
| | | M | | | | |
| | | |1 | | | | |
b ( ( a a ) a ) b
c) Here is another sentence defined by this grammar:
$ b ( ( ( a a ) a ) a ) b $
Here is a leftmost derivation for the above sentence:
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 + id $
Stack Curr Rest of Input Action Reduction
(top at right) Sym Number
----------------------------------------------------------------------------
$ id + id * id ^ id + id $ Shift
$ id + id * id ^ id + id $ Reduce: F --> id 1
$ F + id * id ^ id + id $ Reduce: S --> F 2
$ S + id * id ^ id + id $ Reduce: T --> S 3
$ T + id * id ^ id + id $ Reduce: E --> T 4
$ E + id * id ^ id + id $ Shift
$ E + id * id ^ id + id $ Shift
$ E + id * id ^ id + id $ Reduce: F --> id 5
$ E + F * id ^ id + id $ Reduce: S --> F 6
$ E + S * id ^ id + id $ Reduce: T --> S 7
$ E + T * id ^ id + id $ Shift
$ E + T * id ^ id + id $ Shift
$ E + T * id ^ id + id $ Reduce: F --> id 8
$ E + T * F ^ id + id $ Shift
$ E + T * F ^ id + id $ Shift
$ E + T * F ^ id + id $ Reduce: F --> id 9
$ E + T * F ^ F + id $ Reduce: S --> F 10
$ E + T * F ^ S + id $ Reduce: S --> F ^ S 11
$ E + T * S + id $ Reduce: T --> T * S 12
$ E + T + id $ Reduce: E --> E + T 13
$ E + id $ Shift
$ E + id $ Shift
$ E + id $ Reduce: F --> id 14
$ E + F $ Reduce: S --> F 15
$ E + S $ Reduce: T --> S 16
$ E + T $ Reduce: E --> E + T 17
$ E $ Reduce: P --> E 18
$ P $ Acc
Parse tree (not asked for), showing each reduction used in order.
(Notice that it is constructed bottom-up and left-to-right.)
P
|18
E
|17
+--------------------------------+-----+
| | |
E | |
|13 | |
+----+----------+ | |
| | | | |
| | T | |
| | |12 | |
| | +----+----------+ | |
| | | | | | |
E | | | S | |
|4 | | | |11 | |
T | T | +----+-----+ | T
|3 | |7 | | | | | |16
S | S | | | S | S
|2 | |6 | | | |10 | |15
F | F | F | F | F
|1 | |5 | |8 | |9 | |14
id + id * id ^ id + id
Rightmost derivation backwards (not asked for).
In red parens is reduction used for next line.
id + id * id ^ id + id <=== ( 1)
F + id * id ^ id + id <=== ( 2)
S + id * id ^ id + id <=== ( 3)
T + id * id ^ id + id <=== ( 4)
E + id * id ^ id + id <=== ( 5)
E + F * id ^ id + id <=== ( 6)
E + S * id ^ id + id <=== ( 7)
E + T * id ^ id + id <=== ( 8)
E + T * F ^ id + id <=== ( 9)
E + T * F ^ F + id <=== (10)
E + T * F ^ S + id <=== (11)
E + T * S + id <=== (12)
E + T + id <=== (13)
E + id <=== (14)
E + F <=== (15)
E + S <=== (16)
E + T <=== (17)
E <=== (18)
P
3. RPN Evaluator
There was a huge variation in how students wrote this program.
Students employed 3 basic strategies, with variations and high-tech tweeks.
3.1: Straightforward if-elif-else based on the operator.
Most students used this method.
# rpn.py: evaluate RPN
import sys
def error(n):
sys.stdout.write("Error: " + str(n) + "\n")
def eval_rpn(s):
if len(s) == 0:
error(0)
return None
st = []
for c in s:
if c.isdigit():
st.append(float(c))
elif len(st) >= 2:
p2 = st.pop()
p1 = st.pop()
if c == '+':
val = p1 + p2
elif c == '-':
val = p1 - p2
elif c == '*':
val = p1 * p2
elif c == '/':
val = p1 / p2
elif c == '^':
val = p1 ** p2
else:
error(1)
st.append(val)
else:
error(2)
# end of while
if len(st) != 1:
error(3)
return st[0]
# end of eval
def prob3(s):
res = eval_rpn(s)
sys.stdout.write("rpn:" + s + ", res:" + str(res) + "\n")
prob3("23+")
prob3("234*+")
prob3("34*5+")
prob3("23+4*")
prob3("324+*51+/2-")
prob3("53+21+2^^")
prob3("2345^*6*+7+")
prob3("32^41*2*-12/^3-21*/")
prob3("23-41+5*^6/24-7*-8-")
Output:
% python rpn.py
rpn:23+, res:5.0
rpn:234*+, res:14.0
rpn:34*5+, res:17.0
rpn:23+4*, res:20.0
rpn:324+*51+/2-, res:1.0
rpn:53+21+2^^, res:134217728.0
rpn:2345^*6*+7+, res:18441.0
rpn:32^41*2*-12/^3-21*/, res:-1.0
rpn:23-41+5*^6/24-7*-8-, res:5.83333333333
|
3.2: Tricky: convert the current portion of RPN that one wants
to evaluate into infix form (putting the operator in the middle),
and then use Python eval. At least 6 students used some variation
of this method.
#!/usr/bin/python
"""
"rpn.py", by Sean Soderman
Take in RPN strings from a file and translates them to Python
expressions, then evaluates them (as floating point numbers)
and prints the result to stdout.
"""
import sys
import re
fd = 0
#Translate carats to double stars for Python operations
p = {'^' : '**'}
#'in' is a satisfying boolean operation to use
ops = ['*', '+', '/', '-', '^']
if len(sys.argv) < 2:
print("Usage: %s " % (sys.argv[0]))
sys.exit(1)
else:
fd = open(sys.argv[1])
for line in fd:
#Refresh stack between lines.
stack = []
for char in line:
if char.isdigit():
stack.append(char)
#I have hit an operator
elif char in ops:
op = p.get(char, char)
num2 = stack.pop()
num1 = stack.pop()
stack.append(str(eval(num1 + op + num2)))
#Hit a newline
else:
print(float(stack[0]))
|
3.3: I wanted to use a Python dictionary, with second entries
the function to use. After discovering the "operator" module, I was
able to get it to work. At least 5 students (plus me) used some variation
on this method.
# rpn.py: evaluate RPN
import sys
from operator import *
ops = {'+':add, '-':sub, '*':mul, '/':div, '^':pow,
'%':mod} # last entry added later
def error(n):
sys.stdout.write("Error: " + str(n) + ", ")
def eval_rpn(s):
st = []
for c in s:
if c.isdigit():
st.append(float(c))
elif len(st) >= 2:
if not c in ops.keys():
error(1)
else:
arg = st.pop()
st.append(ops[c](st.pop(),arg) )
# for example, ops['+'] is the function "add"
else:
error(2)
if len(st) != 1:
error(3)
else:
return st[0]
def prob3(s):
sys.stdout.write("rpn:" + s + ", \tres:" + str(eval_rpn(s)) + "\n")
prob3("23+")
prob3("234*+")
prob3("34*5+")
prob3("23+4*")
prob3("324+*51+/2-")
prob3("53+21+2^^")
prob3("2345^*6*+7+")
prob3("32^41*2*-12/^3-21*/")
prob3("23-41+5*^6/24-7*-8-")
prob3("23/")
# erroneous input
prob3("")
prob3("23+*")
prob3("2+3")
prob3("23+4")
prob3("+23")
prob3("+*")
prob3("23")
prob3("83%") # no longer an error
prob3("%@")
prob3("2 3 +")
Output:
% python rpn.py
rpn:23+, res:5.0
rpn:234*+, res:14.0
rpn:34*5+, res:17.0
rpn:23+4*, res:20.0
rpn:324+*51+/2-, res:1.0
rpn:53+21+2^^, res:134217728.0
rpn:2345^*6*+7+, res:18441.0
rpn:32^41*2*-12/^3-21*/, res:-1.0
rpn:23-41+5*^6/24-7*-8-, res:5.83333333333
rpn:23/, res:0.666666666667
Error: 3, rpn:, res:None
Error: 2, rpn:23+*, res:5.0
Error: 2, Error: 3, rpn:2+3, res:None
Error: 3, rpn:23+4, res:None
Error: 2, Error: 3, rpn:+23, res:None
Error: 2, Error: 2, Error: 3, rpn:+*, res:None
Error: 3, rpn:23, res:None
rpn:83%, res:2.0
Error: 2, Error: 2, Error: 3, rpn:%@, res:None
Error: 2, Error: 1, rpn:2 3 +, res:5.0
|
|