Gramática de expresiones de análisis sintáctico

En la literatura y en este artículo se observan sintaxis tanto abstractas como concretas para el análisis de expresiones. La sintaxis abstracta es esencialmente una fórmula matemática y se utiliza principalmente en contextos teóricos, mientras que la sintaxis concreta permite controlar directamente un analizador . La sintaxis concreta principal es la definida por Ford ^{[ 1 ] ( Fig. 1)} , aunque muchas herramientas tienen su propia variante. Otras herramientas ^{[ 3 ]} se asemejan más al uso de una codificación nativa del lenguaje de programación para la sintaxis abstracta como sintaxis concreta.

"terminal" No terminal 'otra terminal'

Identificador LEFTARROW Expresión

Se trata de un PEG que reconoce fórmulas matemáticas que aplican las cinco operaciones básicas a números enteros no negativos.

Expr ← Suma Suma ← Producto (( '+' / '-' ) Producto ) * Producto ← Potencia (( '*' / '/' ) Potencia ) * Potencia ← Valor ( '^' Potencia ) ? Valor ← [ 0-9 ] + / '(' Expr ')'

En el ejemplo anterior, los símbolos terminales son caracteres de texto, representados por caracteres entre comillas simples, como '('y ')'. El rango [0-9]es un atajo para los diez caracteres desde '0'hasta '9'. (Esta sintaxis de rango es la misma que la sintaxis utilizada por las expresiones regulares ). Los símbolos no terminales son los que se expanden a otras reglas: Valor , Potencia , Producto , Suma y Expr . Nótese que las reglas Suma y Producto no conducen a la asociatividad izquierda deseada de estas operaciones (no manejan la asociatividad en absoluto, y debe manejarse en el paso de posprocesamiento después del análisis), y la regla Potencia (al referirse a sí misma a la derecha) da como resultado la asociatividad derecha deseada del exponente. También tenga en cuenta que una regla como (con la intención de lograr la asociatividad izquierda) causaría una recursión infinita, por lo que no se puede usar en la práctica aunque se pueda expresar en la gramática.Sum←Sum(('+'/'-')Product)?

La diferencia fundamental entre las gramáticas libres de contexto y las gramáticas de expresiones de análisis sintáctico radica en que el operador de elección de las gramáticas de expresiones de análisis sintáctico es ordenado . Si la primera alternativa tiene éxito, la segunda se ignora. Por lo tanto, la elección ordenada no es conmutativa , a diferencia de la elección no ordenada presente en las gramáticas libres de contexto. La elección ordenada es análoga a los operadores de corte suave disponibles en algunos lenguajes de programación lógica .

La consecuencia es que, si una gramática libre de contexto (GLC) se translitera directamente a una gramática de pares de expresiones (PEG), cualquier ambigüedad en la primera se resuelve seleccionando de forma determinista un árbol de análisis sintáctico entre los posibles. Al elegir cuidadosamente el orden en que se especifican las alternativas gramaticales, el programador tiene un gran control sobre qué árbol de análisis sintáctico se selecciona.

Las gramáticas de expresiones de análisis sintáctico también añaden los predicados sintácticos " y" y "no" . Dado que pueden utilizar una subexpresión arbitrariamente compleja para "anticipar" la cadena de entrada sin consumirla realmente, proporcionan una potente función de anticipación sintáctica y desambiguación, en particular cuando la reordenación de las alternativas no permite especificar el árbol de análisis sintáctico exacto deseado.

Cada no terminal en una gramática de expresión de análisis representa esencialmente una función de análisis en un analizador descendente recursivo , y la expresión de análisis correspondiente representa el "código" que compone la función. Cada función de análisis conceptualmente toma una cadena de entrada como argumento y produce uno de los siguientes resultados:

• éxito , en el que la función puede opcionalmente avanzar o consumir uno o más caracteres de la cadena de entrada que se le proporciona, o
• fallo , en cuyo caso no se consume ninguna entrada.

Una expresión de análisis atómico que consta de un único terminal (es decir, un literal) se ejecuta correctamente si el primer carácter de la cadena de entrada coincide con dicho terminal; en ese caso, se consume el carácter de entrada. De lo contrario, la expresión produce un error. Una expresión de análisis atómico que consiste en una cadena vacía siempre se ejecuta correctamente sin consumir ninguna entrada.

Una expresión de análisis atómico que consiste en un no terminal A representa una llamada recursiva a la función no terminal A. Un no terminal puede tener éxito sin consumir realmente ninguna entrada, y esto se considera un resultado distinto del fallo.

