Dada una cadena y un CFG, ¿qué caracteres pueden seguir a la cadena (en las formas de sentencia del CFG)?

10

Deje el conjunto de terminal y el conjunto de símbolos no terminales de algunos gramática libre de contexto .N GΣnortesol

Digamos que tengo una cadena tal que donde y son las formas enunciativas de . x a y S ( G ) x , y ( Σ N ) S ( G ) Gun(Σnorte)+XunyS(sol)X,y(Σnorte)S(sol)sol

Dado , me gustaría determinar un conjunto .C = { b w a b z S ( G ) , b Σ N }solC={siwunsizS(sol),siΣnorte}

Para aclarar, en este caso, son cadenas de terminales y no terminales y es de longitud uno.bw,X,y,z,un,sisi

Puedo ver cómo hacer esto si también es de longitud uno; cada es un miembro del siguiente conjunto de (incluidos los no terminales).unsiun

Sin embargo, tengo curiosidad si es posible para una secuencia de personajes. Para mi solicitud, la cadena de no es mucho más largo que el lado derecho de las producciones en .unsol

La distinción entre terminales y no terminales es algo muda en mi aplicación porque estoy usando una gramática generativa; y creo que esto no generará muchos problemas ya que es de longitud uno.si

Thomas
fuente
1
¿Cuál es tu aplicación? ¿Estás construyendo un analizador?
Raphael
¿Podemos suponer que la gramática está en alguna forma normal o tiene que funcionar para las arbitrarias?
Raphael
@AlextenBrink: e son cadenas arbitrarias. Solo estoy mirando un fragmento / subcadena. xy
Thomas
@Raphael: estoy tratando de automatizar las transformaciones de las gramáticas del sistema L ... por lo que no está en forma normal. De hecho, volveré a editar esta pregunta para que sea más precisa.
Thomas
Espero no haber cambiado demasiado la pregunta, ahora tiene una naturaleza ligeramente diferente.
Thomas

Respuestas:

6

Describiré un algoritmo que funciona. Su tiempo de ejecución no debería ser tan malo. También puede calcular previamente un poco de esto.

Asumiré que no contiene no terminales (aunque probablemente sea fácil adaptarse a ese caso) y que no conoces x , y o la derivación de a . También supondré que su gramática no contiene producciones que nunca se usan en ninguna derivación ( A A, por ejemplo).unXyunUNUN

El problema principal es analizar , ya que desea saber en qué tipo de estados termina, para saber qué puede seguir a . Esto no es tan fácil como no sabes x .ununX

Usamos una adaptación del algoritmo de Earley . Querrás entender ese algoritmo primero. Nuestro algoritmo funciona casi de la misma manera, excepto que nuestros pasos de inicialización y finalización son diferentes.

Para la inicialización, sembramos nuestro primer conjunto con un elemento Earley por cada aparición de (el primer carácter en a ) en cualquier producción de su gramática. Establecemos el puntero posterior de este elemento en -1, un valor no válido. Esto es importante en nuestra finalización modificada. Esencialmente, el -1 significa 'No tengo idea de dónde se inició esta producción'.un1un

Ahora, realizamos el algoritmo Earley por separado para cada posible artículo inicial de Earley. No podemos simplemente hacerlos todos al mismo tiempo, ya que los análisis pueden interferir entre sí. No puedo ver fácilmente un método más rápido que retroceder aquí.

Para el paso de finalización, solo tenemos que hacer una modificación para manejar -1 punteros de retroceso. Como hemos completado una producción cuyo origen desconocemos, estamos en problemas. Sin embargo, el método utilizado para calcular los conjuntos de búsqueda LUNLR(1)anticipada L A L R ( 1 ) de Pennello y DeRemer nos salva: lo que necesitamos aquí es exactamente los conjuntos de búsqueda anticipada . Cada elemento en estos conjuntos de búsqueda anticipada tiene una posición correspondiente en la gramática, que a su vez corresponde a una posible continuación de la producción completa.LUNLR(1)

Desafortunadamente, realmente no veo otra opción que retroceder aquí una vez más. Para cada posición en el conjunto de búsqueda anticipada, realiza el paso de finalización con esta posición y continúa el análisis desde allí. Lo haces por separado para cada análisis. Tenga en cuenta que si su gramática es , su búsqueda anticipada determinará de manera única a qué posición debe ir, para que no tenga que retroceder.LUNLR(1)

un

Editar: creo que he encontrado el método que elimina la mayor parte de la sobrecarga introducida por el retroceso. Asociamos con cada elemento Earley un conjunto de identificadores, que son cadenas, ya que tendremos que usar prefijos de estos identificadores. En la inicialización, agregamos todos los elementos iniciales al conjunto de Earley y asociamos un identificador único con cada conjunto.

En los pasos del escáner y del predictor, los identificadores se transfieren a los nuevos elementos. Los elementos de Earley en el mismo conjunto de Earley que solo difieren en sus identificadores se fusionan al fusionar sus identificadores. Tenga en cuenta que podemos realizar pasos de escáner y predictor en estos nuevos elementos con identificadores, sin tener que realizar este paso para cada identificador por separado.

LUNLR(1)

Esencialmente, hacemos el retroceso utilizando estos identificadores, de modo que no hagamos doble trabajo en los pasos del escáner y del predictor.

Alex ten Brink
fuente
unun
@Thomas Eso no es demasiado difícil: simplemente considera que el no terminal es un terminal para esa posición en particular en el análisis: aún predice y completa en forma normal, pero también lo considera al escanear.
Alex ten Brink
Sí, de hecho, ahora que entiendo su solución, no debería haber ninguna diferencia.
Thomas