Existe algum algoritmo de análise não-geral de CFG que reconheça o EPAL?

EPAL, o idioma dos palíndromos pares, é definido como o idioma gerado pela seguinte gramática inequívoca e livre de contexto:

$S \rightarrow a a$

$S \rightarrow b b$

$S \rightarrow a S a$

$S \rightarrow b S b$

O EPAL é o 'bane' de muitos algoritmos de análise: ainda não encontrei nenhum algoritmo de análise para CFGs inequívocos que possam analisar qualquer gramática que descreva o idioma. É frequentemente usado para mostrar que existem CFGs inequívocos que não podem ser analisados por um analisador específico. Isso inspirou minha pergunta:

Existe algum algoritmo de análise que aceita apenas CFGs inequívocos que funcionam no EPAL?

Obviamente, é possível projetar um analisador ad-hoc de duas passagens para a gramática que analisa o idioma em tempo linear. Estou interessado em analisar métodos que não foram projetados especificamente com o EPAL em mente.

formal-languages formal-grammars parsers Alex ten Brink
fonte

Estou quase com medo de perguntar: o que há de errado com LL (1) por descendência recursiva?

Raphael

A descida recursiva sem retorno atrás não pode lidar com o EPAL, pois o idioma não é LL (k) para nenhum k. A descida recursiva com retorno pode lidar com a gramática no tempo

O (n^{2})

$O(n^2)$ , mas esse é um algoritmo geral com comportamento exponencial de pior caso, que não é o que estou procurando.

Alex-Brink

não é exponencial, é quadrático.

é exponencial.

O (N^{2})

$O(N^2)$

O (2^{N})

$O(2^N)$

22330 Victor Stafusa

@ Victor: o retorno tem um comportamento exponencial em algumas gramáticas, mas não nessa gramática específica. Ainda assim, o fato de ser um algoritmo que trabalha com gramáticas ambíguas desconta-o como resposta à minha pergunta.

Alex-Brink

@jmad: minha intenção não é analisar o idioma (você pode fazer isso trivialmente em tempo linear), mas sim satisfazer minha curiosidade: já vi isso sendo usado como exemplo de um idioma que não pode ser analisado por um método de análise tantas vezes que estou curioso para saber se existe algum método de análise que o reconheça.

Alex-Brink

Respostas:

Considere o seguinte esboço de uma estratégia de análise por seu próprio risco.

Em vez de ler a entrada apenas de uma extremidade, lemos de ambos os lados e procuramos regras de correspondência. Podemos fazer isso no estilo descendente recursivo; em uma chamada para , encontre o prefixo e o sufixo na entrada, de modo que exista uma regra , desça para na palavra restante. Se não houver uma regra correspondente, rejeite a palavra. $A()$ $w$ $v$ $A \to wBv$ $B()$

$A \to wBv$ $A \to w'B'v'$ $w \not\equiv_p w'$ $v \not\equiv_s v'$ $\Theta(n^2)$

A idéia não funciona para gramáticas não lineares. Gramáticas lineares, porém ambíguas, em geral não podem ser analisadas sem retorno (pelo menos para entradas negativas).

$w \not\equiv_p v$ meios aqui que e , ou seja, nem palavra é um prefixo do outro. é semelhante para sufixos. $w \not\sqsubseteq v$ $v \not\sqsubseteq w$ $\not\equiv_s$

Rafael
fonte

Excelente! Exatamente o que eu estava procurando. É ótimo que uma linguagem que não seja para qualquer seja analisável por um algoritmo tão simples.

N L R (k)

$NLR(k)$

k

$k$

Alex-Brink

Depois de pensar mais sobre isso, descobri um pequeno erro na sua descrição: a gramática linear não é ambíguo, mas não existe um prefixo exclusivo como você o descreve. Ainda existe um prefixo exclusivo, mas talvez você precise procurar dentro do não-terminal para obtê-lo, e seu tempo de execução se torna . Seu algoritmo funciona no .

S \to a A b | a B b, A \to a, B \to b

$S \rightarrow a A b | a B b, A \rightarrow a, B \rightarrow b$

O (n^{2})

$O(n^2)$

E P A L

$EPAL$

Alex10 Brink

@AlextenBrink Good catch. Eu editei para explicar isso.

Raphael