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

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

Digamos que tengo una cadena tal que donde y son las formas enunciativas de . x a y ∈ S ( G ) x , y ∈ ( Σ ∪ N ) ∗ S ( G ) $a \in (\Sigma \cup N)^+$$x a y \in \mathcal{S}(G)$$x,y\in (\Sigma \cup N)^*$$\mathcal{S}(G)$$G$

Dado , me gustaría determinar un conjunto .C = { b ∣ w a b z ∈ S ( G ) , b ∈ Σ ∪ N $G$$C = \{ b \mid wabz \in \mathcal{S}(G), b \in \Sigma \cup N \}$

Para aclarar, en este caso, son cadenas de terminales y no terminales y es de longitud uno.$w, x, y, z, a, b$$b$

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).$a$$b$$a$

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 .$a$$G$

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.$b$

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).$a$$x$$y$$a$$A \rightarrow A$

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 .$a$$a$$x$

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'.$a_1$$a$

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 $LALR(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.$LALR(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.$LALR(1)$

$a$

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.

$LALR(1)$

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