Gramáticas LR(0)

Tal como antes para as gramáticas LL, o interesse aqui está nas gramáticas LR(1) porém o caso LR(0) é importante como introdução para o processo de construção do analisador sintático.

• Gramáticas LR(0)
  • Contextos LR(0)
  • Itens LR(0)
  • Autómato Finito dos Itens LR(0) Válidos
  • Analisador Sintático LR(0)
  • Tabela de Análise Sintática LR(0)
  • Autómato de Pilha LR(0)
  • Conclusão

Contextos LR(0)

Problema. Quando é que uma produção pode ser aplicada numa derivação "válida"?

Isto é, será possível determinar quando a aplicação de uma produção numa derivação contribui para uma palavra gerada pela gramática das outras aplicações, em que o resultado não é gerado pela gramática?

No caso das derivações direitas

Contexto-LR(0). Prefixo Viável. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC com terminador $\#$ e em que $S$ não é recursivo.

• A palavra $up\in {\left(V\cup \Sigma \right)}^{\ast }$ é um Contexto-LR(0) da produção $A\to p$ se existir uma derivação direita $$S\stackrel{\ast }{{\Rightarrow }_R}uAv{\Rightarrow }_{R}upv,v\in {\Sigma }^{\ast }.$$

  • Isto é, há uma redução $upv{\stackrel{\ast }{\Leftarrow }}_{R}S$ que começa por $A\to p$.

• Um prefixo viável é um prefixo de um contexto-LR(0).

• Dada uma produção, o conjunto dos seus contextos-LR(0) é uma linguagem regular.

N.B. Na definição acima é importante ter presente que se tratam de derivações direitas. Portanto, quando $A\to p$ é aplicada em $uAv$:

• O sufixo $v$ é formado só por terminais.
• O prefixo $u$ é o "contexto" para a aplicação da regra $A\to p$.

Intuitivamente pretende-se que os Contextos-LR(0) tenham informação suficiente para determinar que produção aplicar em cada passo de uma derivação. Isto é, se os Contextos-LR(0) forem disjuntos tem-se um método determinista para fazer derivações direitas.

Por exemplo, dada a GIC $$\begin{array}{rl}S& \to aA|aB\\ A& \to aAb|b\\ B& \to bBa|b\end{array}$$

As derivações direitas têm uma das seguintes formas

$$\begin{array}{rlrlrlrlr}S& \stackrel{S\to aA}{{\Rightarrow }_R}& aA& \stackrel{A\to aAb}{{\Rightarrow }_R}& \dots & \stackrel{A\to aAb}{{\Rightarrow }_R}& a{a}^{n}A{b}^n& \stackrel{A\to b}{{\Rightarrow }_R}& a{a}^{n}b{b}^n\\ S& \stackrel{S\to aB}{{\Rightarrow }_R}& aB& \stackrel{B\to aBa}{{\Rightarrow }_R}& \dots & \stackrel{B\to bBa}{{\Rightarrow }_R}& a{b}^{n}B{a}^n& \stackrel{B\to b}{{\Rightarrow }_R}& a{b}^{n}b{a}^n\end{array}$$

pelo que os Contextos-LR(0) das produções são:

$$\begin{array}{lr}\text{produc¸a˜o}& \text{Contexto-LR(0)}\\ S\to aA& \left\{aA\right\}\\ S\to aB& \left\{aB\right\}\\ A\to aAb& \left\{a^{n}aAb:n>0\right\}\\ A\to b& \left\{a{a}^{n}b:n\ge 0\right\}\\ B\to bBa& \left\{a{b}^{n}bBa:n\ge 0\right\}\\ B\to b& \left\{a{b}^{n}b:n\ge 0\right\}\end{array}$$

Neste caso, $ab$ é um contexto-LR(0) tanto de $A\to b$ como de $B\to b$ (com $n=0$ em ambos os casos).

O que é que isto significa? Quando se procura descobrir como $ab$ poderá ter sido derivada à esquerda, há duas possibilidades:

• Ou $S\stackrel{S\to aA}{{\Rightarrow }_R}aA\stackrel{A\to b}{{\Rightarrow }_R}ab$.
• Ou $S\stackrel{S\to aB}{{\Rightarrow }_R}aB\stackrel{B\to b}{{\Rightarrow }_R}ab$.

