Metoda pochodnych Brzozowskiego jest bardzo ładną techniką do budowania deterministycznych automatów z wyrażeń regularnych w ładnie algebraiczny sposób. Opracowałem kilka uroczych uogólnień tej techniki do obsługi niektórych większych klas gramatycznych, ale algorytmy są na tyle proste, że wydaje się całkiem możliwe, że zostały wcześniej odkryte. Ale wydaje się, że odniesienia do potomków tej techniki nie pojawiają się zbyt wiele. Czy ktoś coś wie?
2
Jestem bardzo ciekawy, o jakich klasach gramatycznych myślisz. Jeśli chodzi o potomków, technika Antimirałowa, która zamiast tego produkuje niedeterministyczne automaty, jest bardzo przyjemna: Częściowe pochodne wyrażeń regularnych i konstrukcji automatów skończonych , TCS 155 (2), 1996, ( dx.doi.org/10.1016/0304-3975(95 ) 00182-4 ).
—
Sylvain,
masz na myśli uogólnienia na bardziej złożone języki, takie jak zwykły <bezkontekstowy <kontekstowy <...?
—
s8soj3o289,
Głównie przyglądałem się podsystemom CFG z grubsza w sąsiedztwie VPL.
—
Neel Krishnaswami
... ale zbiór instrumentów pochodnych nie jest wtedy skończony. I rzeczywiście, jeśli chcesz czegoś deterministycznego, jak w metodzie Brzozowskiego, prawdopodobnie ograniczasz się do DCFL (dlatego myślę, że może to mieć sens w przypadku VPL).
—
Sylvain,