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.

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=\del{V, \Sigma, P, S}$ uma GIC com terminador $\#$ e em que $S$ não é recursivo.

A palavra $\alert{up} \in \clpar{V \cup \Sigma}$ é um Contexto-LR(0) da produção $A \to p$ se existir uma derivação direita $$S \iderR uAv \derR \alert{up}v, v \in \cl{\Sigma}.$$

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{aligned} S &\to aA \alt aB \cr A &\to aAb \alt b \cr B &\to bBa \alt b \end{aligned} $$

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

$$ \begin{aligned} S &\nderR{S \to aA} &aA &\nderR{A\to aAb} &\ldots &\nderR{A\to aAb} &aa^n A b^n &\nderR{A \to b} &aa^n bb^n \cr S &\nderR{S \to aB} &aB &\nderR{B\to aBa} &\ldots &\nderR{B\to bBa} &ab^n B a^n &\nderR{B \to b} &ab^n ba^n \end{aligned} $$

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

$$ \begin{array}{lr} \text{produção} & \text{Contexto-LR(0)} \cr \hline S \to aA & \set{aA} \cr S \to aB & \set{aB} \cr A \to aAb & \set{a^naAb \st n > 0} \cr A \to b & \set{aa^n b \st n \geq 0} \cr B \to bBa & \set{ab^nbBa \st n \geq 0} \cr B \to b & \set{ab^nb \st n \geq 0} \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 à direita, há duas possibilidades:

Ou $S \nderR{S \to aA} aA \nderR{A \to b} ab$.
Ou $S \nderR{S \to aB} aB \nderR{B \to b} 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{aligned} S &\to X\# \cr X &\to XY \alt \nil \cr Y &\to aYa \alt b \end{aligned} $$ os contextos-LR(0) são: $$ \begin{array}{lr} S \to X\# & X\# \cr X \to XY & XY \cr X \to \nil & \nil \cr Y \to aYa & X\cl{a} aYa\cr Y \to b & X\cl{a}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\#$:

O maior prefixo de $aabaa\#$ que é um contexto-LR(0) é $\nil$, de $X \to \nil$.
Portanto, a produção aplicada foi $X \to \nil$, à palavra $Xaabaa\#$.
O maior prefixo de $Xaabaa\#$ que é um contexto-LR(0) é $Xaab$, de $Y \to b$.
Portanto, foi aplicada $Y \to b$ a $XaaYaa\#$.
O maior prefixo de $XaaYaa\#$ que é um contexto-LR(0) é $XaaYa$, de $Y \to aYa$.
Portanto, foi aplicada $Y \to aYa$ a $XaYa\#$.
O maior prefixo de $XaYa\#$ que é um contexto-LR(0) é $XaYa$, de $Y \to aYa$.
Portanto, foi aplicada $Y \to aYa$ a $XY\#$.
O maior prefixo de $XY\#$ que é um contexto-LR(0) é $XY$, de $X \to XY$.
Portanto, foi aplicada $X \to XY$ a $X\#$.
O maior prefixo de $X\#$ que é um contexto-LR(0) é $X\#$, de $S \to X\#$.
Portanto, foi aplicada $S \to X\#$ e a derivação está encontrada:

