Po co rozdzielać leksowanie i parsowanie?

15

Możliwe jest parsowanie dokumentu za pomocą pojedynczego przejścia z automatu stanów. Jaka jest korzyść z dwóch przejść, tj. posiadanie leksera do konwersji tekstu na tokeny i parsera do testowania reguł produkcyjnych dla tych tokenów? Dlaczego nie mieć pojedynczego przejścia, które stosuje reguły produkcji bezpośrednio do tekstu?

compilers parsers Brent
źródło
2
Powiązane: programmers.stackexchange.com/questions/128888/…
Użytkownik
2
Zostało to już omówione w CS, stackexchange, z wieloma bardzo technicznymi komentarzami w odpowiedzi na Ekspresyjną moc lexer + parser . Ale może być miejsce na dalsze odpowiedzi.
babou
Zastanawiam się, czy paralelizm w stylu rurociągu (aczkolwiek wysoce niezrównoważone etapy) może być dodatkową zaletą. Interesujące może być także zachowanie instrukcji i pamięci podręcznej danych. O ile (jeśli w ogóle) takie skrócenie czasu kompilacji zależy od konkretnego sprzętu.
Paul A. Clayton
Jednym z dość oczywistych (przynajmniej dla mnie) powodów jest to, że możesz wtedy używać skanera osobno. W praktyce często używam flex do skanowania danych wejściowych, ale rzadko potrzebuję pełnej mocy yacc.
jamesqf

Odpowiedzi:

13

Nie musisz ich rozdzielać. Ludzie łączą je w parsery bez skanera .

Kluczową wadą parserów bez skanera wydaje się być to, że wynikowe gramatyki są raczej skomplikowane - bardziej skomplikowane niż odpowiednia kombinacja wyrażeń regularnych wykonujących leksykację i gramatyki bezkontekstowej wykonującej analizę w strumieniu tokena. W szczególności gramatyki do analizowania bez skanera mają tendencję do dwuznaczności. Łatwiej jest usunąć niejednoznaczność dla gramatyk pracujących na strumieniu tokenu.

Pragmatyczną zaletą korzystania z dedykowanej wstępnej fazy leksykalnej jest to, że nie łączysz kolejnego parsera ze szczegółami leksykalnymi. Jest to przydatne podczas wczesnego rozwoju języka programowania, gdy szczegóły leksykalne i składniowe wciąż się często zmieniają.

Martin Berger
źródło
1
T.P.P.P.T.
@babou Tak, to prawda. Nie znam żadnych formalnych wyników wyrażenia regularnego złożonego z LL (k) wychodzi z LL (k) lub podobnego. Co więcej, leksykowanie zwykle nie odbywa się w zwykłych językach, ale w czymś mocniejszym, a mianowicie w zwykłych językach z najdłuższym dopasowaniem i priorytetami słów kluczowych. Nie jestem pewien, co to dokładnie jest klasa językowa i jakie są jej właściwości zamykające.
Martin Berger
2
Jeśli twoje spojrzenie w przyszłość wymaga odczytania identyfikatora, kompozycja będzie wymagać nieograniczonego spojrzenia w przyszłość, ponieważ (w zasadzie) nie ma ograniczenia co do długości identyfikatorów.
babou
@babou Nie jestem pewien. Jeśli najdłuższe słowo kluczowe ma długość 17 znaków, każdy dłuższy ciąg musi być identyfikatorem lub być niepoprawny leksykalnie.
Martin Berger
Ale twój identyfikator, ewentualnie łańcuch, liczba lub inny literał, jest sekwencją złożoną z ponad 17 pojedynczych symboli, która może stać przed tokenem, którego faktycznie potrzebujesz. To wielkie spojrzenie w przyszłość, bez ograniczeń. Możesz skończyć z niedeterministycznym językiem.
babou