¿Generalizaciones del método de Brzozowski de derivadas de expresiones regulares a gramáticas?

El método de derivación de Brzozowski es una técnica muy bonita para construir autómatas deterministas a partir de expresiones regulares de una manera muy algebraica. He elaborado algunas generalizaciones lindas de esta técnica para manejar algunas clases más grandes de gramáticas, pero los algoritmos son lo suficientemente sencillos que parece bastante posible que hayan sido descubiertos antes. Pero las referencias de Google a los descendientes de esta técnica no parecen aparecer mucho. Alguien sabe de algo?

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

Tengo mucha curiosidad acerca de qué clases de gramáticas estás pensando. Sobre los descendientes, la técnica de Antimirov, que produce autómatas no deterministas en su lugar, es muy agradable: derivadas parciales de expresiones regulares y construcciones de autómatas finitos , TCS 155 (2), 1996, ( dx.doi.org/10.1016/0304-3975(95 ) 00182-4 ).

Sylvain el

¿te refieres a generalizaciones a lenguajes más complejos, como <contexto-libre <sensible al contexto <...?

s8soj3o289

He estado buscando subsistemas de CFG aproximadamente en el vecindario de VPL, principalmente.

Neel Krishnaswami

... pero el conjunto de derivados no es finito entonces. Y, de hecho, si desea algo determinista como con el método de Brzozowski, probablemente esté restringido a DCFL (por lo tanto, imagino que puede tener sentido para VPL).

Sylvain

arxiv.org/abs/1604.04695

Mehrdad

Respuestas:

En Total Parser Combinators (ICFP 2010) utilizo los derivados de Brzozowski para establecer que la membresía lingüística es decidible para una cierta clase de gramáticas potencialmente infinitas.

Nils Anders Danielsson
fuente

Quizás te interese este artículo:

Yacc está muerto por Matthew Might y David Darais, 2010

Presentamos dos enfoques novedosos para analizar lenguajes sin contexto. El primer enfoque se basa en una extensión de la derivada de Brzozowski de expresiones regulares a gramáticas libres de contexto. El segundo enfoque se basa en una generalización de la derivada a los combinadores analizadores. La recompensa de estas técnicas es una biblioteca de análisis pequeña (menos de 250 líneas de código), fácil de implementar, capaz de analizar gramáticas arbitrarias libres de contexto en bosques de análisis perezoso. Se proporcionan implementaciones para Scala y Haskell. Los experimentos preliminares con Expresiones S analizaron millones de tokens por segundo, lo que sugiere que esta técnica es lo suficientemente eficiente como para usarla en la práctica.

También de potencial interés:

Yacc is Not Dead , reseña de este artículo de Russ Cox, de re2 fama.
Yacc está muerto: una actualización , respuesta de Matt Might.
Perla funcional: análisis con derivados por Matthew Might, David Darais y Daniel Spiewak - una versión actualizada del documento "Yacc is Dead", presentado en ICFP 2011 en Tokio.

Mikhail Glushenkov
fuente

Título de papel muy divertido! :-)

Dai Le

A mediados de los años 80, mientras trabajaba en analizadores de ascenso recursivo y factorización de gramáticas, comencé definiendo derivadas parciales de gramáticas.

Mucha teoría agradable allí.

Usted tiene alguna pregunta especifica?

GHR
fuente

En este momento solo estoy buscando trabajo relacionado. Como he estado pensando principalmente en analizadores de descenso recursivo, las aplicaciones para el análisis de estilo LR, como usted sugiere, son particularmente interesantes. ¿Puedes señalarme alguno de tus papeles?

Neel Krishnaswami