Recursión izquierda y factorización de izquierda: ¿cuál va primero?

Question

Si tengo una gramática que tiene una producción que contiene recursión a la izquierda y a la izquierda como factoring como

$ qquad displaystyle f to fba mid cds mid c $

¿Cuál tiene prioridad, recursión de izquierda o factorización de izquierda?

Answer 1

Las transformaciones como el factorización de la izquierda o la eliminación de la recursión de la izquierda no tienen reglas de precedencia. Obviamente, las gramáticas resultantes pueden ser diferentes, pero reconocerán el mismo idioma.

El ejemplo de la gramática de la pregunta es más difícil que el típico problema de tarea de pregrado. Entonces, mostrar nuestro trabajo será útil.

Recursión izquierda

Definamos una transformación que elimina la recursión a la izquierda.

Dado

$ qquad displayStyle a a a alpha_0 mid a alpha_1 mid dots mid a alpha_n mid b beta_0 mid b beta_1 mid dots mid b beta_n $,

Quitamos la recursión izquierda como esta:

$ qquad displaystyle begin {align} a_h & a b beta_0 mid b beta_1 mid dots mid b beta_n a_t & a alpha_0 mid alpha_1 mid dots mid mid mid mid mid mid mid mid mid mid mid mid mid mid alpha_n a_ {t^+} & to a_t a_ {t^+} mid a_t a & a a_h a_ {t^+} mid a_h end {align} $

La generalidad de lo anterior generalmente no se da en los textos del compilador, pero los textos de análisis como Grune y Jacobs cubren esto. El factoring izquierdo se puede aplicar a la gramática transformada anteriormente, pero solo introducirá reglas adicionales que no cambiarán la respuesta. Entonces lo haremos simplificar La presentación sin factorización adicional de izquierda se realiza.

En esta respuesta, no cubriremos problemas de recursión de izquierda indirecta porque solo nos preocupan las reglas de una sola no terminal. Sin embargo, tenga en cuenta que se puede tratar la recursión indirecta izquierda. (Abra una pregunta separada si eso es importante).

Factoring de izquierda

Eliminar el factoring de izquierda se encuentra en la mayoría de los textos de compilador introductorios realizados así. Dado

$ qquad displaystyle a to xy mid xz $

Rendimientos de Factoring de izquierda:

$ qquad displaystyle begin {align} a_s & to y mid z a & to x a_s end {align} $

Ahora eso es realizar las transformaciones en ambos pedidos.

Factoring de izquierda primero

Dejemos factorizar la gramática de la pregunta

$ qquad displaystyle begin {align} f_s & a ds mid varepsilon f & to fb a mid c f_s end {align} $

y luego retire la recursión a la izquierda:

$ qquad displaystyle begin {align} f_h & a c f_s f_t & to b a f_ {t^+} & a f_t f_ {t^+} | F_t f_s & a ds mid varepsilon f & a f_h f_ {t^+} mid f_h end {align} $

Eliminar primero la recursión izquierda

Y para el otro pedido, eliminemos la recursión de la izquierda de la gramática de la pregunta

$ qquad displayStyle begin {align} f_h & to c ds mid c f_t & to b a f_ {t^+} & a f_t f_ {t^+} mid f_t F & a f_h f_ {t^+} mid f_h end {align} $

y luego a la izquierda Factor el terminal $ C $:

$ qquad displaystyle begin {align} f_ {hs} & a ds mid varepsilon f_h & a c f_ {hs} f_t & a b a f_ {t^+} & a f_t f_ {t^+} mid f_t f & a f_h f_ {t^+} mid f_h end {align} $

¡Ajá, las gramáticas resultantes son las mismas!

En general, demostrar que dos gramáticas son equivalentes es indecidible. Entonces, si una serie de transformaciones de gramática podría influir en el lenguaje que se reconoce Entonces, sería desastroso.