Compiladores

Operaciones de pila
1. Apile un símbolo específico en la pila.
2. Desapile el símbolo en el tope de la pila.
3. Dejar la pila sin cambios.
Operaciones de estado
1. Obtener el próximo símbolo de entrada y hacer este el actual símbolo de entrada.
2. Detener el presente símbolo de entrada como el actual símbolo de entrada.
Una máquina de pila se especifica por los siguientes 5ítems.
1. Un conjunto finito de símbolos de entrada los cuales incluyen una marca de fin de secuencia.
2. Un conjunto de símbolos de pila los cuales incluyen un símbolo de fin de pila.
3. Un conjunto finito de estados los cuales incluyen un estado inicial.
4. Un control el cual asigna una salida o transición a cada combinación de símbolos de entrada, símbolos de pila y estado.Las transiciones sin salida consisten de una transición de pila, una operación de estado y una operación de entrada como se especificó anteriormente.
5. Una pila inicializada la cual puede estar representada en notación símbolo del tope a la derecha con el fin de pila seguido por (posible nula) secuencia de otros símbolos de pila.
Cuando se describen las transiciones de una máquina de pila,denotamos las operaciones usando las palabras DESAPILAR, APILAR, AVANCE y RETENGA de la siguiente manera:
* Desapilar: significa desapilar el símbolo en el tope de la fila.
* Apilar (A): Donde A es un símbolo de la pila significa apilar a A.
* Estados (S): Si es un estado, significa que el estado será usado como próximo estado.
* Avance: Significa que la próxima entrada será usadacomo entrada actual.
* Retenga: Significa que la entrada actual será retenida.
Ejemplo: Hacer una máquina de pila que resuelva el problema de los paréntesis derechos e izquierdos.
1. Conjunto de entrada { (, ), ˧ }
2. Conjunto de símbolos en la pila { A, }
3. Conjunto de estados {S}, estado inicial.
4. Las transiciones son:
(, A, S = Apile (A), Estado (S), Avance.

(,, S = Apile (A), Estado (S), Avance.
), A, S = Desapile, Estado (S), Avance.

), , S = Rechace.
˧, A, S = Rechace.

˧, , S = Acepte.

S inicio de pila

Acepte
| ( | ) | ˧ |
A | Apile(A) Avance | Desapile Avance | Rechace |
˧ | Apile(A) Avance | Rechace | Acepte |

Un conjunto regular
{ 1n 0n } n>0 n 1’s seguidos de n 0’s1100; 10; 111000
{ 1n 0m } n>m>0 110; 1100; 1110
{ an bm cm dn } n>0; m>0; aabcdd; abbccd
(abc)r = cba
{w wr} = w en (0+1)*
Ejemplo: El siguiente ejemplo involucra una máquina de pila que tiene más de un estado.
Reconocer { 0n 1n } n > 0
Cada 0 que aparezca se apila y cada vez que aparezca un 1, se desapila el 0, se acepta la secuencia cuando si y solo si la pila estávacía (La secuencia está completa). Si ocurre un 0 después de un 1 la secuencia se rechaza. Para simplificar y evitar confusiones usaremos el símbolo Z para apilar en lugar de 0. En el primer estado se apilan los 0’s representados por Z. En el segundo estado es donde se desapila Z por cada ocurrencia de un 1 y si se rechaza la secuencia si aparece un 0. Para representar los estados usaremos S1 y S2.Ejemplo: Analizar la secuencia 000111; 001011

Acepte

Rechace

Tablas de secuencia
| 0 | 1 | ˧ |
Z | Estado (S1) Apile(Z) Avance | Estado (S1) Desapile(Z) Avance | Rechace |
 
 
|
| Estado (S1) Apile(Z) Avance | Rechace | Rechace |
| (a) S1 |

| 0 | 1 | ˧ |
Z | Rechace | Estado (S1) Desapile(Z) Avance | Rechace |
 
 
|
| Rechace |Rechace | Acepte |
| (b) S2 |

Especificación de la máquina que reconoce el conjunto {0n 1n} n>0
1. Conjunto de entrada {0,1, ˧}
2.

Conjunto de símbolos en la pila {Z , }
3. Conjunto de entradas {S1, S2}
4. Transición en (a) y (b)
5.

Inicio de pila

Operaciones de pila extendidas.

A las máquinas de pilas anteriores se les llama máquinas de pila...