Parsers
Frank Coelho de Alcantara - 2021
Exercício 1 - Gabarito
- $EXP = (EXP) | EXP \space\space OP\space\space IDENT$
- $OP = + | - | \times | \div$
- $IDENT = a | b | c$
Regras de Produção:
- $EXP$
- $EXP\space\space OP\space\space IDENT$
- $EXP \times IDENT$
- $(EXP) \times IDENT$
- $(EXP\space\space OP \space\space IDENT) \times IDENT$
- $(EXP + IDENT) \times IDENT$$
- $(IDENT + IDENT) \times IDENT$$
- $(a + IDENT) \times IDENT$$
- $(a + b) \times IDENT$$
- $(a + b) \times c$$
Parsers
Gramáticas Livres de Contexto
Símbolos à esquerda são os símbolos não terminais, representados por letras latinas maiúsculas $(𝑆, 𝐴, 𝐵, …)$.
Símbolos à direita podem ser terminais, ou não. Símbolos terminais são representados por letras latinas minúsculas ou outros símbolos $(a, b, c, ...)$.
Várias regras de produção $(𝐴\rightarrow \beta_1, 𝐴\rightarrow \beta_2, …, 𝐴\rightarrow \beta_n)$, com um mesmo não terminal do lado esquerdo podem ser reunidas: $𝐴 \rightarrow \beta_1 | \beta_2 | … |\beta_n$.
Gramáticas Livres de Contexto
Strings com terminais e não terminais, quando existirem, serão representadas por letras gregas minúsculas $(\Gamma, \Delta, \Phi,...)$.
Strings de não terminais são representadas por letras latinas mínúsculas $(S, A, B, C, ...)$.
Strings de terminais são representadas por letras latinas mínúsculas $(a, x, b, z, ...)$.
Um símbolo qualquer, indefinido, que pode ser terminal ou não terminal, será representado por uma letra latina maiúscula $(𝑋, 𝑌, …)$, do fim do alfabeto.
Gramáticas Livres de Contexto
A árvore gerada por derivação pode ser usada para caracterizar as gramáticas livres de contexto.
Consideramos equivalentes todas as derivações que correspondem a mesma árvore.
Derivação
Derivação à esquerda (leftmost derivation): a regra é sempre aplicada ao primeiro não terminal da cadeia, o que fica mais à esquerda.
Derivação à direita (rightmost derivation): a regra é sempre aplicada ao último não terminal da cadeia, o que fica mais à direita.
O algoritmo de parser definirá a forma como faremos a derivação, definindo qual a derivação que vamos utilizar para substituir símbolos terminais por não terminais, ou vice-versa.
Ambiguidade
Uma gramática é ambígua se, para uma string $w$ qualquer, existem duas ou mais árvores de derivação distintas, duas ou mais derivações a esquerda ou duas ou mais derivações a direita.
Podemos mostrar que uma gramática é ambígua mostrando que para uma determinada string $w$ existem árvores sintáticas distintas.
Quando a gramática é sua as ambiguidades são resolvidas com regras de produção mais explicitas.
Exemplo Clássico if-then-else
Considere a gramática a seguir:
- $STMT \rightarrow if \space EXPR \space then \space STMT \space else \space STMT$
- $\space\space\space\space\space\space\space\space |\space if \space EXPR \space then \space STMT$
- $\space\space\space\space\space\space\space\space |\space outras\space declarações$
A gramática definida por este fragmento de regras de produção é conhecida por ser ambígua e permitir a criação de, pelo menos, duas árvores sintáticas diferentes. Para a declaração: $$if\space\space EXPR \space\space then\space\space if\space\space EXPR\space\space then\space\space STMT\space\space else \space\space STMT$$
Exemplo Clássico - Ambiguidade
A ambiguidade ocorre por que as duas regras podem ser usadas intercambiavelmente. E pode ser resolvida se explicitarmos melhor as regras.
Ambiguidade Solução
Criamos uma gramática onde o else seja referente ao if imediatamente anterior.
- $STMT \rightarrow WITHELSE \space\space\space |\space NOELSE$
- $WITHELSE \rightarrow if\space\space EXPR\space\space then\space\space WITHELSE\space\space else\space\space WITHELSE\space\space STMT $
- $NOELSE \rightarrow if \space\space EXPR\space\space then\space\space STMT$
- $NOELSE \rightarrow if \space\space EXPR\space\space then\space\space WITHELSE\space\space else\space\space NOELSE$
Montamos if com else, ou sem else, na ordem certa. Verifique se este novo conjunto de regras produz ambiguidade, ou não, no seu caderno, a mão.
Top-Down Parser
Construiremos a árvore sintática a partir da Raiz (topo) e da esquerda para direita.
Nesta árvore nós são símbolos não terminais e folhas são símbolos terminais.
Começaremos pelo símbolo inicial, neste caso o S.Exemplo
Considere a gramática a seguir e encontre a árvore de derivações para $“a + a * a”$:
- $G= \{\Sigma = \{ +, *, (, ), a\}$,
- $\space\space\space 𝑵=\{𝑺, 𝑻, 𝑭\}$,
- $\space\space\space𝑺=\{𝑺\}$,
- $\space\space\space𝑷=\{ $
- $\space\space\space\space\space\space𝑺 \rightarrow 𝑺+𝑻$;
- $\space\space\space\space\space\space𝑺 \rightarrow 𝑻$;
- $\space\space\space\space\space\space𝑻 \rightarrow 𝑻∗𝑭$;
- $\space\space\space\space\space\space𝑻 \rightarrow 𝑭$;
- $\space\space\space\space\space\space𝑭 \rightarrow (𝑺)$;
- $\space\space\space\space\space\space𝑭 \rightarrow 𝒂\}\}$;
Exemplo
- $𝑺 \rightarrow 𝑺+𝑻$;
- $𝑺 \rightarrow 𝑻$;
- $𝑻 \rightarrow 𝑻∗𝑭$;
- $𝑻 \rightarrow 𝑭$;
- $𝑭 \rightarrow (𝑺)$;
- $𝑭 \rightarrow 𝒂$;
$𝑆 \rightarrow 𝑆+𝑇$ $𝑆 \Rightarrow 𝑆+𝑇;$
$𝑆→𝑇$$\Rightarrow 𝑇+𝑇;$
$𝑇→𝐹$$\Rightarrow 𝐹+𝑇;$
$𝐹→𝑎$$\Rightarrow 𝑎+𝑇;$
$𝑇→𝑇∗𝐹$$\Rightarrow 𝑎+𝑇∗𝐹;$
$𝑇→𝐹$$\Rightarrow 𝑎+𝐹∗𝐹;$
$𝐹→𝑎$$\Rightarrow 𝑎+𝑎∗𝐹;$
$𝐹→𝑎$$\Rightarrow 𝑎+𝑎∗𝑎;$
Exemplo
$𝑆 \rightarrow 𝑆+𝑇$ $𝑆 \Rightarrow 𝑆+𝑇;$
$𝑆→𝑇$$\Rightarrow 𝑇+𝑇;$
$𝑇→𝐹$$\Rightarrow 𝐹+𝑇;$
$𝐹→𝑎$$\Rightarrow 𝑎+𝑇;$
$𝑇→𝑇∗𝐹$$\Rightarrow 𝑎+𝑇∗𝐹;$
$𝑇→𝐹$$\Rightarrow 𝑎+𝐹∗𝐹;$
$𝐹→𝑎$$\Rightarrow 𝑎+𝑎∗𝐹;$
$𝐹→𝑎$$\Rightarrow 𝑎+𝑎∗𝑎;$
Leftmost / Rightmost
- $𝑺 \rightarrow 𝑺+𝑻$;
- $𝑺 \rightarrow 𝑻$;
- $𝑻 \rightarrow 𝑻∗𝑭$;
- $𝑻 \rightarrow 𝑭$;
- $𝑭 \rightarrow (𝑺)$;
- $𝑭 \rightarrow 𝒂$;
Leftmost
$𝑆 \Rightarrow 𝑆+𝑇;$
$\Rightarrow 𝑇+𝑇;$
$\Rightarrow 𝐹+𝑇;$
$\Rightarrow 𝑎+𝑇;$
$\Rightarrow 𝑎+𝑇∗𝐹;$
$\Rightarrow 𝑎+𝐹∗𝐹;$
$\Rightarrow 𝑎+𝑎∗𝐹;$
$\Rightarrow 𝑎+𝑎∗𝑎;$
Rightmost
$𝑆 \Rightarrow 𝑆+𝑇;$
$\Rightarrow 𝑆+𝑇∗𝐹;$
$\Rightarrow 𝑆+𝑇∗𝑎;$
$\Rightarrow 𝑆+𝐹∗𝑎;$
$\Rightarrow 𝑆+𝑎∗𝑎;$
$\Rightarrow 𝑇+𝑎∗𝑎;$
$\Rightarrow 𝐹+𝑎∗𝑎;$
$\Rightarrow 𝑎+𝑎∗𝑎;$
Bottom-up Parser
Bottom-up Parser
Considere uma string $w$ qualquer:
- Escolha uma substring $\beta $ de tal forma que: $\beta $ seja o fator mais a esquerda de $w$ desde que exista uma regra de produção $𝐴\rightarrow𝛽$.
- Troque $\beta $ por $𝐴$ em $w$.
- Repita até chegar ao símbolo inicial.
Exemplo
Considere a gramática definida a seguir e encontre a derivação que prove que “abbcde” pertence a linguagem definida por esta gramática.
- $G= \{ \Sigma = \{ a, b, c, d, e\}$;
- $\space\space\space𝑵=\{𝑺, A, B\}$;
- $\space\space\space𝑺=\{𝑺\}$ ;
- $\space\space\space𝑷=\{ $
- $\space\space\space\space\space\space 𝑺 \rightarrow 𝒂𝑨𝑩𝒆$;
- $\space\space\space\space\space\space A \rightarrow 𝑨𝒃𝒄$;
- $\space\space\space\space\space\space A \rightarrow b$;
- $\space\space\space\space\space\space B \rightarrow d \} \}$
Exemplo
- $𝑺 \rightarrow 𝒂𝑨𝑩𝒆$;
- $A \rightarrow 𝑨𝒃𝒄$;
- $A \rightarrow b$;
- $B \rightarrow d$;
| Strings | Produções | Escolha |
|---|---|---|
| $abbcde$ | $𝑨 \rightarrow 𝒃$ | |
| $𝑩 \rightarrow 𝒅$ | $𝑨 \rightarrow 𝒃$ | |
| $aAbcde$ | $𝑨 \rightarrow 𝑨𝒃𝒄$ | |
| $𝑨 \rightarrow 𝒃$ | ||
| $𝑩 \rightarrow 𝒅$ | $𝑨 \rightarrow 𝑨𝒃𝒄$ | |
| $aAde$ | $𝑩 \rightarrow 𝒅$ | $𝑩 \rightarrow 𝒅$ |
| $aABe$ | $𝑺 \rightarrow 𝒂𝑨𝑩𝒆$ | $𝑺 \rightarrow 𝒂𝑨𝑩𝒆$ |
| $S$ |
Shift Reduce
Os parsers desta categoria também são chamados de SR Parsers (Shift-Reduce). De tal forma que:
Shift: leia o próximo símbolo;
Reduce: substitua uma substring $w$ correspondente ao lado direito.
A repetição recursiva destas instruções constrói a árvore.
Bottom-up Algoritmo
Vamos colocar símbolos na pilha até que a pilha tenha tantos símbolos quanto necessário para reconhecer o lado direito de uma regra de produção. Assim que isso acontecer faremos a troca destes símbolos pelo não terminal correspondente.
A sequência de símbolos na pilha que está pronta para ser reduzida é chamada de handle.
O handle é o lado direito de uma regra de produção segundo determinado pela gramática.
Shift Reduce
Shift: o símbolo corrente na pilha e lê o próximo símbolo.
Reduce: o conteúdo da pilha usando uma regra de produção.
A redução do conteúdo da pilha pode ser chamado de Handle Pruning. Para isso usamos:
- Uma Pilha, ou stack, armazena os símbolos que serão substituídos.
- Um Buffer, contendo os outros símbolos. Aqueles que ainda serão avaliados.
- Uma Tabela, contendo as regras e os passos que estão ocorrendo.
Handle Prunning Exemplo
Considere a gramática definida pelo seguinte conjunto de regras de produção e encontre a derivação para “a + a * a”.
- $𝑺 \rightarrow 𝑺+𝑺;$
- $𝑺 \rightarrow 𝑺∗𝑺;$
- $𝑺 \rightarrow (𝑺)$
- $𝑺 \rightarrow 𝒂$
Handle Prunning Solução
- $𝑺 \rightarrow 𝑺+𝑺;$
- $𝑺 \rightarrow 𝑺∗𝑺;$
- $𝑺 \rightarrow (𝑺)$
- $𝑺 \rightarrow 𝒂$
| Pilha | Buffer | Ação |
|---|---|---|
| $\$$ | $ a+a*a\$$ | Shift |
| $\$a$ | $+a*a\$$ | Reduce $S \rightarrow a$ |
| $\$S$ | $+a*a\$$ | Shift |
| $\$S+$ | $a*a\$$ | Shift |
| $\$S+a$ | $*a\$$ | Reduce $S \rightarrow a$ |
| $\$S+S$ | $*a\$$ | Shift |
| $\$S+S*$ | $a\$$ | Shift |
| $\$S+S*a$ | $\$$ | Reduce $S \rightarrow a$ |
| $\$S+S*S$ | $\$$ | Reduce $S \rightarrow S*S$ |
| $\$S+S$ | $\$$ | Reduce $S \rightarrow S+S$ |
| $\$S$ | $\$$ | Accept |
Discussão 1
Refaça este exemplo cuidadosamente veja se é possível encontrar outra sequência de substituição.
Se encontrar outra sequência de substituição. As árvores sintáticas serão iguais?
Compare seus achados com os achados dos seus colegas de classe.
Vocês terão 10 minutos para isso.
Para Lembrar: Parsers
Parsers - Top-Down
- Da raiz para as folhas;
- Da esquerda para direita;
- A derivação mais a esquerda;
- O parse deverá escolher uma regra que atenda esta derivação.
O que acontece quando não existe uma regra adequada?
Parsers - Backtracing
Se, a qualquer momento, não existir uma regra de produção que permita a derivação, o parser deve voltar e refazer a árvore; talvez uma das escolhas de regras possa ser alterada.
A essa operação damos o nome de Backtrack.
Parsers - Backtracing
Existem dois algoritmos para varrer uma árvore sintáticas conhecidos por sua eficiência: deep-first e breadth-first.
No deep-first havendo duas opções, armazenamos uma e seguimos com a outra, se algo der errado voltamos neste ponto e seguimos a outra alternativa.
Parsers - Backtracing
No breadth-first, armazenamos um conjunto de soluções parciais e examinamos estas soluções em busca de soluções melhores eventualmente o conjunto irá conter toda a árvore.
criamos um conjunto para cada opção e vamos eliminando opções ruins.
Parsers - NonBacktracing
Classe de parsers que usa um ponteiro apontando para o próximo símbolo na string;
Usam uma classe de gramática especial chamada de LL(k);
O k representa o número de símbolos analisados em cada passo (previstos???).
Gramáticas LL(1)
Definimos gramáticas LL(1) de tal forma que:$$𝑮=\{𝑵,\Sigma, 𝑷, 𝑺\}$$
Onde: $$𝒘 \in \Sigma^∗, 𝑨\in 𝑵, \alpha, \beta \space \space 𝒆 \space \space \gamma \in (𝑵\cup \Sigma)^∗$$
Cujas derivações serão dadas por:$$𝑺 \rightarrow 𝒘𝑨 \gamma \space | \space 𝒘 \alpha 𝜸 \space | \space 𝒘𝒙 \in \Sigma^∗$$
$$ 𝑺 \rightarrow 𝒘𝑨 \gamma \space | \space 𝒘\beta \gamma \space | \space 𝒘𝒚 \in \Sigma^∗$$
LL(1) - Resumo
Exemplo LL(1)
Considere o alfabeto $\Sigma = \{n, +, *, (, )\}$, o seguinte conjunto de Regras de produção e a Tabela de derivação a seguir, para gerar a árvore sintática de "n*n" sem aspas:
- $S \rightarrow TR$
- $R \rightarrow \varepsilon$
- $R \rightarrow +S$
- $T \rightarrow FG$
- $G \rightarrow \varepsilon$
- $G \rightarrow *T$
- $F \rightarrow n$
- $F \rightarrow (S)$
| $n$ | $+$ | $*$ | $($ | $)$ | $\$$ | |
|---|---|---|---|---|---|---|
| $S$ | $1$ | $ $ | $ $ | $1$ | $ $ | $ $ |
| $R$ | $ $ | $3$ | $2$ | $ $ | $2$ | $2$ |
| $T$ | $4$ | $ $ | $ $ | $4$ | $ $ | $ $ |
| $G$ | $ $ | $5$ | $6$ | $ $ | $5$ | $5$ |
| $F$ | $7$ | $ $ | $ $ | $8$ | $ $ | $ $ |
Parser n*n
- $S \rightarrow TR$
- $R \rightarrow \varepsilon$
- $R \rightarrow +S$
- $T \rightarrow FG$
- $G \rightarrow \varepsilon$
- $G \rightarrow *T$
- $F \rightarrow n$
- $F \rightarrow (S)$
| $n$ | $+$ | $*$ | $($ | $)$ | $\$$ | |
|---|---|---|---|---|---|---|
| $S$ | $1$ | $ $ | $ $ | $1$ | $ $ | $ $ |
| $R$ | $ $ | $3$ | $2$ | $ $ | $2$ | $2$ |
| $T$ | $4$ | $ $ | $ $ | $4$ | $ $ | $ $ |
| $G$ | $ $ | $5$ | $6$ | $ $ | $5$ | $5$ |
| $F$ | $7$ | $ $ | $ $ | $8$ | $ $ | $ $ |
Começamos com $S$, temos $D(S,n)=1$, expandimos $S$ usando $S \rightarrow TR$;
Temos $D(T,n)=4$, expandimos $T \rightarrow FG$;
Temos $D(F,n)=7$, expandimos $F \rightarrow n$;
Chegamos no $n$ mudamos o lookahead para $*$;
Temos $D(G,*)=6$, expandimos $G \rightarrow *T$;
Chegamos no $*$ mudamos o lookahead para $n$;
Temos $D(T,n)=4$, expandimos $T \rightarrow FG$;
Temos $D(F,n)=7$, expandimos $F \rightarrow n$;
Chegamos no $n$ mudamos o lookahead para $\$$;
Temos $D(G,\$)=5$, expandimos $G \rightarrow \varepsilon$;
Temos $D(R,\$)=2$, expandimos $R \rightarrow \varepsilon$;
Árvore de n*n
Começamos com $S$, temos $D(S,n)=1$, expandimos $S$ usando $S \rightarrow TR$;
Temos $D(T,n)=4$, expandimos $T \rightarrow FG$;
Temos $D(F,n)=7$, expandimos $F \rightarrow n$;
Chegamos no $n$ mudamos o lookahead para $*$;
Temos $D(G,*)=6$, expandimos $G \rightarrow *T$;
Chegamos no $*$ mudamos o lookahead para $n$;
Temos $D(T,n)=4$, expandimos $T \rightarrow FG$;
Temos $D(F,n)=7$, expandimos $F \rightarrow n$;
Chegamos no $n$ mudamos o lookahead para $\$$;
Temos $D(G,\$)=5$, expandimos $G \rightarrow \varepsilon$;
Temos $D(R,\$)=2$, expandimos $R \rightarrow \varepsilon$;
Buffer e Pilha
- $S \rightarrow TR$
- $R \rightarrow \varepsilon$
- $R \rightarrow +S$
- $T \rightarrow FG$
- $G \rightarrow \varepsilon$
- $G \rightarrow *T$
- $F \rightarrow n$
- $F \rightarrow (S)$
| $n$ | $+$ | $*$ | $($ | $)$ | $\$$ | |
|---|---|---|---|---|---|---|
| $S$ | $1$ | $ $ | $ $ | $1$ | $ $ | $ $ |
| $R$ | $ $ | $3$ | $2$ | $ $ | $2$ | $2$ |
| $T$ | $4$ | $ $ | $ $ | $4$ | $ $ | $ $ |
| $G$ | $ $ | $5$ | $6$ | $ $ | $5$ | $5$ |
| $F$ | $7$ | $ $ | $ $ | $8$ | $ $ | $ $ |
| $Localizado$ | $Pilha$ | $Buffer$ | $Ação$ |
|---|---|---|---|
| $S\$$ | $n*n\$$ | Reduce $S \rightarrow TR$ | |
| $TR\$$ | $n*n\$$ | Reduce $T \rightarrow FG$ | |
| $FGR\$$ | $n*n\$$ | Reduce $F \rightarrow n $ | |
| $nGR\$$ | $n*n\$$ | Encontrei $n$ | |
| $n$ | $GR\$$ | $*n\$$ | Reduce $G \rightarrow *T$ |
| $n$ | $*TR\$$ | $*n\$$ | Encontrei $*$ |
| $n*$ | $TR\$$ | $n\$$ | Reduce $T \rightarrow FG$ |
| $n*$ | $FGR\$$ | $n\$$ | Reduce $F \rightarrow n$ |
| $n*$ | $nGR\$$ | $n\$$ | Encontrei $n$ |
| $n*n$ | $GR\$$ | $\$$ | Reduce $G \rightarrow \varepsilon $ |
| $n*n$ | $R\$$ | $\$$ | Reduce $R \rightarrow \varepsilon $ |
| $n*n$ | $\$$ | $\$$ | Fim |
Exercício LL(1)
Considere o alfabeto $\Sigma = \{n, +, *, (, )\}$, o seguinte conjunto de Regras de produção e a tabela a seguir:
- $S \rightarrow TR$
- $R \rightarrow \varepsilon$
- $R \rightarrow +S$
- $T \rightarrow FG$
- $G \rightarrow \varepsilon$
- $G \rightarrow *T$
- $F \rightarrow n$
- $F \rightarrow (S)$
| $n$ | $+$ | $*$ | $($ | $)$ | $\$$ | |
|---|---|---|---|---|---|---|
| $S$ | $1$ | $ $ | $ $ | $1$ | $ $ | $ $ |
| $R$ | $ $ | $3$ | $2$ | $ $ | $2$ | $2$ |
| $T$ | $4$ | $ $ | $ $ | $4$ | $ $ | $ $ |
| $G$ | $ $ | $5$ | $6$ | $ $ | $5$ | $5$ |
| $F$ | $7$ | $ $ | $ $ | $8$ | $ $ | $ $ |
Vamos usar a tabela para gerar a árvore sintática abstrata da string "n+n*n" sem as aspas.
Bottom-UP Parser
Usam uma classe de gramática especial chamada de $LR(k)$;
O $k$ representa o número de símbolos previsto.
Shift-Reduce Parser
Quatro operações: Shift, Reduce, Accept e Error;
É o parser mais simples da família $LR(k)$.
Shift-Reduce Parser
O $K$ indica quantos símbolos a frente;
É um parser não recursivo, Shift-Reduce, e Botton Up;
O Shift-Reduce é um $LL(k)$ com $k=0$.
Família LR
- SLR(1) – Simple LR Parser:
- Poucas gramáticas;
- Poucos estados, tabela simples;
- Simples e fácil, código e tabela.
- LR(1) – LR Parser:
- Todas as gramáticas LR(1);
- Muitos estados, tabela grande;
- Difícil, código e tabela.
- LALR(1) – Look-Ahead LR Parser:
- Trabalha com gramáticas intermediárias;
- Tantos estados quanto um SLR(1);
- Melhor usar uma ferramenta para criar.
Família LR - Obs.
Praticamente todas as linguagens de programação podem ser especificadas em uma gramática $LR(1)$;
Os algoritmos $LALR(1)$ e $SLR$ são variações do $LR(k)$;
$LALR(1)$ todas as linguagens "reais" e com aplicação prática. Usam menos memória no processo de interpretação;
Todas as variações ($SLR$, $LALR$, $LR$) usam o mesmo algoritmo mas com tabelas de formato diferente.
O formato da tabela define a dificuldade na criação do parser.
Comparação LL LR
Por quê LR(1)?
Podem ser construídos para qualquer linguagem de programação sobre uma gramática livre de contexto. Podemos criar gramáticas LR que não são livres de contexto, mas estas tem pouca ou nenhuma utilidade em Linguagens de Programação.
O algoritmo é um método de parsing sem backtracking, baseado em Shift-Reduce que pode ser implementado de forma mais eficiente, mantendo complexidade baixa.
Pode detectar erros de sintaxe assim que seja possível identificar estes erros fazendo uma varredura da esquerda para a direita.
A classe de gramáticas $LR$ é um subconjunto da classe $LL$.
Quando encontramos um problema
Como não temos nenhuma função para adivinhar o futuro, podemos usar o backtracking. A cada opção, mantemos uma árvore na memória, tentamos uma regra de produção. Se não der certo, voltamos até o ponto da opção e tentamos outra regra. Nem pensar!
Opcionalmente, podemos definir um prefixo viável, um prefixo de um handle que pode aparecer na pilha.
A ideia é construir uma $MEF$ para reconhecer os prefixos viáveis e, um ou dois tokens, do resto da string. Realizando a redução sempre que reconhecemos um token
Exemplo MEF - Enunciado
Considere o conjunto de regras de produção a seguir para a string: “abbcde” sem as aspas.
- $𝑆^′\rightarrow 𝑆\$$
- $𝑆 \rightarrow aABe$
- $𝐴 \rightarrow 𝐴b𝑐 | b$
- $𝐵 \rightarrow 𝑑$
Exemplo MEF - Explicação
| Pilha | Buffer | Operação |
|---|---|---|
| $\$$ | $abbcde\$$ | Shift |
| $a$ | $bbcde\$$ | Shift |
| $ab$ | $bcde\$$ | Reduce |
| $aA$ | $bcde\$$ | Shift |
| $aAb$ | $cde\$$ | Shift |
| $aAbc$ | $de\$$ | Reduce |
| $aA$ | $de\$$ | shift |
| $aAd$ | $e\$$ | Reduce |
| $aAB$ | $e\$$ | Shift |
| $aABe$ | $\$$ | Reduce |
| $S$ | $\$$ | Shift |
| $\$$ | $\$$ | Accept |
- $𝑆^′\rightarrow 𝑆\$$
- $𝑆 \rightarrow aABe$
- $𝐴 \rightarrow 𝐴b𝑐 | b$
- $𝐵 \rightarrow 𝑑$
A repetição é um problema!
A solução com a MEF inclui muitas repetições, voltamos ao estado inicial a cada nova avaliação da pilha;
Só alteramos a parte do string que corresponde ao Handle;
Nós queremos que complexidade seja $O(n)$ ou, idealmente $O(1)$;
Cada gramática irá requerer uma MEF diferente.
Exemplo MEF - LR(1)
Considere o conjunto de regras de produção a seguir para a string: “abbcde” sem as aspas.
- $𝑆^′\rightarrow 𝑆\$$
- $𝑆 \rightarrow aABe$
- $𝐴 \rightarrow 𝐴b𝑐 | b$
- $𝐵 \rightarrow 𝑑$
Exemplo MEF - LR(1): o porquê.
Considere o conjunto de regras de produção a seguir para a string: “abbcde” sem as aspas.
Ações
- linha = estado corrente;
- coluna = próximo terminal;
- $sn$ = shift; move a MFE para o estado $n$;
- $rn$ = reduce, usando a regra $n$;
- $acc$ = Accept, o string foi reconhecido
- vazio = erro de sintaxe;
Vai Para
- $linha$ = Estado corrente (topo da pilha, depois de um push não terminal);
- $coluna$ = Lado esquerdo da regra de redução (não-terminal);
- $gn$ = vai para a MEF no estado $n$;
- $vazio$ = fizemos algo errado na tabela de Vai Para
Exemplo MEF - LR(1): Passo 1.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$$ | $\$1$ | $abbcde\$$ |
Exemplo MEF - LR(1): Passo 2.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$a$ | $\$12$ | $bbcde\$$ |
Exemplo MEF - LR(1): Passo 3.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$ab$ | $\$124$ | $bcde\$$ |
Exemplo MEF - LR(1): Passo 4.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aA$ | $\$12$ | $bcde\$$ |
Exemplo MEF - LR(1): Passo 5.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aA$ | $\$123$ | $bcde\$$ |
Exemplo MEF - LR(1): Passo 6.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aAb$ | $\$1236$ | $cde\$$ |
Exemplo MEF - LR(1): Passo 7.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aAbc$ | $\$12367$ | $de\$$ |
Exemplo MEF - LR(1): Passo 8.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aA$ | $\$12$ | $de\$$ |
Exemplo MEF - LR(1): Passo 9.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aAd$ | $\$123$ | $de\$$ |
Exemplo MEF - LR(1): Passo 10.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aAb$ | $\$1235$ | $e\$$ |
Exemplo MEF - LR(1): Passo 11.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aAB$ | $\$123$ | $e\$$ |
Exemplo MEF - LR(1): Passo 12.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aABe$ | $\$1238$ | $e\$$ |
Exemplo MEF - LR(1): Passo 13.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$aABe$ | $\$12389$ | $\$$ |
Exemplo MEF - LR(1): Passo 14.
string: abbcde
| Pilha | Estados | Buffer |
|---|---|---|
| $\$S$ | $\$1$ | $\$$ |
Uma Nova Notação
Considere a regra $A \rightarrow XY$, podemos representar o progresso na regra.
- $A \rightarrow \cdot XY$
- $A \rightarrow X \cdot Y$
- $A \rightarrow XY \cdot$
O $\cdot$ representa o progresso de formação da regra no parser.
MEF - Revisada
Obras Citadas
AHO, A. V. et al.
Compiladores: princípios, técnicas e ferramentas.
2º. ed. Boston, MA, USA: Pearson Education Inc. , 2007.
CASS, S. The 2016 Top Programming Languages. IEEE
Spectrum, 2016. Disponível em:
Material de apoio
Você pode baixar o material de apoio clicando aqui
Obras Citadas
AHO, A. V. et al.
Compiladores: princípios, técnicas e ferramentas.
2º. ed. Boston, MA, USA: Pearson Education Inc. , 2007.
CASS, S. The 2016 Top Programming Languages. IEEE
Spectrum, 2016. Disponível em: