❧ Gramáticas ❧

Considere a seguinte gramática.

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{S\} \\ T &= \{a, b\} \\ S &= S \end{split} \hspace{1cm} \begin{split} P = S &\to aS \mid b \end{split} $$

Aqui, o símbolo inicial é $S$ e a linguagem gerada contém cadeias formadas por zero ou mais $a$ seguidos de um $b$, como $b$, $ab$ e $aaab$. Veja como seria uma derivação possível para $aaab$:

$$ \begin{split} S &\Rightarrow aS \\ &\Rightarrow aaS \\ &\Rightarrow aaaS \\ &\Rightarrow aaab \end{split} $$

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{E\} \\ T &= \{id, +\} \\ S &= E \end{split} \hspace{1cm} \begin{split} P = E &\to E + E \mid id \end{split} $$

e a cadeia:

$$ id + id + id $$

Essa entrada pode ser lida de duas formas diferentes? Se sim, quais são elas?

Sim. A mesma cadeia admite duas árvores sintáticas, porque a gramática não fixa sozinha como os operandos devem ser agrupados:

• $(id + id) + id$;
• $id + (id + id)$.

Podemos enxergar isso também por duas derivações diferentes, ambas começando no símbolo inicial $E$.

Como as duas árvores são válidas para a mesma cadeia, a gramática é ambígua. Em outras palavras, a gramática não determina sozinha como os operandos devem ser agrupados.

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{E\} \\ T &= \{id, +, *, (, )\} \\ S &= E \end{split} \hspace{1cm} \begin{split} P = E &\to E + E \mid E * E \mid (E) \mid id \end{split} $$

e a cadeia:

$$ id + id * id $$

Quando misturamos soma e multiplicação, qual agrupamento a gramática deveria impor?

Ela admite pelo menos estas duas leituras:

Também podemos construir duas derivações diferentes a partir do símbolo inicial $E$.

Matematicamente, a segunda leitura é a desejada. O problema é que a gramática original não obriga isso, ela permite ambas. Portanto, a ambiguidade aqui não é um detalhe estético da árvore. Ela muda o significado da expressão.

Como a gramática reescrita força id + id * id a ser lida com a multiplicação primeiro?

Vamos derivar a cadeia

$$ id + id * id $$

usando a nova gramática.

$$ \begin{split} E &\Rightarrow E + T \\ &\Rightarrow T + T \\ &\Rightarrow F + T \\ &\Rightarrow id + T \\ &\Rightarrow id + T * F \\ &\Rightarrow id + F * F \\ &\Rightarrow id + id * F \\ &\Rightarrow id + id * id \end{split} $$

Repare que a derivação não cria a estrutura $(id + id) * id$. A própria organização em níveis impede esse agrupamento e força a leitura em que a multiplicação aparece dentro da soma.

Como expressar associatividade à direita para o expoente sem perder a associatividade à esquerda de + e *?

Vamos estender a gramática de expressões com um nível para potência. Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{E, T, P, F\} \\ T &= \{id, +, *, \text{\textasciicircum}, (, )\} \\ S &= E \end{split} \hspace{1cm} \begin{split} P = E &\to E + T \mid T \\ T &\to T * P \mid P \\ P &\to F^{P} \mid F \\ F &\to (E) \mid id \end{split} $$

Nessa organização, $+$ e $*$ continuam associativos à esquerda, enquanto o expoente passa a ser associativo à direita. Isso acontece porque, na produção de $P$, a continuação da potência reaparece do lado direito.

Vamos derivar:

$$ id^{id^{id}} $$

$$ \begin{split} E &\Rightarrow T \\ &\Rightarrow P \\ &\Rightarrow F^{P} \\ &\Rightarrow id^{P} \\ &\Rightarrow id^{F^{P}} \\ &\Rightarrow id^{id^{P}} \\ &\Rightarrow id^{id^{F}} \\ &\Rightarrow id^{id^{id}} \end{split} $$

Como o não terminal $P$ reaparece do lado direito da potência, a árvore induzida é:

Portanto, a leitura será: $id^{(id^{id})}$

Por que id - id - id é agrupado da esquerda para a direita nessa gramática?

Para enxergar a associatividade à esquerda, pense agora em:

$$ id - id - id $$

