Análisis | Conjunto 1 (Introducción, Ambigüedad y Analizadores) – Part 1

En este artículo, estudiaremos varios tipos de análisis. Es uno de los temas más importantes en Compiler desde el punto de vista de GATE. El funcionamiento de varios analizadores se explicará desde el punto de vista de resolución de preguntas GATE.
Requisito previo : conocimiento básico de gramáticas, árboles de análisis, ambigüedad.

Rol del analizador:

En la fase de análisis de sintaxis, un compilador verifica si los tokens generados por el analizador léxico están agrupados de acuerdo con las reglas sintácticas del lenguaje. Esto lo hace un analizador. El analizador obtiene una string de tokens del analizador léxico y verifica que la string puede ser la gramática del idioma de origen. Detecta e informa cualquier error de sintaxis y produce un árbol de análisis desde el cual se puede generar código intermedio.

position of parser

Antes de pasar a los tipos de analizadores, discutiremos algunas ideas sobre algunas cosas importantes necesarias para comprender el análisis.

Gramáticas libres de contexto :
la sintaxis de un lenguaje de programación se describe mediante gramática libre de contexto (CFG). CFG consta de un conjunto de terminales, un conjunto de no terminales, un símbolo de inicio y un conjunto de producciones.
Notación – ? ? ? dónde ? es a es una sola variable [V]
? ? (V+T)*

Ambigüedad
Una gramática que produce más de un árbol de análisis sintáctico para alguna oración se dice que es ambigua.
Por ejemplo, considere una gramática
S -> aS | Sá | a
Ahora, para la string aaa, tendremos 4 árboles de análisis, por lo tanto, ambiguos

parse tree

Para obtener más información, consulte quiz.geeksforgeeks.org/ambiguous-grammar/

Eliminación de la recursividad izquierda:
una gramática se deja recursiva si tiene una S no terminal (variable) tal que hay una derivación
S -> Sα | β
donde α? (V+T)* y β? (V+T)* (secuencia de terminales y no terminales que no comienzan con S)
Debido a la presencia de recursividad por la izquierda, algunos analizadores de arriba hacia abajo entran en un bucle infinito, por lo que debemos eliminar la recursividad por la izquierda.
Sean las producciones de la forma A -> Aα ₁ | Aa ₂ | Aa ₃ | ….. | Aa _m | β1 | _{_}β2 | _{_}…. | β _n
Donde ningún βi comienza con A . luego reemplazamos las producciones A por
A -> β ₁ A’ | β2 _{_}un’ | ….. | β _n A’
A’ -> α ₁ A’ | α ₂ A’ | α ₃ A’| ….. | α _m A’ | ε
El no terminal A genera las mismas strings que antes, pero ya no se deja recursivo.
Veamos algunos ejemplos para entender mejor

$\\ Example 1: \\ \\S\rightarrow S\overset{\alpha _{1}}{ab} \hspace{2 mm}/\hspace{2 mm} S\overset{\alpha _{2}}{cd} \hspace{2 mm}/ \hspace{2 mm}S\overset{\alpha _{3}}{ef}\hspace{2 mm} /\hspace{2 mm} \overset{\beta_{1}}{g}\hspace{2 mm}/\hspace{2 mm}\overset{\beta_{2}}{h}\\ \\ S\rightarrow gS'/hS'\\ \\ S'\rightarrow \epsilon /abS'/cdS'/efS' \\ \\ Example 2:\\ \\ S\rightarrow (L)/a \hspace{2 cm} No\hspace{2 mm} left\hspace{2 mm} Recursion\\ \\ L\rightarrow L,S/S \hspace{2 cm} left\hspace{2 mm} Recursion\\ \\ L\rightarrow Sl' \\ \\ L'\rightarrow \epsilon/ SL' \\$

Eliminación de la factorización izquierda:
se dice que una gramática se factoriza a la izquierda cuando tiene la forma –
A -> αβ ₁ | αβ2 | _{_}αβ3 | _{_}…… | αβ _norte | γ es decir, las producciones comienzan con el mismo terminal (o conjunto de terminales). Al ver la entrada α, no podemos saber de inmediato qué producción elegir para expandir A.
La factorización izquierda es una transformación gramatical que es útil para producir una gramática adecuada para el análisis predictivo o de arriba hacia abajo. Cuando la elección entre dos producciones A alternativas no está clara, es posible que podamos reescribir las producciones para diferir la decisión hasta que se haya visto suficiente entrada para tomar la decisión correcta.
Para la gramática A -> αβ ₁ | αβ ₂| αβ3 | _{_}…… | αβ _norte | γ
La gramática factorizada por la izquierda equivalente será –
A -> αA’ | γ
A’ -> β ₁ | β2 | _{_}β3 | _{_}…… | norte _{_}

