Pushdown Automata & Parsing

A análise é usada para derivar uma string usando as regras de produção de uma gramática. É usado para verificar a aceitabilidade de uma string. O compilador é usado para verificar se uma string está sintaticamente correta ou não. Um analisador pega as entradas e constrói uma árvore de análise.

Um analisador pode ser de dois tipos -

Top-Down Parser - A análise de cima para baixo começa do topo com o símbolo inicial e deriva uma string usando uma árvore de análise.
Bottom-Up Parser - A análise de baixo para cima começa de baixo para cima com a string e chega ao símbolo inicial usando uma árvore de análise.

Projeto do analisador de cima para baixo

Para análise de cima para baixo, um PDA tem os seguintes quatro tipos de transições -

Estale o não terminal do lado esquerdo da produção no topo da pilha e empurre sua corda do lado direito.
Se o símbolo do topo da pilha corresponder ao símbolo de entrada que está sendo lido, abra-o.
Empurre o símbolo inicial 'S' na pilha.
Se a string de entrada for totalmente lida e a pilha estiver vazia, vá para o estado final 'F'.

Exemplo

Projete um analisador de cima para baixo para a expressão "x + y * z" para a gramática G com as seguintes regras de produção -

P: S → S + X | X, X → X * Y | Y, Y → (S) | Eu iria

Solution

Se o PDA for (Q, ∑, S, δ, q ₀ , I, F), então a análise de cima para baixo é -

(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)

⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)

⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)

Projeto de um analisador de baixo para cima

Para análise ascendente, um PDA tem os seguintes quatro tipos de transições -

Empurre o símbolo de entrada atual na pilha.
Substitua o lado direito de uma produção no topo da pilha pelo lado esquerdo.
Se o topo do elemento da pilha corresponder ao símbolo de entrada atual, destaque-o.
Se a string de entrada for totalmente lida e apenas se o símbolo inicial 'S' permanecer na pilha, retire-o e vá para o estado final 'F'.