Isto é, em $ab$ não "há informação suficiente" para saber qual foi a última produção aplicada, $A\to b$ ou $B\to b$.

Considerando agora a GIC

$$\begin{array}{rl}S& \to X\#\\ X& \to XY|\lambda \\ Y& \to aYa|b\end{array}$$

os contextos-LR(0) são:

$$\begin{array}{lr}S\to X\#& X\#\\ X\to XY& XY\\ X\to \lambda & \lambda \\ Y\to aYa& X{a}^{\ast }aYa\\ Y\to b& X{a}^{\ast }b\end{array}$$

Os contextos-LR(0) podem ser descobertos explorando a árvore das derivações direitas:

Árvore das Derivações Direitas
Os contextos-LR(0) estão sublinhados.

Agora, para encontrar uma derivação de $aabaa\#$:

1. O maior prefixo de $aabaa\#$ que é um contexto-LR(0) é $\lambda$, de $X\to \lambda$.
2. Portanto, a produção aplicada foi $X\to \lambda$, à palavra $Xaabaa\#$.
3. O maior prefixo de $Xaabaa\#$ que é um contexto-LR(0) é $Xaab$, de $Y\to b$.
4. Portanto, foi aplicada $Y\to b$ a $XaaYaa\#$.
5. O maior prefixo de $XaaYaa\#$ que é um contexto-LR(0) é $XaaYa$, de $Y\to aYa$.
6. Portanto, foi aplicada $Y\to aYa$ a $XaYa\#$.
7. O maior prefixo de $XaYa\#$ que é um contexto-LR(0) é $XaYa$, de $Y\to aYa$.
8. Portanto, foi aplicada $Y\to aYa$ a $XY\#$.
9. O maior prefixo de $XY\#$ que é um contexto-LR(0) é $XY$, de $X\to XY$.
10. Portanto, foi aplicada $X\to XY$ a $X\#$.
11. O maior prefixo de $X\#$ que é um contexto-LR(0) é $X\#$, de $S\to X\#$.
12. Portanto, foi aplicada $S\to X\#$ e a derivação está encontrada:

