Primeros pasos con el análisis

Un analizador simple

La forma más sencilla de escribir un analizador es utilizar la técnica de descenso recursivo. Esto crea un analizador de arriba hacia abajo (que puede describirse formalmente como LL(1)). Para empezar con el ejemplo primero tenemos que establecer las reglas gramaticales de nuestro idioma. En este ejemplo, usaremos asignaciones de expresiones aritméticas simples para expresiones que solo pueden usar el operador más:

 Assignment --> Identifier := Expression
 Expression --> Expression + Term | Term
 Term --> Identifier | (Expression)
 Identifier --> x | y | z 

Para cada regla de la gramática podemos escribir un procedimiento para reconocer los tokens entrantes a la regla. Para los propósitos de este ejemplo, podemos asumir una rutina llamada NextToken que invoca un analizador léxico para proporcionar el token, y una rutina llamada error que se usa para generar un mensaje de error. El lenguaje utilizado está basado en Pascal.

 var token:char;  (* Updated by NextToken *) 

 procedure identifier;
 begin
    if token in ['x','y','z']
    then
        NextToken
    else
        error('Identifier expected')
 end; 

Puede ver que este código implementa la regla para reconocer un ‘Identificador’. Entonces podemos implementar la regla para un ‘Término’ de manera similar:

 procedure expression forward; 

 procedure term;
 begin
     if token = '('
     then
         begin
         nextToken;
         expression;
         if token <> ')'
         then
             error(') expected')
         else NextToken
         end
     else
         identifier
 end; 

Cuando llegamos a implementar la regla para Expresión tenemos un problema; el primer elemento de la regla ‘Expresión’ es en sí mismo una ‘Expresión’. Esto nos llevaría a escribir lo siguiente:

procedure expression;
begin
expression;
...
end;

Esto es directamente autorrecursivo y, por lo tanto, se repetiría para siempre. La gramática analizada por algoritmos de arriba hacia abajo no puede ser recursiva por la izquierda por este motivo. Una forma fácil de solucionar este problema es reformular la recursividad como iteración de la siguiente manera:

Expression --> Term { + Term}* 

Ahora podemos codificar la regla gramatical como:

 procedure expression;
 begin
     term;
     while token = '+'
         do
         begin
             NextTerm;
             term
         end
 end; 

Ahora podemos completar el analizador con la regla restante para la asignación:

procedure assignment;
begin 
    identifier;
    if token <> '='
    then
        error('= expected')
    else
        begin
        NextToken;
        expression;
        end
 end; 

Lo que necesitas para analizar

Al realizar el análisis, antes de comenzar, se debe especificar la [gramática] (https://en.wikipedia.org/wiki/Grammar) para el idioma. También se necesita una fuente de tokens para el analizador.

El analizador podría ser un código escrito a mano, o se podría usar una herramienta generadora de analizador. Si se utiliza una herramienta generadora de analizadores, será necesario descargar e instalar esa herramienta si aún no se ha incluido en su plataforma.

Definiciones de gramática

Normalmente, una gramática para un analizador debería escribirse en [forma libre de contexto] (https://en.wikipedia.org/wiki/Context-free_grammar). Una notación como BNF(Backus-Naur Form) o [EBNF(Extended Back-Naur Form)](https:// en .wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form) se usa a menudo para esto. Otras notaciones comúnmente utilizadas para describir los lenguajes de programación pueden ser [diagramas ferroviarios] (https://en.wikipedia.org/wiki/Syntax_diagram).

Análisis léxico

Los tokens normalmente se proporcionan para el analizador mediante un [analizador léxico (o escáner)] (https://en.wikipedia.org/wiki/Lexical_analysis). Se pueden encontrar más detalles en la documentación de un analizador léxico (TBC).

Técnicas de análisis

Para codificar manualmente un analizador, sería necesario elegir un [algoritmo apropiado] (https://en.wikipedia.org/wiki/Parsing) que se adapte tanto al lenguaje analizado como a los medios de implementación. Los algoritmos de análisis se clasifican en dos tipos de [análisis de arriba hacia abajo] (https://en.wikipedia.org/wiki/Top-down_parsing) y [análisis de abajo hacia arriba] (https://en.wikipedia.org/ wiki/análisis de abajo hacia arriba). Un analizador de arriba hacia abajo (recursivo) es más fácil de aprender para un principiante cuando comienza a escribir analizadores.

Herramientas generadoras de analizador

La forma más común de crear un analizador es utilizar una herramienta generadora de analizadores. Hay muchas herramientas de este tipo, pero algunas de las más utilizadas son:

Ejemplo de análisis de una oración en inglés

Por ejemplo, en la oración:

Ese pastel es extremadamente agradable.

Las reglas del idioma inglés harían de cake un sustantivo, extremadamente un adverbio que modifica el adjetivo bonito, y a través de este análisis se podría entender el significado.

Sin embargo, este análisis depende de que reconozcamos que la secuencia de símbolos utilizados son palabras. Si los caracteres utilizados no nos resultaran familiares, no podríamos hacer esto. Si encontramos una oración usando una notación desconocida, como el chino, analizarla de esta manera puede ser difícil. Aquí hay un ejemplo de oración en chino:

Puedo escribir un poco de chino.

Para cualquiera que no lea los caracteres chinos, no estaría claro qué símbolos se combinaron para formar palabras. Lo mismo podría ser cierto para un algoritmo informático al procesar inglés o chino.

Por lo tanto, el análisis debe realizarse mediante un proceso conocido como análisis léxico o escaneo, donde los caracteres individuales se agrupan en símbolos reconocidos, que comúnmente podríamos llamar palabras, pero que en los algoritmos de análisis se denominan tokens.