Jaka jest różnica między lex i yacc

Question

Pracowałem z lexem przy wykonywaniu niektórych kodów, gdy znaleziono jakieś wyrażenie regularne, Czy Yacc może zrobić coś więcej? Jeśli tak, to co?

Answer 1

Lex to narzędzie do konstruowania analizatorów leksykalnych, które mogą wykonywać dość głupie leksykalne (np. Znajdowanie słów kluczowych). Yacc to generator parsera, który może tworzyć parsery dla prawdziwych języków komputerowych. Jego analiza jest zwykle oparta na wynikach lex (który jest strumieniem tokenów) iz tego może stworzyć twoje drzewo-drzewo języka programowania - coś, co jest więcej niż lex.

Tradycyjnie konstruktorzy kompilatorów rozróżniają analizy leksykalne i syntaktyczne - które są dwoma ważnymi krokami w kompilatorze (kolejne, np. Tworzenie kodu, optymalizacja).

Answer 2

Tak, YACC to analizator składni, Lex to analizator leksykalny. Są one zazwyczaj używane razem: ty Lex jako wejście łańcuchowe, a YACC tokeniczne dane wejściowe dostarczone przez Lex.

Teraz wyrażenie regularne może reprezentować tylko zwykłe języki. Jednym z ograniczeń zwykłego języka jest brak "pamięci". Nie można zdefiniować reguł akceptacji w łańcuchu w oparciu o to, co było wcześniej.

Widać to głównie w przypadku nawiasów. Język regularny nie może dopasować nawiasu zagnieżdżonego do prawidłowego poziomu. Lub dowolną inną taką strukturę. Gramatyki (większości) języków komputerowych mogą i są, i z tego powodu nie mogą być przetwarzane za pomocą Lexera lub wyrażenia regularnego. W tym momencie przychodzi YACC.

Można również odwrócić to pytanie. Jeśli YACC może zrobić więcej, dlaczego nie użyć go do analizy leksykalnej? Tak się składa, że ​​bardzo sprawnie można sprawdzić poprawność wyrażenia regularnego, co nie ma miejsca w przypadku gramatyk ogólnych - nie na tym samym poziomie. Mimo to YACC może przeprowadzić podstawową analizę leksykalną, jeśli leksykalne reguły języka są dość proste.

Answer 3

lex to lexical analyzer. Dzieli tekst na żetony. Jego moc jest w przybliżeniu odpowiednikiem dopasowywania wyrażenia regularnego. Yacc to parser generator. Wykonuje sekwencję tokenów (powiedzmy z lex) i interpretuje je jako serię zdań. Jego moc jest w przybliżeniu odpowiednikiem gramatyk bez kontekstu.

Typowa aplikacja lex i yacc służy do implementacji języków programowania. lex tokenizuje dane wejściowe, dzieląc je na słowa kluczowe, stałe, interpunkcyjne itp. yacc następnie implementuje rzeczywisty język komputera; rozpoznawanie na przykład instrukcji for lub definicji funkcji.

W sensie praktycznym, często używasz lex do przetwarzania tekstu wejściowego na kawałki. Następnie użyj yacc, aby połączyć te kawałki razem i przetworzyć je w większe znaczenie.

Answer 4

lex służy do wprowadzania tokenów. To znaczy, oddzielanie danych wejściowych od obiektów najniższego poziomu, które definiuje twoja gramatyka. Na przykład, możesz użyć lex do identyfikacji słów kluczowych, identyfikatorów, ciągów znaków, komentarzy, spacji i tak dalej.

yacc służy do analizowania gramatyki gramatyki. Gramatyka to opis twojego języka, zazwyczaj zdefiniowany w EBNF lub innej gramatyce bezkontekstowej. Kiedy opisujesz swoją gramatykę w narzędziu yacc, możesz użyć jej do uruchomienia działań twojego narzędzia, gdy elementy języka zostaną rozpoznane. Może to być na przykład tworzenie drzew składni do rozwiązywania ekspresji, definiowanie obiektów zakresu, rejestrowanie zmiennych definicji i tak dalej.

Są to produkty bezpłatne.

Answer 5

lex i yacc są zwykle używane razem. W ten sposób można zwykle zbudować aplikację przy użyciu zarówno:

strumień wejściowy (znaków) -> Lex (tokeny) -> Yacc (Abstract Syntax Tree) -> Twój Applcation

Bardziej ogólnie, co Lex zrobi od początku plik źródłowy i spróbuje dopasować kilka wyrażeń regularnych (lex ma własną, specjalną składnię do tego, która jest nieco inna niż wyrażenia regularne perl lub sed), a następnie wywoła inny program z każdym rozpoznanym tokenem. Tokeny mogą być po prostu zwykłą wyliczoną wartością, np. Dla słowa kluczowego lub operatora, lub mogą zawierać pewne metadane, jak na przykład wartość dosłowną.

Lex jest zwykle (choć niekoniecznie) używany do wywołania Yacc. Yacc używa algorytmu parsera LALR, który w przybliżeniu działa, przesuwając każdy token na stos. Jeśli stos ma sekwencję rozpoznanych żetonów, to pokaże wszystkie żetony, wykona akcję i wypchnie kolejny żeton na stos.

Właściwym słownictwem dla tego, na czym działa Yacc, są terminale i nieterminale. Terminal jest tokenem pobieranym z programu wywołującego (zwykle Lex), a nieterminalny jest wynikiem dopasowywania sekwencji na stosie.

Zwykle działania podejmowane przez każdą regułę Yacc mają na celu ocenę wyniku obliczeń, z którymi reguła odpowiada, lub utworzenie reprezentacji pośredniej, takiej jak drzewo składniowe, w celu przetworzenia kolejnej warstwy aplikacji.

Yacc, podobnie jak lex, może być używany oddzielnie od drugiego. Na przykład możesz użyć Yacc, przekazując mu poszczególne znaki z tekstu źródłowego i używać reguł Yacc do rozpoznawania każdego rodzaju tokena. Jednak Yacc nie jest zaprojektowany tak, aby był bardzo łatwy w użyciu w ten sposób, więc wynikowy lekser będzie znacznie bardziej złożony niż równoważny leksykon w Lex. Bardziej typowym zastosowaniem byłoby ręczne ustawienie lexera ze względu na wydajność lub dlatego, że potrzebujesz mądrzejszego lexera. Typowym przykładem drugiego przypadku jest używany w językach podobnych do C, które muszą wiedzieć o poprzednich zastosowaniach identyfikatorów, aby wiedzieć, czy są one używane do opisywania typów lub zmiennych.