$\\ \\ Example 1: \\ \\ S\rightarrow iEtS\hspace{2 mm} / \hspace{2 mm} iEtS eS/a/b \\ \\ S\rightarrow iEtSS'/a/b\\ \\ S'\rightarrow eS/ \epsilon \\ \\ Example 2:\\ \\ S\rightarrow a/ab/abc/abcd/e/f\\ \\ S\rightarrow aS'/e/f \\ \\ S'\rightarrow bS"/\epsilon \hspace{2 cm} -for\hspace{2 mm} single\hspace{2 mm} a \\ \\ S"\rightarrow cS'''/\epsilon \hspace{2 cm} -for\hspace{2 mm} ab \\ \\ S'''\rightarrow d/\epsilon \hspace{2.4 cm} -for\hspace{2 mm} abc \\$

El proceso de derivar la string de la gramática dada se conoce como derivación (análisis).
Dependiendo de cómo se realice la derivación, tenemos dos tipos de analizadores:

Analizador de arriba hacia abajo
Analizador ascendente

Estudiaremos los analizadores desde el punto de vista GATE.

Analizador
de arriba hacia abajo El análisis de arriba hacia abajo intenta construir el árbol de análisis desde la raíz hasta la hoja. El analizador de arriba hacia abajo comenzará desde el símbolo de inicio y procederá a la string. Sigue la derivación más a la izquierda. En la derivación más a la izquierda, siempre se elige el no terminal más a la izquierda en cada oración.

Análisis de descenso recursivo

S()
{     Choose any S production, S ->X₁X₂…..Xk;
      for (i = 1 to k)
      {
          If ( Xi is a non-terminal)
          Call procedure Xi();
          else if ( Xi equals the current input, increment input)
          Else /* error has occurred, backtrack and try another possibility */
      }
}

Entendámoslo mejor con un ejemplo.
$\\ \\ S\rightarrow ABC/DEF/GHI \hspace{4.5 cm} G\rightarrow d\\ \\ A\rightarrow ab/gh/m\hspace{6 cm} F\rightarrow d \\ \\ B\rightarrow cd/ij/n \hspace{6.2 cm} H\rightarrow e \\ \\ C\rightarrow ef/kl/o \hspace{6.1 cm} I\rightarrow f\\ \\ S\rightarrow aS'/e/f\\ \\ D\rightarrow a \\ \\ E\rightarrow b\hspace{6.1 cm} Input:abijef\\ \\ \\$

Recursive Decent Parsing

Un programa de análisis de descenso recursivo consta de un conjunto de procedimientos, uno para cada no terminal. La ejecución comienza con el procedimiento para el símbolo de inicio que se detiene si su cuerpo de procedimiento escanea toda la string de entrada.

Análisis predictivo no recursivo:
este tipo de análisis no requiere retroceso. Los analizadores predictivos se pueden construir para la gramática LL (1), la primera ‘L’ significa escanear la entrada de izquierda a derecha, la segunda ‘L’ significa la derivación más a la izquierda y ‘1’ para usar un símbolo de entrada anticipado en cada paso para tomar decisiones de acción de análisis.
Antes de pasar a los analizadores LL(1), vaya PRIMERO y SIGA
https://www.geeksforgeeks.org/first-set-in-syntax-analysis/
https://www.geeksforgeeks.org/follow-set-in -análisis de sintaxis/

Construcción de la tabla de análisis predictivo LL(1)

Para cada producción A -> α, repita los siguientes pasos:
agregue A -> α debajo de M[A, b] para todos los b en PRIMERO (α)
Si PRIMERO (α) contiene ε, agregue A -> α debajo de M [A, c ] para todo c en SEGUIR(A).
Tamaño de la tabla de análisis = (No. de terminales + 1) * #variables

Por ejemplo, considere la gramática
S -> (L) | a
L -> SL’
L’ -> ε | SL’

LL 1 grammer

Para cualquier gramática si M tiene múltiples entradas entonces no es gramática LL(1)
Ej –
S -> iEtSS’/a
S’ ->eS/ε
E -> b

grammer

Notas importantes

      1. If a grammar contain left factoring then it can not be LL(1)
        Eg - S -> aS | a      ---- both productions go in a
      2. If a grammar contain left recursion it can not be LL(1)
        Eg - S -> Sa | b 
                S -> Sa goes to FIRST(S) = b
                S -> b goes to b, thus b has 2 entries hence not LL(1)
      3. If a grammar is ambiguous then it can not be LL(1)
      4. Every regular grammar need not be LL(1) because 
         regular grammar may contain left factoring, left recursion or ambiguity.

parser_9

Discutiremos el analizador de abajo hacia arriba en el próximo artículo ( Conjunto 2 ).

Este artículo es una contribución de Parul Sharma

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Rol del analizador:

Deja una respuesta Cancelar la respuesta