PLY is a Python implementation of Lex and Yacc originally written for Unix. Previously, I used it for tokenizing prerequisite strings. The goal is to have a program that performs the following trick:
|
|
|
|
|
Input |
Interpretation |
|
|
MATH 135 or 145, STAT 220 or 230 or 240 |
MATH 135/MATH 145, STAT 220/STAT 230 |
|
|
AMATH 250 and MATH 237 or 247; Level at least 3A;
Not open to General Mathematics students. |
AMATH 250, MATH 237/MATH 247 |
|
|
BIOL 140, 140L, (BIOL 208 or 330) and (BIOL 308 or
330) |
BIOL 140, BIOL 140L, BIOL 208/BIOL 330, BIOL
308/BIOL 330 |
|
|
(AMATH 341/CM 271/ CS 371 or CS 370) and (MATH 128
or 138 or 148) |
AMATH 341/CM 271/CS 371/CS 370, MATH 128/MATH
138/MATH 148 |
|
|
MATH 135 or 145, STAT 220 or 230 or 240 |
MATH 135/MATH 145, STAT 220/STAT 230/STAT 240 |
|
|
AMATH 250 and MATH 237 |
AMATH 250, MATH 237 |
|
|
(BIOL 140,BIOL 208 or 330) and (BIOL 308 or
330) |
BIOL 140/BIOL 208/BIOL 330, BIOL 308/BIOL 330 |
|
|
MATH 229 or 239 or 249 and (One of CO 227, 250/350,
355, CO 352/CM 340); |
MATH 229/MATH 239/MATH 249, CO 227/CO 250/CO
350 |
|
|
(CS 240 or SE 240), CS 246, ECE 222 |
CS 240/SE 240, CS 246, ECE 222 |
|
|
CS 241 and (STAT 206 or 230 or 240) |
CS 241, STAT 206/STAT 230/STAT 240 |
|
At first glance, it looks like a simple task. Just replace “,” “and” with “,”, and replace “/” “or” with “/”. Regular expressions could do that. Then there comes the issue with the comma and its interpretation depending on the level in the hierarchy. So using PLY to do the same thing turned out to be much easier, since grammar rules are used instead of regular expressions. I put together a quick prototype in an hour.
import ply.yacc as yacc
import sys
sys.path.append("/Documents/Projects/ply/")
from prereqlex import tokens
def p_prereq_cp(p):
'prereq : cp'
p[0] = p [1]
def p_prereq_cp_and(p):
'cp : course AND cp'
p[0] = p[1] + ' ' + p[3]
def p_prereq_cp_or(p):
'cp : course OR cp'
p[0] = p[1] + ' ' + p[3]
def p_prereq_cp_comma(p):
'cp : course COMMA cp'
p[0] = p[1] + ' ' + p[3]
def p_prereq_cp_parens(p):
'cp : LPARENS cp RPARENS'
p[0] = p[2]
def p_prereq_cp_course(p):
'cp : course'
p[0] = p[1]
def p_prereq_course_extra(p):
'course : course OR NUM'
p[0] = p[1] + ' ' + p[3]
def p_prereq_course_default(p):
'course : DEPT NUM'
p[0] = p[1] + ' ' + p[2]
# Error rule for syntax errors
def p_error(p):
print "Syntax error in input!"
# Build the parser
parser = yacc.yacc()
while True:
try:
s = raw_input('> ')
except EOFError:
break
if not s: continue
result = parser.parse(s)
print result
> MATH 125 or 135
MATH 125 135
> MATH 125 or MATH 135
MATH 125 MATH 135
That’s pretty good for a start, but doesn’t get much better for interpreting the input correctly.
def p_prereq_cp_lp_ep(p):
'prereq : cp SEMI lp SEMI ep'
p[0] = p[1]
def p_prereq_cp_lp(p):
'prereq : cp SEMI lp'
p[0] = (p[1] , 'Level ' + p[3])
def p_prereq_cp_ep(p):
'prereq : cp SEMI ep'
p[0] = p[1] + ' Exclude ' + p[3]
def p_prereq_cp(p):
'prereq : cp'
p[0] = p[1]
def p_prereq_cp_and(p):
'cp : cp AND cg'
p[0] = ('AND', p[1], p[3])
def p_prereq_cp_comma(p):
'cp : cp COMMA cg'
p[0] = ('COMMA', p[1], p[3])
def p_prereq_cp_comma_and(p):
'cp : cp COMMA AND cg'
p[0] = ('COMMA', p[1], p[4])
def p_prereq_cp_semi(p):
'cp : cp SEMI cg'
p[0] = ('SEMI', p[1], p[3])
def p_prereq_cp_semi_and(p):
'cp : cp SEMI AND cg'
p[0] = ('SEMI', p[1], p[4])
def p_prereq_cp_defualt(p):
'cp : cg'
p[0] = p[1]
def p_prereq_cg_or(p):
'cg : cg OR courses'
p[0] = ('OR', p[1], p[3])
def p_prereq_cg_slash(p):
'cg : cg SLASH courses'
p[0] = ('SLASH', p[1], p[3])
def p_prereq_cg_comma(p):
'cg : cg COMMA courses'
p[0] = ('COMMA', p[1], p[3])
def p_prereq_cg_comma_or(p):
'cg : cg COMMA OR courses'
p[0] = ('COMMA', p[1], p[4])
def p_prereq_cg_parens(p):
'cg : LPARENS cg RPARENS'
p[0] = p[2]
def p_prereq_cg_one_of(p):
'cg : ONE OF cg'
p[0] = ('OR', p[3])
def p_prereq_cg_courses(p):
'cg : courses'
p[0] = p[1]
def p_prereq_courses_or(p):
'courses : courses OR course'
p[0] = ('OR', p[1], p[3])
def p_prereq_courses_slash(p):
'courses : courses SLASH course'
p[0] = ('SLASH', p[1], p[3])
def p_prereq_courses_comma(p):
'courses : courses COMMA course'
p[0] = ('COMMA', p[1], p[3])
def p_prereq_courses_default(p):
'courses : course'
p[0] = p[1]
def p_prereq_course_default(p):
'course : DEPT NUM'
p[0] = p[1] + ' ' + p[2]
def p_prereq_course_short(p):
'course : NUM'
p[0] = p[1]
def p_prereq_lp(p):
'lp : LEVEL AT LEAST TERM'
p[0] = p[4]
def p_prereq_ep(p):
'ep : NOT OPEN TO'
p[0] = ''
precedence = (
('left', 'AND', 'SEMI'),
('left', 'COMMA'),
('left', 'SLASH'),
('left', 'OR'),
('left', 'DEPT'),
('right', 'NUM'),
)
# Error rule for syntax errors
def p_error(p):
print "Syntax error at '%s'" % p
import logging
logging.basicConfig(
level = logging.INFO,
filename = "parselog.txt",
filemode = "w",
format = "%(filename)10s:%(lineno)4d:%(message)s"
)
log = logging.getLogger()
parser = yacc.yacc(debug=True,debuglog=log)
prereqs = ('CHEM 120, 123; one of PHYS 111, 121; and one of PHYS 112, 122',
'EARTH 121, 121L or 122, 122L or 153 or CIVE 153 or CIVE 253 or GEOE 153 or ENVE 153',
'PHYS 112 or 122 or 125',
'CHEM 254 or EARTH 421, CHEM 350',
'(One of PHYS 112, 122, 125) and (one of MATH 118, 119, 128, 138, 148) and (one of AMATH 250, 350, CIVE 222, ENVE 223, MATH 218, 228, ME 203, SYDE 211)',
'One of PSCI 250, 255, 260, 264',
'One of ANTH 201/CLAS 221, ANTH 203, 233',
'MATH 135 or 145, STAT 220 or 230 or 240',
'AMATH 250 and MATH 237 or 247; Level at least 3A',
'BIOL 140, 140L, (BIOL 208 or 330)',
'(CS 240 or SE 240), CS 246, ECE 222',
'CS 246, (SE 240 or CS 240)',
'(AMATH 341/CM 271/ CS 371 or CS 370) and (MATH 128 or 138 or 148)',
'MATH 135 or 145, STAT 220 or 230 or 240',
'AMATH 250 and MATH 237',
'(BIOL 140,BIOL 208 or 330) and (BIOL 308 or 330)',
'MATH 229 or 239 or 249 and (One of CO 227, 250/350, 355, CO 352/CM 340)',
'(CS 240 or SE 240), CS 246, ECE 222',
'CS 241 and (STAT 206 or 230 or 240)')
limit = float("infinity");
i = 0;
for s in prereqs:
if i < limit:
result = parser.parse(s, debug=log)
print result
i += 1
Output:
('SEMI', ('SEMI', ('COMMA', 'CHEM 120', '123'), ('OR', ('COMMA', 'PHYS 111', '121'))), ('OR', ('COMMA', 'PHYS 112', '122')))
('OR', ('OR', ('OR', ('OR', ('OR', ('COMMA', ('OR', ('COMMA', 'EARTH 121', '121L'), '122'), '122L'), '153'), 'CIVE 153'), 'CIVE 253'), 'GEOE 153'), 'ENVE 153')
('OR', ('OR', 'PHYS 112', '122'), '125')
('COMMA', ('OR', 'CHEM 254', 'EARTH 421'), 'CHEM 350')
('AND', ('AND', ('OR', ('COMMA', ('COMMA', 'PHYS 112', '122'), '125')), ('OR', ('COMMA', ('COMMA', ('COMMA', ('COMMA', 'MATH 118', '119'), '128'), '138'), '148'))), ('OR', ('COMMA', ('COMMA', ('COMMA', ('COMMA', ('COMMA', ('COMMA', ('COMMA', 'AMATH 250', '350'), 'CIVE 222'), 'ENVE 223'), 'MATH 218'), '228'), 'ME 203'), 'SYDE 211')))
('OR', ('COMMA', ('COMMA', ('COMMA', 'PSCI 250', '255'), '260'), '264'))
('OR', ('COMMA', ('COMMA', ('SLASH', 'ANTH 201', 'CLAS 221'), 'ANTH 203'), '233'))
('OR', ('OR', ('COMMA', ('OR', 'MATH 135', '145'), 'STAT 220'), '230'), '240')
(('AND', 'AMATH 250', ('OR', 'MATH 237', '247')), 'Level 3A')
Syntax error at 'LexToken(LPARENS,'(',1,16)'
Syntax error at 'LexToken(RPARENS,')',1,32)'
None
('COMMA', ('OR', 'CS 240', 'SE 240'), ('COMMA', 'CS 246', 'ECE 222'))
Syntax error at 'LexToken(LPARENS,'(',1,8)'
Syntax error at 'LexToken(RPARENS,')',1,25)'
None
('AND', ('OR', ('SLASH', ('SLASH', 'AMATH 341', 'CM 271'), 'CS 371'), 'CS 370'), ('OR', ('OR', 'MATH 128', '138'), '148'))
('OR', ('OR', ('COMMA', ('OR', 'MATH 135', '145'), 'STAT 220'), '230'), '240')
('AND', 'AMATH 250', 'MATH 237')
('AND', ('OR', ('COMMA', 'BIOL 140', 'BIOL 208'), '330'), ('OR', 'BIOL 308', '330'))
('AND', ('OR', ('OR', 'MATH 229', '239'), '249'), ('OR', ('SLASH', ('COMMA', ('COMMA', ('SLASH', ('COMMA', 'CO 227', '250'), '350'), '355'), 'CO 352'), 'CM 340')))
('COMMA', ('OR', 'CS 240', 'SE 240'), ('COMMA', 'CS 246', 'ECE 222'))
('AND', 'CS 241', ('OR', ('OR', 'STAT 206', '230'), '240'))
This was the BNF grammar encoded:
prereq : cp
cp : cp AND cgparens
| cp COMMA cgparens
| cp COMMA AND cgparens
| cp SEMI cgparens
| cp SEMI AND cgparens
| cg
cg : cg OR courses
| cg SLASH courses
| cg COMMA courses
| cg COMMA OR courses
| LPARENS cg RPARENS
| ONE OF cg
| courses
courses : courses OR course
| courses SLASH course
| courses COMMA course
| course
course : DEPT NUM
| NUM
, which gives a surprising error whenever parenthesis appeared:
yacc.py: 389:Action : Reduce rule [course -> DEPT NUM] with ['BIOL','140'] and goto state 23
yacc.py: 423:Result : ('BIOL 140')
yacc.py: 389:Action : Reduce rule [courses -> course] with ['BIOL 140'] and goto state 22
yacc.py: 423:Result : ('BIOL 140')
yacc.py: 389:Action : Reduce rule [course -> NUM] with ['140L'] and goto state 24
yacc.py: 423:Result : ('140L')
yacc.py: 389:Action : Reduce rule [courses -> courses COMMA course] with ['BIOL 140',',','140L'] and goto state 21
yacc.py: 423:Result : (('COMMA', 'BIOL 140', '140L'))
yacc.py: 493:Error : courses COMMA . LexToken(LPARENS,'(',1,16)
yacc.py: 493:Error : courses COMMA . error
yacc.py: 493:Error : courses . error
yacc.py: 493:Error : . error
yacc.py: 389:Action : Reduce rule [course -> DEPT NUM] with ['BIOL','208'] and goto state 23
yacc.py: 423:Result : ('BIOL 208')
yacc.py: 389:Action : Reduce rule [courses -> course] with ['BIOL 208'] and goto state 22
yacc.py: 423:Result : ('BIOL 208')
yacc.py: 389:Action : Reduce rule [course -> NUM] with ['330'] and goto state 24
yacc.py: 423:Result : ('330')
yacc.py: 389:Action : Reduce rule [courses -> courses OR course] with ['BIOL 208','or','330'] and goto state 19
yacc.py: 423:Result : (('OR', 'BIOL 208', '330'))
yacc.py: 389:Action : Reduce rule [cg -> courses] with [] and goto state 18
yacc.py: 423:Result : (('OR', 'BIOL 208', '330'))
yacc.py: 493:Error : cg . LexToken(RPARENS,')',1,32)
yacc.py: 493:Error : cg . error
yacc.py: 493:Error : . error
yacc.py: 493:Error : . $end
It means the parser just refused to use the rule cg : courses and subsequently cg : LPARENS cg RPARENS. At that time, I thought it must be something wrong with the grammar. Forgetting the parenthesis would have been an option, only if the compiler gave the correct interpretation. With that in mind, I worked on getting the final result:
def p_prereq_cp_lp_ep(p):
'prereq : cp SEMI lp SEMI ep'
p[0] = p[1]
def p_prereq_cp_lp(p):
'prereq : cp SEMI lp'
p[0] = p[1] + 'Level ' + p[3]
def p_prereq_cp_ep(p):
'prereq : cp SEMI ep'
p[0] = p[1] + ' Exclude ' + p[3]
def p_prereq_cp(p):
'prereq : cp'
p[0] = p[1]
def p_cp(p):
'''cp : cg
| cp AND cg
| cp COMMA cg
| cp COMMA AND cg
| cp SEMI cg
| cp SEMI AND cg'''
if (len(p) == 2):
p[0] = p[1]
elif (len(p) == 4):
p[0] = p[1] + ', ' + p[3]
else:
p[0] = p[1] + ', ' + p[4]
def p_cg(p):
'''cg : cl
| LPARENS cg RPARENS
| ONE OF cl'''
if (len(p) == 2):
p[0] = p[1]
elif (p[1] == 'LPARENS'):
p[0] = p[2]
else:
p[0] = p[3]
def p_cl(p):
'''cl : courses
| cl OR courses
| cl SLASH courses
| cl COMMA courses'''
if (len(p) == 2):
p[0] = p[1]
else:
p[0] = p[1] + '/' + p[3]
def p_courses(p):
'courses : DEPT nums'
p[0] = p[1] + ' ' + p[2]
def p_nums(p):
'''nums : NUM
| nums OR NUM
| nums SLASH NUM
| nums COMMA NUM'''
if (len(p) == 2):
p[0] = p[1]
else:
p[0] = p[1] + '/' + p[3]
def p_lp(p):
'lp : LEVEL AT LEAST TERM'
p[0] = p[4]
def p_ep(p):
'ep : NOT OPEN TO'
p[0] = ''
# Error rule for syntax errors
def p_error(p):
print "Syntax error at '%s'" % p
I realize at this point that PLY couldn’t fly:
yacc.py: 389:Action : Reduce rule [nums -> NUM] with ['121'] and goto state 19
yacc.py: 423:Result : ('121')
yacc.py: 389:Action : Reduce rule [nums -> nums COMMA NUM] with ['121',',','121L'] and goto state 22
yacc.py: 423:Result : ('121/121L')
yacc.py: 389:Action : Reduce rule [nums -> nums OR NUM] with ['121/121L','or','122'] and goto state 20
yacc.py: 423:Result : ('121/121L/122')
yacc.py: 389:Action : Reduce rule [nums -> nums COMMA NUM] with ['121/121L/122',',','122L'] and goto state 22
yacc.py: 423:Result : ('121/121L/122/122L')
yacc.py: 389:Action : Reduce rule [nums -> nums OR NUM] with [,'or','153'] and goto state 20
yacc.py: 423:Result : ('121/121L/122/122L/153')
yacc.py: 493:Error : DEPT nums OR . LexToken(DEPT,'CIVE',1,39)
It seems to be stuck on the rule nums : nums OR NUM. I did a test by deleting that rule. Then it parsed the rest of the string fine, just missing a few NUMs. For some reason, PLY just refused to use the rule cl : cl OR courses. I checked the PLY documentation. Yup, PLY turned out to be an iron balloon. “shift/reduce conflicts are resolved in favor of shifting (the default).” Of course, once the mystery is solved, the solution is not hard to find.