Diseño del compilador: análisis de sintaxis

El análisis sintáctico o el análisis sintáctico es la segunda fase de un compilador. En este capítulo, aprenderemos los conceptos básicos utilizados en la construcción de un analizador sintáctico.

Hemos visto que un analizador léxico puede identificar tokens con la ayuda de expresiones regulares y reglas de patrones. Pero un analizador léxico no puede verificar la sintaxis de una oración dada debido a las limitaciones de las expresiones regulares. Las expresiones regulares no pueden verificar los tokens de equilibrio, como los paréntesis. Por lo tanto, esta fase usa gramática libre de contexto (CFG), que es reconocida por autómatas pushdown.

CFG, por otro lado, es un superconjunto de gramática regular, como se muestra a continuación:

Implica que cada gramática regular también está libre de contexto, pero existen algunos problemas que están más allá del alcance de la gramática regular. CFG es una herramienta útil para describir la sintaxis de los lenguajes de programación.

Gramática libre de contexto

En esta sección, primero veremos la definición de gramática libre de contexto e introduciremos terminologías utilizadas en la tecnología de análisis sintáctico.

Una gramática libre de contexto tiene cuatro componentes:

Un conjunto de non-terminals(V). Los no terminales son variables sintácticas que denotan conjuntos de cadenas. Los no terminales definen conjuntos de cadenas que ayudan a definir el lenguaje generado por la gramática.
Un conjunto de tokens, conocido como terminal symbols(Σ). Los terminales son los símbolos básicos a partir de los cuales se forman las cadenas.
Un conjunto de productions(PAGS). Las producciones de una gramática especifican la manera en que los terminales y los no terminales pueden combinarse para formar cadenas. Cada producción consta de unnon-terminal llamado el lado izquierdo de la producción, una flecha y una secuencia de fichas y / o on- terminals, llamado el lado derecho de la producción.
Uno de los no terminales se designa como el símbolo de inicio (S); desde donde comienza la producción.

Las cadenas se derivan del símbolo de inicio reemplazando repetidamente un no terminal (inicialmente el símbolo de inicio) por el lado derecho de una producción, para ese no terminal.

Ejemplo

Tomamos el problema del lenguaje palíndromo, que no se puede describir mediante la expresión regular. Es decir, L = {w | w = w ^R } no es un idioma común. Pero se puede describir mediante CFG, como se ilustra a continuación:

G = ( V, Σ, P, S )

Dónde:

V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S = { Q }

Esta gramática describe el lenguaje palíndromo, como: 1001, 11100111, 00100, 1010101, 11111, etc.

Analizadores de sintaxis

Un analizador o analizador sintáctico toma la entrada de un analizador léxico en forma de flujos de tokens. El analizador analiza el código fuente (flujo de token) contra las reglas de producción para detectar cualquier error en el código. La salida de esta fase es unparse tree.

De esta manera, el analizador realiza dos tareas, es decir, analizar el código, buscar errores y generar un árbol de análisis como salida de la fase.

Se espera que los analizadores analicen todo el código incluso si existen algunos errores en el programa. Los analizadores utilizan estrategias de recuperación de errores, que aprenderemos más adelante en este capítulo.

Derivación

Una derivación es básicamente una secuencia de reglas de producción para obtener la cadena de entrada. Durante el análisis, tomamos dos decisiones para alguna forma de entrada enunciada:

Decidir el no terminal que se va a reemplazar.
Decidir la regla de producción, por la cual, se reemplazará el no terminal.

Para decidir qué no terminal reemplazar con la regla de producción, podemos tener dos opciones.

Derivación más a la izquierda

Si la forma enunciada de una entrada se escanea y se reemplaza de izquierda a derecha, se denomina derivación más a la izquierda. La forma de oración derivada de la derivación más a la izquierda se llama forma de oración a la izquierda.

Derivación más a la derecha

Si escaneamos y reemplazamos la entrada con reglas de producción, de derecha a izquierda, se conoce como derivación más a la derecha. La forma de oración derivada de la derivación más a la derecha se llama forma de oración a la derecha.

Example

Reglas de producción:

E → E + E
E → E * E
E → id

Cadena de entrada: id + id * id

La derivación más a la izquierda es:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Observe que el no terminal del extremo izquierdo siempre se procesa primero.

La derivación más a la derecha es:

E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id

Parse árbol

