Gramáticas LR(1)

Gerador de Analisador Sintático a partir da GIC.

• Gramáticas LR(1)
  • Item LR(1)
  • Autómato Finito dos Itens LR(1) Válidos
  • Tabela de Análise Sintática LR(1)
  • Autómato de Pilha Reconhecedor LR(1)
  • Gramáticas LALR(1)

Embora as gramáticas LR(0) proporcionem um algoritmo completo e eficiente para a análise sintática, as linguagens abrangidas não incluem expressões algébricas, pelo que é necessário considerar um esquema mais adequado.

Aqui que entram as gramáticas LR(1), que usam informação sobre o "proximo terminal não processado" (o avanço) para guiar o processo da análise sintática.

Item LR(1)

Seguindo a estrutura da apresentação das gramáticas LR(0), define-se:

1. Itens, Itens Válidos e Fecho de um conjunto de itens.
2. Autómato dos itens válidos.
3. Condições LR(1).
4. Tabela de Análise Sintática.
5. Autómato de Pilha Reconhecedor.

Item LR(1). Item LR(1) Válido. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC.

Um Item LR(1) de $G$ tem a forma $$\left(A\to u\cdot v,L\right)$$ onde:

• núcleo $A\to u\cdot v$ é um item LR(0).
• símbolos de avanço $L\subseteq \Sigma \cup \left\{\#\right\}$.

O item LR(1) $\left(A\to u\cdot v,L\right)$ é válido para $xu$ se, para cada $a\in L$ existe uma derivação $$S\stackrel{\ast }{{\Rightarrow }_R}xAy$$ com $a\in \text{primeiros}\left(y\#\right)$.

O fecho de um conjunto de itens afeta os símbolos de avanço.

O Fecho LR(1) de um conjunto $X$ de itens LR(1) define-se recursivamente:

• base $X\subseteq {\text{fecho}}_1\left(X\right)$.
• passo Se $\left(A\to u\cdot Bv,L\right)\in {\text{fecho}}_1\left(X\right),B\in V$ então, para cada produção $B\to w$ também $$\left(B\to \cdot w,K\right)\in {\text{fecho}}_1\left(X\right)$$ onde $$K=\{\begin{array}{ll}\text{primeiros}\left(v\right)\cup L& v\stackrel{\ast }{\Rightarrow }\lambda \\ \text{primeiros}\left(v\right)& \text{caso contraˊrio}\end{array}$$
• fecho nada mais pertence a ${\text{fecho}}_1\left(X\right)$.

Por exemplo, dada a GIC $$\begin{array}{rl}S& \to AbA\\ A& \to Aa|\lambda \end{array}$$ tem-se $$\begin{array}{rl}{\text{fecho}}_1\left(S\to Ab\cdot A,\left\{\#\right\}\right)& =\left\{\left(S\to Ab\cdot A,\left\{\#\right\}\right)\right\}\\ & \cup \left\{\left(A\to \cdot Aa,\left\{\#\right\}\right),\left(A\to \cdot ,\left\{\#\right\}\right)\right\}\\ & \cup \left\{\left(A\to \cdot Aa,\left\{a\right\}\right),\left(A\to \cdot ,\left\{a\right\}\right)\right\}\\ & =\left\{\begin{array}{c}S\to Ab\cdot A,\#\\ A\to \cdot Aa,\#\\ A\to \cdot ,\#\\ A\to \cdot Aa,a\\ A\to \cdot ,a\end{array}\right\}\end{array}$$

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

Tal como nas gramáticas LR(0), os itens LR(1) válidos são reconhecidos por um AFD.

Autómato dos Itens LR(1) Válidos (AIV). Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC qualquer e $$G^{\prime }=\left(V\cup \left\{S^{\prime }\right\},\Sigma ,P\cup \left\{S^{\prime }\to S\right\},S^{\prime }\right).$$

O autómato dos itens LR(1) válidos de $G^{\prime }$ é o AFD $A=\left(Q,V\cup \Sigma ,\delta ,0,Q\setminus \left\{\varnothing \right\}\right)$ tal que:

• estado inicial $0={\text{fecho}}_1\left(S^{\prime }\to S,\#\right)$.
• transição Para cada $q\in Q,x\in V\cup \Sigma$,

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

Por exemplo, para a GIC dada acima:

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

O cálculo de ${\text{fecho}}_1\left(S^{\prime }\to \cdot S,\#\right)$ passo-a-passo:

1. Como ocorre $\cdot S$, é necessário adicionar os itens iniciais de $S$. O núcleo é $S\to \cdot AbA$.
2. Para calcular o avanço deste item, note-se que inicialmente $(S^{\prime }\to \cdot S\stackrel{v}{\overbrace{\lambda }},\stackrel{L}{\overbrace{\#}})$ portanto, pela definição de ${\text{fecho}}_1$, $K=\text{primeiros}\left(\lambda \right)\cup L=\varnothing \cup \left\{\#\right\}=\left\{\#\right\}$.
3. Portanto, o item LR(1) a acrescentar em $0$ é $S\to \cdot AbA,\#$.
4. Agora, de $S\to \cdot AbA,\#$ é preciso acrescentar os itens iniciais de $A$. Os núcleos são $A\to \cdot Aa$ e $A\to \cdot$. O cálculo dos avanços é idêntico para estes dois itens.
5. Estes itens resultam de $S\to \cdot A\stackrel{v}{\overbrace{b}}A,\#$. Pela definição de ${\text{fecho}}_1$, $K=\text{primeiros}\left(b\right)=\left\{b\right\}$.
6. Portanto, são acrescentados dois itens LR(1): $A\to \cdot Aa,b$ e $A\to \cdot ,b$.
7. Do item $A\to \cdot A\stackrel{v}{\overbrace{a}},b$, pelas razões anteriores, é necessário acrescentar dois itens LR(1): $A\to \cdot Aa,a$ e $A\to \cdot ,a$.
8. Torna a acontecer $A\to \cdot A\stackrel{v}{\overbrace{a}},a$ mas os itens que resultam já constam no ${\text{fecho}}_1$ e nada mais é acrescentado.
9. Finalmente o fecho tem vários itens com o mesmo núcleo e que diferem apenas no avanço. Neste caso esses itens "fundem-se" num único, unindo os avanços:
   1. $A\to \cdot Aa,b$ e $A\to \cdot Aa,a$ fundem-se em $A\to \cdot Aa,ab$.
   2. $A\to \cdot ,b$ e $A\to \cdot ,a$ fundem-se em $A\to \cdot ,ab$.

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

Tal como no caso das gramáticas LR(0), os estados do AIV LR(1) permitem determinar se o processo da análise sintática pode, ou não, ser aplicado.

Para que a análise sintática seja determinista é necessário que os estados sejam livres de conflitos (redução/redução e redução/transferência). No caso das gramáticas LR(0), sem informação sobre os avanços, cada estado do AIV pode determinar ou uma única redução ou uma transferência. Nos AIV das gramáticas LR(1) os itens têm avanços, que proporcionam decisões mais informadas em cada caso.

No AIV acima, visto como um AIV LR(0), o estado $5$ tem um conflito redução/transferência. Mas o avanço do item $S\to AbA,\#$ restringe a aplicação da redução apenas quando o avanço na entrada é $\#$. Portanto não há conflito com uma eventual transferência de $a$.

Em cada estado, cada avanço identifica a ação (reduzir, transferir, aceitar, rejeitar) no processo da análise sintática.

Portanto, a tabela de análise sintática LR(1) tem uma ação possível para cada símbolo terminal. Especificamente:

Tabela de Análise Sintática LR(1). (TAS LR(1)) Dada uma GIG e o seu AIV LR(1), a tabela de análise sintática LR(1) tem:

• Para cada estado do AIV LR(1), uma linha, exceto para o estado $\varnothing$.
• Para cada símbolo $\left(V\cup \Sigma \right)\setminus \left\{S^{\prime }\right\}$, uma coluna que descreve a transição do AIV.
• Para cada símbolo $a\in \Sigma \cup \left\{\#\right\}$, uma coluna que, cruzada com a linha do estado $\mathbf{q}$, determina a ação:
  • aceitar (ou $A$) se $\mathbf{q}$ contém um item completo de $S^{\prime }$ e se $a=\#$.
  • transferir (ou $T$) se $\mathbf{q}$ contém um item $A\to u\cdot av,L$.
  • reduzir (ou $R:A\to p$) se $\mathbf{q}$ contém o item completo $A\to p\cdot ,L$, $A\ne S$ e $a\in L$.
  • rejeitar (omitido).

Por exemplo, A TAS LR(1) do exemplo acima é:

$$\begin{array}{rccccccc}\mathbf{q}& S& A& a& b& a& b& \#\\ 0& 1& 2& & & A\to \lambda & A\to \lambda & \\ 1& & & & & & & \text{aceitar}\\ 2& & & 3& 4& \text{transferir}& \text{transferir}& \\ 3& & & & & A\to Aa& A\to Aa& \\ 4& & 5& & & A\to \lambda & & A\to \lambda \\ 5& & & 6& & \text{transferir}& & S\to AbA\\ 6& & & & & A\to Aa& & A\to Aa\end{array}$$

Comparando esta tabela com as obtidas nas TAS LR(0), a coluna ação é mais específica, considerando agora os símbolos de avanço e, portanto, a ação depende não só do estado no AIV mas também do próximo símbolo na entrada.

Numa TAS LR(1) mantém-se a necessidade de determinar, sem ambiguidade, cada ação no processo da análise sintática. Em relação ao caso LR(0), a escolha da ação depende não só do estado do AIV mas também do símbolo de avanço.

Quando esta informação (estado AIV + símbolo de avanço) não é suficiente para determinar uma única ação tem-se um conflito, que pode ser de dois tipos:

• Conflito Redução/Redução LR(1): Num estado com dois itens completos em que os avanços se intersetam. Formalmente, se no AIV LR(1) existe um estado com dois itens completos distintos $\left(A\to p\cdot ,L\right)$ e $\left(B\to q\cdot ,K\right)$ e $L\cap K\ne \varnothing$.
• Conflito Redução/Transferência LR(1): Num estado com um item completo em que sai uma aresta "com um terminal" que está no avanço desse item completo. Formalmente, se no AIV LR(1) existe um item completo $\left(A\to p\cdot ,L\right)$ e um item $\left(B\to u\cdot av,L\right)$ e $a\in L$.

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

Autómato de Pilha Reconhecedor LR(1)

Quando o AIV LR(1) de uma GIC está livre de conflitos é possível definir-se um autómato de pilha para reconhecer a linguagem gerada pela GIC. Além disso, para as palavras geradas/aceites, a observação da computação permite recuperar a derivação direita da respetiva palavra.

Autómato de Pilha Reconhecedor LR(1). Seja $G=(V,\Sigma ,P,S)$ uma GIC LR(1) e $A=(Q,V\cup \Sigma ,{\delta }_A,0,Q\setminus \left\{\varnothing \right\})$ o seu AIV LR(1). O Autómato de Pilha Reconhecedor LR(1) (APR LR(1)) de $G$, que reconhece a linguagem gerada por $G$, é $$R=\left(Q_R,\Sigma \cup \left\{\#\right\},V\cup \Sigma \cup Q\setminus \left\{\varnothing \right\},\delta ,p_I,F_R\right)$$ com

• estados de controlo: $Q_R=\left\{p_I,p\right\}\cup \left\{p_a:a\in \Sigma \cup \left\{\#\right\}\right\}$.
• estados finais: $F_R=\left\{p_{\#}\right\}$.

e em que a transição, $\delta$, é definida pelos seguintes elementos:

• iniciar: $\left(p,0\right)\in \delta \left(p_I,\lambda ,\lambda \right)$.
• avançar: Para cada $a\in \Sigma \cup \left\{\#\right\}$ então $\left(p_a,\lambda \right)\in \delta \left(p,a,\lambda \right)$.
• transferir: Para cada $q\in Q$ com um item $\left(A\to u\cdot av,L\right)$ em que $a\in \Sigma$ e $q^{\prime }={\delta }_A\left(q,a\right)$ então $\left(p,q^{\prime }aq\right)\in \delta \left(p_a,\lambda ,q\right)$.
• reduzir: Para cada estado $q\in Q$ com um item completo $\left(A\to a_1{a}_2\cdots a_n\cdot ,L\right)$ com $A\ne S^{\prime }$ e para cada $a\in L$, 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=q$$ e $q^{\prime }={\delta }_A\left(q_0,A\right)$ então $\left(p_a,q^{\prime }A{q}_0\right)\in \delta \left(p_a,\lambda ,q_n{a}_n\cdots q_2{a}_2{q}_1{a}_1{q}_0\right)$.
• aceitar: Para cada estado $q\in Q$ com um item completo $\left(S^{\prime }\to a_1{a}_2\cdots a_n\cdot ,L\right)$ do símbolo inicial da GIC, se $\#\in L$ e quando no AIV existe a computação $$0\stackrel{a_1}{⊢}{q}_1\stackrel{a_2}{⊢}\cdots \stackrel{a_n}{⊢}{q}_n=q$$ então $\left(p_{\#},\lambda \right)\in \delta \left(p_{\#},\lambda ,q_n{a}_n\cdots q_2{a}_2{q}_1{a}_{1}0\right).$

Alternativamente as transições do APR LR(1) podem ser descritas 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{Avanc¸ar}& & & & \\ & a\in \Sigma \cup \left\{\#\right\}& p& a,\lambda /\lambda & p_a\\ & & & & \\ \text{Transferir}& & & & \\ & \left(A\to u\cdot av,L\right)\in q& p_a& \lambda ,q/q^{\prime }aq& p\\ & a\in \Sigma & & & \\ & & & & \\ & q^{\prime }={\delta }_A\left(q,a\right)& & & \\ & & & & \\ \text{Reduzir}& & & & \\ & \left(A\to a_1\cdots a_n\cdot ,L\right)\star \in q& p_a& \lambda ,\alpha /\beta & p_a\\ & A\ne S^{\prime }& & & \\ & a\in L& & & \\ & & & & \\ & 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}& & & & \\ & \left(S^{\prime }\to a_1\cdots a_n\cdot ,L\right)\star \in q& p_{\#}& \lambda ,\alpha /\lambda & p_{\#}\\ & \#\in L& & & \\ & & & & \\ & 0\stackrel{a_1}{⊢}\cdots \stackrel{a_n}{⊢}{q}_n,q_n=q& & & \\ & \alpha =q_n{a}_n\cdots a_{1}0& & & \end{array}$$

Intuitivamente os estados do APR LR(1) refinam os do APR LR(0) com informação sobre o avanço. O estado $p$ "consulta" o símbolo de avanço (por exemplo, $a$) e encaminha a computação para o respetivo estado $p_a$, onde os passos são feitos sob o pressuposto "o avanço é $a$".

A computação fica em $p_a$ até $a$ ser transferido da entrada para a pilha. Depois dessa transferência é necessário tornar a consultar o avanço (em $p$) e proceder de acordo com o novo avanço.

O símbolo $\#$ marca o fím da entrada e é processado de acordo com esse pressuposto. Por exemplo, não há transições de $p_{\#}$ para $p$ e só neste estado pode ocorrer a ação aceitar.

Continuando o exemplo anterior, a transição do APR LR(1) tem as seguintes arestas:

• iniciar transições $p_I⊢p$: $\lambda ,\lambda /0$.
• avançar $$\begin{array}{clcl}\text{terminal}& \text{de}& \text{aresta}& \text{para}\\ a& p& a,\lambda /\lambda & p_a\\ b& p& b,\lambda /\lambda & p_b\\ \#& p& \#,\lambda /\lambda & p_{\#}\end{array}$$
• transferir $$\begin{array}{llcl}\text{AIV}& \text{APR: de}& \text{APR: aresta}& \text{APR: para}\\ 2\stackrel{a}{⊢}3& p_a& \lambda ,2/3a2& p\\ 2\stackrel{b}{⊢}4& p_b& \lambda ,2/4b2& p\\ 5\stackrel{a}{⊢}6& p_a& \lambda ,5/6a5& p\end{array}$$
• reduzir $$\begin{array}{llllr}\text{AIV: estado}& \text{AIV: item completo de}A\ne S^{\prime }& \text{AIV: avanc¸os}& \text{AIV: computac¸a˜o}& \text{APR: aresta}\\ 0& A\to \lambda \cdot & a,b& 0& \lambda ,0/2A0\\ 3& A\to Aa\cdot & a,b& 0\stackrel{A}{⊢}2\stackrel{a}{⊢}3& \lambda ,3a2A0/2A0\\ 4& A\to \lambda \cdot & \#,a& 4& \lambda ,4/5A4\\ 5& S\to AbA\cdot & \#& 0\stackrel{A}{⊢}2\stackrel{b}{⊢}4\stackrel{A}{⊢}5& \lambda ,5A4b2A0/1S0\\ 6& A\to Aa\cdot & \#,a& 4\stackrel{A}{⊢}5\stackrel{a}{⊢}6& \lambda ,6a5A4/5A4\end{array}$$
• aceitar $$\begin{array}{llllr}\text{AIV: estado}& \text{AIV: item completo de}{S}^{\prime }& \text{AIV: avanc¸os}& \text{AIV: computac¸a˜o}& \text{APR: aresta}\\ 1& S^{\prime }\to S\cdot & \#& 0& \lambda ,1S0/\lambda \end{array}$$

que corresponde ao diagrama

Diagrama do APR LR(1)
As arestas $p\to p_x$ são avançar, $p_x\to p_x$ reduzir e aceitar e $p_x\to p$ são transferir.

Como é que este APR processa palavras? Por exemplo, $aba$ é gerada pela GIC, enquanto que $bab$ não.

Para $aba$ o APR tem a computação $$\begin{array}{crllll}\text{estado}& \text{pilha}& \text{entrada}& \text{proˊximo estado}& \text{aresta}& \text{ac¸a˜o}\\ p_I& \lambda & aba\#& p& \lambda ,\lambda /0& \text{iniciar}\\ p& 0& aba\#& p_a& a,\lambda /\lambda & \text{avanc¸ar}\\ p_a& 0& ba\#& p_a& \lambda ,0/2A0& \text{reduzir }A\to \lambda \\ p_a& 2A0& ba\#& p& \lambda ,2/3a2& \text{transferir}\\ p& 3a2A0& ba\#& p_b& b,\lambda /\lambda & \text{avancar}\\ p_b& 3a2A0& a\#& p_b& \lambda ,3a2A0/2A0& \text{reduzir }A\to Aa\\ p_b& 2A0& a\#& p& \lambda ,2/4b2& \text{transferir}\\ p& 4b2A0& a\#& p_a& a,\lambda /\lambda & \text{avanc¸ar}\\ p_a& 4b2A0& \#& p_a& \lambda ,4/5A4& \text{reduzir }A\to \lambda \\ p_a& 5A4b2A0& \#& p& \lambda ,5/6a5& \text{transferir}\\ p& 6a5A4b2A0& \#& p_{\#}& \#,\lambda /\lambda & \text{avanc¸ar}\\ p_{\#}& 6a5A4b2A0& \lambda & p_{\#}& \lambda ,6a5A4/5A4& \text{reduzir }A\to Aa\\ p_{\#}& 5A4b2A0& \lambda & p_{\#}& \lambda ,5A4b2A0/1S0& \text{reduzir }S\to AbA\\ p_{\#}& 1S0& \lambda & p_{\#}& \lambda ,1S0/\lambda & \text{aceitar }(S^{\prime }\to S)\\ p_{\#}& \lambda & \lambda & & & \end{array}$$ que aceita e mostra a derivação $S{\Rightarrow }_{R}AbA{\Rightarrow }_{R}AbAa{\Rightarrow }_{R}Aba{\Rightarrow }_{R}Aaba{\Rightarrow }_{R}aba$. Quando à computação de $bab$, rejeita:

$$\begin{array}{crllll}\text{estado}& \text{pilha}& \text{entrada}& \text{proˊximo estado}& \text{aresta}& \text{ac¸a˜o}\\ p_I& \lambda & bab\#& p& \lambda ,\lambda /0& \text{iniciar}\\ p& 0& bab\#& p_b& b,\lambda /\lambda & \text{avanc¸ar}\\ p_b& 0& ab\#& p_b& \lambda ,0/2A0& \text{reduzir}A\to \lambda \\ p_b& 2A0& ab\#& p& \lambda ,2/4b2& \text{transferir}\\ p& 4b2A0& ab\#& p_a& a,\lambda /\lambda & \text{avanc¸ar}\\ p_a& 4b2A0& b\#& p_a& \lambda ,4/5A4& \text{reduzir}A\to \lambda \\ p_a& 5A4b2A0& b\#& p& \lambda ,5/6a5& \text{transferir}\\ p& 6a5A4b2A0& b\#& p_b& \lambda ,\lambda /\lambda & \text{avanc¸ar}\\ p_b& 6a5A4b2A0& \#& \varnothing & \varnothing & \text{rejeitar}\end{array}$$

Com este exemplo termina a resolução do Problema Principal de ALP — Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p\in A$ de forma computável, eficiente e adequada.

1. A linguagem é adequada se for formalmente definida por uma GIC LR(1).
2. Dada uma GIC que gere a linguagem, a construção algorítmica do seu AIV LR(1) é eficiente.
3. Pode-se verificar algoritmicamente e de forma eficiente se a GIC é LR(1), confirmando que nenhum estado do seu AIV LR(1) tem contradições. Nesse caso a linguagem é adequada.
4. A construção do APR LR(1) a partir do AIV LR(1) é, também, algorítmica e eficiente.
5. Dada uma palavra sobre o alfabeto da linguagem, o processamento pelo APR LR(1) é eficiente (e, claro, algorítmico). Adicionalmente, se a palavra está na linguagem, é possível recuperar a sua derivação na GIC para efeitos de processamento semântico.

Resumindo, este processo define um algoritmo (qua pode ser implementado em qualquer linguagem de programação comum) que é eficiente e resolve o Problema Principal de ALP.

Gramáticas LALR(1)

Neste ponto é fácil melhorar o seguinte problema: a construção do AIV gera muitos estados, o que pode ter um efeito negativo no desempenho dos restantes passos.

Quando dois estados do AIV têm os mesmos núcleos e, eventualmente, avanços distintos, a fusão consiste em juntar esses dois estados num único, cujos itens são obtidos:

• os núcleos são os mesmos;
• cada avanço é a união dos avanços dos itens correspondentes.

Usando um exemplo anterior

Diagrama do Autómato dos Itens LR(1) Válidos
Os estados $3$ e $6$ têm exatamente os mesmos núcleos.

O amalgamento deste AIV é

Autómato Amalgamado
O estado $36$ resulta de fundir $3$ com $6$. Neste exemplo não há mais fusões possíveis.

Formalmente:

Autómato Amalgamado. Seja $A=\left(Q,\Sigma ,\delta ,0,F\right)$ um AIV LR(1).

Se $X=\left\{q_1,\dots ,q_n\right\}$ for um conjunto de estados de $A$ com os mesmos núcleos, a fusão destes estados é o estado $\hat{X}$ com os itens $\left(A\to u\cdot v,L_1\cup \cdots L_n\right)$ tais que $\left(A\to u\cdot v,L_i\right)\in q_i$.

Seja $\left\{Q_1,\dots ,Q_n\right\}$ uma partição de $Q$ tal que:

• todos os estados de $Q_i$ têm os mesmos núcleos e
• se $i\ne j$ os núcleos dos estados de $Q_i$ e $Q_j$ são disjuntos. então

O autómato amalgamado $A^{\prime }$ é o autómato que resulta de fundir os estados com o mesmo conjunto de núcleos: $$A^{\prime }=\left(Q_A,\Sigma ,{\delta }^{\prime },\widehat{\left\{0\right\}},Q_A\setminus \left\{\widehat{\left\{\varnothing \right\}}\right\}\right)$$ com

• estados de controlo $Q_A=\left\{\widehat{Q_1},\dots ,\widehat{Q_n}\right\}$.
• transição ${\delta }^{\prime }\left(\widehat{Q_i},a\right)=\widehat{Q_j}$ se existe $q\in Q_i$ tal que $\delta \left(q,a\right)\in Q_j$.

Os autómatos amalgamados definem uma classe de gramáticas distinta de LR(1):

Gramática LALR(1). Uma GIC é LALR(1) se o seu autómato amalgamado satisfaz as condições LR(1): não tem conflitos redução/redução nem redução/transferência.

O principal interesse das gramáticas LALR(1) é, essencialmente, prático: Intuitivamente, são as gramáticas com "bons" AIV depois de amalgamados.