3.6 Análisis Sintáctico por Precedencia de Operadores

Estas gramáticas tienen la propiedad (entre otros requisitos fundamentales) de que ningún lado derecho de la producción es Є ni tiene dos no terminales adyacentes. Una gramática con esta última propiedad se denomina gramática de operadores.

Ejemplo. La siguiente gramática para expresiones

E -> EAE | (E) | - E |id

A -> +| - |*| / | \

no es una gramática de operadores, porque el lado derecho EAE tiene dos (de hecho tres) no terminales consecutivos. Sin embargo, si se sustituye cada una de sus alternativas por A, se obtiene la siguiente gramática de operadores:

E->E+E | E-E | E*E | E/E | E\E | (E) |-E | id

A continuación se describe una técnica de análisis sintáctico fácil de implantar llamada análisis sintáctico por precedencia de operadores. Históricamente, la técnica se describió primero como una manipulación de componentes léxicos sin hacer referencia a ninguna gramática subyacente. De hecho, cuando se termina de construir un analizador sintáctico por precedencia de operadores a partir de una gramática, se puede efectivamente prescindir de la gramática, utilizando los no terminales de la pila tan sólo como indicadores de los atributos asociados a los no terminales.

Como técnica general de análisis sintáctico, el análisis por precedencia de operadores tiene varios inconvenientes. Por ejemplo, es difícil manejar componentes léxicos como el signo menos, que tiene dos precedencias distintas (dependiendo de si es unario o binario). Peor aún, como la relación entre una gramática para el lenguaje que está siendo analizado y el mismo analizador sintáctico por precedencia de operadores es muy frágil, no siempre se puede tener la seguridad de que el analizador acepta exactamente el lenguaje deseado. Por último, sólo una pequeña clase de gramática puede analizarse usando las técnicas de precedencia de operadores.

Sin embargo, dada su sencillez, se han construido con éxito muchos compiladores que utilizan las técnicas de análisis sintáctico por precedencia de operadores para expresiones.

Con frecuencia, estos analizadores utilizan el descenso recursivo, para proposiciones y construcciones de alto nivel. Incluso se han construido analizadores sintácticos por precedencia de operadores para lenguajes completos.

En el análisis sintáctico por precedencia de operadores, se definen tres relaciones de precedencia disjuntas, <^*, ^. , y,^*> , entre algunos pares de terminales. Estas relaciones de precedencia guían la selección de mangos y tienen los siguientes significados:

Se debe prevenir  que aunque estas relaciones pueden parecer similares a las relaciones aritméticas "menor que", "igual a" y "mayor que", las relaciones de precedencia tienen propiedades muy diferentes. Por ejemplo, se podría tener a <^*b y a ^*> b para el mismo lenguaje, o podría no cumplirse ninguna de     a<^*b,  a^. b  y a^*>b para algunos terminales a y b.

Hay dos maneras habituales de determinar qué relaciones de precedencia deben cumplirse entre un par de terminales. El primer método que se estudia es intuitivo y se basa en las nociones tradicionales de asociatividad y precedencia dé operadores. Por ejemplo, si * tiene mayor precedencia que +, se hace + <^* * y  *^*> +. El segundo método para seleccionar las relaciones de precedencia de operadores consiste en construir primero una gramática no ambigua para el lenguaje, una gramática que refleje la asociatividad y precedencia correctas en sus árboles de análisis sintáctico.

Uso de las relaciones de precedencia de operadores

La intención de las relaciones de precedencia es delimitar el mango de una forma de frase derecha, con <^*  marcando el extremo izquierdo, ^. apareciendo en el interior del mango y ^*> marcando el extremo derecho. Para mayor precisión, supóngase que se tiene una forma de frase derecha de una gramática de operadores. El hecho de que no aparezcan no terminales adyacentes en los lados derechos de las producciones supone que tampoco ninguna forma de frase derecha tendrá dos no terminales adyacentes. Por tanto, se puede escribir la forma de frase derecha como β0a1β1… anβn en donde cada βi es o Є (la cadena vacía) o un solo no terminal, y cada ai es un solo terminal.

