Gramáticas LR(k)

Análise Sintática Ascendente Determinista.

Introdução

As gramáticas LL(1) resolvem o problema da Análise Sintática no sentido em que proporcionam:

  1. Uma representação adequada para definir linguagens de programação.
  2. Um método computacional e eficiente para determinar se uma palavra é gerada por uma gramática.

No entanto a construção do analisador sintático LL(1) a partir de uma GIC arbitrária implica alguns passos manuais (human in the middle) que devem ser evitados.

O objetivo para esta secção é resolver esses problemas:

Obter um programa que tem como entrada uma GIC e que produz um segundo programa que tem como entrada uma palavra e que determina se essa palavra pertence, ou não, à linguagem dada ao primeiro programa. Isto é, definir um programa Super tal que:

  1. Se G for uma GIC, P = Super(G).
  2. Seja p uma palavra. P(p) é "verdade" ou "falso" conforme G gera, ou não, p.
  3. Tanto Super e P são eficientes.

Conteúdo

Para atingir esse objetivo:

  1. São definidas as gramáticas LR(k), Left-to-right Rightmost derivation in reverse, em português "derivação direita da esquerda-para-a-direita em reverso", onde "em reverso" significa que os passos da derivação são descobertos do último para o primeiro, isto é, como numa pesquisa ascendente.
  2. Dada uma gramática LR(n) é construído um analisador sintático como autómato de pilha determinista.

Estes analisadores sintáticos são eficientes no sentido em que detetam erros sintáticos assim que possível (isto é, quando a gramática não gera a palavra) mas (como se vai ver) o processo para os construir é muito trabalhoso quando feito à mão.

O "k" em LR(k) refere-se ao número de símbolos de avanço necessários para escolher deterministicamente as operações do AP. Para as gramáticas LR(0) não é preciso qualquer avanço, para as LR(1) é necessário um símbolo de avanço, etc.