El operador de secuencia e ₁ e ₂ primero invoca e ₁ y, si e ₁ tiene éxito, invoca posteriormente e ₂ sobre el resto de la cadena de entrada que no fue procesada por e ₁ y devuelve el resultado. Si e ₁ o e ₂ fallan, la expresión de secuencia e ₁ e ₂ falla (no consume ninguna entrada).

El operador de elección e ₁ / e ₂ primero invoca a e ₁ y, si e ₁ tiene éxito, devuelve su resultado inmediatamente. De lo contrario, si e ₁ falla, el operador de elección retrocede a la posición de entrada original donde invocó a e ₁ , pero luego llama a e ₂ y devuelve el resultado de e ₂ .

Los operadores zero-or-more , one-or-more y optional consumen cero o más, una o más, o cero o una repeticiones consecutivas de su subexpresión e , respectivamente. Sin embargo, a diferencia de las gramáticas libres de contexto y las expresiones regulares , estos operadores siempre se comportan de manera voraz , consumiendo la mayor cantidad de entrada posible y sin retroceder nunca. (Los comparadores de expresiones regulares pueden comenzar comparando de manera voraz, pero luego retrocederán e intentarán comparaciones más cortas si no coinciden). Por ejemplo, la expresión a* siempre consumirá tantas 'a' como estén disponibles consecutivamente en la cadena de entrada, y la expresión (a* a) siempre fallará porque la primera parte (a*) nunca dejará ninguna 'a' para que la segunda parte la compare.

La expresión de predicado y & e invoca la subexpresión e , y luego tiene éxito si e tiene éxito y falla si e falla, pero en ningún caso consume ninguna entrada .

La expresión de no predicado  ! e tiene éxito si e falla y falla si e tiene éxito, sin consumir de nuevo ninguna entrada en ninguno de los casos.

La siguiente regla recursiva coincide con las sentencias if/then/else estándar de estilo C, de tal manera que la cláusula "else" opcional siempre se vincula al "if" más interno, debido a la priorización implícita del operador "/". (En una gramática libre de contexto , esta construcción produce la clásica ambigüedad del "else" colgante ).

S ← 'si' C 'entonces' S 'si no' S / 'si' C 'entonces' S

La siguiente regla recursiva coincide con la sintaxis de comentarios anidados al estilo Pascal, (* which can (* nest *) like this *). Recuerde que .coincide con cualquier carácter individual.

C ← Inicio N * Fin Inicio ← '(*' Fin ← '*)' N ← C / ( ! Inicio ! Fin . )

La expresión de análisis coincide con el texto "foo" y lo consume, pero solo si va seguido del texto "bar". La expresión de análisis coincide con el texto "foo", pero solo si no va seguido del texto "bar". La expresión coincide con una sola "a", pero solo si no forma parte de una secuencia arbitrariamente larga de "a" seguida de una "b".foo&(bar)foo!(bar)!(a+b)a

La expresión de análisis coincide y consume una secuencia de longitud arbitraria de('a'/'b')*${\displaystyle a}$'arena${\displaystyle b}$La regla de producción coincide con el lenguaje libre de contexto simple .S←('a'S'b')?${\displaystyle \{a^{n}b^{n}:n\geq 0\}}$.

La siguiente gramática de expresiones de análisis describe el lenguaje clásico no libre de contexto.${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 0\}}$: ^{[ 5 ]}

S ← & ( A ! ( 'a' / 'b' )) 'a' * B ! . A ← ( 'a' A 'b' ) ? B ← ( 'b' B 'c' ) ?

Un analizador sintáctico Pika ^{[ 8 ]} utiliza programación dinámica para aplicar las reglas PEG de abajo hacia arriba y de derecha a izquierda, lo cual es lo contrario del orden de descenso recursivo normal de arriba hacia abajo y de izquierda a derecha. El análisis sintáctico en orden inverso resuelve el problema de la recursión izquierda, lo que permite que las reglas recursivas izquierdas se utilicen directamente en la gramática sin tener que reescribirlas en una forma no recursiva izquierda, y también confiere al analizador capacidades óptimas de recuperación de errores, algo que históricamente ha resultado difícil de lograr para los analizadores sintácticos de descenso recursivo.

