Jakie istnieją dobre oznaczenia dla deterministycznych, bezkontekstowych i widocznych języków popychających?

Deterministyczne języki bezkontekstowe (DCFL) i języki z widocznym przesunięciem w dół (VPL) są zestawami języków formalnych między językami bezkontekstowymi (CFL) i zwykłymi (REG). Czy istnieje czytelny zapis, który można wyrazić zwykłym ASCII, takim jak Backus-Naur-Form dla CFL i wyrażenia regularne dla REG?

fl.formal-languages Jakob
źródło

Przydatne może być wyjaśnienie znaczenia „dobra” w tytule pytania. Co jest złego w używaniu BNF do opisywania DCFL?

Tsuyoshi Ito

Przez dobre rozumiem, że powinno być łatwe do czytania i pisania dla ludzi, więc powinno być oparte na ASCII. BNF jest świetny - wyrażenia regularne są zwartym podzbiorem BNF. Ale który podzbiór BNF definiuje DCFL, a który VPL?

Jakob

Odpowiedzi:

$q,z,a\to q',\gamma$ $q,q'$ $Q$ $z$ $\gamma$ $a$ symbol wejściowy lub pusty ciąg. Sam zapis nie wymusza determinizmu, ale można go łatwo sprawdzić. Używając bezkontekstowej notacji gramatycznej (jako BNF), napotkasz problemy, ponieważ DCFL są właściwą podklasą CFL i, jak zauważył DaniCL, nie możesz ogólnie zadecydować, biorąc pod uwagę CFG, czy jej język jest deterministyczny.

$A\to a\alpha b$ $A$ $a$ $b$ $\alpha$

$a$ $b$

Sylvain
źródło

Dzięki! Jeśli chodzi o DCFL, myślę, że to właściwy kierunek. Konkretna składnia zawiera przydatne skróty dla podzbiorów, które są analizowane przez wyrażenia regularne. Jeśli chodzi o VPL, nie jestem jeszcze pewien, ponieważ VLP może mieć wiszące symbole wywoływania i zwracania, w przeciwieństwie do modeli drzewiastych, takich jak XML. Możesz lepiej porównać to z dowolną podsekwencją zdarzeń SAX z dowolnego drzewa XML. Wątpię, czy RelaxNG może to opisać.

Jakob

Uwaga Korzystanie z ... jest deterministyczne. jest poza tym - nie mówi nic o tym, czy istnieje podklasa CFG, która bardzo wyraźnie opisuje wszystkie DCFL i nic więcej. Takich jak gramatyka LR (k).

reinierpost

@reinerpost: prawda, ale (w mojej obronie) nie rozważałbym gramatyki LR (1) jako zapisu notacji składniowej , ponieważ trzeba sprawdzić warunek LR (1).

Sylvain,

Aby znaleźć reprezentację kanoniczną, rozważ następujące kwestie: klasa DCFL jest równoważna klasie języków generowanych przez gramatykę LR (k), która ponownie jest równoważna LR (1). Oznacza to, że możesz znaleźć gramatykę LR (1) dla każdego DCFL. Oczywiście, gramatyka LR (1) jest nadal gramatyką bezkontekstową, ale ze specjalną właściwością: z gramatyki LR (1) możemy łatwo budować tabele analizowania, aby poprowadzić deterministyczny parser (z wyprzedzeniem 1 symbolu, stąd LR (1)). Te tabele analiz byłyby inną reprezentacją, choć nieco mniej czytelną.

Nawiasem mówiąc, należy pamiętać, że nie można rozstrzygnąć, czy dany język bezkontekstowy jest deterministyczny (twierdzenie Greibacha).

Muszę przyznać, że nigdy nie słyszałem o VPL.

DaniCL
źródło

Cóż, reprezentacje kanoniczne rzadko są łatwe do odczytania, ale dzięki za wskazówki. Jeśli Twierdzenie Greibacha głosi, że istnieją języki w CFL, których nie można zdecydować się na DCFL - jak określić te języki? Jeśli masz gramatykę, możesz wyrazić ją w formie Backus Naur (BNF), więc Twierdzenie Greibacha wydaje się sugerować, że nie ma podzbioru BNF, który dokładnie wyraża DCFL? Widoczne języki przesuwania są również znane jako „zagnieżdżone słowa”. Ta klasa języków jest stosunkowo nowa, ale istotna w przypadku analizowania uporządkowanych drzew i podobnych struktur.

Jakob

O problemie nierozstrzygalności: język jest CFL, jeśli istnieje generująca go gramatyka bezkontekstowa (CFG). Jeśli otrzymasz CFG, możesz zdecydować, czy ta gramatyka jest LR (k), a zatem deterministyczna. (To samo dotyczy automatów wypychających - łatwo sprawdzić, czy dany PDA jest deterministyczny, czy nie.) Załóżmy jednak, że masz CFG, który nie jest LR (k) - to nie znaczy, że językiem nie jest DCFL ; możesz po prostu nie być w stanie znaleźć dla niego gramatyki LR (k).

DaniCL

„możesz zdecydować, czy ta gramatyka to LR (k)” dla ustalonego k.

Sylvain,

@Jakob: Twierdzenie Greibacha nie stwierdza, że nawet gdyby tak było, oznaczałoby to jedynie, że arbitralne CFG nie są odpowiednim formalizmem notacji dla DCFG, podobnie jak nie są dobrym formalizmem notacji dla zwykłych języków (czy to CFG opisuje również, że zwykły język jest nierozstrzygalny). Nie ma jednak nic złego w wybieraniu podklasy CFG (np. Zwykłe gramatyki dla zwykłych języków).

reinierpost

W podręcznikach istnieje tradycja niedbałych sformułowań: mają tendencję do wydawania takich stwierdzeń, jak: „nierozstrzygalne jest, czy CFL jest regularny / deterministyczny”, a co tak naprawdę przez to rozumieją, „nie można rozstrzygnąć, czy CFG opisuje regularne / deterministyczne język".

reinierpost