Ambiguidade & Parsers LR(1)

Frank Coelho de Alcantara -2021    

Exercício LL(1)

Considere o alfabeto $\Sigma = \{n, +, *, (, )\}$, o seguinte conjunto de Regras de produção e a Tabela D a seguir:

  1. $S \rightarrow TR$
  2. $R \rightarrow \varepsilon$
  3. $R \rightarrow +S$
  4. $T \rightarrow FG$
  5. $G \rightarrow \varepsilon$
  6. $G \rightarrow *T$
  7. $F \rightarrow n$
  8. $F \rightarrow (S)$
$n$ $+$ $*$ $($ $)$ $\$$
$S$ $1$ $ $ $ $ $1$ $ $ $ $
$R$ $ $ $3$ $2$ $ $ $2$ $2$
$T$ $4$ $ $ $ $ $4$ $ $ $ $
$G$ $ $ $5$ $6$ $ $ $5$ $5$
$F$ $7$ $ $ $ $ $8$ $ $ $ $

use para gerar a árvore sintática abstrata da string "n+n*n" sem as aspas.

Exercício LL(1) - Solução

  1. $S \rightarrow TR$
  2. $R \rightarrow \varepsilon$
  3. $R \rightarrow +S$
  4. $T \rightarrow FG$
  5. $G \rightarrow \varepsilon$
  6. $G \rightarrow *T$
  7. $F \rightarrow n$
  8. $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 * n$ Reduce ST R
   T R $ n + n * n $ Reduce TF G
   F G R $ n + n * n $ Reduce Fn
   n G R $ n + n * n $ Encontrei n
n G R $ + n * n $ Reduce G → ε
n R $ + n * n $ Reduce R+ S
n + S $ + n * n $ Encontrei +
n + S $ n * n $ Reduce ST R
n + T R $ n * n $ Reduce TF G
n + F G R $ n * n $ Reduce Fn
n + n G R $ n * n $ Encontrei n
n + n G R $ * n $ Reduce G* T
n + n *T R $ * n $ Encontrei *
n + n * T R $ n $ Reduce TF G
n + n * F G R $ n $ Reduce Fn
n + n * n G R $ n $ Encontre n
n + n * n G R $ $ Reduce G → ε
n + n * n R $ $ Reduce R → ε
n + n * n $ $ Fim

Só para Lembrar

Se uma declaração possui mais de uma derivação à esquerda, em uma determinada gramática, esta gramática é ambígua.

Se uma declaração possui mais de uma derivação à direita, em uma determinada gramática, esta gramática é ambígua.

A derivação à direita e a derivação à esquerda podem ser diferentes e, ainda assim, a gramática pode não ser ambígua.

A ambiguidade é caracterizada pela existência de árvores sintáticas diferentes para a mesma declaração.

Exemplo Clássico if-then-else

Considere a gramática a seguir:

  1. $STMT \rightarrow if \space EXPR \space then \space STMT \space else \space STMT$
  2. $\space\space\space\space\space\space\space\space |\space if \space EXPR \space then \space STMT$
  3. $\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

árvore sintática da gramática anterior árvore sintática da gramática anterior

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.

  1. $STMT \rightarrow WITHELSE \space\space |\space NOELSE$
  2. $WITHELSE \rightarrow if\space\space EXPR\space\space then\space\space WITHELSE\space\space else\space\space WITHELSE\space\space OUTROSTMT $
  3. $NOELSE \rightarrow if \space\space EXPR\space\space then\space\space STMT$
  4. $\space\space\space\space\space\space\space\space |\space if \space\space EXPR\space\space then\space\space WITHELSE\space\space else\space\space NOELSE$

Assim montamos if com else, ou sem, na ordem certa.

Bottom-UP Parser

símbolo meramente ilustrativo, sem valor didático

Classe de parsers que usa um ponteiro apontando para o próximo símbolo na string;

Varrem das folhas até a raiz;

Usam uma classe de gramática especial chamada de $LR(k)$;

Onde O $k$ representa o número de símbolos previsto.

Shift-Reduce Parser

símbolo meramente ilustrativo, sem valor didático
Um buffer para armazenar a string e uma pilha para as regras de produção;
Quatro operações: Shift, Reduce, Accept e Error;
É o parser mais simples da família $LR(k)$.

