Czy języki programowania zazwyczaj pilnują, by ich gramatyka była nie bardziej skomplikowana, niż LALR(1)?

(Z góry przepraszam, jeśli dział jest nieodpowiedni i proszę o przeniesienie do odpowiedniego)

pieczarek napisał(a):

Niemniej nikt dzisiaj już nie pisze sam parserów... (chyba, że ktoś jest poważnie niedouczony, lub musi zastosować specyficzne kruczki optymalizacyjne). Obecnie wykorzystuje się generatory parserów, które na podstawie definicji, generują kod parsera. Popularne to Yacc,/BISON czy lex/flex dla języka C.

Yacc o ile wiem jest LALR(1); flexa nie znam, ale jeśli wierzyć cioci Wiki, to jest on wręcz do języków regularnych?

W ogóle - proszę mnie poprawić, jeśli się mylę - tego rodzaju generatory parserów zazwyczaj są tylko do języków LALR(1). Czy to oznacza, że języki programowania zazwyczaj są nie bardziej skomplikowane, niż LALR(1)?

Pamiętam, że kilka lat temu na uczelni należało zaprojektować język programowania i napisać do niego interpreter. No i przeoczyłem, że mój język nie był LALR(1), więc natknąłem się na problemy z yaccem. Przez chwilę myślałem, żeby samemu napisać parser do mojego języka, ale w końcu zrezygnowałem i doprowadziłem go do LALR(1), chociaż odbyło się to kosztem zrobienia z niego jeszcze większego brzydactwa. Więc ograniczyłem się do LALR(1) nie bez pewnego żalu.

Jak to jest z tymi językami? Są języki nie mieszczące się w LALR(1)? Czy zazwyczaj raczej się uznaje, że jeśli gramatyka nie jest LALR(1), to jest to smell i próbuje się za wszelką cenę doprowadzić to jednak do LALR(1)?

pieczarek napisał(a):

Niemniej nikt dzisiaj już nie pisze sam parserów... (chyba, że ktoś jest poważnie niedouczony, lub musi zastosować specyficzne kruczki optymalizacyjne). Obecnie wykorzystuje się generatory parserów, które na podstawie definicji, generują kod parsera. Popularne to Yacc,/BISON czy lex/flex dla języka C.

Tu już się nie zgodzę bo parsery PureScripta, Elm i Idrisa są napisane inaczej. Są napisane z użyciem parser combinator

Yacc o ile wiem jest LALR(1); flexa nie znam, ale jeśli wierzyć cioci Wiki, to jest on wręcz do języków regularnych?

Lex jest do wyciągania tokenów żeby potem użyć ich w Yacc. Jeśli używałeś Bisona to pewnie używałeś Flexa

Jak to jest z tymi językami? Są języki nie mieszczące się w LALR(1)? Czy zazwyczaj raczej się uznaje, że jeśli gramatyka nie jest LALR(1), to jest to smell i próbuje się za wszelką cenę doprowadzić to jednak do LALR(1)?

Musiałeś naprawdę niezłe nakombinować XD Jedyny język z mainstreamu o którym słyszałem że nie mieści się w LALR(1) to C++
Z drugiej strony składnia Scali została teraz podobno uproszczona i Odersky chwali się że parser Scali 3 jest dużo prostszy niż parser C++ ( ale to raczej ma mały związek z LALR(1) :p )

Jeżeli wychodzisz o fałszywego stwierdzenia, no to chyba do sensownych wniosków łatwo nie dojdziesz :D

W tamtym wątku pisałem dlaczego Niemniej nikt dzisiaj już nie pisze sam parserów nie odzwierciedla rzeczywistości

Parser generators vs. handwritten parsers: surveying major language implementations in 2021

Developers often think parser generators are the sole legit way to build programming language frontends, possibly because compiler courses in university teach lex/yacc variants. But do any modern programming languages actually use parser generators anymore?

...

Summary
Of the 2021 Redmonk top 10 languages, 8 of them have a handwritten parser. Ruby and Python use parser generators.

Jeżeli chcesz coś więcej na ten temat, to masz dyskusję na HNie: https://news.ycombinator.com/item?id=28258945 a może nawet https://lobste.rs/s/10pkib/parser_generators_vs_handwritten

Osobiście uważam że samodzielne pisanie parserów to jakaś asceza. Pisać ręcznie to można tylko recursive descent parser gdzie jest kupa nudej roboty, lub funkcyjne zrobić sobie parser combinator framework który będzie powolny jak ślimak.

Budowa parserów opiera się na bardzo dobrze opracowanej teorii. Parserów LR człowiek nie jest w stanie pisać bo ich działanie w dużym skrócie polega na tym że automat skończony steruje automatem ze stosem, a wywód reguł idzie wstecz. To tak jakby wszystkie wyrażenia matematyczne pisać wspak.
</offtop>

Chętnie bym się poudzielał ale już niewiele pamiętam z tego tematu. Jestem za to dumnym posiadaczem książki z niebieskim smokiem.

Przeczytaj sobie kiedy powstało C i np. taki LALR. W dawnych czasach twórcy mieli wywalone na teorię kompilacji, bo nie istniała albo dopiero startowała.
Co do parserów: pamiętaj, że parsery takie jak LR czy LALR to dobra teoria mogąca być dobrą inspiracją. W praktyce masz wziąć pod uwagę legacy (https://stackoverflow.com/a/8379898/4638604), możliwość produkowania ładnych errorów czy to, że syntax to nie wszystko. Dużą część gramatyki można olać w parserze przerzucając ciężar na semantic analysis

Poza ładnymi erorrami dodałbym recovery, bo o ile kompilując compile program.txt masz wywalone na wiele rzeczy, to gdy klepiesz już w IDE

to sprawa się komplikuje, bo w większości przypadków taki kod jest niepoprawny, a nadal chcesz sensownie wspomagać pisarza, a więc musisz z tego wybrnąć, pominąć/obsłużyć błąd i spróbować się odnaleźć.

Przykładowo kompilator C#, Roslyn potrafi z kompletnie bezsensownego kodu wygenerować coś, co da się pokolorować, wygląda to +- tak:

W ogóle tam jest dużo czarów aby UX zapewnic, m.in wymyślili coś takiego jak red-green trees

które zostały później użyte m.in w Ruście oraz śłifcie

Widziałem proposala do C++ odrzuconego "bo to zbyt skomplikowane w implementacji". Więc pewnie ktoś patrzy na stopień skomplikowania.