単純な文法を解析するのが最善ですか？
https://stackoverflow.com/questions/2945357
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
わかりました、だから私はこのプロジェクトについてたくさんの質問をしましたが、私はまだ私が考えているデザインにあまり自信がないので、より広い規模で質問するつもりです。
コースカタログの前提条件の説明を解析しています。説明はほとんど常に特定のフォームに従います。これにより、それらのほとんどを解析できると思います。
テキストから、もちろん前提条件の関係のグラフを生成したいと思います。 （データを解析した後、その部分は簡単になります。）
一部のサンプル入力と出力：
"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
説明全体が単なるコースである場合、直接出力されます。
コースが結合されている場合（ "and"）、それらはすべて同じリストに出力されます
コースが分離されている場合（ "または"）、それらは別々のリストにあります
ここには、「と」と「または」の両方があります。
簡単にする1つの注意事項：「/」または「または」のネストは、例3に示すように、フレーズのネストは決して大きくないようです。
これを行うための最良の方法は何ですか？私はPlyから始めましたが、競合を減少/減少させる方法を解決する方法を理解できませんでした。 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 同じデータがありますが、それは複雑な感じがします...
また、次のようなMISCテキストを含む多くの説明があります。
"CS 2110 or permission of instructor"
"INFO 3140 or equivalent experience"
"PYSCH 2210 and sophomore standing"
しかし、私がそのテキストを解析することは重要ではありません。
この問題にアプローチするより良い方法は何ですか？
解決
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)]]
他のヒント
シンプルな文法の場合、私は解析表現文法（PEG）を解析するのが本当に好きです。これは、再帰的な出生パーサーを書く規律のある構造化された方法に相当します。 Pythonのような動的に型付けされた言語では、別の「パーサージェネレーター」を持たずに有用なことをすることができます。つまり、還元紛争やLR解析の他のアルカナを伴うナンセンスはありません。
少し検索しました Pypeg Pythonの素敵なライブラリのようです。
私は文法を解析することについてあまり知らないふりをしていません。あなたの場合、Unutbuによる解決策はあなたが必要とするすべてです。しかし、私は彼の最近の一連のブログ投稿でエリック・リッパートからの解析についてかなり学びました。
http://blogs.msdn.com/b/ericlippert/archive/2010/04/26/every-program-there-is-part-one.aspx
これは、文法の作成と解析を通過し、文法を最適化して解析をより簡単にパフォーマンスできるようにする7部のシリーズです。彼は特定の文法のすべての組み合わせを生成するためのC＃コードを生成しますが、それをPythonに変換して、あなた自身のかなり単純な文法を解析するのはあまりにもストレッチではありません。
私はこの質問が10年前後であり、今では確かに答えられていることを知っています。私は主にこの答えを投稿して、私が理解したことを自分自身を証明しています PEG 最後にパーサー。私は素晴らしいものを使っています parsimonious モジュール ここ。
そうは言っても、解析文法を考え出し、ASTを構築して、これを訪れて、目的の構造を取得できます。
from parsimonious.nodes import NodeVisitor
from parsimonious.grammar import Grammar
from itertools import groupby
grammar = Grammar(
r"""
term = course (operator course)*
course = coursename? ws coursenumber
coursename = ~"[A-Z]+"
coursenumber = ~"\d+"
operator = ws (and / or / comma) ws
and = "and"
or = (comma ws)? "or"
comma = ","
ws = ~"\s*"
"""
)
class CourseVisitor(NodeVisitor):
def __init__(self):
self.current = None
self.courses = []
self.listnum = 1
def generic_visit(self, node, children):
pass
def visit_coursename(self, node, children):
if node.text:
self.current = node.text
def visit_coursenumber(self, node, children):
course = (self.current, int(node.text), self.listnum)
self.courses.append(course)
def visit_or(self, node, children):
self.listnum += 1
courses = ["CS 2110", "CS 2110 and INFO 3300",
"CS 2110, INFO 3300", "CS 2110, 3300, 3140",
"CS 2110 or INFO 3300", "MATH 2210, 2230, 2310, or 2940"]
for course in courses:
tree = grammar.parse(course)
cv = CourseVisitor()
cv.visit(tree)
courses = [list(v) for _, v in groupby(cv.courses, lambda x: x[2])]
print(courses)
ここで、私たちは底から上へ道を歩き、白人、オペレーターのようなブリケットから始めて or, and と , 最終的にコースにつながり、最終的に term. 。訪問者クラスは、目的の（まあ、一種の、最後のタプル要素を取り除く必要がある）構造を構築します。
競合を削減/削減する場合、「または」の優先順位を指定する必要があります。 「CS 101およびCS 102またはCS 201」を意味する、「[CS 101、CS 102] [CS 201]]を意味する、「CS 101およびCS 102またはCS 201」を意味する、「最もタイトな」と推測します。
両方の例を見つけることができれば、文法は曖昧であり、あなたは運が悪いです。ただし、結果をどうするかに応じて、このあいまいさを不足しているままにすることができるかもしれません。
PS、言語は通常のように見えます、DFAを考慮することができます。
