Что вы получите, если добавите параметры в контекстно-свободные грамматики?

Я думал о грамматиках для чувствительных к индендангу языков, и похоже, что грамматики CF сработают, если их объединить с параметрами. В качестве примера рассмотрим этот фрагмент для упрощенной грамматики Python в 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 '    ')+)
    ;

Мой вопрос: есть ли у этого вида грамматик (CFG с параметрами) имя?

Похоже, что для этой грамматики не составит труда написать парсер рекурсивного спуска (параметры должны быть в основном парсерами). Какие могут быть трудности с этим подходом?

Повышает ли добавление параметров поддерживаемый языковой класс над контекстно-свободным?

Аффиксные грамматики (параметризованные контекстно-свободные грамматики) широко изучались выдающимся голландским ученым-компьютерщиком Корнелисом Х.А. Костером , начиная с его статьи 1962 года «Базовый английский, порождающая грамматика для части английского языка», написанной в соавторстве с LGLT Meertens. В 1970 году он создал формализм концепции; полезный обзор доступен в его статье 1971 года «Грамматика аффиксов для языков программирования», версию которой я нашел на Citeseer .

В этой статье Костер сравнивает свой формализм (и другой подобный) с двухуровневыми грамматиками Ван Вейнгаардена и находит их очень похожими.

Бесценная аннотированная библиография методов разбора Дика Груна включает большое количество других полезных ссылок для аффиксных грамматик и других нехомских формализмов. (См. Раздел 18.2.6 библиографии, хотя в других разделах есть полезные статьи.) Грюн кратко описывает аффиксные грамматики в п. 15.3.2 второго издания «Техника синтаксического анализа: практическое руководство» (и даже более кратко в первом издании (доступно онлайн), отмечая тот факт, что легко адаптировать нисходящие (и другие) методы синтаксического анализа.

$a^n b^n c^n$

Костер, который также был редактором отчета Algol 68, был первым разработчиком языка описания компилятора (CDL) , основанного на его идеях о грамматике аффиксов. Этот инструментарий и его более поздние производные использовались в производстве в течение многих лет. На этой странице , которую я нашел с помощью поиска Google и чье постоянство я не могу гарантировать, есть ссылки на руководство и сайт загрузки для CDL3.

Возьмем лемму прокачки для CFG :

Взять грамматику

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

Это описывает звездный треугольник:

*
**
***
**
*

$uvwxy$$\{uv^nwx^ny|n>0\}$$vx$

Это означает, что звездный треугольник не является контекстно-свободным языком.

Или более простой пример:

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

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

Я никогда не видел этот формализм, представленный (даже в чем-то вроде техник синтаксического анализа Груна ), в зависимости от того, как именно вы определяете, «параметры должны быть в основном парсерами», он выглядит сопоставимым с двухуровневыми грамматиками ван Вейнгаардена, которые имеют ту же мощность, что и грамматика неограниченной фазовой структуры (т.е. более мощная, чем контекстно-зависимая, вы можете написать грамматику VW, которая дает все программы остановки).