Po co rozdzielać leksowanie i parsowanie?

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

Powiązane: programmers.stackexchange.com/questions/128888/…

— Użytkownik

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

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

T

$T$

P

$P$

P

$P$

P_{T}

$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

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