Compiladores

http://compiladores.galeon.com/tarea_4.htm

Analizador sintactico (parser)
 
Un analizador sintactico (parser), se encarga de determinar si un string de simbolos (tokens) es aceptado por las reglas de produccion definidas en una gramatica dada.
Al momento de analizar un string de entrada, es util la construcción de un árbol sintactico.
Si consideramos la gramatica:
type  -> simple          | id
          | array [ simple ] of type
simple -> integer
           | char
           | num dotdot num
y un string de entrada w = array [num dotdot num ] of integer, podemos construir un árbol sintactico como sigue:
Podemos construir un analizador predictivo para el árbol anterior. En particular a este analizador se le denomina Parser Recursivo-Descendente. Este analizadorademas de ser recursivo utiliza rastero hacia atras o backtracking para expandir los símbolos no terminales de la gramática.
Consideremos ahora la siguiente gramatica:
E -> E + T T
T -> T * F  F
F -> ( E ) id
Un analizador sintactico recursivo descendente, en algun momento ciclaria su funcionamiento, debido a que trataria de expandir sus reglas de producción sobre el mismosímbolo no términal.
Para evitar esto, se hace necesaria la transformación de la gramática de tal modo que se elimine la recursión por la izquierda.
Sea A - A a b una regla de producción con recursión a la izquierda. Su transformación se realiza de la forma A - bA' y A' - a A' e.
Utilizando la regla anterior, podemos transformar la gramática en:
E -> T E'
E' -> +T E' e
T -> F T'T' -> * F T' e
F -> ( E )  id
Esta gramática puede ser utilizada ahora en el analizador recursivo descendente. Sin embargo, podemos emplear también un analizador que no es recursivo y no requiere el uso de backtracking. Un analizador predictivo no recursivo basa su funcionamiento en saber que simbolos estan en primer lugar en la parte derecha de las reglas de produccion de una gramatica.Este analizador requiere que la gramática no tenga recursión por la izquierda.
Un parser predictivo no recursivo utiliza un buffer de entrada un stack, una tabla sintactica y una salida.
1. El buffer de entrada contiene la cadena a ser analizada seguida de un signo $, que indica el final del string
2. El stack contiene una secuencia de símbolos gramáticales con el signo $ como primerelemento. Inicialmente el stack contiene el símbolo de inicio de la gramática colocado arriba de $.
3. La tabla sintactica es un arreglo bidimensional M[A, a], donde A es un no-terminal y a puede ser un terminal o el simbolo $.
4. El analizador es controlado por un programa que funciona con el siguiente algoritmo:
push $,
push S (símbolo inicial de la gramática)
ip apunta al primersímbolo de w$ (cadena de entrada)
repeat
       sea X el símbolo superior del stack
       sea a el siguiente símbolo de entrada
       if X es terminal o $
              if X = a
                     pop X
                     avanzar ip
              else Error
       else // X es no terminal
              if M[X, a] = X - Y1 Y2 Y3 ... Yk
                     pop X                     push Yk ... Y3 Y2 Y1 con Y1 al inicio
                     salida: producción X - Y1 Y2 Y3 ... Yk
              else Error
until X = $
Para la gramática:
E -> T E'
E' -> +T E' e
T -> F T'
T' -> * F T' e
F -> ( E )  id
 
Su tabla sintactica queda así |
No terminal | id | + | * | ( | ) | $ |
E | E - T E' |   |   | E - T E' |   |   |
E' |   | E' -+ T E' |   |   | E' - e | E' - e |
T | T - F T' |   |   | T - F T' |   |   |
T' |   | T' - e | T' - * F T' |   | T' - e | T' - e |
F | F - id |   |   | F - ( E ) |   |   |

Los movimientos hechos por el parser asi:
Stack | Input | Output |
$ E | id + id * id $ |   |
$ E' T | id + id * id $ | E -> T E' |
$ E' T' F | id + id * id $ | T -> F T' |
$ E' T' id | id +...