Teoría del compilador | Serie 1

Se han hecho las siguientes preguntas en el examen GATE CS.

1. ¿Cuál de las siguientes derivaciones utiliza un analizador de arriba hacia abajo al analizar una string de entrada? Se supone que la entrada se explora en orden de izquierda a derecha (GATE CS 2000).
(a) Derivación más a la izquierda
(b) Derivación más a la izquierda trazada al revés
(c) Derivación más a la derecha
(d) Derivación más a la derecha trazada al revés

respuesta (a)

Análisis de arriba hacia abajo (LL)
En el análisis de arriba hacia abajo, simplemente comenzamos con el símbolo de inicio y comparamos el lado derecho de las diferentes producciones con la primera entrada para ver cuál de las producciones se debe usar.

Un analizador de arriba hacia abajo se llama analizador LL porque analiza la entrada de izquierda a derecha y construye una derivación de la oración más a la izquierda.

Algoritmo (análisis de arriba hacia abajo)

  a) In the current string, choose leftmost nonterminal.
  b) Choose a production for the chosen nonterminal. 
  c) In the string, replace the nonterminal by the right-hand-side 
     of the rule.
  d) Repeat until no more nonterminals. 

Las gramáticas LL a menudo se clasifican por números, como LL (1), LL (0), etc. El número entre paréntesis indica el número máximo de terminales que podemos tener que mirar a la vez para elegir la producción adecuada en cualquier punto de la gramática.

El tipo de gramática LL más común (y útil) es LL(1), donde siempre puede elegir la producción correcta mirando solo el primer terminal en la entrada en un momento dado. Con LL(2) tienes que mirar dos símbolos, y así sucesivamente. Existen gramáticas que no son gramáticas LL(k) para ningún valor fijo de k, y lamentablemente son bastante comunes.

Veamos un ejemplo de análisis de arriba hacia abajo para seguir la gramática. Deje que la string de entrada sea ax.

    S -> Ax
    A -> a
    A -> b

Un analizador LL (1) comienza con S y pregunta «¿qué producción debo intentar?» Naturalmente, predice la única alternativa de S. A partir de ahí, intenta hacer coincidir A llamando al método A (en un analizador de descenso recursivo). Lookahead y predice la producción

   A -> a

El analizador coincide con a, vuelve a S y coincide con x. Hecho. El árbol de derivación es:

     S
    / \
   A   x
   |
   a

Referencias:
http://www.garshol.priv.no/download/text/bnf.html
http://en.wikipedia.org/wiki/Top-down_parsing
http://en.wikipedia.org/wiki/LL_parser

2 El proceso de asignar direcciones de carga a las diversas partes del programa y ajustar el código y los datos en el programa para reflejar las direcciones asignadas se denomina (GATE CS 2001)
a) Ensamblaje
b) Análisis
c) Reubicación
d) Resolución de símbolos

Respuesta: (c)
La reubicación es el proceso de reemplazar referencias simbólicas o nombres de bibliotecas con direcciones utilizables reales en la memoria antes de ejecutar un programa. Por lo general, lo hace el enlazador durante la compilación (en el momento de la compilación), aunque puede hacerlo en tiempo de ejecución un cargador reubicado. Los compiladores o ensambladores suelen generar el ejecutable con cero como la dirección de inicio más baja. Antes de la ejecución del código objeto, estas direcciones deben ajustarse para que indiquen las direcciones de tiempo de ejecución correctas.

La reubicación generalmente se realiza en dos pasos:
1. Cada código de objeto tiene varias secciones como código, datos, .bss, etc. Para combinar todos los objetos en un solo ejecutable, el enlazador fusiona todas las secciones de tipo similar en una sola sección de ese tipo. . El enlazador luego asigna direcciones de tiempo de ejecución a cada sección y cada símbolo. En este punto, el código (funciones) y los datos (variables globales) tendrán direcciones de tiempo de ejecución únicas.
2. Cada sección hace referencia a uno o más símbolos que deben modificarse para que apunten a las direcciones de tiempo de ejecución correctas.

