Frases de permutação com análise de LR

16

Uma frase de permutação é uma extensão das definições gramaticais livres de contexto (E) BNF: uma frase de permutação contém produções (ou equivalentes, não terminais) a . Na posição da frase de permutação, gostaríamos de ver cada uma dessas produções exatamente uma vez, mas não estamos interessados ​​em ordenar essas não-terminais.{A1,,An}nA1An

Por exemplo:

S <- X { A, B, C } Y

é equivalente a:

S <- X  A B C  Y
S <- X  A C B  Y
S <- X  B A C  Y
S <- X  B C A  Y
S <- X  C A B  Y
S <- X  C B A  Y

O conceito parece ser introduzido em "Estendendo gramáticas sem contexto com frases de permutação" . Nele também é descrito como analisar essas frases em tempo linear usando um analisador LL (1).

O documento "Analisando frases de permutação" descreve um método para analisar frases de permutação usando combinadores de analisador. Estes são os únicos dois artigos que encontrei que falam sobre frases de permutação e como analisá-las.

Visto que podemos analisar facilmente esses tipos de frases de permutação com analisadores baseados em LL (1), meu palpite seria que podemos fazer o mesmo com analisadores de estilo LR (1). Minha pergunta é, portanto:

Uma gramática contendo frases de permutação pode ser analisada no tempo linear no tamanho da string de entrada usando máquinas LR (1) enquanto mantém uma tabela de tamanho razoável?

O(|G|!)

O(2|G|)

Embora isso seja melhor, é claro que não é bom o suficiente - ter uma frase de permutação de 30 itens tornaria a gramática inutilizável. Ainda existe uma parte da análise de LR que ainda não tocamos, e esse é o procedimento baseado em pilha real usado para a análise. Imagino que armazenar contadores na pilha possa resolver o problema, mas não sei como fazer isso.

No momento, estou implementando um gerador de analisador e, no domínio do problema, as frases de permutação seriam um presente do céu. Como estou usando máquinas LR (1), a pergunta acima se seguiu.

Alex ten Brink
fonte
A complexidade da análise de LR (1) já é exponencial no tamanho da gramática sem frases de permutação - exceto se você implementar um cálculo "on the fly" do analisador, mas parecerá mais um analisador Earley do que um LR genuíno (1) um.
27412 Sylvain
2
Sobre o restante da sua pergunta: cstheory.stackexchange.com/questions/4962/… mostra um limite inferior exponencial do tamanho de um CFG para permutações e pela construção polinomial usual de CFGs de PDAs, isso implica um limite inferior exponencial no o tamanho do PDA também.
27412 Sylvain
11
Eu não tinha olhado para o jornal sobre LL (1). De fato, o analisador implementado não é mais um PDA. Ainda não acredito na existência de uma "tabela de tamanho razoável", uma vez que a associação para gramáticas comutativas sem contexto é NP-completa (consulte, por exemplo, dx.doi.org/10.3233/FI-1997-3112 ), mas é verdade que as instâncias rígidas podem não ser LR (1).
27412 Sylvain
2
@Sylvain: Você pode explicar como a pergunta 4962 se relaciona com essa? Na pergunta 4962, a permutação é fixa para cada comprimento de entrada e as seqüências a serem permutadas são alteradas. Na pergunta atual, não corrigimos a permutação. Portanto, não vejo nenhuma conexão real entre eles.
Tsuyoshi Ito 27/01
2
@Tsuyoshito Ito: No LR (1), a análise de um DPDA equivalente à gramática de entrada é primeiro construída e depois executada na sequência de caracteres para reconhecer. Como existe um CFG de tamanho linear com frases de permutação para cada idioma de permutação, o artigo de Yuval Filmus (que é mais abrangente do que sua resposta sobre a história: veja cs.toronto.edu/~yuvalf/CFG-LB.pdf ) mostra que não esse DPDA pode ter tamanho polinomial no tamanho da gramática de entrada.
27412 Sylvain

Respostas:

1

Você já pensou em converter isso em um problema semântico? Em vez de regras gramaticais para todas as permutações de não-terminais {A, B, C}, basta ter uma regra para reconhecer (A | B | C) ^ 3 junto com o código interno especial que garante que apenas um de cada seja reconhecido, caso contrário, declara um erro. Eu inseriria uma produção vazia antes da cláusula acima, cuja redução aciona a inicialização do que você está usando para contar A, B e C e uma depois, cuja redução aciona a verificação do contador e (se necessário) afirma o erro. (é claro que isso pode ser um pouco complicado se a gramática for recursiva em A, B e / ou C)

PMar
fonte
0

Eu não acho que alguém precise de um balcão. Basicamente, você apenas verifica todas as permutações, mas quebra

pseudo-código:

perm-match(input, pattern)
     if pattern = nil return true

     foreach(rule in pattern)
         if (match(input, rule))
             perm-match(input - matchedpart, pattern - rule)
             break
         end
     end
     return false
end

Aqui está um exemplo mais concreto

Suponha que estamos tentando corresponder a qualquer permutação de abcd e nossa string é bcda

  • Etapa 1: encontre o primeiro símbolo correspondente. Nesse caso, é b
  • Etapa 2: remova esse símbolo do nosso padrão e reduza a corda: por exemplo, acd e cda são deixados
  • Etapa 3: repita a etapa 1 nas novas seqüências
    • c corresponde no cda, o que nos deixa com ad e da
    • a combina em da que nos deixa com d e d
    • d corresponde em d, o que nos deixa nulos nas duas cadeias

Então você vê que esse algoritmo simples pode verificar uma permutação facilmente, simplesmente comparando "strings" fora de ordem. Observe que a complexidade da função é O (n!) Pior caso e O (1) melhor caso. Em certo sentido, estamos mantendo a contagem armazenando os símbolos para combinar em uma matriz. Eu pensaria que isso seria "rápido" em geral, uma vez que não se lida com n muito grande na maioria dos casos.

Uiy
fonte
2
nn=50.