Que boas notações existem para linguagens determinísticas livres de contexto e visivelmente pushdown?

Linguagens livres de contexto determinísticas (DCFL) e linguagens visivelmente pushdown (VPL) são conjuntos de linguagens formais entre linguagens livres de contexto (CFL) e linguagens regulares (REG). Existe uma notação legível que pode ser expressa em ASCII simples, como Backus-Naur-Form for CFL e expressões regulares para REG?

fl.formal-languages Jakob
fonte

Pode ser útil esclarecer o significado de "bom" no título da pergunta. O que há de errado em usar o BNF para descrever um DCFL?

Tsuyoshi Ito

Por bem, quero dizer que deve ser fácil ler e escrever para seres humanos, portanto deve ser baseado em ASCII. O BNF é ótimo - expressões regulares são um subconjunto compacto do BNF. Mas qual subconjunto do BNF define DCFL e qual define VPL?

Jakob

Respostas:

$q,z,a\to q',\gamma$ $q,q'$ $Q$ $z$ $\gamma$ $a$ um símbolo de entrada ou a sequência vazia. A notação em si não impõe determinismo, mas é facilmente verificada. Usando uma notação gramatical sem contexto (como BNF), você terá problemas, já que os DCFLs são uma subclasse adequada de CFLs e, como observado pelo DaniCL, você não pode decidir, em geral, considerando um CFG, se seu idioma é determinístico.

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

$a$ $b$

Sylvain
fonte

Obrigado! Em relação aos DCFLs, acho que essa é a direção certa. Uma sintaxe concreta teria algumas abreviações úteis para subconjuntos analisados por expressões regulares. Em relação aos VPLs, ainda não tenho certeza, porque é permitido que um VLP tenha símbolos de chamada e retorno pendentes em contraste com modelos de árvore como XML. Você pode compará-lo melhor com uma sub-sequência arbitrária de eventos SAX de uma árvore XML arbitrária. Duvido que o RelaxNG possa descrever isso.

Jakob

A observação Usando ... é determinística. está fora de questão - não diz nada sobre se há uma subclasse do CFG que obviamente descreve todos os DCFLs e nada mais. Como gramáticas LR (k).

reinierpost

@reinerpost: true, mas (em minha defesa) eu não consideraria as gramáticas LR (1) como uma notação sintática , porque é preciso verificar a condição LR (1).

Sylvain

Para encontrar uma representação canônica, considere o seguinte: a classe do DCFL é equivalente à classe de idiomas gerada pelas gramáticas LR (k), que novamente é equivalente a LR (1). Isso significa que você pode encontrar uma gramática LR (1) para cada DCFL. Obviamente, uma gramática LR (1) ainda é uma gramática livre de contexto, mas com uma propriedade especial: das gramáticas LR (1), podemos facilmente criar tabelas de análise para orientar um analisador determinístico (com visualizador de 1 símbolo, portanto, LR (1) Essas tabelas de análise seriam outra representação, embora um pouco menos legível.

A propósito, lembre-se de que é indecidível se uma determinada linguagem livre de contexto é determinística (Teorema de Greibach).

Devo admitir que nunca ouvi falar da VPL.

DaniCL
fonte

Bem, representações canônicas raramente são fáceis de ler, mas obrigado pelas instruções. Se o Teorema de Greibach afirma que existem idiomas no CFL que não podem ser decididos no DCFL - como você especifica esses idiomas? Se você possui uma gramática, pode expressá-la na Forma Backus Naur (BNF), de modo que o Teorema de Greibach parece sugerir que não existe um subconjunto de BNF que expresse exatamente a DCFL? Os idiomas visivelmente pushdown também são conhecidos como "palavras aninhadas". Essa classe de idiomas é relativamente nova, mas relevante para analisar árvores ordenadas e estruturas similares.

Jakob

Sobre a questão da indecidibilidade: uma linguagem é uma CFL se existir uma gramática livre de contexto (CFG) que a gera. Se você receber um CFG, poderá decidir se essa gramática é LR (k), portanto determinística. (O mesmo se aplica aos autômatos de empilhamento - é fácil verificar se um determinado PDA é determinístico ou não.) No entanto, suponha que você tenha um CFG que não seja LR (k) - isso não significa que o idioma não seja um DCFL ; talvez você não consiga encontrar uma gramática LR (k).

DaniCL

"você pode decidir se esta gramática é LR (k)" para k fixo.

Sylvain

@Jakob: O teorema de Greibach não afirma que, e mesmo que afirmativo , isso significaria apenas que CFGs arbitrários não são um formalismo de notação adequado para DCFGs, assim como não são um bom formalismo de notação para idiomas regulares (se um O CFG descreve que um idioma comum também é indecidível). No entanto, não há nada errado em escolher uma subclasse dos CFGs (por exemplo, as gramáticas regulares para idiomas regulares).

Reinierpost

Há uma tradição de redação desleixada nos livros didáticos aqui: eles tendem a fazer declarações como "é indecidível se uma CFL é regular / determinística" quando o que elas realmente querem dizer com isso é "é indecidível se um CFG descreve uma regular / determinística língua".

Reinierpost