$$ S \nderR{S \to X\#} X\# \nderR{X \to XY} XY \# \nderR{Y \to aYa} XaYa\# \nderR{Y \to aYa} XaaYaa\# \nderR{Y \to b} Xaabaa\# \nderR{X \to \nil} aabaa\# $$

Note-se que:

Foi encontrada uma derivação direita (rightmost derivation).
A “pilha” é lida da esquerda-para-a-direita (left-to-right).
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 $\nil$.
Rejeitar quando a pilha não é um prefixo viável.

O resultado é: $$ \begin{array}{ll|cl} \text{pilha} & \text{palavra} & \text{Contexto} & \text{ação} \cr \hline \nil & aabaa\# & X \to \nil & R \cr X & aabaa\# & \text{viável} & T \cr Xa & abaa\# & \text{viável} & T \cr Xaa & baa\# & \text{viável} & T \cr Xaab & aa\# & Y \to b & R \cr XaaY & aa\# & \text{viável} & T \cr XaaYa & a\# & Y \to aYa & R \cr XaY & a\# & \text{viável} & T \cr XaYa & \# & T \to aYa & R \cr XY & \# & X \to XY & R \cr X & \# & \text{viável} & T\cr X\# & \nil & S \to X\# & R \cr S & \nil && \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}{ll|cl} \text{pilha} & \text{palavra} & \text{Contexto} & \text{ação} \cr \hline \nil & abb\# & X \to \nil & R \cr X & abb\# & \text{viável} & T \cr Xa & bb\# & \text{viável} & T \cr Xab & b\# & Y \to b & R \cr XaY & b\# & \text{viável} & T \cr XaYb & \# & \text{inviá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=\del{V, \Sigma, P, V}$ 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 \nil \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{aligned} S &\to \cdot X \# & S &\to X \cdot \# & \alert{S} &\alert{\to X\# \cdot} \cr X &\to \cdot XY & X &\to X \cdot Y & \alert{X} &\alert{\to XY \cdot} \cr \alert{X} &\alert{\to \cdot} \cr Y &\to \cdot aYa & Y &\to a\cdot Ya &Y &\to aY\cdot a &\alert{Y} &\alert{\to aYa \cdot }\cr Y &\to \cdot b & \alert{Y} &\alert{\to b \cdot} \end{aligned} $$ com os itens completos assinalados assim: $\alert{A \to p\cdot}$.

Fecho. Seja $I$ um conjunto de itens. O fecho de $I$, denotado $\fecho\at{I}$ define-se recursivamente por:

base $I \subseteq \fecho\at{I}$.

passo Se $A \to u\cdot Bv \in \fecho\at{I}$ com $B \in V$ então, para cada produção $B \to p \in P$, também $B \to \cdot p \in \fecho\at{I}$.

Por exemplo, usando a gramática anterior,

$$\fecho\at{X\to X\cdot Y} = \set{X \to X \cdot Y, Y \to \cdot aYa, Y \to \cdot b}$$

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 = \del{V, \Sigma, P, S}$ uma GIC. O autómato dos itens válidos, que reconhece os prefixos viáveis de $G$ é o AFD $A = \del{Q, V \cup \Sigma, \delta, q_I, Q \setminus \set{\empty}}$ em que:

estado inicial $q_I = \fecho\at{\set{S\to \cdot p \st S \to p \in P}}$.

transição Para cada $q \in Q$ e $x \in V \cup \Sigma$

$$\delta\at{q, x} = \fecho\at{\set{A \to u\alert{x\cdot} v \st A \to u\alert{\cdot x} v \in q}}$$

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

$$ \begin{array}{c|cl||cc} \text{estado} & \exists\text{completo}? & \text{itens} & \text{símbolo} & \text{para} \cr \hline \q{0} & \checkmark & S \to \cdot X \#, X \to \cdot XY, X \to \cdot \cr &&& X & \q{1} \cr \hline \q{1} && S \to X \cdot \#, X \to X \cdot Y, Y \to \cdot aYa, Y \to \cdot b \cr &&& \# & \q{2} \cr &&& Y & \q{3} \cr &&& a & \q{4} \cr &&& b & \q{5} \cr \hline \q{2} & \checkmark & S \to X \#\cdot \cr \hline \q{3} & \checkmark & X \to XY \cdot \cr \hline \q{4} && Y \to a \cdot Y a, Y \to \cdot aYa, Y \to \cdot b \cr &&& Y & \q{6} \cr &&& a & \q{4} \cr &&& b & \q{5} \cr \hline \q{5} &\checkmark & Y \to b \cdot \cr \hline \q{6} && Y \to a Y \cdot a\cr &&& a & \q{7} \cr \q{7} & \checkmark& Y \to a Y a \cdot \cr \end{array} $$

Note-se que há mais um estado, $\empty$, 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 $\empty$):