Supóngase que entre ai y ai+1 se cumple exactamente una de las relaciones <^*, ^.  , o ^*> . Además, úsese $ para marcar cada extremo de la cadena y defínanse $ <· b y b ·> $ para todos los terminales b. Ahora supóngase que se eliminan los no terminales de la cadena y se coloca la relación correcta <·, ^.  o ·>, entre cada par de terminales y entre los terminales de los extremos y los símbolos $ que marcan los finales de la cadena.

Por ejemplo, supóngase que inicialmente se tiene la forma de frase derecha id + id • id y que las relaciones de precedencia son las de la figura:

Entonces, la cadena con las relaciones de precedencia insertadas es:

$<·id·> +<·id·>* <·id·>$                           (1)

Por ejemplo, se inserta <· entre el $ de la izquierda e id puesto que <· es la entrada en la fila $ y la columna id. Se puede encontrar el mango mediante el siguiente proceso:

1. Examínese la cadena desde el extremo izquierdo hasta encontrar el primer ·> . En (1), esto ocurre entre el primer id y +.
2. Después, examínese hacia atrás (a la izquierda) saltando sobre los  ^. hasta encontrar un <·. En (1) se examina hacia atrás hasta el símbolo $.
3.  El mango contiene todo lo que esté a la izquierda del primer ·> y a la derecha del <· encontrado en el paso 2, incluidos los no terminales intermedios o que rodeen a <· y ·>. (Es necesaria la inclusión de los no terminales que rodean para que no aparezcan dos no terminales adyacentes en una forma de frase derecha.) En (1), el mango es el primer id.

Obtención de relaciones de precedencia de operadores a partir de la asociatividad y la precedencia

Siempre se pueden crear relaciones de precedencia de operadores de la forma que se considere adecuada y esperar que el algoritmo de análisis sintáctico por precedencia de operadores funcione correctamente al guiarse por ellas. Para un lenguaje de expresiones aritméticas, como el generado por la gramática

E->E+E | E-E | E*E | E/E | E\E | (E) |-E | id

se pueden usar las siguientes técnicas heurísticas para producir un conjunto adecuado de relaciones de precedencia. Obsérvese que la gramática  es ambigua. y las formas de frase derechas podrían tener muchos mangos. Se establecen las siguientes reglas para seleccionar mangos "apropiados" para reflejar un determinado conjunto de reglas de asociatividad y precedencia para operadores binarios .

1. Si el operador Ѳ, tiene mayor precedencia que el operador Ѳ2 , hágase Ѳ1 ·> Ѳ2 y Ѳ2<· Ѳ1. Por ejemplo, si * tiene mayor precedencia que + hágase * ·> + y  + <· *. Estas relaciones garantizan que, en una expresión de la forma E+ E* E+ E. el central E9E será el mango que se reducirá primero.
2. Si Ѳ1 y Ѳ2 son operadores de igual precedencia (de hecho, pueden ser el mismo operador), entonces hágase Ѳ1 ·>Ѳ2   y Ѳ2 ·> Ѳ1 si los operadores son asociativos por la izquierda, o hágase Ѳ1 <· Ѳ2 y Ѳ2 <·Ѳ1, si son asociativos por la derecha. Por ejemplo, si + y - son asociativos por la izquierda, entonces hágase + ·> +,  + ·>  - , -·>  -  y - ·> +. Si t es asociativo por la derecha, entonces hágase t <· t. Estas relaciones garantizan que para E- E+ E se seleccionará E-E como mango y que para Et Et E se seleccionará la última E t E.
3. Hágase Ѳ <· id, id ·> Ѳ, Ѳ < · (, ( <· Ѳ, ) ·>   Ѳ, Ѳ ·> ), Ѳ ·> $. y $<·Ѳ para todos los operadores Ѳ. Hágase también:

Estas reglas garantizan que tanto id como (.E) se reducirán a E. Asimismo, $ sirve como marcador de los extremos izquierdo y derecho, lo cual hace que los mangos se encuentren entre los dos símbolos $ siempre que sea posible.