Jak najlepiej przeanalizować prostą gramatykę?

Ok, więc zadałem kilka mniejszych pytań na temat tego projektu, ale nadal nie mam wiele zaufania do projektów, które wymyślam, więc zadam pytanie na szerszą skalę.

Analizuję wstępne opisy do katalogu kursów. Opisy prawie zawsze mają określoną formę, co sprawia, że myślę, że mogę przeanalizować większość z nich.

Z tekstu chciałbym wygenerować wykres oczywiście wstępnych zależności. (Ta część będzie spokojnie, po przeanalizowaniu danych.)

Niektóre przykładowe wejścia i wyjścia: 

"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. Jeśli cały opis jest tylko kursem, jest wyprowadzany bezpośrednio.

  2. Jeśli kursy są połączone ("i"), wszystkie są wyjściowe na tej samej liście

  3. Jeśli kurs jest wyłączony ("lub"), znajdują się one w osobnych listach

  4. Tutaj mamy zarówno "i", jak i "lub".

Jedno zastrzeżenie, które ułatwia sprawę: wydaje się zagnieżdżenie fraz "i" / " lub " nigdy nie jest większe niż pokazano w przykładzie 3.

Jaki jest najlepszy sposób, aby to zrobić? Zacząłem od PLY, ale nie mogłem wymyślić, jak rozwiązać konflikty reduce/reduce. Zaletą PLY jest to, że łatwo jest manipulować tym, co generuje każda reguła parsowania: 

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

Z PyParse, jest mniej jasne, jak zmodyfikować wyjście parseString(). Zastanawiałam się nad oparciem się na pomyśle @ Alex Martelli o utrzymaniu stanu w obiekcie i zbudowaniu wyjście z tego, ale nie jestem pewien dokładnie, jak to jest najlepiej zrobić.

 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)

Na przykład do obsługi przypadków "lub": 

    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

Skąd disjunctionCourses() wie, które mniejsze Zwroty należy wyłączyć? Wszystko, co otrzymuje to tokeny, ale to, co zostało do tej pory przetworzone, jest przechowywane w result, więc jak funkcja może powiedzieć, które dane w result odpowiadają którym elementom token? Myślę, że mógłbym przeszukać tokeny, a następnie znaleźć element result z tymi samymi danymi, ale to wydaje się zawiłe...

Także, istnieje wiele opisów, które zawierają różne teksty, takie jak: 

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

Ale to nie jest krytyczne, że analizuję ten tekst.

Jaki jest lepszy sposób podejścia do tego problemu?

Author: martineau, 2010-05-31
Source

4 answers

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)]]
 22
Author: unutbu,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-31 18:58:01

Dla prostych gramatyk bardzo lubię parsowanie gramatyk wyrażeń( PEGs), które stanowią zdyscyplinowany, zorganizowany sposób pisania rekurencyjnego parsera. W dynamicznie wpisywanym języku, takim jak Python, możesz robić przydatne rzeczy bez posiadania oddzielnego "generatora parserów". Oznacza to, że nie ma bzdur z konfliktami reduce-reduce lub innymi arkanami parsowania LR.

Trochę poszperałem i pyPEG wydaje się być ładną biblioteką dla Pythona.

 5
Author: Norman Ramsey,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-31 20:59:33

Jeśli pojawi się zmniejsz / zmniejsz konflikty, musisz określić pierwszeństwo "or" I "and". Im " i "bind", czyli "CS 101 i CS 102 lub CS 201" oznacza [[CS 101, CS 102] [CS 201]].

Jeśli znajdziesz przykłady obu, gramatyka jest dwuznaczna i masz pecha. Jednak może być w stanie pozostawić tę dwuznaczność bez sprecyzowania, wszystko w zależności od tego, co zamierzasz zrobić z wynikami.

PS, wygląda na to, że język jest zwykły, można rozważ DFA.

 0
Author: Johan Benum Evensberget,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-31 18:46:51

Nie udaję, że wiem wiele o parsowaniu gramatyki, a dla Twojego przypadku rozwiązanie przez unutbu jest wszystkim, czego potrzebujesz. Ale nauczyłem się sporo o parsowaniu od Erica Lipperta w jego ostatniej serii wpisów na blogu.

Http://blogs.msdn.com/b/ericlippert/archive/2010/04/26/every-program-there-is-part-one.aspx{[4]

Jest to seria 7 części, która przechodzi przez tworzenie i parsowanie gramatyki, a następnie optymalizację gramatyki, aby parsowanie było łatwiejsze i bardziej wydajne. Produkuje Kod C# do generowania wszystkich kombinacji poszczególnych gramatyk, ale nie powinno być zbyt wiele rozciągania, aby przekonwertować go do Pythona, aby przeanalizować dość prostą gramatykę.

 0
Author: Josh Smeaton,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-05-31 23:18:59