$$ \begin{array}{r|cccccc} q & S & X & Y & a & b & \# \cr \hline if\q{0} && \q{1} \cr f\q{1} &&& \q{3} & \q{4} & \q{5} & \q{2} \cr f\q{2} \cr f\q{3} \cr f\q{4} &&& \q{6} & \q{4} & \q{5} \cr f\q{5} \cr f\q{6} &&&& \q{7} \cr f\q{7} \cr \empty \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 $\empty$ não está representado.

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

O “nome” do estado, um inteiro $\q{0}, \q{1}, \ldots$
A “raiz” dos itens, que resultam da transição.
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 $\empty$).

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

$$ \begin{array}{ll|cl} \text{pilha} & \text{palavra} &\text{estado AIV} & \text{ação} \cr \hline \nil & aabaa\# & \q{0} & R: X \to \nil \cr X & aabaa\# & \q{1} & T \cr Xa & abaa\# & \q{4} & T \cr Xaa & baa\# & \q{4} & T \cr Xaab & aa\# & \q{5} & R: Y \to b \cr XaaY & aa\# & \q{6} & T \cr XaaYa & a\# & \q{7} & R: Y \to aYa \cr XaY & a\# & \q{6} & T \cr XaYa & \# & \q{7} & R: T \to aYa \cr XY & \# & \q{3} & R: X \to XY \cr X & \# & \q{1} & T\cr X\# & \nil & \q{2} & R: S \to X\# \cr S & \nil & & \text{aceitar} \end{array} $$

enquanto que para $abb\#$, que não é gerada pela gramática: $$ \begin{array}{ll|cl} \text{pilha} & \text{palavra} & \text{estado AIV} & \text{ação} \cr \hline \nil & abb\# & \q{0} & R: X \to \nil \cr X & abb\# & \q{1} & T \cr Xa & bb\# & \q{4} & T \cr Xab & b\# & \q{5} & R: Y \to b \cr XaY & b\# & \q{6} & T \cr XaYb & \# & \empty & \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{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}{r|ccc|ccc||l} q & S & X & Y & a & b & \# & \text{ação} \cr \hline \q{0} && \q{1} &&&&& R: X \to \nil \cr \q{1} &&& \q{3} & \q{4} & \q{5} & \q{2} & T \cr \q{2} &&&&&&& A \cr \q{3} &&&&&&& R: X \to XY \cr \q{4} &&& \q{6} & \q{4} & \q{5} && T \cr \q{5} &&&&&&& R: Y \to b\cr \q{6} &&&& \q{7} &&& T\cr \q{7} &&&&&&& R: Y \to aYa\cr \end{array} $$

Nesta tabela:

O estado $\empty$, 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 $\empty$.
Por convenção, o estado $\q{0}$ é o inicial.
Nos estados com itens completos do símbolo inicial da GIC (no exemplo acima, o estado $\q{2}$) a ação é “aceitar”, $A$, em vez de ser “reduzir”, $R$.