Exemplo Shift-Reduce

Considere e gramática a seguir para a string "n+n*n" sem as aspas.

  1. $𝑷=\{𝑺 \rightarrow 𝑺+S$;
  2. $𝑺 \rightarrow S*S$;
  3. $S \rightarrow (S)$;
  4. $S \rightarrow n \}$;
Tabela mostrando a derivação da gramática apresentada para a string: n+n*n

Shift-Reduce Parser

símbolo meramente ilustrativo, sem valor didático
$LR(k)$ L para da Esquerda para direita (from Left) e R para usar a redução mais a direita (Rightmost Reduction);
O $K$ indica quantos símbolos a frente;
É um parser não recursivo, Shift-Reduce, e Botton Up;
O Shift-Reduce é um $LR(k)$ com $k=0$.

Família LR

símbolo meramente ilustrativo, sem valor didático
  1. SLR(1) – Simple LR Parser:
    • Poucas gramáticas;
    • Poucos estados, tabela simples;
    • Simples e fácil, código e tabela.
  2. LR(1) – LR Parser:
    • Todas as gramáticas LR(1);
    • Muitos estados, tabela grande;
    • Difícil, código e tabela.
  3. 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.

símbolo meramente ilustrativo, sem valor didático
Todas as linguagens de programação podem ser especificadas em uma gramática $LR(1)$. Ou, praticamente todas;
Os algoritmos $LALR(1)$ e $SLR$ são variações do $LR(k)$;
$LALR(1)$ todas as linguagens reais, usando menos memória;
Todas as variações ($SLR$, $LALR$, $LR$) usam o mesmo algoritmo mas com tabelas de formato diferente.

Comparação LL LR

símbolo meramente ilustrativo, sem valor didático

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 e identificar estes erros fazendo uma varredura da esquerda para a direita.

A classe de gramáticas $LL$ é um subconjunto da classe $LR$.

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 é um handle que pode aparecer na pilha e permita a derivação.

A ideia é construir uma $MEF$ para reconhecer os prefixos viáveis destacando, 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.

símbolo meramente ilustrativo, sem valor didático
  1. $𝑆^′\rightarrow 𝑆\$$
  2. $𝑆 \rightarrow aABe$
  3. $𝐴 \rightarrow 𝐴b𝑐 | b$
  4. $𝐵 \rightarrow 𝑑$

Exemplo MEF - Explicação

símbolo meramente ilustrativo, sem valor didático
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
  1. $𝑆^′\rightarrow 𝑆\$$
  2. $𝑆 \rightarrow aABe$
  3. $𝐴 \rightarrow 𝐴b𝑐 | b$
  4. $𝐵 \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, no máximo, $O(n)$;

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.

tabela com os valores das ações da MEF para o LR(k)
  1. $𝑆^′\rightarrow 𝑆\$$
  2. $𝑆 \rightarrow aABe$
  3. $𝐴 \rightarrow 𝐴b𝑐 | b$
  4. $𝐵 \rightarrow 𝑑$

Exemplo MEF - LR(1): o porquê.

Considere o conjunto de regras de produção a seguir para a string: “abbcde” sem as aspas.

tabela com os valores das ações da MEF para o LR(k)

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

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$$ $\$1$ $abbcde\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 2.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$a$ $\$12$ $bbcde\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 3.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$ab$ $\$124$ $bcde\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 4.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aA$ $\$12$ $bcde\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 5.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aA$ $\$123$ $bcde\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 6.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aAb$ $\$1236$ $cde\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 7.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aAbc$ $\$12367$ $de\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 8.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aA$ $\$12$ $de\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 9.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aAd$ $\$123$ $de\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 10.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aAb$ $\$1235$ $e\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 11.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aAB$ $\$123$ $e\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 12.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aABe$ $\$1238$ $e\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 13.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$aABe$ $\$12389$ $\$$
tabela com os valores das ações da MEF para o LR(k)

Exemplo MEF - LR(1): Passo 14.

string: abbcde

tabela com os valores das ações da MEF para o LR(k)
Pilha Estados Buffer
$\$S$ $\$1$ $\$$
tabela com os valores das ações da MEF para o LR(k)

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

tabela com os valores das ações da MEF para o LR(k)