com a gramática:

$$ E \to E - T \mid T $$

A estrutura gerada tende a ser:

ou seja: $(id - id) - id$

Esse detalhe é importante porque mudar a associatividade muda o resultado de várias operações, como subtração, divisão e potenciação.

Em if c then if c then a else a, com qual if o else deve se ligar?

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{S\} \\ T &= \{if, then, else, c, a\} \\ S &= S \end{split} \hspace{1cm} \begin{split} P = S &\to \text{if } c\ \text{then } S \mid \text{if } c\ \text{then } S\ \text{else } S \mid a \end{split} $$

e a cadeia:

$$ \text{if } c\ \text{then if } c\ \text{then } a\ \text{else } a $$

O else pode se ligar ao if mais interno ou ao mais externo. Como a gramática não deixa explícito qual ligação deve ser preferida, surgem duas árvores possíveis.

Esse exemplo mostra que ambiguidades são problemas de estrutura e interpretação, não apenas de cálculo numérico.

Por que a produção abaixo trava um parser descendente?

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{E, T\} \\ T &= \{id, +\} \\ S &= E \end{split} \hspace{1cm} \begin{split} P = E &\to E + T \mid T \\ T &\to id \end{split} $$

Observe a produção:

$$ E \to E + T \mid T $$

Se o parser começar tentando reconhecer $E$, ele pode seguir este raciocínio:

$$ E \Rightarrow E + T \Rightarrow E + T + T \Rightarrow E + T + T + T \Rightarrow \cdots $$

Repare no ponto central. Ele continua expandindo $E$ sem consumir a entrada. Esse é exatamente o motivo do problema, o parser fica preso numa chamada recursiva que não avança sobre a cadeia.

Como eliminar a recursão à esquerda de A -> Aa | b sem alterar a linguagem?

Elimine a recursão à esquerda de:

$$ A \to Aa \mid b $$

Temos uma alternativa recursiva e uma não recursiva. Aplicando o molde:

$$ \begin{split} A &\to bA' \\ A' &\to aA' \mid \epsilon \end{split} $$

Agora o parser reconhece primeiro $b$ e só depois aceita quantas continuações $a$ forem necessárias.

Como reescrever uma lista com várias alternativas recursivas à esquerda?

