Redes

Analizador_sintáctico_LR Para otros usos de este término, véase Analizador (desambiguación). Es un analizador sintáctico ascendente, para algunas gramáticas libres de contexto Analizador sintácticos LR. También conocidos como parser LR, son un tipo de analizadores para algunas gramáticas libres de contexto. Pertenece a la familia de los analizadores ascendentes, ya que construyen el árbolsintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis por desplazamiento reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico. Concepto:

Contenido
• 1 Un analizador LR consta de: • 2 Proceso de análisis LR. • 3 Pasos para construir un Autómata • 4 Implantación de analizadores sintácticos LR(k). • 5 Tablas de análisis sintácticos LR. • 6 Comparación entreanalizadores sintácticos LR(k) y LL(k). • 7 Véase también • 8 Fuente

Un analizador LR consta de:
1. Un programa conductor 2. Una entrada 3. Una salida 4. Una tabla de análisis sintáctico, compuesta de 2 partes (ACCIÓN Y GOTO) Cabe acotar que el programa conductor es siempre igual, solo variando para cada lenguaje la tabla de análisis sintáctico. El algoritmo para reconocer cadenas es elsiguiente: dado el primer carácter de la cadena y el estado inicial de la tabla, buscar qué acción corresponde en la tabla de acción. Si el estado es shift n (n ? N), se coloca el carácter y el número de estado n en la pila, se lee el siguiente carácter y repite el procedimiento, solo que esta vez buscamos en el estado correspondiente. SI ACCIÓN = REDUCE n (n ? N), se sacan de la pila tantas tuplas(estado, símbolo) como el largo de la cola de la producción en el n-ésimo lugar, y se reemplaza por la cabeza de esta producción. El nuevo estado sale de buscar en la tabla GOTO usando para ubicarlo el número de estado que quedo en el tope de la pila, y el no terminal en la cabeza. En la tabla acción también encontraremos ACEPTAR que se toma la cadena como valida y se termina el análisis o ERROR que serechaza la cadena.

Proceso de análisis LR.
En términos generales un analizador sintáctico LR transfiere símbolos de su entrada a la pila hasta que los símbolos superiores de la pila sean iguales al lado derecho de alguna regla de reescritura de la gramática en que se basa el analizador. Al llegar a este punto el analizador sintáctico puede reemplazar estos símbolos con el no terminal que seencuentra en el lado izquierdo de la regla de reescritura antes de transferir otros símbolos de la entrada a la pila. De esta manera, la pila acumula cadenas de terminales y no terminales, que a su vez son reemplazados por no terminales ?más altos? de la gramática. Por último, todo el contenido de la pila se reduce al símbolo inicial de la gramática, indicando que los símbolos leídos hasta ese puntoforman una cadena que puede derivarse con la gramática.

Contenido

1

Analizador_sintáctico_LR Con base a este esquema general los analizadores sintácticos LR(k) se clasifican como analizador sintáctico ascendente, ya que sus actividades corresponden a la construcción de ocurrencias de no terminales a partir de sus componentes, hasta generar el símbolo inicial de la gramática. Losanalizadores sintácticos LL(k) se conocen como analizadores sintácticos descendentes ya que comienzan con el símbolo inicial de la pila y dividen los no terminales de la pila hasta generar una cadena similar a la entrada. Un analizador sintáctico LR(k) se basa en un autómata de pila construido a partir de una gramática independiente del contexto, con la excepción de que el autómata se construye con lopasos siguientes:

Pasos para construir un Autómata
1. Establecer cuatro estados: inicial (i), aceptación (?) y dos llamados p y q. 2. Introducir las transiciones (i, l, l; p, #) y (q, l, #; ?, l), # no pertenece a la gramática. 3. Para cada símbolo terminal x en la gramática, introducir la transición (p, x, l; p, x) que sirve para que el autómata transfiera a la pila los símbolos de entrada...