$$S\stackrel{S\to X\#}{{\Rightarrow }_R}X\#\stackrel{X\to XY}{{\Rightarrow }_R}XY\#\stackrel{Y\to aYa}{{\Rightarrow }_R}XaYa\#\stackrel{Y\to aYa}{{\Rightarrow }_R}XaaYaa\#\stackrel{Y\to b}{{\Rightarrow }_R}Xaabaa\#\stackrel{X\to \lambda }{{\Rightarrow }_R}aabaa\#$$

Note-se que:

1. Foi encontrada uma derivação direita (rightmost derivation).
2. A "pilha" é lida da esquerda-para-a-direita (left-to-right).
3. O processo encontra a derivação em reverso (in reverse).

A derivação anterior pode ser organizada numa tabela com quatro tipos de ações:

• Reduzir $A\to w$ quando a pilha tem um Contexto-LR(0) de $A\to w$.
• Transferir o primeiro símbolo da palavra para a pilha, quando a pilha tem um prefixo viável que não é um Contexto-LR(0).
• Aceitar quando a pilha é $S$ e a palavra $\lambda$.
• Rejeitar quando a pilha não é um prefixo viável.

O resultado é: $$\begin{array}{rlcl}\text{pilha}& \text{palavra}& \text{Contexto}& \text{ac¸a˜o}\\ \lambda & aabaa\#& X\to \lambda & R\\ X& aabaa\#& \text{viaˊvel}& T\\ Xa& abaa\#& \text{viaˊvel}& T\\ Xaa& baa\#& \text{viaˊvel}& T\\ Xaab& aa\#& Y\to b& R\\ XaaY& aa\#& \text{viaˊvel}& T\\ XaaYa& a\#& Y\to aYa& R\\ XaY& a\#& \text{viaˊvel}& T\\ XaYa& \#& T\to aYa& R\\ XY& \#& X\to XY& R\\ X& \#& \text{viaˊvel}& T\\ X\#& \lambda & S\to X\#& R\\ S& \lambda & & \text{aceitar}\end{array}$$

A derivação de $aabaa\#$ pode ser recuperada da coluna "ação", lida em reverso.

Para procurar uma derivação de $abb\#$, que não é gerada pela gramática: $$\begin{array}{rlcl}\text{pilha}& \text{palavra}& \text{Contexto}& \text{ac¸a˜o}\\ \lambda & abb\#& X\to \lambda & R\\ X& abb\#& \text{viaˊvel}& T\\ Xa& bb\#& \text{viaˊvel}& T\\ Xab& b\#& Y\to b& R\\ XaY& b\#& \text{viaˊvel}& T\\ XaYb& \#& \text{inviaˊvel}& \text{rejeitar}\end{array}$$

Itens LR(0)

Os exemplos acima ilustram a utilidade dos contextos-LR(0) para a análise sintática. Embora não sejam facilmente encontrados a partir da definição, o conjunto dos Contextos-LR(0) de uma produção é uma linguagem regular que pode ser definida por um certo autómato finito determinista.

Para definir esse AFD é preciso começar pelos seus estados:

Item LR(0). Seja $G=\left(V,\Sigma ,P,V\right)$ uma GIC.

• Os itens LR(0) de $G$ são as "produções" que se obtêm de $P$ acrescentado um $\cdot$ em todas as posições possíveis:
  • Se $A\to \lambda \in P$ então $A\to \cdot$ é um item LR(0) de $G$.
  • Se $A\to uv\in P$ então $A\to u\cdot v$ é um item LR(0) de $G$.
• Um item completo é um item em que o $\cdot$ está o mais à direita possível.
• Um item $A\to u\cdot v$ é válido para o prefixo viável $xu$ se $xuv$ é um contexto LR(0); Isto é, se $A\to uv$ é candidato a reduzir.

Usando a gramática do exemplo anterior, os seus itens LR(0) são $$\begin{array}{rlrlrlrl}S& \to \cdot X\#& S& \to X\cdot \#& S& \to X\#\cdot & & \\ X& \to \cdot XY& X& \to X\cdot Y& X& \to XY\cdot & & \\ X& \to \cdot & & & & & & \\ Y& \to \cdot aYa& Y& \to a\cdot Ya& Y& \to aY\cdot a& Y& \to aYa\cdot \\ Y& \to \cdot b& Y& \to b\cdot & & & & \end{array}$$ com os itens completos assinalados assim: $A\to p\cdot$.

Fecho. Seja $I$ um conjunto de itens. O fecho de $I$, denotado $\text{fecho}\left(I\right)$ define-se recursivamente por:

• base $I\subseteq \text{fecho}\left(I\right)$.
• passo Se $A\to u\cdot Bv\in \text{fecho}\left(I\right)$ com $B\in V$ então, para cada produção $B\to p\in P$, também $B\to \cdot p\in \text{fecho}\left(I\right)$.

Por exemplo, usando a gramática anterior,

$$\text{fecho}\left(X\to X\cdot Y\right)=\left\{X\to X\cdot Y,Y\to \cdot aYa,Y\to \cdot b\right\}$$

Autómato Finito dos Itens LR(0) Válidos

Os fechos dos itens são usado para construir um autómato finito que determina a ação nas tabelas acima.

Autómato dos Itens Válidos (AIV). Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC. O autómato dos itens válidos, que reconhece os prefixos viáveis de $G$ é o AFD $A=\left(Q,V\cup \Sigma ,\delta ,q_I,Q\setminus \left\{\varnothing \right\}\right)$ em que:

• estado inicial $q_I=\text{fecho}\left(\left\{S\to \cdot p:S\to p\in P\right\}\right)$.
• transição Para cada $q\in Q$ e $x\in V\cup \Sigma$

$$\delta \left(q,x\right)=\text{fecho}\left(\left\{A\to ux\cdot v:A\to u\cdot xv\in q\right\}\right)$$

Continuando com a gramática anterior, o seu autómato dos itens válidos tem os seguintes estados e transição:

$$\begin{array}{cclcc}\text{estado}& \exists \text{completo}?& \text{itens}& \text{sıˊmbolo}& \text{para}\\ 0& ✓& S\to \cdot X\#,X\to \cdot XY,X\to \cdot & & \\ & & & X& 1\\ 1& & S\to X\cdot \#,X\to X\cdot Y,Y\to \cdot aYa,Y\to \cdot b& & \\ & & & \#& 2\\ & & & Y& 3\\ & & & a& 4\\ & & & b& 5\\ 2& ✓& S\to X\#\cdot & & \\ 3& ✓& X\to XY\cdot & & \\ 4& & Y\to a\cdot Ya,Y\to \cdot aYa,Y\to \cdot b& & \\ & & & Y& 6\\ & & & a& 4\\ & & & b& 5\\ 5& ✓& Y\to b\cdot & & \\ 6& & Y\to aY\cdot a& & \\ & & & a& 7\\ 7& ✓& Y\to aYa\cdot & & \end{array}$$

Note-se que há mais um estado, $\varnothing$, que não se representa e que recebe todas as transições que não estão especificadas.

Este AFD pode ser representado numa tabela mais convencional (todas as transições não assinaladas vão para $\varnothing$):

$$\begin{array}{rcccccc}q& S& X& Y& a& b& \#\\ if0& & 1& & & & \\ f1& & & 3& 4& 5& 2\\ f2& & & & & & \\ f3& & & & & & \\ f4& & & 6& 4& 5& \\ f5& & & & & & \\ f6& & & & 7& & \\ f7& & & & & & \\ \varnothing & & & & & & \end{array}$$

Porém, pode ser mais simples calcular graficamente os estados e a transição do autómato dos itens válidos.

Diagrama do Autómato dos Itens Válidos
Em cada estado os itens completos são assinalados com $\star$. O estado $\varnothing$ não está representado.

Neste diagrama cada estado tem dois ou três "andares". De cima para baixo:

1. O "nome" do estado, um inteiro $0,1,\dots$
2. A "raiz" dos itens, que resultam da transição.
3. Restantes itens, para se obter o fecho da "raiz".

Analisador Sintático LR(0)

O Autómato dos itens válidos serve para determinar a ação na derivação. Em cada passo o AIV processa a pilha e a ação é:

• Aceitar se a pilha tem apenas $S$.
• Reduzir se terminar num estado com um item completo. Nesse caso a redução é da produção do item completo.
• Transferir o próximo símbolo da palavra se terminar num estado sem itens completos.
• Rejeitar se não puder processar a palavra (isto é, vai parar a $\varnothing$).

Recuperando o exemplo anterior, o processamento de $aabaa\#$ é:

$$\begin{array}{rlcl}\text{pilha}& \text{palavra}& \text{estado AIV}& \text{ac¸a˜o}\\ \lambda & aabaa\#& 0& R:X\to \lambda \\ X& aabaa\#& 1& T\\ Xa& abaa\#& 4& T\\ Xaa& baa\#& 4& T\\ Xaab& aa\#& 5& R:Y\to b\\ XaaY& aa\#& 6& T\\ XaaYa& a\#& 7& R:Y\to aYa\\ XaY& a\#& 6& T\\ XaYa& \#& 7& R:T\to aYa\\ XY& \#& 3& R:X\to XY\\ X& \#& 1& T\\ X\#& \lambda & 2& R:S\to X\#\\ S& \lambda & & \text{aceitar}\end{array}$$

enquanto que para $abb\#$, que não é gerada pela gramática: $$\begin{array}{rlcl}\text{pilha}& \text{palavra}& \text{estado AIV}& \text{ac¸a˜o}\\ \lambda & abb\#& 0& R:X\to \lambda \\ X& abb\#& 1& T\\ Xa& bb\#& 4& T\\ Xab& b\#& 5& R:Y\to b\\ XaY& b\#& 6& T\\ XaYb& \#& \varnothing & \text{rejeitar}\end{array}$$

Tabela de Análise Sintática LR(0)

A tabela de análise sintática (TAS) estende a transição do AIV com as ações associadas aos respetivos estados. Tem uma linha para cada estado e uma coluna para cada símbolo de $V\cup \Sigma$. Além disso tem também uma coluna, $\text{ac¸a˜o}$, que indica que ação corresponde a um prefixo que termine nesse estado.

Para a gramática que tem vindo a servir de exemplo, a TAS é:

$$\begin{array}{rccccccl}q& S& X& Y& a& b& \#& \text{ac¸a˜o}\\ 0& & 1& & & & & R:X\to \lambda \\ 1& & & 3& 4& 5& 2& T\\ 2& & & & & & & A\\ 3& & & & & & & R:X\to XY\\ 4& & & 6& 4& 5& & T\\ 5& & & & & & & R:Y\to b\\ 6& & & & 7& & & T\\ 7& & & & & & & R:Y\to aYa\end{array}$$

Nesta tabela:

• O estado $\varnothing$, a que corresponde a ação "rejeitar", não é representado e portanto todos os estados mostrados na TAS são finais.
• As transições não representadas levam ao estado $\varnothing$.
• Por convenção, o estado $0$ é o inicial.
• Nos estados com itens completos do símbolo inicial da GIC (no exemplo acima, o estado $2$) a ação é "aceitar", $A$, em vez de ser "reduzir", $R$.

Dado que a coluna $\text{ac¸a˜o}$ determina se no analisador sintático é feita uma transferência ou uma redução (e nesse caso, de que produção), se essa informação for ambígua não é possível fazer análise sintática determinista LR(0).

Portanto é necessário que cada estado defina exatamente uma ação.

Como as reduções são feitas em estados com itens completos (por exemplo, os estados $0,2,3,5,7$ acima) e as transferência são feitas em estados de que sai alguma "aresta com um terminal" (os estados $1,4,6$ acima), as ambiguidades (conflitos) possíveis são:

• Conflito Redução/Redução LR(0): Se num estado estiverem dois itens completos então esse estado define duas reduções possíveis.
• Conflito Redução/Transferência LR(0): Se num estado com um item completo sair uma aresta "com um terminal" então esse estado define uma redução e uma transferência.

Estas condições permitem caraterizar as gramáticas LR(0):

Teorema das Gramáticas LR(0). Uma GIC é LR(0) se e só se o seu AIV não tem conflitos redução/redução LR(0) nem redução/transferência LR(0).

Autómato de Pilha LR(0)

Pretende-se não só fazer análise sintática determinista mas também que esta seja livre de passos manuais (human in the middle). O AIV proporciona dois passos desse processo:

• Determina se a GIC dada é LR(0).
• Define a ação em cada passo do analisador sintático.

Falta definir formalmente o processamento do próprio analisador sintático, o que será feito com um autómato de pilha.

Autómato de Pilha Reconhecedor LR(0). Seja $G=(V,\Sigma ,P,S)$ uma GIC LR(0) e $A=(Q,V\cup \Sigma ,{\delta }_A,0,Q\setminus \left\{\varnothing \right\})$ o seu AIV. O Autómato de Pilha Reconhecedor (APR) de $G$, que reconhece a linguagem gerada por $G$, é $$R=\left(\left\{p_I,p\right\},\Sigma ,V\cup \Sigma \cup Q\setminus \left\{\varnothing \right\},\delta ,p_I,\left\{p\right\}\right)$$ em que a transição, $\delta$, é definida pelos seguintes elementos:

• iniciar: $\left(p,0\right)\in \delta \left(p_I,\lambda ,\lambda \right)$.
• transferir: $\left(p,q^{\prime }aq\right)\in \delta \left(p,a,q\right)$ se $q^{\prime }={\delta }_A\left(q,a\right)$ com $a\in \Sigma$.
• reduzir: Para cada estado $q_n\in Q$ com um item completo $A\to a_1{a}_2\cdots a_n\cdot$ com $A\ne S$ e $q^{\prime }={\delta }_A\left(q_0,A\right)$, $\left(p,q^{\prime }A{q}_0\right)\in \delta \left(p,\lambda ,q_n{a}_n\cdots q_2{a}_2{q}_1{a}_1{q}_0\right)$ quando no AIV existe a computação $$q_0\stackrel{a_1}{⊢}{q}_1\stackrel{a_2}{⊢}{q}_2\cdots \stackrel{a_n}{⊢}{q}_n.$$
• aceitar: Para cada estado $q_n\in Q$ com um item completo $S\to a_1{a}_2\cdots a_n\cdot$ do símbolo inicial da GIC, $\left(p,\lambda \right)\in \delta \left(p,\lambda ,q_n{a}_n\cdots q_2{a}_2{q}_1{a}_{1}0\right)$ quando no AIV existe a computação $$0\stackrel{a_1}{⊢}{q}_1\stackrel{a_2}{⊢}\cdots \stackrel{a_n}{⊢}{q}_n.$$

Intuitivamente a pilha do APR intercala estados do AIC com símbolos de $V\cup \Sigma$ de forma a descrever "fragmentos de computação do AIV". Por exemplo, a computação de $abb\#$ $$\begin{array}{rlclrrr}\text{pilha}& \text{palavra}& \text{estado AIV}& \text{ac¸a˜o}& \text{pilha APR}& \text{topo: de}& \text{topo: para}\\ \lambda & abb\#& 0& R:X\to \lambda & 0& 0& 1X0\\ X& abb\#& 1& T& 1X0& 1& 4a1\\ Xa& bb\#& 4& T& 4a1X0& 4& 5b4\\ Xab& b\#& 5& R:Y\to b& 5b4a1X0& 5b4& 6Y4\\ XaY& b\#& 6& T& 6Y4a1X0& 6& \varnothing b6\\ XaYb& \#& \varnothing & \text{rejeitar}& \varnothing b6Y4a1X0& & \end{array}$$ enquanto que de $aabaa\#$ é: $$\begin{array}{rlclr}\text{pilha}& \text{palavra}& \text{estado AIV}& \text{ac¸a˜o}& \text{pilha APR}\\ \lambda & aabaa\#& 0& R:X\to \lambda & 0\\ X& aabaa\#& 1& T& 1X0\\ Xa& abaa\#& 4& T& 4a1X0\\ Xaa& baa\#& 4& T& 4a4a1X0\\ Xaab& aa\#& 5& R:Y\to b& 5b4a4a1X0\\ XaaY& aa\#& 6& T& 6Y4a4a1X0\\ XaaYa& a\#& 7& R:Y\to aYa& 7a6Y4a4a1X0\\ XaY& a\#& 6& T& 6Y4a1X0\\ XaYa& \#& 7& R:T\to aYa& 7a6Y4a1X0\\ XY& \#& 3& R:X\to XY& 3Y1X0\\ X& \#& 1& T& 1X0\\ X\#& \lambda & 2& R:S\to X\#& 2\#1X0\\ S& \lambda & & \text{aceitar}& \lambda \end{array}$$

Estes exemplos ilustram como o topo da pilha determina a transição do APR: O primeiro símbolo identifica o estado do AIV e este define ou uma transferência ou uma redução (incluindo o caso particular da aceitação).

• No caso de reduzir (ou aceitar) são considerados mais símbolos da pilha, de forma a "capturar" todo o lado direito da produção, que é substituído pela respetiva variável.
• No caso da operação ser uma transferência o terminal da palavra é comparado com a parte correspondente na pilha e, se coincidirem, ambos são "consumidos".

Neste processo é mantido o registo dos estados do AIV percorridos pelas respetivas computações.

Alternativamente as transições do APR podem ser definidas pela seguinte tabela:

$$\begin{array}{lllcr}\text{Operac¸a˜o}& \text{Condic¸a˜o}& \text{De}& \text{Aresta}& \text{Para}\\ \text{Iniciar}& & & & \\ & & p_I& \lambda ,\lambda /0& p\\ & & & & \\ \text{Transferir}& & & & \\ & q^{\prime }={\delta }_A\left(q,a\right)& p& a,q/q^{\prime }aq& p\\ & & & & \\ \text{Reduzir}& & & & \\ & A\to a_1\cdots a_n\cdot \star \in q& p& \lambda ,\alpha /\beta & p\\ & A\ne S& & & \\ & & & & \\ & q_0\stackrel{a_1}{⊢}\cdots \stackrel{a_n}{⊢}{q}_n,q_n=q& & & \\ & \alpha =q_n{a}_n\cdots a_1{q}_0& & & \\ & & & & \\ & q_0\stackrel{A}{⊢}{q}^{\prime }& & & \\ & \beta =q^{\prime }A{q}_0& & & \\ & & & & \\ \text{Aceitar}& & & & \\ & S\to a_1\cdots a_n\cdot \star \in q& p& \lambda ,\alpha /\lambda & p\\ & & & & \\ & 0\stackrel{a_1}{⊢}\cdots \stackrel{a_n}{⊢}{q}_n,q_n=q& & & \\ & \alpha =q_n{a}_n\cdots a_{1}0& & & \end{array}$$

Por exemplo para a GIC anterior, com a TAS (calculada acima, repetida aqui)

$$\begin{array}{rccccccl}q& S& X& Y& a& b& \#& \text{ac¸a˜o}\\ 0& & 1& & & & & R:X\to \lambda \\ 1& & & 3& 4& 5& 2& T\\ 2& & & & & & & A\\ 3& & & & & & & R:X\to XY\\ 4& & & 6& 4& 5& & T\\ 5& & & & & & & R:Y\to b\\ 6& & & & 7& & & T\\ 7& & & & & & & R:Y\to aYa\end{array}$$ as transições do APR são:

• iniciar $\lambda ,\lambda /0$ é a única transição $p_I\to p$.

• transferir Estas transições são $p⊢p$:

  $$\begin{array}{lr}\text{AIV: Computac¸a˜o}& \text{APR: Transic¸a˜o}\\ 1\stackrel{a}{⊢}4& a,1/4a1\\ 1\stackrel{b}{⊢}5& b,1/5b1\\ 1\stackrel{\#}{⊢}2& \#,1/2\#1\\ 4\stackrel{a}{⊢}4& a,4/4a4\\ 4\stackrel{b}{⊢}5& b,4/5b4\\ 6\stackrel{a}{⊢}7& a,6/7a6\end{array}$$

• reduzir Estas transições são $p⊢p$:

  $$\begin{array}{lllr}\text{AIV: Estado}& \text{AIV: Item completo de}A\ne S& \text{AIV: Computac¸a˜o}& \text{APR: Transic¸a˜o}\\ 0& X\to \lambda \cdot & 0& \lambda ,0/1X0\\ 3& X\to XY\cdot & 0\stackrel{X}{⊢}1\stackrel{Y}{⊢}3& \lambda ,3Y1X0/1X0\\ 5& Y\to b\cdot & 1\stackrel{b}{⊢}5& \lambda ,5b1/3Y1\\ & & 4\stackrel{b}{⊢}5& \lambda ,5b4/6Y4\\ 7& Y\to aYa\cdot & 1\stackrel{a}{⊢}4\stackrel{Y}{⊢}6\stackrel{a}{⊢}7& \lambda ,7a6Y4a1/3Y1\\ & & 4\stackrel{a}{⊢}4\stackrel{Y}{⊢}6\stackrel{a}{⊢}7& \lambda ,7a6Y4a4/6Y4\end{array}$$

• aceitar Estas transições são $p⊢p$:

  $$\begin{array}{lllr}\text{AIV: Estado}& \text{AIV: Item completo de}S& \text{AIV: Computac¸a˜o}& \text{APR: Transic¸a˜o}\\ 2& S\to X\#\cdot & 0\stackrel{X}{⊢}1\stackrel{\#}{⊢}2& \lambda ,2\#1X0/\lambda \end{array}$$

O diagrama do APR é:

Diagrama do APR
As transições para transferir estão no ciclo superior, aceitar no direito e reduzir no inferior.

O APR replica os passos (informais) do analisador sintático. A computação de $abb\#$ pelo APR é:

$$\begin{array}{crlll}\text{Estado}& \text{Pilha}& \text{Entrada}& \text{Transic¸a˜o}& \text{Ac¸a˜o}\\ p_I& \lambda & abb\#& \lambda ,\lambda /0& \text{iniciar}(p_I⊢p)\\ p& 0& abb\#& \lambda ,0/1X0& \text{reduzir}X\to \lambda \\ p& 1X0& abb\#& a,1/4a1& \text{transferir}\\ p& 4a1X0& bb\#& b,4/5b4& \text{transferir}\\ p& 5b4a1X0& b\#& \lambda ,5b4/6Y4& \text{reduzir}Y\to b\\ p& 6Y4a1X0& b\#& \varnothing & \text{rejeitar}\end{array}$$ e pára porque atinge uma configuração sem transições definidas (o topo é $6$ e o símbolo da entrada é $b$). Por outro lado a computação de $aabaa\#$ é: $$\begin{array}{crlll}\text{Estado}& \text{Pilha}& \text{Entrada}& \text{Transic¸a˜o}& \text{Ac¸a˜o}\\ p_I& \lambda & aabaa\#& \lambda ,\lambda /0& \text{iniciar}(p_I⊢p)\\ p& 0& aabaa\#& \lambda ,0/1X0& \text{reduzir}X\to \lambda \\ p& 1X0& aabaa\#& a,1/4a1& \text{transferir}\\ p& 4a1X0& abaa\#& a,4/4a4& \text{transferir}\\ p& 4a4a1X0& baa\#& b,4/5b4& \text{transferir}\\ p& 5b4a4a1X0& aa\#& \lambda ,5b4/6Y4& \text{reduzir}Y\to b\\ p& 6Y4a4a1X0& aa\#& a,6/7a6& \text{transferir}\\ p& 7a6Y4a4a1X0& a\#& \lambda ,7a6Y4a4/6Y4& \text{reduzir}Y\to aYa\\ p& 6Y4a1X0& a\#& a,6/7a6& \text{transferir}\\ p& 7a6Y4a1X0& \#& \lambda ,7a6Y4a1/3Y1& \text{reduzir}Y\to aYa\\ p& 3Y1X0& \#& \lambda ,3Y1X0/1X0& \text{reduzir}X\to XY\\ p& 1X0& \#& \#,1/2\#1& \text{transferir}\\ p& 2\#1X0& \lambda & \lambda ,2\#1X0/\lambda & \text{aceitar}S\to X\#\\ p& \lambda & \lambda & & \end{array}$$ e termina numa configuração com um estado final e com a pilha e a entrada ambas vazias. Neste caso, lendo em reverso as produções obtém-se a derivação direita da palavra dada: $$S\stackrel{S\to X\#}{{\Rightarrow }_R}X\#\stackrel{X\to XY}{{\Rightarrow }_R}XY\#\stackrel{Y\to aYa}{{\Rightarrow }_R}XaYa\#\stackrel{Y\to aYa}{{\Rightarrow }_R}XaaYaa\#\stackrel{Y\to b}{{\Rightarrow }_R}Xaabaa\#\stackrel{X\to \lambda }{{\Rightarrow }_R}aabaa\#$$

Este exemplo ilustra o tratamento "automático" da análise sintática das gramáticas LR(k).

• Dada uma GIC, a construção do AIV e a respetiva TAS permite determinar se a GIC é, ou não LR(0).
• Se o for, a TAS é usada para construir o APR que reconhece a linguagem gerada pela GIC.
• Além disso, o processamento de uma palavra aceite pelo APR permite encontrar a derivação direita dessa palavra.
• Em todo este processo, desde a construção do AIV e da TAS, do APR e a computação de palavras os algoritmos são eficientes (isto é, o número de passos é polinomial no tamanho do input.)

Resta saber se as gramáticas LR(0) são adequadas.

Considerando a seguinte gramática de expressões algébricas simplificadas:

$$\begin{array}{rl}S& \to E\#\\ E& \to E+T|T\\ T& \to T\times F|F\\ F& \to n|(E)\end{array}$$

Na construção do AIV desta GIC o estado inicial tem os seguintes itens:

$$\begin{array}{rl}& 0\\ S& \to \cdot E\#\\ E& \to \cdot E+T\\ E& \to \cdot T\\ T& \to \cdot T\times F\\ ⋮& \end{array}$$

Deste estado sai uma aresta $T$ que leva a um novo estado com os seguintes itens $$\begin{array}{rlr}& ?& \\ E& \to T\cdot & \star \\ T& \to T\cdot \times F& \\ ⋮& & \end{array}$$ onde existe um conflito redução/transferência (a redução de $E\to T$ com a transferência de $\times$).

Este exemplo mostra que as gramáticas LR(0) são demasiado simples para definir expressões algébricas e portanto não são adequadas para definir as linguagens de programação.

A solução para este problema consiste em "adaptar" a ideia das gramática LL(1), considerando os símbolos de avanço, ao processo das gramáticas LR(0).

Conclusão

• O que conseguimos resolver
• O que falta resolver.