Referencias:
http://en.wikipedia.org/wiki/Relocation_(computer_science)

3. ¿Cuál de las siguientes afirmaciones es falsa? (GATE CS 2001)
a) Una gramática inequívoca tiene la misma derivación más a la izquierda y más a la derecha
b) Un analizador LL(1) es un analizador de arriba hacia abajo
c) LALR es más poderoso que SLR
d) Una gramática ambigua nunca puede ser LR(k) para cualquier k

Respuesta: (a)
Si una gramática tiene más de una derivación más a la izquierda (o más a la derecha) para una sola forma oracional, la gramática es ambigua. Las derivaciones más a la izquierda y más a la derecha para una forma oracional pueden diferir, incluso en una gramática no ambigua

4. ¿Cuál de las siguientes reglas gramaticales viola los requisitos de una gramática de operadores? P, Q, R son no terminales y r,s,t son terminales (GATE CS 2004).
(i) P -> QR
(ii) P -> QsR
(iii) P -> ε
(iV) P -> QtRr

a) (i) únicamente
b) (i) y (iii) únicamente
c) (ii) y (iii) únicamente
d) (iii) y (iv) únicamente

Respuesta: (b)
Explicación:
un analizador de precedencia de operadores es un analizador de abajo hacia arriba que interpreta una gramática de precedencia de operadores. Por ejemplo, la mayoría de las calculadoras utilizan analizadores de precedencia de operadores para convertir la notación infija legible por humanos con formato de orden de operaciones a un formato legible por computadora optimizado internamente como la notación polaca inversa (RPN).

Una gramática de precedencia de operadores es un tipo de gramática libre de contexto que se puede analizar con un analizador de precedencia de operadores. Tiene la propiedad de que ninguna producción tiene un lado derecho vacío (ε) o dos no terminales adyacentes en su lado derecho. Estas propiedades permiten que los terminales de la gramática se describan mediante una relación de precedencia, y un analizador que explota esa relación es considerablemente más simple que los analizadores de propósito general como los analizadores LALR.

Referencias:
http://en.wikipedia.org/wiki/Operator-precedence_grammar
http://en.wikipedia.org/wiki/Operator-precedence_parser

5. Considere la gramática con las siguientes reglas de traducción y E como símbolo de inicio.
E -> E1 #T {E.valor = E1.valor * T.valor}
| T {E.value = T.value}
T -> T1 & F {T.value = T1.value + F.value}
|F {T.value= F.value}
F -> num {F.value = num .valor}

Calcule el valor E para la raíz del árbol de análisis para la expresión: 2 # 3 & 5 # 6 &4. (GATE CS 2004)
a) 200
b) 180
c) 160
d) 40

Respuesta: (c)
Explicación:
Podemos calcular el valor construyendo el árbol de análisis sintáctico para la expresión 2 # 3 & 5 # 6 &4.

Alternativamente, podemos calcular considerando las siguientes reglas de precedencia y asociatividad.
La precedencia en una gramática se aplica asegurándose de que una regla de producción con un operador de mayor precedencia nunca produzca una expresión con un operador de menor precedencia.
En la gramática dada, ‘&’ tiene mayor precedencia que ‘#’.

La asociatividad por la izquierda para el operador * en una gramática se aplica asegurándose de que para una regla de producción como S -> S1 * S2 en gramática, S2 nunca debe producir una expresión con *. Por otro lado, para asegurar una correcta asociatividad, S1 nunca debe producir una expresión con *.
En la gramática dada, tanto ‘#’ como & son asociativos por la izquierda.

Entonces, la expresión 2 # 3 & 5 # 6 &4 se convertirá en
((2 # (3 & 5)) # (6 & 4))
Apliquemos las reglas de traducción, obtenemos
((2 * (3 + 5)) * (6 + 4)) = 160.