Generalizações do método de Brzozowski de derivadas de expressões regulares para gramáticas?

O método de derivadas de Brzozowski é uma técnica muito bonita para construir autômatos determinísticos a partir de expressões regulares de uma maneira bastante algébrica. Eu elaborei algumas generalizações engraçadas dessa técnica para lidar com algumas classes maiores de gramática, mas os algoritmos são simples o suficiente para que pareça bem possível que eles tenham sido descobertos antes. Mas as referências do Google aos descendentes dessa técnica parecem não aparecer muito. Alguém sabe de alguma coisa?

reference-request fl.formal-languages parsing Neel Krishnaswami
fonte

Estou bastante curioso sobre quais classes de gramática você está pensando. Sobre os descendentes, a técnica de Antimirov, que produz autômatos não determinísticos, é muito agradável: derivadas parciais de expressões regulares e construções de autômatos finitos , TCS 155 (2), 1996, ( dx.doi.org/10.1016/0304-3975(95 ) 00182-4 ).

23410 Sylvain

você quer dizer generalizações para linguagens mais complexas, como regular <sem contexto <sensível ao contexto <...?

s8soj3o289

Estive observando subsistemas de CFGs aproximadamente no bairro de VPLs, principalmente.

Neel Krishnaswami

... mas o conjunto de derivativos não é finito então. E, de fato, se você deseja algo determinístico, como no método de Brzozowski, provavelmente está restrito aos DCFLs (portanto, imagino que possa fazer sentido para os VPLs).

precisa

arxiv.org/abs/1604.04695

Mehrdad

Respostas:

No Total Parser Combinators (ICFP 2010), uso derivativos de Brzozowski para estabelecer que a associação ao idioma é decidível para uma certa classe de gramáticas potencialmente infinitas.

Nils Anders Danielsson
fonte

Você pode estar interessado neste artigo:

Yacc está morto por Matthew Might e David Darais, 2010

Apresentamos duas novas abordagens para analisar linguagens sem contexto. A primeira abordagem é baseada em uma extensão da derivada de Brzozowski de expressões regulares para gramáticas sem contexto. A segunda abordagem é baseada em uma generalização do derivado para os combinadores do analisador. A recompensa dessas técnicas é uma biblioteca de análise pequena (com menos de 250 linhas de código) e fácil de implementar, capaz de analisar gramáticas arbitrárias e livres de contexto em florestas de análise preguiçosas. Implementações para Scala e Haskell são fornecidas. Experimentos preliminares com expressões S analisaram milhões de tokens por segundo, o que sugere que essa técnica é suficientemente eficiente para uso na prática.

Também de interesse potencial:

Yacc não está morto , revisão deste artigo por Russ Cox, da re2 fama.
Yacc está morto: uma atualização , resposta de Matt Might.
Pérola funcional: análise com derivativos de Matthew Might, David Darais e Daniel Spiewak - uma versão atualizada do artigo "Yacc is Dead", apresentado no ICFP 2011 em Tóquio.

Mikhail Glushenkov
fonte

Título em papel muito engraçado! :-) #

Dai Le

Em meados dos anos 80, enquanto trabalhava em analisadores de subida recursiva e fatoração de gramáticas, comecei definindo derivadas parciais de gramáticas.

Muita teoria legal lá.

Você tem alguma pergunta específica?

GHR
fonte

No momento, estou apenas procurando trabalhos relacionados. Como estive pensando principalmente em analisadores de descida recursiva, encontraria aplicativos para análise no estilo LR, como você sugere, particularmente intrigantes. Você pode me apontar algum dos seus documentos?

Neel Krishnaswami