Dado que a coluna $\text{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 $\q{0}, \q{2}, \q{3}, \q{5}, \q{7}$ acima) e as transferência são feitas em estados de que sai alguma “aresta com um terminal” (os estados $\q{1}, \q{4}, \q{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, \q{0}, Q \setminus \set{\empty})$ o seu AIV. O Autómato de Pilha Reconhecedor (APR) de $G$, que reconhece a linguagem gerada por $G$, é $$R = \del{\set{p_I, p}, \Sigma, V \cup \Sigma \cup Q \setminus \set{\empty}, \delta, p_I, \set{p}}$$ em que a transição, $\delta$, é definida pelos seguintes elementos:

iniciar: $\alert{\del{p, \q{0}} \in \delta\at{p_I, \nil, \nil}}$.

transferir: $\alert{\del{p, q’ a q} \in \delta\at{p, a, q}}$ se $q’ = \delta_A\at{q, a}$ 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 \not= S$ e $q’ = \delta_A\at{q_0, A}$, $\alert{\del{p, q’ A q_0} \in \delta\at{p, \nil, q_n a_n \cdots q_2 a_2 q_1 a_1 q_0}}$ quando no AIV existe a computação $$q_0 \trf{a_1} q_1 \trf{a_2} q_2 \cdots \trf{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, $\alert{\del{p, \nil} \in \delta\at{p, \nil, q_n a_n \cdots q_2 a_2 q_1 a_1 \q{0}}}$ quando no AIV existe a computação $$\q{0} \trf{a_1} q_1 \trf{a_2} \cdots \trf{a_n} q_n.$$

Intuitivamente $$ \begin{array}{ll|cl||rrr} \text{pilha} & \text{palavra} \hline \nil & abb\# & \q{0} X & abb\# & \q{1} & T Xa & bb\# & \q{4} & T Xab & b\# & \q{5} & R: Y \to b XaY & b\# & \q{6} & T XaYb & \# & \empty \end{array} $$ enquanto que de $aabaa\#$ é: $$ \begin{array}{ll|cl||r} \text{pilha} & \text{palavra} \hline \nil & aabaa\# & \q{0} X & aabaa\# & \q{1} & T Xa & abaa\# & \q{4} & T Xaa & baa\# & \q{4} & T Xaab & aa\# & \q{5} & R: Y \to b XaaY & aa\# & \q{6} & T XaaYa & a\# & \q{7} & R: Y \to aYa XaY & a\# & \q{6} & T XaYa & \# & \q{7} & R: T \to aYa XY & \# & \q{3} & R: X \to XY X & \# & \q{1} & T X\# & \nil & \q{2} & R: S \to X\# S & \nil & & \text{aceitar} \end{array} $$ 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\#$ é & \text{estado AIV} & \text{ação} & \text{pilha APR} & \text{topo: de} & \text{topo: para} \cr & R: X \to \nil & \q{0} & \q{0} & \q{1} X \q{0}\cr & \q{1}X\q{0} & \q{1} & \q{4} a \q{1} \cr & \q{4}a\q{1}X\q{0} & \q{4} & \q{5} b \q{4} \cr & \q{5}b\q{4}a\q{1}X\q{0} & \q{5}b\q{4} & \q{6}Y\q{4}\cr & \q{6}Y\q{4}a\q{1}X\q{0} & \q{6} & \alert{\empty} b \q{6} \cr & \text{rejeitar} & \alert{\empty} b\q{6}Y\q{4}a\q{1}X\q{0} & \text{estado AIV} & \text{ação} & \text{pilha APR} \cr & R: X \to \nil & \q{0} \cr & \q{1}X\q{0} \cr & \q{4}a\q{1}X\q{0} \cr & \q{4}a\q{4}a\q{1}X\q{0} \cr & \q{5}b\q{4}a\q{4}a\q{1}X\q{0} \cr & \q{6}Y\q{4}a\q{4}a\q{1}X\q{0} \cr & \q{7}a\q{6}Y\q{4}a\q{4}a\q{1}X\q{0} \cr & \q{6}Y\q{4}a\q{1}X\q{0} \cr & \q{7}a\q{6}Y\q{4}a\q{1}X\q{0} \cr & \q{3}Y\q{1}X\q{0} \cr & \q{1}X\q{0} \cr & \q{2} \# \q{1}X\q{0} \cr & \nil

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}{l||l|lcr} \text{Operação} & \text{Condição} & \text{De} & \text{Aresta} & \text{Para} \cr \hline \text{Iniciar}\cr & & p_I & \nil, \nil/\q{0} & p \cr\cr \hline \text{Transferir}\cr &q’ = \delta_A\at{q, a} & p & a, q / q’ a q & p \cr\cr \hline \text{Reduzir}\cr &A \to a_1 \cdots a_n\cdot\star \in q & p & \nil, \alpha / \beta & p \cr & A \not= S \cr \cr & q_0 \trf{a_1} \cdots \trf{a_n} q_n, q_n = q \cr & \alpha = q_n a_n \cdots a_1 q_0 \cr \cr & q_0 \trf{A} q’ \cr & \beta = q’ A q_0 \cr\cr \hline \text{Aceitar}\cr &S \to a_1 \cdots a_n\cdot\star \in q & p & \nil, \alpha / \nil & p \cr \cr & \q{0} \trf{a_1} \cdots \trf{a_n} q_n, q_n =q \cr & \alpha = q_n a_n \cdots a_1 \q{0} \end{array} $$

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

iniciar $\nil,\nil/\q{0}$ é a única transição $p_I \to p$.
transferir Estas transições são $p \tr p$:

$$ \begin{array}{l|r} \text{AIV: Computação} & \text{APR: Transição} \cr \hline \q{1} \trf{a} \q{4} & a, \q{1} / \q{4}a\q{1} \cr \q{1} \trf{b} \q{5} & b, \q{1} / \q{5}b\q{1} \cr \q{1} \trf{\#} \q{2}& \#, \q{1} / \q{2}\#\q{1} \cr \hline \q{4} \trf{a} \q{4} & a, \q{4} / \q{4}a\q{4} \cr \q{4} \trf{b} \q{5} & b, \q{4} / \q{5}b\q{4} \cr \hline \q{6} \trf{a} \q{7} & a, \q{6} / \q{7}a\q{6} \cr \end{array} $$
reduzir Estas transições são $p \tr p$:

$$ \begin{array}{lll|r} \text{AIV: Estado} & \text{AIV: Item completo de}\ A\not= S & \text{AIV: Computação} & \text{APR: Transição} \cr \hline \q{0} & X \to \nil \cdot & \q{0} & \nil, \q{0}/\q{1}X\q{0} \cr \hline \q{3} & X \to XY \cdot & \q{0} \trf{X} \q{1} \trf{Y} \q{3} & \nil,\q{3}Y\q{1}X\q{0}/ \q{1} X \q{0} \cr \hline \q{5} & Y \to b \cdot & \q{1} \trf{b} \q{5} & \nil, \q{5}b\q{1}/\q{3}Y\q{1} \cr && \q{4} \trf{b} \q{5} & \nil, \q{5}b\q{4}/\q{6}Y\q{4} \cr \hline \q{7} & Y \to aYa \cdot & \q{1} \trf{a} \q{4} \trf{Y} \q{6} \trf{a} \q{7} & \nil, \q{7}a\q{6}Y\q{4}a\q{1}/\q{3}Y\q{1} \cr && \q{4} \trf{a} \q{4} \trf{Y} \q{6} \trf{a} \q{7} & \nil, \q{7}a\q{6}Y\q{4}a\q{4}/\q{6}Y\q{4} \cr \end{array} $$
aceitar Estas transições são $p \tr p$:

$$ \begin{array}{lll|r} \text{AIV: Estado} & \text{AIV: Item completo de}\ S & \text{AIV: Computação} & \text{APR: Transição} \cr \hline \q{2} & S \to X\# \cdot & \q{0} \trf{X} \q{1} \trf{\#} \q{2} & \nil, \q{2}\# \q{1} X \q{0}/\nil \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}{c|rl|l|l} \text{Estado} & \text{Pilha} & \text{Entrada} & \text{Transição} & \text{Ação}\cr \hline p_I & \nil & abb\# & \nil, \nil/\q{0} & \text{iniciar}\ (p_I \tr p) \cr p & \q{0} & abb\# & \nil, \q{0}/\q{1}X\q{0} & \text{reduzir}\ X\to\nil \cr p & \q{1}X\q{0} & abb\# & a, \q{1} / \q{4}a\q{1} & \text{transferir} \cr p & \q{4}a\q{1}X\q{0} & bb\# & b, \q{4} / \q{5}b\q{4} & \text{transferir} \cr p & \q{5}b\q{4}a\q{1}X\q{0} & b\# & \nil, \q{5}b\q{4}/\q{6}Y\q{4} & \text{reduzir}\ Y\to b \cr p & \q{6}Y\q{4}a\q{1}X\q{0} & b\# & \empty & \text{rejeitar} \end{array} $$ e pára porque atinge uma configuração sem transições definidas (o topo é $\q{6}$ e o símbolo da entrada é $b$). Por outro lado a computação de $aabaa\#$ é: $$ \begin{array}{c|rl|l|l} \text{Estado} & \text{Pilha} & \text{Entrada} & \text{Transição} & \text{Ação}\cr \hline p_I & \nil & aabaa\# & \nil, \nil/\q{0} & \text{iniciar}\ (p_I \tr p) \cr p & \q{0} & aabaa\# & \nil, \q{0}/\q{1}X\q{0} & \text{reduzir}\ X\to\nil \cr p & \q{1}X\q{0} & aabaa\# & a, \q{1} / \q{4}a\q{1} & \text{transferir} \cr p & \q{4}a\q{1}X\q{0} & abaa\# & a, \q{4} / \q{4}a\q{4} & \text{transferir} \cr p & \q{4}a\q{4}a\q{1}X\q{0} & baa\# & b, \q{4} / \q{5}b\q{4} & \text{transferir} \cr p & \q{5}b\q{4}a\q{4}a\q{1}X\q{0} & aa\# & \nil, \q{5}b\q{4}/\q{6}Y\q{4} & \text{reduzir}\ Y\to b \cr p & \q{6}Y\q{4}a\q{4}a\q{1}X\q{0} & aa\# & a, \q{6} / \q{7}a\q{6} & \text{transferir} \cr p & \q{7}a\q{6}Y\q{4}a\q{4}a\q{1}X\q{0} & a\# & \nil, \q{7}a\q{6}Y\q{4}a\q{4}/\q{6}Y\q{4} & \text{reduzir}\ Y\to aYa \cr p & \q{6}Y\q{4}a\q{1}X\q{0} & a\# & a, \q{6} / \q{7}a\q{6} & \text{transferir} \cr p & \q{7}a\q{6}Y\q{4}a\q{1}X\q{0} & \# & \nil, \q{7}a\q{6}Y\q{4}a\q{1}/\q{3}Y\q{1} & \text{reduzir}\ Y\to aYa \cr p & \q{3}Y\q{1}X\q{0} & \# & \nil,\q{3}Y\q{1}X\q{0}/ \q{1} X \q{0} & \text{reduzir}\ X\to XY \cr p & \q{1}X\q{0} & \# & \#, \q{1} / \q{2}\#\q{1} & \text{transferir} \cr p & \q{2}\#\q{1}X\q{0} & \nil & \nil, \q{2}\# \q{1} X \q{0}/\nil & \text{aceitar}\ S\to X \# \cr p & \nil & \nil & \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 \nderR{S \to X\#} X\# \nderR{X \to XY} XY \# \nderR{Y \to aYa} XaYa\# \nderR{Y \to aYa} XaaYaa\# \nderR{Y \to b} Xaabaa\# \nderR{X \to \nil} 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{aligned} S &\to E\# \cr E &\to E + T \alt T \cr T &\to T \times F \alt F \cr F &\to n \alt (E) \end{aligned} $$

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

$$ \begin{aligned} &\q{0} \cr \hline S &\to \cdot E \# \cr \hline E &\to \cdot E + T \cr E &\to \cdot T \cr T &\to \cdot T \times F \cr \vdots \end{aligned} $$

Deste estado sai uma aresta $T$ que leva a um novo estado com os seguintes itens $$ \begin{aligned} &\q{?} \cr \hline E &\to T \cdot & \star\cr T &\to T \cdot \times F \cr \vdots \end{aligned} $$ 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.

Keyboard shortcuts

Autómatos e Linguagens de Programação