title: How best to parse a simple grammar?
body: <p>Ok, so I've asked a bunch of smaller questions about this project, but I still don't have much confidence in the designs I'm coming up with, so I'm going to ask a question on a broader scale.</p>
  
  <p>I am parsing pre-requisite descriptions for a course catalog. The descriptions almost always follow a certain form, which makes me think I can parse most of them.</p>
  
  <p>From the text, I would like to generate a graph of course pre-requisite relationships. (That part will be easy, after I have parsed the data.)</p>
  
  <p>Some sample inputs and outputs:</p>
  
  <pre><code>"CS 2110" =&gt; ("CS", 2110) # 0
  
  "CS 2110 and INFO 3300" =&gt; [("CS", 2110), ("INFO", 3300)] # 1
  "CS 2110, INFO 3300" =&gt; [("CS", 2110), ("INFO", 3300)] # 1
  "CS 2110, 3300, 3140" =&gt; [("CS", 2110), ("CS", 3300), ("CS", 3140)] # 1
  
  "CS 2110 or INFO 3300" =&gt; [[("CS", 2110)], [("INFO", 3300)]] # 2
  
  "MATH 2210, 2230, 2310, or 2940" =&gt; [[("MATH", 2210), ("MATH", 2230), ("MATH", 2310)], [("MATH", 2940)]] # 3  
  </code></pre>
  
  <ol>
  <li><p>If the entire description is just a course, it is output directly.</p></li>
  <li><p>If the courses are conjoined ("and"), they are all output in the same list</p></li>
  <li><p>If the course are disjoined ("or"), they are in separate lists</p></li>
  <li><p>Here, we have both "and" and "or".</p></li>
  </ol>
  
  <p>One caveat that makes it easier: it appears that the nesting of "and"/"or" phrases is never greater than as shown in example 3.</p>
  
  <p>What is the best way to do this? I started with PLY, but I couldn't figure out how to resolve the reduce/reduce conflicts. The advantage of PLY is that it's easy to manipulate what each parse rule generates:</p>
  
  <pre><code>def p_course(p):
   'course : DEPT_CODE COURSE_NUMBER'
   p[0] = (p[1], int(p[2]))
  </code></pre>
  
  <p>With PyParse, it's less clear how to modify the output of <code>parseString()</code>. I was considering building upon @Alex Martelli's idea of keeping state in an object and building up the output from that, but I'm not sure exactly how that is best done.</p>
  
  <pre><code> def addCourse(self, str, location, tokens):
    self.result.append((tokens[0][0], tokens[0][1]))
  
   def makeCourseList(self, str, location, tokens):
  
    dept = tokens[0][0]
    new_tokens = [(dept, tokens[0][1])]
    new_tokens.extend((dept, tok) for tok in tokens[1:])
  
    self.result.append(new_tokens)
  </code></pre>
  
  <p>For instance, to handle "or" cases:</p>
  
  <pre><code>    def __init__(self):
              self.result = []
              # ...
    self.statement = (course_data + Optional(OR_CONJ + course_data)).setParseAction(self.disjunctionCourses)
  
  
  
   def disjunctionCourses(self, str, location, tokens):
    if len(tokens) == 1:
     return tokens
  
    print "disjunction tokens: %s" % tokens
  </code></pre>
  
  <p>How does <code>disjunctionCourses()</code> know which smaller phrases to disjoin? All it gets is tokens, but what's been parsed so far is stored in <code>result</code>, so how can the function tell which data in <code>result</code> corresponds to which elements of <code>token</code>? I guess I could search through the tokens, then find an element of <code>result</code> with the same data, but that feel convoluted...</p>
  
  <p>Also, there are many descriptions that include misc text, like:</p>
  
  <pre><code>"CS 2110 or permission of instructor"
  "INFO 3140 or equivalent experience"
  "PYSCH 2210 and sophomore standing"
  </code></pre>
  
  <p>But it isn't critical that I parse that text.</p>
  
  <p><strong>What's a better way to approach this problem?</strong></p>