Muchos algoritmos de análisis sintáctico requieren un paso de preprocesamiento en el que la gramática se compila primero en un formato ejecutable opaco, a menudo mediante algún tipo de autómata. Las expresiones de análisis sintáctico se pueden ejecutar directamente (aunque normalmente sigue siendo recomendable transformar las expresiones de gramática sintáctica legibles por humanos que se muestran en este artículo a un formato más nativo, como las expresiones S , antes de evaluarlas).

En comparación con las expresiones regulares puras (es decir, describir un lenguaje reconocible mediante un autómata finito ), los PEG son muchísimo más potentes. En particular, pueden manejar recursión ilimitada y, por lo tanto, hacer coincidir paréntesis hasta una profundidad de anidamiento arbitraria; las expresiones regulares, en el mejor de los casos, pueden realizar un seguimiento del anidamiento hasta una profundidad fija, porque un autómata finito (que tiene un conjunto finito de estados internos) solo puede distinguir un número finito de profundidades de anidamiento diferentes. En términos más teóricos,${\displaystyle \{a^{n}b^{n}\}_{n\geqslant 0}}$(el lenguaje de todas las cadenas de cero o más${\displaystyle a}$'s, seguido de un número igual de${\displaystyle b}$s) no es un lenguaje regular , pero se ve fácilmente que es un lenguaje de expresiones de análisis sintáctico, que coincide con la gramática.

inicio ← AB ! . AB ← ( 'a' AB 'b' ) ?

Aquí está la expresión inicial. La parte garantiza que la entrada termine después de , al decir "no hay siguiente carácter"; a diferencia de las expresiones regulares, que tienen restricciones mágicas o para esto, las expresiones de análisis pueden expresar el final de la entrada usando solo las primitivas básicas.AB !.!.AB$\Z

Las expresiones de análisis sintáctico son similares a las de las expresiones regulares, pero la diferencia radica en que operan estrictamente en modo voraz. Esto se debe, en última instancia, a que *se trata de una elección ordenada. Como consecuencia, algo puede coincidir como expresión regular pero no como expresión de análisis sintáctico:+?/

[ab]?[bc][cd]

es una expresión regular válida y una expresión de análisis válida. Como expresión regular, coincide con bc, pero como expresión de análisis no coincide, porque [ab]?coincidirá con b, luego [bc]coincidirá con c, sin dejar nada para [cd], por lo que en ese punto la coincidencia de la secuencia falla. "Intentarlo de nuevo" haciendo que [ab]?coincida con la cadena vacía va explícitamente en contra de la semántica de las expresiones de análisis; este no es un caso límite de un algoritmo de coincidencia particular, sino que es el comportamiento buscado.

Incluso las expresiones regulares que dependen del no determinismo pueden compilarse en una gramática de expresiones de análisis sintáctico, al tener un no terminal separado para cada estado del autómata finito no determinista correspondiente (NFA, por sus siglas en inglés) y codificar su función de transición en las definiciones de estos no terminales.

A ← 'x' B / 'x' C / 'y' D

En esencia, significa "transición del estado A al estado B o C si el siguiente carácter es x, o al estado D si el siguiente carácter es y". No utilizaría las variantes de expresión de análisis sintáctico de las operaciones de repetición.

Para aceptar estados del NFA, la definición del no terminal debe estar entre ?. En cuanto a los estados de entrada del NFA, todos deben estar listados, separados por /, en la definición del no terminal inicial.

Cabe señalar que, si bien es posible transformar una expresión regular en un autómata finito determinista (AFD) en lugar de un autómata finito no determinista (AFND), esto debe evitarse , ya que el equivalente en AFD de una expresión regular puede ser exponencialmente mayor. De hecho, existe una secuencia de expresiones regulares cuyos equivalentes en AFD son todos exponencialmente mayores.

Las PEG se pueden dar cómodamente en términos de caracteres, mientras que las gramáticas libres de contexto (GLC) generalmente se dan en términos de tokens, lo que requiere un paso adicional de tokenización antes del análisis propiamente dicho. ^{[ 9 ]} Una ventaja de no tener un tokenizador separado es que diferentes partes del lenguaje (por ejemplo, minilenguajes incrustados ) pueden tener fácilmente diferentes reglas de tokenización.

En el sentido formal estricto, las PEG son probablemente incomparables con las CFG, pero en la práctica hay muchas cosas que las PEG pueden hacer que las CFG puras no pueden, mientras que es difícil encontrar ejemplos de lo contrario. En particular, las PEG se pueden diseñar para resolver ambigüedades de forma nativa, como el problema del " else colgante " en C, C++ y Java, mientras que el análisis sintáctico basado en CFG a menudo necesita una regla externa a la gramática para resolverlas. Además, cualquier PEG se puede analizar en tiempo lineal usando un analizador packrat, como se describió anteriormente, mientras que el análisis sintáctico según una CFG general es asintóticamente equivalente ^{[ 10 ]} a la multiplicación de matrices booleanas (por lo tanto, probablemente entre tiempo cuadrático y cúbico).

Un ejemplo clásico de un lenguaje formal que se demuestra que no está libre de contexto es el lenguaje${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 0\}}$: un número arbitrario de${\displaystyle a}$Los 's van seguidos de un número igual de${\displaystyle b}$'s, que a su vez van seguidas de un número igual de${\displaystyle c}$'s. Esto también es un lenguaje de expresiones de análisis sintáctico, que coincide con la gramática: ^{[ 5 ]}

