Quitar izquierda recursividad de Contexto Gramáticas - Ordenamiento de no terminales

Question

Me han puesto en marcha recientemente el algoritmo del Paull para eliminar-recursividad por la izquierda de gramáticas libres de contexto:

Asignar un ordenamiento $ A_1, puntos \, $ A_n a los no terminales de la gramática.

por $ i: = 1 $ a $ $ n do begin
$ \ Quad $ de $ j: = 1 $ a $ I-1 $ do begin
$ \ Quad \ quad $ para cada producción de la forma $ A_i \ a A_j \ alpha $ do begin
$ \ Quad \ quad \ quad $ retirar $ A_i \ a A_j \ alpha $ de la gramática
$ \ Quad \ quad \ quad $ para cada producción de la forma $ A_j \ a \ beta $ do begin
$ \ Quad \ quad \ quad \ quad añadir $ $ A_i \ a \ beta \ alpha $ a la gramática
$ \ Quad \ quad \ quad $ final
$ \ Quad \ quad $ final
$ \ Quad $ final
$ \ Quad $ transformar el A_i $ $ -productions para eliminar la recursividad directa izquierda
final

De acuerdo con este documento, la eficiencia del algoritmo depende fundamentalmente de la orden de los no terminales escogidos en el principio; el documento analiza en detalle esta cuestión y sugerir optimizaciones.

Algunos notación:

diremos que un símbolo $ X $ es un esquina izquierda directa de un no terminal $ A $, si hay un $ A $ -producción con $ X $ como el más a la izquierda símbolo en el lado derecho. Se define el relación esquina izquierda para ser el cierre transitivo reflexivo de la relación-esquina directa izquierda, y definimos el relación-apropiada esquina izquierda para ser el transitiva cierre de la relación directa-esquina izquierda. Un no terminal es recursiva izquierda si se trata de una esquina correcta izquierda del mismo; un no terminal es directamente recursiva por la izquierda si se trata de una esquina izquierda directa de sí mismo; y un no terminal es indirectamente recursiva por la izquierda si es recursivo izquierda, pero no directamente recursiva por la izquierda.

Esto es lo que proponen los autores:

En el bucle interno del algoritmo de Paull, para no terminales $ A_i $ y $ A_j $, de manera que $ i> j $ e $ A_j $ es un rincón directa izquierda de $ A_i $, reemplazamos todas las apariciones de $ A_j $ como una esquina izquierda directa de $ $ A_i con todas las posibles expansiones de $ A_j $.

Esto sólo contribuye a la eliminación de la recursión por la izquierda de la gramática si A_i $ $ es una izquierda recursiva no terminal, y $ $ A_j se encuentra en un camino que hace A_i $ $ recursiva por la izquierda; es decir, si A_i $ $ es una esquina izquierda de $ A_j $ (además de $ $ A_j ser una esquina izquierda de $ A_i $).

podría eliminar los reemplazos que son inútiles en la eliminación de recursión por la izquierda si podíamos pedir los no terminales de la gramática de manera que, si $ i> j $ e $ A_j $ es un rincón directa izquierda de $ A_i $, entonces $ A_i $ es también una esquina izquierda de $ A_j $.

Podemos lograr esto al ordenar los no terminales con el fin de que el número de esquinas distintas de izquierda que tienen decreciente.

Dado que la relación de esquina de la izquierda es transitivo, si C es una esquina directa izquierda de B, cada esquina izquierda de C es también una esquina izquierda de B.

Además, ya hemos definido la relación esquina izquierda a ser reflexiva, B es una esquina izquierda de la misma.

Por lo tanto, si C es una esquina directa izquierda de B, debe seguir B en el orden de número de esquinas distintas izquierda decreciente, a no ser que B es una esquina izquierda de C.

Lo único que quiero es saber cómo ordenar los no terminales en el principio, pero no lo consigue desde el papel. Alguien puede explicarlo de una manera más sencilla? Pseudocódigo me ayudaría a entender mejor.

Answer 1

Esto no es realmente muy complicado. Vamos a suponer que épsilon producciones ya se han eliminado de la lengua, ya que sólo se oscurecer el concepto clave de "esquina izquierda".

Formulario de un gráfico G, donde los vértices son todos los no terminales de la gramática. Ahora dibuja una arista dirigida de A a B si existe alguna regla de producción que se ve como "A -> B [...]". Las llamadas de papel B una "esquina izquierda directo" de A. Más generalmente, algún otro C no terminal se llama una "esquina izquierda" de A si existe alguna trayectoria de A a C a lo largo de los bordes de este gráfico. Esto puede hacerse calculando el transitivo cierre de G, lo llaman H.

El documento sugiere ordenar los vértices contando el número de esquinas izquierda cada vértice A ha (es decir, cuántos otros no terminales se puede llegar desde A, o el grado de salida de A en el gráfico H), luego ordenarlos en orden decreciente por este número.

Una de las motivaciones handwavy de esta política es que si hay un importante no terminal (decir el símbolo de comenzar S) con conexiones a muchos otros símbolos), entonces tiene sentido para purgar izquierda recursividad de S desde el principio, porque si lo deja para más adelante habrá más copias de S que es necesario ampliar a cabo. Creo que la explicación en el papel es más convincente, pero quizás menos obvio.