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

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?

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).

$a^n b^n c^n$

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.

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$$\{uv^nwx^ny|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')

$\{b^nab^nab^n | n\ge0 \}$

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).