Un árbol de análisis es una descripción gráfica de una derivación. Es conveniente ver cómo se derivan las cadenas del símbolo de inicio. El símbolo de inicio de la derivación se convierte en la raíz del árbol de análisis. Veamos esto con un ejemplo del último tema.

Tomamos la derivación más a la izquierda de a + b * c

La derivación más a la izquierda es:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Paso 1:

E → E * E

Paso 2:

E → E + E * E

Paso 3:

E → id + E * E

Paso 4:

E → id + id * E

Paso 5:

E → id + id * id

En un árbol de análisis:

Todos los nodos hoja son terminales.
Todos los nodos interiores son no terminales.
El recorrido en orden da una cadena de entrada original.

Un árbol de análisis muestra la asociatividad y la precedencia de los operadores. El subárbol más profundo se atraviesa primero, por lo tanto, el operador en ese subárbol tiene prioridad sobre el operador que está en los nodos principales.

Ambigüedad

Se dice que una gramática G es ambigua si tiene más de un árbol de análisis (derivación izquierda o derecha) para al menos una cadena.

Example

E → E + E
E → E – E
E → id

Para la cadena id + id - id, la gramática anterior genera dos árboles de análisis:

El lenguaje generado por una gramática ambigua se dice que es inherently ambiguous. La ambigüedad en la gramática no es buena para la construcción de un compilador. Ningún método puede detectar y eliminar la ambigüedad automáticamente, pero puede eliminarse reescribiendo toda la gramática sin ambigüedad o estableciendo y siguiendo las restricciones de asociatividad y precedencia.

Asociatividad

Si un operando tiene operadores en ambos lados, el lado en el que el operador toma este operando se decide por la asociatividad de esos operadores. Si la operación es asociativa a la izquierda, entonces el operador de la izquierda tomará el operando o si la operación es asociativa a la derecha, el operador de la derecha tomará el operando.

Example

Las operaciones como la suma, la multiplicación, la resta y la división son asociativas a la izquierda. Si la expresión contiene:

id op id op id

será evaluado como:

(id op id) op id

Por ejemplo, (id + id) + id

Operaciones como Exponenciación son asociativas a la derecha, es decir, el orden de evaluación en la misma expresión será:

id op (id op id)

Por ejemplo, id ^ (id ^ id)

Precedencia

Si dos operadores diferentes comparten un operando común, la precedencia de los operadores decide cuál tomará el operando. Es decir, 2 + 3 * 4 puede tener dos árboles de análisis sintáctico diferentes, uno correspondiente a (2 + 3) * 4 y otro correspondiente a 2+ (3 * 4). Al establecer la precedencia entre los operadores, este problema se puede eliminar fácilmente. Como en el ejemplo anterior, matemáticamente * (multiplicación) tiene prioridad sobre + (suma), por lo que la expresión 2 + 3 * 4 siempre se interpretará como:

2 + (3 * 4)

Estos métodos reducen las posibilidades de ambigüedad en un idioma o su gramática.

Recursión izquierda

Una gramática se vuelve recursiva a la izquierda si tiene una 'A' no terminal cuya derivación contenga la propia 'A' como el símbolo más a la izquierda. La gramática recursiva a la izquierda se considera una situación problemática para los analizadores de arriba hacia abajo. Los analizadores de arriba hacia abajo comienzan a analizar desde el símbolo de Inicio, que en sí mismo no es terminal. Entonces, cuando el analizador encuentra el mismo no terminal en su derivación, se vuelve difícil para él juzgar cuándo dejar de analizar el no terminal izquierdo y entra en un bucle infinito.

Example:

(1) A => Aα | β

(2) S => Aα | β 
    A => Sd

(1) es un ejemplo de recursividad inmediata a la izquierda, donde A es cualquier símbolo no terminal y α representa una cadena de no terminales.

(2) es un ejemplo de recursividad indirecta a la izquierda.

Un analizador de arriba hacia abajo analizará primero la A, que a su vez producirá una cadena que consta de A y el analizador puede entrar en un bucle para siempre.

Eliminación de la recursividad izquierda

Una forma de eliminar la recursividad por la izquierda es utilizar la siguiente técnica:

La producción

A => Aα | β

se convierte en las siguientes producciones

A => βA'
A'=> αA' | ε

Esto no afecta las cadenas derivadas de la gramática, pero elimina la recursividad izquierda inmediata.