S ← & ( A ! ( 'a' / 'b' )) 'a' * B ! . A ← ( 'a' A 'b' ) ? B ← ( 'b' B 'c' ) ?

Para Aque coincida, el primer tramo de${\displaystyle a}$'s debe ir seguido exactamente del mismo número de${\displaystyle b}$'s y nada más, y además Btiene que coincidir donde el${\displaystyle a}$cambio de${\displaystyle b}$de, lo que significa esos${\displaystyle b}$Los 's van seguidos de un número igual de${\displaystyle c}$'s.

El análisis PEG se realiza típicamente mediante el análisis packrat , que utiliza memorización ^{[ 11 ] [ 12 ]} para eliminar pasos de análisis redundantes. El análisis packrat requiere almacenamiento interno proporcional al tamaño total de la entrada, en lugar de a la profundidad del árbol de análisis como con los analizadores LR. Si esta es una diferencia significativa depende de las circunstancias; si el análisis es un servicio proporcionado como una función , entonces el analizador habrá almacenado el árbol de análisis completo hasta que lo devuelva, y ese árbol de análisis ya será típicamente de un tamaño proporcional al tamaño total de la entrada. Si el análisis se proporciona como un generador , entonces se podría permitir mantener solo partes del árbol de análisis en memoria, pero la viabilidad de esto depende de la gramática. Una gramática de expresión de análisis puede diseñarse de manera que solo después de consumir la entrada completa el analizador descubra que necesita retroceder al principio, ^{[ 13 ]} lo que nuevamente podría requerir almacenamiento proporcional al tamaño total de la entrada.

Para gramáticas recursivas y algunas entradas, la profundidad del árbol de análisis puede ser proporcional al tamaño de la entrada, ^{[ 14 ]} por lo que tanto un analizador LR como un analizador packrat parecerán tener el mismo rendimiento asintótico en el peor de los casos. Sin embargo, en muchos dominios, por ejemplo, el código fuente escrito a mano , la profundidad de anidamiento de expresiones tiene un límite prácticamente constante, bastante independiente de la longitud del programa, porque las expresiones anidadas más allá de cierta profundidad tienden a ser refactorizadas . Cuando no es necesario mantener el árbol de análisis completo, un análisis más preciso tendría en cuenta la profundidad del árbol de análisis por separado del tamaño de la entrada. ^{[ 15 ]}

Para lograr una complejidad global lineal, el almacenamiento utilizado para la memorización debe proporcionar, además, acceso amortizado en tiempo constante a los elementos de datos memorizados. En la práctica, esto no supone ningún problema (por ejemplo, una tabla hash de tamaño dinámico lo consigue), pero esto utiliza aritmética de punteros , por lo que presupone una máquina de acceso aleatorio . Las discusiones teóricas sobre estructuras de datos y algoritmos tienden implícitamente a presuponer un modelo más restringido (posiblemente el del cálculo lambda , o quizás el de Scheme ), donde una tabla dispersa debe construirse utilizando árboles, y el acceso a los elementos de datos no es en tiempo constante. Los algoritmos de análisis sintáctico tradicionales, como el analizador LL, no se ven afectados por esto, pero se convierte en un inconveniente para la reputación de los analizadores que almacenan datos en exceso: se basan en operaciones aparentemente de mala reputación.

Visto desde otra perspectiva, esto significa que los analizadores sintácticos Packrat aprovechan la potencia computacional fácilmente disponible en los sistemas de la vida real, que los algoritmos de análisis sintáctico más antiguos no saben cómo utilizar.

