Co byś otrzymał, gdybyś dodał parametry do gramatyk bezkontekstowych?

13

Myślałem o gramatyce dla języków wrażliwych na indukcje i wygląda na to, że gramatyki CF zrobiłyby to samo, gdyby były połączone z parametrami. Jako przykład rozważ ten fragment uproszczonej gramatyki języka Python w formacie podobnym do ANTLR:

// on top-level the statements have empty indent
program  
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent) 
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

Moje pytanie: czy tego rodzaju gramatyki (CFG z parametrami) mają nazwę?

Wygląda na to, że napisanie parsera rekurencyjnego dla tej gramatyki nie byłoby trudne (parametry powinny być w zasadzie parserami). Jakie mogą być trudności z tym podejściem?

Czy dodanie parametrów podnosi obsługiwaną klasę języka powyżej kontekstu?

Aivar
źródło
1
Jeśli zestaw wartości, które mogą przyjmować parametry, jest skończony, to wciąż jest trywialnie pozbawiony kontekstu (możesz następnie iterować wszystkie wartości i zapisywać je wszystkie).
maniak zapadkowy
1
Warto zauważyć, że twoja propozycja dotyczy języków wrażliwych na wcięcia ze stałym wcięciem. Python (i inne tego rodzaju języki) nie są w ten sposób ograniczone; akceptują wszelkie wcięcia, których chce użytkownik. Nie ma to wpływu na analizowalność (z wyjątkiem obsługi znaków tabulatorów), ale trudno byłoby wyrazić swoją propozycję, przynajmniej tak, jak ją rozumiem.
rici
gramatyki atrybutów
Hendrik Jan
@HendrikJan, gramatyki atrybutów to sposób na opisanie gramatyki działaniem semantycznym, nie kontrolują parsowania.
AProgrammer
1
Jeśli celem jest obsługa wcięć, jest to bardziej odpowiednie dla tokenizera niż parsera. Niech tokenizer wyśle ​​wirtualne tokeny INDENT i UNINDENT, gdy zmieni się poziom wcięcia. Nie ma zatem potrzeby rozszerzania gramatyki języka o informacje o wcięciach.
John Kugelman

Odpowiedzi:

14

Gramatyki afiksów (sparametryzowane gramatyki bezkontekstowe) były szeroko badane przez wybitnego holenderskiego informatyka Cornelisa HA Kostera , zaczynając od jego artykułu z 1962 r. „Podstawowy angielski, gramatyka generatywna dla części angielskiego”, napisanego wspólnie z LGLT Meertens. W 1970 roku opracował formalizm koncepcji; użyteczny przegląd jest dostępny w jego artykule z 1971 r. „Afiks gramatyki dla języków programowania”, którego wersję znalazłem na Citeseer .

W tym artykule Koster porównuje swój formalizm (i inny podobny) z dwupoziomowymi gramatykami Van Wijngaarden i stwierdza, że ​​są one bardzo podobne.

Nieoceniona bibliograficzna analiza technik parsowania Dicka Grune'a zawiera wiele innych przydatnych odniesień do afiksów gramatycznych i innych form nie-chomskich. (Patrz rozdział 18.2.6 bibliografii, chociaż w innych rozdziałach znajdują się przydatne artykuły). Grune krótko przytwierdza gramatykę w §15.3.2 drugiego wydania Parsing Techniques: A Practical Guide (a jeszcze bardziej krótko w pierwszym wydaniu , dostępne online), wspominając o tym, że łatwo jest dostosować techniki analizy odgórnej (i inne).

anbncn

Koster, który był również redaktorem raportu Algol 68, był pierwotnym twórcą języka opisu kompilatora (CDL) , opartego na jego pomysłach na temat afiksów gramatycznych. Ten zestaw narzędzi i jego późniejsze pochodne były używane w produkcji przez wiele lat. Ta strona , którą znalazłem podczas wyszukiwania w Google i której trwałości nie mogę zagwarantować, zawiera linki do strony z instrukcją obsługi i pobierania dla CDL3.

rici
źródło
Wydaje mi się, że języki CDL bardziej przypominają gramatykę atrybutów : wartości atrybutów mogą być obliczane przez funkcje zdefiniowane zewnętrznie. Zastrzegam sobie gramatykę afiksów nazw dla przypadków, w których relacje między wartościami afiksów (atrybutów) są zdefiniowane w ramach formalizmu, jak w gramatyce rozszerzonego afiksu .
reinierpost
@reinierpost: Oczywiście masz prawo do własnej terminologii; przywilej nie jest ograniczony do jaj antropomorficznych. Jednak sam podręcznik CDL twierdzi, że „CDL3 jest językiem implementacji opartym na gramatyce afiksów”, co moim zdaniem należy wziąć pod uwagę. (Podręcznik dostępny na ftp.cs.kun.nl/pub/cdl3/cdl3-manual-1.2.7.pdf ). Tak twierdziłem w mojej odpowiedzi: że CDL był oparty na pracy Kostera nad gramatykami afiksowymi. Jak zauważa Grune, różnica między gramatyką afiksową i gramatyczną jest niewielka; rozróżnia on, czy afiksy są używane do decydowania o ważności składniowej.
rici
(Cytat pochodzi z pierwszej strony instrukcji.)
rici
Wiem ... i masz rację. Mój komentarz nie miał na celu zaprzeczenia.
reinierpost
6

Weź lemat pompowania dla CFG :

Weź gramatykę

S -> A("")
A(p) -> p 
      | p '\n' A(p"*") '\n' p 

To opisuje trójkąt gwiazdy:

*
**
***
**
*

uvwxy{uvnwxny|n>0}vx

Oznacza to, że trójkąt gwiezdny nie jest językiem bezkontekstowym.

Lub prostszy przykład:

S-> B("")
B(p)-> p 'a' p 'a' p
     | B(p 'b')

{bnabnabn|n0}

maniak zapadkowy
źródło
3

Nigdy nie widziałem tego formalizmu (nawet w czymś takim jak techniki analizy Grune'a ), w zależności od szczegółów, w jaki sposób dokładnie definiujesz „parametry powinny być w zasadzie parserami”, wygląda na to, że da się odwzorować gramatykę dwupoziomową van Wijngaarden, która ma taką samą moc jak nieograniczona gramatyka struktury faz (tzn. mocniejsza niż kontekstowa, możesz napisać gramatykę VW, która daje wszystkie programy zatrzymujące).

AProgrammer
źródło
O ile mi wiadomo, Koster i jego grupa badali dwa typy gramatyk afiksowych: 1) ograniczone formy gramatyki Van Wijngaarden, mające na celu łatwiejsze rozpoznawanie; 2) języki CDL, praktyczne języki opisu kompilatora bez żadnej jawnej manipulacji wartością afiksu, ale z opcją definiowania reguł w języku docelowym (np. Asembler), dzięki czemu Turing jest kompletny.
reinierpost