El segundo método es utilizar el siguiente algoritmo, que debería eliminar todas las recursiones directas e indirectas por la izquierda.

START

Arrange non-terminals in some order like A1, A2, A3,…, A_n

   for each i from 1 to n
      {
      for each j from 1 to i-1
         {
         replace each production of form A_i ⟹Aj
         with A_i ⟹ δ1  | δ2 | δ3 |…|  
         where A_j ⟹ δ₁ | δ₂|…| δ_n  are current A_j productions
         }
      }
   eliminate immediate left-recursion
   
END

Example

El conjunto de producción

S => Aα | β 
A => Sd

después de aplicar el algoritmo anterior, debería convertirse

S => Aα | β 
A => Aαd | βd

y luego, elimine la recursividad izquierda inmediata utilizando la primera técnica.

A  => βdA'
A' => αdA' | ε

Ahora, ninguna parte de la producción tiene recursión por la izquierda directa o indirecta.

Factorización izquierda

Si más de una regla de producción gramatical tiene una cadena de prefijo común, entonces el analizador de arriba hacia abajo no puede elegir qué producción debería tomar para analizar la cadena en cuestión.

Example

Si un analizador de arriba hacia abajo encuentra una producción como

A ⟹ αβ | α | …

Entonces no puede determinar qué producción seguir para analizar la cadena, ya que ambas producciones comienzan desde el mismo terminal (o no terminal). Para eliminar esta confusión, utilizamos una técnica llamada factorización por la izquierda.

La factorización izquierda transforma la gramática para que sea útil para los analizadores de arriba hacia abajo. En esta técnica, hacemos una producción para cada prefijo común y el resto de la derivación se agrega mediante nuevas producciones.

Example

Las producciones anteriores se pueden escribir como

A => αA'
A'=> β |  | …

Ahora el analizador tiene solo una producción por prefijo, lo que facilita la toma de decisiones.

Conjuntos primero y siguiente

Una parte importante de la construcción de la tabla del analizador es crear conjuntos primero y siguiente. Estos conjuntos pueden proporcionar la posición real de cualquier terminal en la derivación. Esto se hace para crear la tabla de análisis sintáctico donde la decisión de reemplazar T [A, t] = α con alguna regla de producción.

Primer set

Este conjunto se crea para saber qué símbolo de terminal se deriva en la primera posición por un no terminal. Por ejemplo,

α → t β

Es decir, α deriva t (terminal) en la primera posición. Entonces, t ∈ PRIMERO (α).

Algoritmo para calcular el primer conjunto

Mira la definición del PRIMER conjunto (α):

si α es un terminal, entonces PRIMERO (α) = {α}.
si α es un no terminal y α → ℇ es una producción, entonces PRIMERO (α) = {ℇ}.
si α es no terminal y α → 1 2 3… ny cualquier FIRST () contiene t, entonces t está en FIRST (α).

El primer conjunto puede verse como:

Seguir conjunto

Asimismo, calculamos qué símbolo terminal sigue inmediatamente a un α no terminal en las reglas de producción. No consideramos lo que puede generar el no terminal, sino que vemos cuál sería el siguiente símbolo de terminal que sigue a las producciones de un no terminal.

Algoritmo para calcular el conjunto de seguimiento:

si α es un símbolo de inicio, entonces FOLLOW () = $
si α es no terminal y tiene una producción α → AB, entonces FIRST (B) está en FOLLOW (A) excepto ℇ.
si α no es terminal y tiene una producción α → AB, donde B ℇ, entonces FOLLOW (A) está en FOLLOW (α).

El conjunto de seguimiento puede verse como: FOLLOW (α) = {t | S * αt *}

Limitaciones de los analizadores de sintaxis

Los analizadores de sintaxis reciben sus entradas, en forma de tokens, de los analizadores léxicos. Los analizadores léxicos son responsables de la validez de un token proporcionado por el analizador de sintaxis. Los analizadores de sintaxis tienen los siguientes inconvenientes:

no puede determinar si un token es válido,
no puede determinar si un token se declara antes de que se utilice,
no puede determinar si un token se inicializa antes de que se utilice,
no puede determinar si una operación realizada en un tipo de token es válida o no.

Estas tareas las realiza el analizador semántico, que estudiaremos en Análisis semántico.

↰ Previous page Next page ↱