Какие хорошие обозначения существуют для детерминированных контекстно-свободных и визуально выпадающих языков?

Детерминированные контекстно-свободные языки (DCFL) и языки визуального нажатия (VPL) являются наборами формальных языков между контекстно-свободными языками (CFL) и обычными языками (REG). Есть ли удобочитаемая нотация, которая может быть выражена в простом ASCII-формате, например Backus-Naur-Form для CFL и регулярных выражений для REG?

fl.formal-languages Jakob
источник

Возможно, было бы полезно уточнить значение слова «хорошо» в заголовке вопроса. Что не так с использованием BNF для описания DCFL?

Цуёси Ито

Под добром я подразумеваю, что это должно быть легко читать и писать для людей, поэтому оно должно быть основано на ASCII. BNF великолепен - регулярные выражения являются компактным подмножеством BNF. Но какое подмножество BNF определяет DCFL, а какое определяет VPL?

Якоб

Ответы:

Что касается DCFL, я не вижу лучшего обозначения, чем переходная функция детерминированного пуш-автомата, то есть написание явных правил вида с состояниями в , символом стека, последовательность символов стека, и $q,z,a\to q',\gamma$ $q,q'$ $Q$ $z$ $\gamma$ $a$ входной символ или пустая строка. Само обозначение не обеспечивает детерминизм, но его легко проверить. Используя не зависящий от контекста грамматический вид обозначений (например, BNF), вы столкнетесь с проблемами, поскольку DCFL являются надлежащим подклассом CFL, и, как отмечается в DaniCL, вы не можете в целом решить, учитывая CFG, является ли его язык детерминированным.

Что касается VPL, то в скобках / в скобках для CFG было бы достаточно, с правилами формы где - нетерминал, - символ вызова, - символ возврата и - ~~последовательность~~ регулярного выражения над смешанным. внутренние символы и нетерминалы. Поскольку любой VPL также является (D) CFL, вы также можете повторно использовать приведенную выше нотацию для автоматов pushdown и проверить, соответствуют ли операции стека вызовам и возвратам, или записать переходное отношение вложенного словесного автомата (который был бы менее избыточным) , $A\to a\alpha b$ $A$ $a$ $b$ $\alpha$

$a$ $b$

Сильвен
источник

Спасибо! Что касается DCFLs, я думаю, что это правильное направление. Конкретный синтаксис будет иметь несколько удобных сокращений для подмножеств, которые анализируются регулярными выражениями. Что касается VPL, я еще не уверен, потому что VLP разрешено иметь висячие вызовы и символы возврата в отличие от древовидных моделей, таких как XML. Вы можете лучше сравнить его с произвольной подпоследовательностью SAX-событий из произвольного дерева XML. Я сомневаюсь, что RelaxNG может описать это.

Якоб

Замечание Использование ... является детерминированным. это не относится к делу - в нем ничего не говорится о том, существует ли подкласс CFG, который очень явно описывает все DCFL, и ничего больше. Такие как LR (k) грамматики.

reinierpost

@reinerpost: верно, но (в мою защиту) я бы не стал рассматривать грамматику LR (1) для обеспечения синтаксической нотации, потому что нужно проверить условие LR (1).

Сильвен

Чтобы найти каноническое представление, рассмотрим следующее: класс DCFL эквивалентен классу языков, генерируемых грамматиками LR (k), что опять-таки эквивалентно LR (1). Это означает, что вы можете найти грамматику LR (1) для каждого DCFL. Конечно, грамматика LR (1) по-прежнему является контекстно-свободной грамматикой, но со специальным свойством: из грамматик LR (1) мы можем легко создавать таблицы синтаксического анализа, чтобы направлять детерминированный синтаксический анализатор (с заглядыванием в 1 символ, следовательно, LR (1)). Эти таблицы разбора были бы другим представлением, хотя и несколько менее читабельным.

Кстати, помните, что неразрешимо, является ли данный контекстно-свободный язык детерминированным (теорема Грейбаха).

Я должен признать, что я никогда не слышал о VPL.

DaniCL
источник

Ну, канонические представления редко легко читаются, но спасибо за указания. Если в теореме Грейбаха говорится, что в CFL есть языки, которые не могут быть включены в DCFL - как вы определяете эти языки? Если у вас есть грамматика, вы можете выразить ее в форме Бэкуса-Наура (БНФ), поэтому теорема Грейбаха, по-видимому, подразумевает, что нет подмножества БНФ, которое бы точно выражало DCFL? Видимые выпадающие языки также известны как «вложенные слова». Этот класс языков является относительно новым, но он актуален для разбора упорядоченных деревьев и подобных структур.

Якоб

О проблеме неразрешимости: язык - это CFL, если существует не зависящая от контекста грамматика (CFG), генерирующая его. Если вам дают CFG, вы можете решить, является ли эта грамматика LR (k), следовательно, детерминированной. (То же самое относится и к автоматам pushdown - легко проверить, является ли данный PDA детерминированным или нет.) Однако предположим, что у вас есть CFG, который не является LR (k) - это не означает, что язык не является DCFL ; вы просто не сможете найти грамматику LR (k) для нее.

DaniCL

«Вы можете решить, является ли эта грамматика LR (k)» для фиксированного k.

Сильвен

@Jakob: Теорема Грейбаха не утверждает, что, и даже если бы она это сделала, это означало бы только то, что произвольные CFG не являются подходящим формами обозначений для DCFG, так же как они не являются хорошим формализмом для обозначения регулярных языков (будь то CFG описывает обычный язык, также неразрешимый). Однако нет ничего плохого в выборе подкласса CFG (например, регулярные грамматики для обычных языков).

reinierpost

Здесь в учебниках есть традиция небрежной формулировки: они, как правило, делают такие заявления, как «неразрешимо, является ли КЛЛ регулярным / детерминированным», тогда как на самом деле это означает «неразрешимо, описывает ли CFG обычный / детерминированный язык».

reinierpost