Una PEG se considera bien formada ^{[ 1 ]} si no contiene reglas recursivas por la izquierda , es decir, reglas que permiten que un no terminal se expanda a una expresión en la que el mismo no terminal aparece como el símbolo más a la izquierda. Para un analizador sintáctico descendente de izquierda a derecha, tales reglas provocan una regresión infinita: el análisis expandirá continuamente el mismo no terminal sin avanzar en la cadena. Por lo tanto, para permitir el análisis packrat, debe eliminarse la recursión por la izquierda.

Suma → Término | Suma '+' Término | Suma '-' Término Argumentos → Arg | Arg ',' Argumentos

Suma ← Término ( '+' Término / '-' Término ) * Argumentos ← Argumento ( ',' Argumento ) *

Valor ← [ 0-9. ] + / '(' Expr ')' Producto ← Expr (( '*' / '/' ) Expr ) + Suma ← Expr (( '+' / '-' ) Expr ) + Expr ← Suma / Producto / Valor

cadena-de-a ← cadena-de-a 'a' | 'a'

cadena-de-a ← 'a' +

Los analizadores PEG packrat no pueden reconocer algunas reglas CFG no deterministas inequívocas, como las siguientes: ^{[ 2 ]}

S ← 'x' S 'x' | 'x'

Ni los algoritmos de análisis sintáctico LL(k) ni LR(k) son capaces de reconocer este ejemplo. Sin embargo, esta gramática puede ser utilizada por un analizador sintáctico CFG general como el algoritmo CYK . No obstante, el lenguaje en cuestión puede ser reconocido por todos estos tipos de analizadores, ya que, de hecho, es un lenguaje regular (el de cadenas de un número impar de x).

Resulta instructivo averiguar exactamente qué hace un analizador PEG cuando intenta hacer coincidir

S ← 'x' S 'x' / 'x'

contra la cadena xxxxxq. Como era de esperar, intenta recursivamente hacer coincidir el no terminal Sen posiciones crecientes en esta cadena, hasta que falla la coincidencia contra q, y después de eso comienza a retroceder. Esto sucede de la siguiente manera:

Puesto: 123456 Cadena: xxxxxq Resultados: ↑ Pos.6: Ninguna rama de S coincide ↑ Pos.5: La primera rama de S falla, la segunda rama tiene éxito, lo que produce una coincidencia de longitud 1. ↑ Pos.4: La primera rama de S falla, la segunda rama tiene éxito, lo que produce una coincidencia de longitud 1. ↑ Pos.3: La primera rama de S tiene éxito, produciendo una coincidencia de longitud 3. ↑ Pos.2: La primera rama de S falla, porque después de la coincidencia de S en 3 viene una q. La segunda rama tiene éxito, produciendo una coincidencia de longitud 1. ↑ Pos.1: La primera rama de S tiene éxito, produciendo una coincidencia de longitud 3.

La comparación con una expresión de análisis sintáctico es voraz , en el sentido de que solo se considera el primer éxito encontrado. Aunque localmente las opciones se ordenen de la más larga a la más larga, no hay garantía de que esta comparación voraz encuentre la coincidencia global más larga.

Los generadores de analizadores LL(k) y LR(k) no se completarán cuando la gramática de entrada sea ambigua. Esta es una característica común en el caso de que la gramática pretenda ser inequívoca, pero presente defectos. Un generador de analizadores PEG resolverá las ambigüedades no intencionadas priorizando la coincidencia más temprana, lo que puede ser arbitrario y dar lugar a análisis inesperados.

El orden de las producciones en una gramática PEG afecta no solo la resolución de la ambigüedad, sino también el idioma que coincide . Por ejemplo, considérese el primer ejemplo PEG en el artículo de Ford ^{[ 1 ]} (ejemplo reescrito en la notación de pegjs.org/online y etiquetado como${\displaystyle G_{1}}$y​​${\displaystyle G_{2}}$⁠ ):

• ⁠${\displaystyle G_{1}}$:​  A = "a" "b" / "a"
• ⁠${\displaystyle G_{2}}$:​  A = "a" / "a" "b"