Agora considere um caso um pouco mais rico. Aqui, a vírgula é um símbolo literal da linguagem, então ela deve aparecer como token, não como separador da escrita matemática.

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{L, Stmt\} \\ T &= \left\{\begin{array}{l} \text{;} \\ \text{,} \end{array}\right. \\ S &= L \end{split} \hspace{1cm} \begin{split} P = L &\to L\text{;}Stmt \mid L\text{,}Stmt \mid Stmt \end{split} $$

Aqui, Stmt representa um comando atômico qualquer. Se quiser um exemplo concreto, pense nele como algo como a ou b.

As partes recursivas são $L\text{;}Stmt$ e $L\text{,}Stmt$, enquanto a parte não recursiva é $Stmt$. Se quisermos visualizar isso com uma lista concreta, podemos imaginar Stmt como a. Nesse caso, uma cadeia como $a\text{,}a\text{;}a$ segue o mesmo molde:

$$ \begin{split} L &\Rightarrow Stmt\ L' \\ &\Rightarrow a\ L' \\ &\Rightarrow a\text{,}Stmt\ L' \\ &\Rightarrow a\text{,}a\ L' \\ &\Rightarrow a\text{,}a\text{;}Stmt\ L' \\ &\Rightarrow a\text{,}a\text{;}a \end{split} $$

Dessa forma:

$$ \begin{split} L &\to Stmt\ L' \\ L' &\to \text{;}Stmt\ L' \mid \text{,}Stmt\ L' \mid \epsilon \end{split} $$

Essa nova forma preserva a linguagem, mas evita a expansão infinita pela esquerda. Além disso, deixa explícita a ideia de que uma lista começa com um elemento base e pode ser seguida por várias continuações.

Como transformar a gramática de expressões para preservar a semântica e remover a recursão à esquerda?

Aplicando o procedimento em $E$:

$$ E \to E + T \mid E - T \mid T $$

Identificamos:

$$ \alpha_1 = +T, \qquad \alpha_2 = -T, \qquad \beta = T $$

Assim:

$$ \begin{split} E &\to T E' \\ E' &\to + T E' \mid - T E' \mid \epsilon \end{split} $$

Fazendo o mesmo para $T$:

$$ \begin{split} T &\to F T' \\ T' &\to * F T' \mid / F T' \mid \epsilon \end{split} $$

A gramática resultante fica:

$$ \begin{split} E &\to T E' \\ E' &\to + T E' \mid - T E' \mid \epsilon \\ T &\to F T' \\ T' &\to * F T' \mid / F T' \mid \epsilon \\ F &\to (E) \mid id \end{split} $$

A gramática transformada ainda aceita id + id - id?

Vamos verificar a derivação de

$$ id + id - id $$

na gramática transformada.

$$ \begin{split} E &\Rightarrow T E' \\ &\Rightarrow F E' \\ &\Rightarrow id E' \\ &\Rightarrow id + T E' \\ &\Rightarrow id + F E' \\ &\Rightarrow id + id E' \\ &\Rightarrow id + id - T E' \\ &\Rightarrow id + id - F E' \\ &\Rightarrow id + id - id E' \\ &\Rightarrow id + id - id \end{split} $$

Observe que a linguagem foi preservada. Continuamos aceitando as mesmas combinações, mas agora em uma forma apropriada para análise descendente.

O que o parser deve fazer quando vê duas produções com o mesmo começo?

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{A\} \\ T &= \{a, b, c\} \\ S &= A \end{split} \hspace{1cm} \begin{split} P = A &\to ab \mid ac \end{split} $$

As duas alternativas começam por $a$. Então, fatoramos:

$$ \begin{split} A &\to aA' \\ A' &\to b \mid c \end{split} $$

Antes, o parser precisava escolher entre duas produções que começavam igual. Agora ele consome $a$ primeiro e deixa a escolha para o momento em que $b$ ou $c$ aparecer.

Qual é o prefixo comum destas declarações e como a fatoração ajuda a leitura?

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{D\} \\ T &= \{int, id, ;, =, num\} \\ S &= D \end{split} \hspace{1cm} \begin{split} P = D &\to \text{int } id\ ; \mid \text{int } id = \text{num}\ ; \end{split} $$

O prefixo comum é $\text{int } id$. Assim:

Aqui, num representa um token léxico de número. Não é uma variável conceitual da gramática.

$$ \begin{split} D &\to \text{int } id\ D' \\ D' &\to ; \mid = \text{num} ; \end{split} $$

Agora a decisão só precisa ser tomada depois que o parser já reconheceu a parte compartilhada pelas duas declarações.

Como fatorar uma gramática em que todas as alternativas começam com id?

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{S, E, L\} \\ T &= \{id, :=, (, )\} \\ S &= S \end{split} \hspace{1cm} \begin{split} P = S &\to id := E \mid id(L) \mid id \end{split} $$

Todas as alternativas começam por $id$. Assim, fatoramos para:

$$ \begin{split} S &\to id\ S' \\ S' &\to := E \mid (L) \mid \epsilon \end{split} $$

Essa nova versão deixa claro o comportamento do parser. Primeiro reconhecer um identificador, depois decidir se ele inicia uma atribuição, uma chamada ou se a produção termina ali.

O que fazer quando o prefixo comum é curto, mas as continuações ainda se parecem muito?

Um caso um pouco mais desafiador é:

Considere a gramática

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{Cmd, Args, Params, Body, Expr\} \\ T &= \{id, (, ), \{, \}, =, ;\} \\ S &= Cmd \end{split} \hspace{1cm} \begin{split} P = Cmd &\to id(Args); \mid id(Params)\{Body\} \mid id = Expr; \end{split} $$

Aqui, Args, Params, Body e Expr também são placeholders. Eles representam o conteúdo interno de cada forma de comando.

O prefixo comum imediato é $id$. A primeira fatoração fica:

$$ \begin{split} Cmd &\to id\ Cmd' \\ Cmd' &\to (Args); \mid (Params)\{Body\} \mid = Expr; \end{split} $$

Essa transformação já melhora a decisão inicial do parser. Ainda assim, perceba que as duas alternativas que começam com $($ continuam próximas demais. Dependendo da definição de $Args$ e $Params$, talvez ainda seja preciso fatorar mais uma vez ou reorganizar essas categorias.

1.
(a) $N$ é o conjunto de não-terminais, $T$ é o conjunto de terminais, $P$ é o conjunto de produções e $S$ é o símbolo inicial.
(b) Uma derivação possível é:

$$ \begin{split} S &\Rightarrow aS \\ &\Rightarrow aaS \\ &\Rightarrow aaaS \\ &\Rightarrow aaab \end{split} $$

(c) Um exemplo de derivação parcial é $S \Rightarrow aS \Rightarrow aaS$.
(d) Forma sentencial intermediária ainda pode conter não-terminais; cadeia final reconhecida contém apenas terminais da linguagem.

2.
(a) Consumir um token significa reconhecer o próximo símbolo da entrada e avançar o ponteiro de leitura.
(b) Não consumir nada significa continuar expandindo regras sem avançar na entrada.
(c) Reconhecer apenas um prefixo significa aceitar só uma parte da cadeia, deixando tokens ainda não consumidos.
(d) O sucesso completo exige que toda a entrada válida tenha sido lida e que reste apenas $, indicando fim da entrada.

3.
(a) Os dois agrupamentos são (id + id) + id e id + (id + id).
(b) No primeiro, a soma da esquerda é formada antes; no segundo, a soma da direita é formada antes. Isso produz árvores com estruturas internas diferentes.
(c) A gramática é ambígua porque a mesma cadeia id + id + id admite mais de uma árvore sintática válida.

4.
(a) As duas leituras são (id + id) * id e id + (id * id).
(b) A leitura aritmética usual é id + (id * id), porque * tem precedência maior que +.
(c) A ambiguidade muda o significado da expressão, pois cada árvore impõe uma ordem diferente de avaliação.

5.
(a) Uma reescrita clássica é:

$$ \begin{split} E &\to E + T \mid T \\ T &\to T * F \mid F \\ F &\to (E) \mid id \end{split} $$

(b) Uma derivação possível é:

$$ \begin{split} E &\Rightarrow E + T \\ &\Rightarrow T + T \\ &\Rightarrow F + T \\ &\Rightarrow id + T \\ &\Rightarrow id + T * F \\ &\Rightarrow id + F * F \\ &\Rightarrow id + id * id \end{split} $$

(c) Como * aparece em um nível mais profundo que +, a multiplicação fica necessariamente dentro do lado direito da soma, impedindo a estrutura (id + id) * id.

6.
(a) Em $P \to F^P \mid F$, a continuação da potência reaparece à direita, então cada novo ^ se encaixa no operando da direita.
(b) O agrupamento correto é id^(id^id).
(c) Em uma gramática como $E \to E - T \mid T$, a recursão ocorre pela esquerda, o que induz o agrupamento (id - id) - id.

7.
(a) O else pode se ligar ao if interno ou ao if externo.
(b) Como as duas estruturas são válidas para a mesma cadeia, a gramática é ambígua.
(c) Uma solução é:

$$ \begin{split} S &\to \text{Matched} \mid \text{Unmatched} \\ \text{Matched} &\to \text{if } c \text{ then Matched else Matched} \mid a \\ \text{Unmatched} &\to \text{if } c \text{ then } S \mid \text{if } c \text{ then Matched else Unmatched} \end{split} $$

(d) Essa separação garante que todo else feche o if mais próximo ainda pendente, eliminando a dupla interpretação.

8.
(a) A recursão à esquerda imediata está em $E \to E + T$.
(b) Um parser descendente pode expandir E chamando E de novo antes de consumir qualquer token.
(c) Uma sequência típica é:
$E \Rightarrow E + T \Rightarrow E + T + T \Rightarrow E + T + T + T \Rightarrow \cdots$
O parser fica preso repetindo a expansão sem avançar sobre a entrada.

9.
(a) Para $A \to Aa \mid b$: $\alpha = a$ e $\beta = b$. Resultado:

$$ \begin{split} A &\to bA' \\ A' &\to aA' \mid \epsilon \end{split} $$

(b) Para $L \to L;Stmt \mid L,Stmt \mid Stmt$: $\alpha_1 = ;Stmt$, $\alpha_2 = ,Stmt$ e $\beta = Stmt$. Resultado:

$$ \begin{split} L &\to Stmt\ L' \\ L' &\to ;Stmt\ L' \mid ,Stmt\ L' \mid \epsilon \end{split} $$

(c) Para $E \to E + T \mid E - T \mid T$: $\alpha_1 = +T$, $\alpha_2 = -T$ e $\beta = T$. Resultado:

$$ \begin{split} E &\to T\ E' \\ E' &\to +T\ E' \mid -T\ E' \mid \epsilon \end{split} $$

10.
(a) Ela é indireta porque $A$ não chama a si mesmo diretamente; o ciclo ocorre por meio de $B$.
(b) Substituindo $B$ em $A$:

$$ A \to (Ac \mid d)a \mid b \implies A \to Aca \mid da \mid b $$

(c) Eliminando a recursão à esquerda:

$$ \begin{split} A &\to da\ A' \mid b\ A' \\ A' &\to ca\ A' \mid \epsilon \end{split} $$

(d) Depois da transformação, o parser reconhece primeiro uma base segura (da ou b) e deixa as repetições para depois, sem laço imediato pela esquerda.

11.
(a) A forma sem recursão à esquerda é:

$$ \begin{split} E &\to T\ E' \\ E' &\to +T\ E' \mid -T\ E' \mid \epsilon \\ T &\to F\ T' \\ T' &\to *F\ T' \mid /F\ T' \mid \epsilon \\ F &\to (E) \mid id \end{split} $$

(b) Uma derivação para id + id - id é:

$$ \begin{split} E &\Rightarrow T E' \\ &\Rightarrow F E' \\ &\Rightarrow id E' \\ &\Rightarrow id + T E' \\ &\Rightarrow id + F E' \\ &\Rightarrow id + id E' \\ &\Rightarrow id + id - T E' \\ &\Rightarrow id + id - F E' \\ &\Rightarrow id + id - id \end{split} $$

(c) A transformação elimina um obstáculo operacional para o parser top-down, mas não garante, sozinha, unicidade de interpretação em qualquer gramática; desambiguação e remoção de recursão à esquerda são objetivos diferentes.

12.
(a) $A \to ab \mid ac$ fatora para:

$$ \begin{split} A &\to aA' \\ A' &\to b \mid c \end{split} $$

A decisão adiada é se, após a, a continuação será b ou c.

(b) $D \to \text{int } id\ ; \mid \text{int } id = \text{num}\ ;$ fatora para:

$$ \begin{split} D &\to \text{int } id\ D' \\ D' &\to ; \mid =\ \text{num}\ ; \end{split} $$

A decisão adiada é se a declaração termina imediatamente ou se possui inicialização.

(c) $S \to id := E \mid id(L) \mid id$ fatora para:

$$ \begin{split} S &\to id\ S' \\ S' &\to := E \mid (L) \mid \epsilon \end{split} $$

A decisão adiada é se o identificador inicia uma atribuição, uma chamada ou aparece sozinho.

(d) $Cmd \to id(Args); \mid id(Params)\{Body\} \mid id = Expr;$ fatora para:

$$ \begin{split} Cmd &\to id\ Cmd' \\ Cmd' &\to (Args); \mid (Params)\{Body\} \mid = Expr; \end{split} $$

A decisão adiada é se o id inicia uma chamada, uma definição com parâmetros e bloco, ou uma atribuição.

13.
(a) O prefixo comum extraído é if E then S.
(b) A fatoração ajuda porque o parser consome primeiro a parte compartilhada e só depois decide se existe um else.
(c) Isso melhora a previsibilidade local da análise, mas não basta para resolver sozinho o problema estrutural do dangling else, que exige desambiguação explícita.

14.
(a) Desambiguação, porque o problema é haver mais de uma árvore para a mesma cadeia.
(b) Eliminação de recursão à esquerda, porque o parser retorna ao mesmo não terminal antes de consumir entrada.
(c) Fatoração à esquerda, porque o problema é o prefixo comum entre produções concorrentes.
(d) Eliminação de recursão à esquerda, porque a semântica já está correta, mas a forma ainda é inadequada para análise descendente.
(e) Desambiguação, porque fatoração melhora a decisão local do parser, mas não elimina por si só múltiplas interpretações semânticas.