34

わかりました、このプロジェクトについてたくさんの小さな質問をしましたが、私が思いついたデザインにはまだあまり自信がありませんので、より広いスケールで質問します.

コースカタログの前提条件の説明を解析しています。ほとんどの場合、記述は特定の形式に従っているため、ほとんどの記述を解析できると思います。

テキストから、コースの前提関係のグラフを生成したいと思います。(データを解析した後、その部分は簡単になります。)

入力と出力の例:

"CS 2110" => ("CS", 2110) # 0

"CS 2110 and INFO 3300" => [("CS", 2110), ("INFO", 3300)] # 1
"CS 2110, INFO 3300" => [("CS", 2110), ("INFO", 3300)] # 1
"CS 2110, 3300, 3140" => [("CS", 2110), ("CS", 3300), ("CS", 3140)] # 1

"CS 2110 or INFO 3300" => [[("CS", 2110)], [("INFO", 3300)]] # 2

"MATH 2210, 2230, 2310, or 2940" => [[("MATH", 2210), ("MATH", 2230), ("MATH", 2310)], [("MATH", 2940)]] # 3

  1. 説明全体が単なるコースの場合は、直接出力されます。

  2. コースが結合されている場合 ("and")、それらはすべて同じリストに出力されます。

  3. コースが切り離されている（「または」）場合、それらは別々のリストにあります

  4. ここでは、"and" と "or" の両方があります。

簡単にするための 1 つの警告: "and"/"or" 句の入れ子は、例 3 に示されているよりも大きくなることはないようです。

これを行う最善の方法は何ですか？PLY から始めましたが、reduce/reduce の競合を解決する方法がわかりませんでした。PLY の利点は、各解析ルールが生成するものを簡単に操作できることです。

def p_course(p):
 'course : DEPT_CODE COURSE_NUMBER'
 p[0] = (p[1], int(p[2]))

PyParse では、 の出力を変更する方法があまり明確ではありませんparseString()。オブジェクトに状態を保持し、そこから出力を構築するという@Alex Martelliのアイデアに基づいて構築することを検討していましたが、それがどのように行われるのが最適かは正確にはわかりません。

 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)

たとえば、「または」の場合を処理するには、次のようにします。

    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

どのdisjunctionCourses()小さなフレーズを分離するかをどうやって知るのですか? 得られるのはトークンだけですが、これまでに解析されたものは に格納されているresultため、関数は のどのデータがresultのどの要素に対応するかをどのように判断できtokenますか? トークンを検索してresult、同じデータを持つ要素を見つけることができると思いますが、複雑に感じます...

また、次のようなその他のテキストを含む多くの説明があります。

"CS 2110 or permission of instructor"
"INFO 3140 or equivalent experience"
"PYSCH 2210 and sophomore standing"

しかし、そのテキストを解析することは重要ではありません。

この問題にアプローチするより良い方法は何ですか?

4

6 に答える 6

26 
def parse(astr):
    astr=astr.replace(',','')
    astr=astr.replace('and','')    
    tokens=astr.split()
    dept=None
    number=None
    result=[]
    option=[]
    for tok in tokens:
        if tok=='or':
            result.append(option)
            option=[]
            continue
        if tok.isalpha():
            dept=tok
            number=None
        else:
            number=int(tok)
        if dept and number:
            option.append((dept,number))
    else:
        if option:
            result.append(option)
    return result

if __name__=='__main__':
    tests=[ ("CS 2110" , [[("CS", 2110)]]),
            ("CS 2110 and INFO 3300" , [[("CS", 2110), ("INFO", 3300)]]),
            ("CS 2110, INFO 3300" , [[("CS", 2110), ("INFO", 3300)]]),
            ("CS 2110, 3300, 3140", [[("CS", 2110), ("CS", 3300), ("CS", 3140)]]),
            ("CS 2110 or INFO 3300", [[("CS", 2110)], [("INFO", 3300)]]),
            ("MATH 2210, 2230, 2310, or 2940", [[("MATH", 2210), ("MATH", 2230), ("MATH", 2310)], [("MATH", 2940)]])]

    for test,answer in tests:
        result=parse(test)
        if result==answer:
            print('GOOD: {0} => {1}'.format(test,answer))
        else:
            print('ERROR: {0} => {1} != {2}'.format(test,result,answer))
            break

収量

GOOD: CS 2110 => [[('CS', 2110)]]
GOOD: CS 2110 and INFO 3300 => [[('CS', 2110), ('INFO', 3300)]]
GOOD: CS 2110, INFO 3300 => [[('CS', 2110), ('INFO', 3300)]]
GOOD: CS 2110, 3300, 3140 => [[('CS', 2110), ('CS', 3300), ('CS', 3140)]]
GOOD: CS 2110 or INFO 3300 => [[('CS', 2110)], [('INFO', 3300)]]
GOOD: MATH 2210, 2230, 2310, or 2940 => [[('MATH', 2210), ('MATH', 2230), ('MATH', 2310)], [('MATH', 2940)]]
于 2010-05-31T18:50:35.000 に答える
7

単純な文法については、構文解析式文法 (PEG) が非常に気に入っています。これは、再帰降下パーサーを作成するための規律ある構造化された方法になります。Python のような動的に型付けされた言語では、別の「パーサー ジェネレーター」がなくても便利なことを行うことができます。これは、reduce-reduce の競合やその他の LR 解析の奥義にナンセンスがないことを意味します。

少し検索したところ、pyPEGは Python の優れたライブラリのようです。

于 2010-05-31T20:59:33.440 に答える
1

私は文法の解析について多くを知っているふりはしません。あなたの場合、 unutbu による解決策があれば十分です。しかし、最近の一連のブログ投稿で、Eric Lippert から構文解析についてかなりのことを学びました。

http://blogs.msdn.com/b/ericlippert/archive/2010/04/26/every-program-there-is-part-one.aspx

これは、文法を作成して解析し、文法を最適化して解析をより簡単にし、パフォーマンスを向上させる 7 つの部分からなるシリーズです。彼は、特定の文法のすべての組み合わせを生成する C# コードを生成しますが、それを Python に変換して独自のかなり単純な文法を解析するのは、それほど難しいことではありません。

于 2010-05-31T21:28:14.040 に答える
1

reduce/reduce の競合が発生した場合は、"or" と "and" の優先順位を指定する必要があります。「and」が最も密接に結びついていると推測しています。つまり、「CS 101 and CS 102 or CS 201」は [[CS 101, CS 102] [CS 201]] を意味します。

両方の例を見つけることができれば、文法はあいまいであり、運が悪い. ただし、結果をどうするかによっては、このあいまいさを未指定のままにしておくことができる場合があります。

PS、言語は通常のようです。DFA を検討できます。

于 2010-05-31T18:46:51.770 に答える