Ford señala que la segunda alternativa en la última regla PEG nunca tendrá éxito porque la primera opción siempre se toma si la cadena de entrada... comienza con 'a'. . ^{[ 1 ]} Específicamente ,${\displaystyle L(G_{1})}$⁠ (es decir, el idioma que coincide con ⁠${\displaystyle G_{1}}$) incluye la entrada "ab", pero${\displaystyle L(G_{2})}$No lo hace. Por lo tanto, agregar una nueva opción a una gramática PEG puede eliminar cadenas del idioma coincidente, por ejemplo :${\displaystyle G_{2}}$⁠ es la adición de una regla a la gramática de producción única, que contiene una cadena que no coincide con ⁠ A = "a" "b"${\displaystyle G_{2}}$⁠ . Además, construir una gramática que coincida ⁠${\displaystyle L(G_{1})\cup L(G_{2})}$de las gramáticas PEG${\displaystyle G_{1}}$y​​${\displaystyle G_{2}}$⁠ no siempre es una tarea trivial. Esto contrasta marcadamente con las gramáticas libres de contexto (GLC), en las que la adición de una nueva producción no puede eliminar cadenas (aunque puede introducir problemas en forma de ambigüedad), y una gramática (potencialmente ambigua) para ⁠${\displaystyle L(G_{1})\cup L(G_{2})}$Se puede construir

S → inicio ( G1 ) | inicio ( G2 )

En marcado contraste con el caso de las gramáticas libres de contexto, no es posible generar elementos de un lenguaje de expresiones de análisis sintáctico a partir de su gramática. Además, es algorítmicamente indecidible si el lenguaje reconocido por una gramática de expresiones de análisis sintáctico es vacío. Una razón para ello es que cualquier instancia del problema de correspondencia de Post se reduce a una instancia del problema de decidir si un lenguaje de expresiones de análisis sintáctico es vacío.

Recordemos que una instancia del problema de correspondencia de Post consiste en una lista${\displaystyle (\alpha _{1},\beta _{1}),(\alpha _{2},\beta _{2}),\dotsc ,(\alpha _{n},\beta _{n})}$de pares de cadenas (de símbolos terminales). El problema consiste en determinar si existe una secuencia${\displaystyle \{k_{i}\}_{i=1}^{m}}$de índices en el rango${\displaystyle \{1,\dotsc ,n\}}$de tal manera que${\displaystyle \alpha _{k_{1}}\alpha _{k_{2}}\dotsb \alpha _{k_{m}}=\beta _{k_{1}}\beta _{k_{2}}\dotsb \beta _{k_{m}}}$Para reducir esto a una gramática de expresión de análisis sintáctico, dejemos${\displaystyle \gamma _{0},\gamma _{1},\dotsc ,\gamma _{n}}$ser arbitrarias distintas por pares cadenas igualmente largas de símbolos terminales (ya con${\displaystyle 2}$símbolos distintos en el alfabeto de símbolos terminales, longitud${\displaystyle \lceil \log _ {2}(n+1)\rceil}$es suficiente) y considere la gramática de expresión de análisis sintáctico $${\displaystyle {\begin{aligned}S&\leftarrow \&(A\,!.)\&(B\,!.)(\gamma _{1}/\dotsb /\gamma _{n})^{+}\gamma _{0}\\A&\leftarrow \gamma _{0}/\gamma _{1}A\alpha _{1}/\dotsb /\gamma _{n}A\alpha _{n}\\B&\leftarrow \gamma _{0}/\gamma _{1}B\beta _{1}/\dotsb /\gamma _{n}B\beta _{n}\end{aligned}}}$$ Cualquier cadena que coincida con el no terminal${\displaystyle A}$tiene la forma${\displaystyle \gamma _ {k_ {m}} \ dotsb \ gamma _ {k_ {2}} \ gamma _ _ {k_ {1}} \ gamma _ {0} \ alpha _ {k_ {1}} \ alpha _ {k_ {2}} \ dotsb \ alpha _ {k_ {m}}}$para algunos índices${\displaystyle k_{1},k_{2},\dotsc ,k_{m}}$. Asimismo, cualquier cadena que coincida con el no terminal${\displaystyle B}$tiene la forma${\displaystyle \gamma _ {k_ {m}} \ dotsb \ gamma _ {k_ {2}} \ gamma _ _ {k_ {1}} \ gamma _ {0} \ beta _ {k_ {1}} \ beta _ {k_ {2}} \ dotsb \ beta _ {k_ {m}}}$Por lo tanto, cualquier cadena que coincida con${\displaystyle S}$tendrá la forma${\displaystyle \gamma _ {k_ {m}} \ dotsb \ gamma _ {k_ {2}} \ gamma _ {k_ {1}} \ gamma _ {0} \ rho}$dónde${\displaystyle \rho =\alpha _ {k_ {1}}\alpha _ {k_ {2}} \dotsb \alpha _ {k_ {m}}=\beta _ {k_ {1}} \ beta _ {k_ {2}} \ dotsb \beta _ {k_ {m}}}$.