Programación de sistemas

ANALIZADOR SINTÁCTICO (PARSER)

ÍNDICE:

- INTRODUCCIÓN 2

- ANÁLISIS DESCENDENTE 2

- DESCENSO RECURSIVO PARA BNF 5

- CÁLCULO DE PRIMEROS Y SIGUIENTES 7

- CONDICIONES EN NOTACIÓN EBNF 11

- TRADUCCIÓN 18

- EJERCICIO DE CONSTRUCCIÓN DE UN ANALIZADOR
POR DESCENSO RECURSIVO 20

- CONSTRUCCIÓN INTERPRETE/COMPILADOR A PARTIR
DEL DIAGRAMA SINTÁCTICO:

*Intérprete 24
* Compilador 28

- ANALIZADOR SINTÁCTICO PARA EL PL/0 32

- RECONOCEDORES LL(1) 39

- TRANSFORMACIONES DE LAS GRAMÁTICAS:

* Recursividad por la izquierda 44
* Factorización 45
* Sustitución 45
* Eliminación de ε 48

- REFERENCIAS BIBLIOGRÁFICAS 51
ANALIZADOR SINTÁCTICO (PARSER)

El analizador sintáctico o reconocedor viene condicionado porla gramática que define el lenguaje, por tanto tiene que estar diseñado en función de la misma. Se encarga de comprobar si pertenece o no a la gramática la secuencia de símbolos (o token) que le pasa el Analizador léxico.
Si es una secuencia tendrá que ver cuál es su estructura o árbol sintáctico.

-A. Descendente.- Existen dos grupos de métodos de análisis
-A. Ascendente.

ANÁLISIS DESCENDENTE

Un método para diseñarlo es el descenso recursivo donde se asocia cada símbolo no terminal a un procedimiento, los procedimientos son recursivos:

N (((( a B c d E

procedure N;
begin
if s = 'a' then A.lex else error;
B;
if s = 'c' then A.lexelse error;
if s = 'd' then A.lex else error;
E;
end.
Si existe más de una regla: N α │ ß │ τ

procedure N;
begin
case s of
a . . f:

α

g . . i:

ß

j . . m:

τ

end;
end.

Siempre que llamemos a un símbolo no terminal, nos encontraremos en 's' con el primer símbolo de la izquierda:

N N

Disponemos, portanto, sólo del primer símbolo del texto de entrada.

Sea α = M x Y z ; y llamamos al conjunto P, los primeros de α, que contienen los símbolos con los que empiezan todas las frases:

P(α) = { s / α ══>* x ε VT*, x = s x' }

α E F x P(α) = P(E F x) = { a, b, n, x }

E a B │ b c │ ε P(E) = { a, b, ε }

F E n │ ε P(F) = { a, b, n, ε }

P(α) ( Vt ( ( ε (

Situviéramos los P(α), P(ß), P(τ) y s sólo perteneciera a uno de ellos, entonces esa opción sería la única a seguir, dicha opción empieza por ese símbolo. Hacemos esta restricción pues en caso contrario habría problemas, esta condición la expresamos de la siguiente forma:

P(α1) ( P(α1) = ( ( i,j i ( j

donde también se impide que ε pertenezca a ambos.

Si s no está en el conjunto de primerosentonces se elige un α k tal que:

( αk / P(αk) ( (

N P

Q N S B

a b αk X Y

(

DESCENSO RECURSIVO PARA BNF:

Vamos recorriendo el árbol a partir de la raíz, llamamos a cada procedimiento correspondiente a cada símbolo no terminaly en cada una de las opciones nos fijamos en cual es el siguiente símbolo que aparece en el programa fuente, así el procedimiento debe decidir cual de las opciones debe seguir. Para ello calcula todos los primeros de la parte derecha, pues se pretende que nunca tenga que volverse atrás.
También se acepta que alguna de las opciones contenga ε, pero si ε pertenece a P(αi) existen varias opciones:- s no pertenece a P(αj) para todo j (((> cogemos ε y lo
s sustituimos.
- s pertenece a P(αj).

En el segundo caso podemos, o bien coger el αj y construir la frase, o bien coger el αi que genere ε y que s provenga de la construcción de la frase del árbol siguiente. Para saber qué opción seguir establecemos una condición para que el método sea aplicable. Para...