Analisador LR canônico - Canonical LR parser

Em ciência da computação , um analisador LR canônico ou analisador LR (1) é um analisador LR (k) para k = 1 , ou seja, com um único terminal de lookahead . O atributo especial desse analisador é que qualquer gramática LR (k) com k> 1 pode ser transformada em uma gramática LR (1). No entanto, as substituições anteriores são necessárias para reduzir k e à medida que as substituições anteriores aumentam, a gramática pode rapidamente se tornar grande, repetitiva e difícil de entender. LR (k) pode lidar com todas as linguagens livres de contexto determinísticas . No passado, esse analisador LR (k) foi evitado por causa de seus enormes requisitos de memória em favor de alternativas menos poderosas, como o LALR e o analisador LL (1) . Recentemente, no entanto, um "analisador mínimo LR (1)", cujos requisitos de espaço são próximos aos analisadores LALR, está sendo oferecido por vários geradores de analisador.

Como a maioria dos analisadores, o analisador LR (1) é gerado automaticamente por compiladores-compiladores como GNU Bison , MSTA, Menhir, HYACC ,.

História

Em 1965 Donald Knuth inventado o analisador LR (K) ( L eft para a direita, R ightmost derivação analisador) um tipo de deslocamento reduzir-analisador , tal como uma generalização das existentes analisadores de precedência . Este analisador tem o potencial de reconhecer todas as linguagens livres de contexto determinísticas e pode produzir derivações esquerda e direita de instruções encontradas no arquivo de entrada. Knuth provou que atinge seu poder máximo de reconhecimento de linguagem para k = 1 e forneceu um método para transformar gramáticas LR (k), k> 1 em gramáticas LR (1).

Os analisadores LR (1) canônicos têm a desvantagem prática de ter enormes requisitos de memória para sua representação interna da tabela do analisador. Em 1969, Frank DeRemer sugeriu duas versões simplificadas do analisador LR, chamadas LALR e SLR . Esses analisadores requerem muito menos memória do que os analisadores Canonical LR (1), mas têm um pouco menos poder de reconhecimento de idioma. Os analisadores LALR (1) têm sido as implementações mais comuns do analisador LR.

No entanto, um novo tipo de analisador LR (1), algumas pessoas chamam de "analisador LR (1) mínimo", foi introduzido em 1977 por David Pager, que mostrou que analisadores LR (1) podem ser criados cujos requisitos de memória rivalizam com os de LALR ( 1) analisadores. Recentemente, alguns geradores de analisador estão oferecendo analisadores LR (1) mínimos, que não apenas resolvem o problema de requisitos de memória, mas também o problema de conflito misterioso inerente aos geradores de analisador LALR (1). Além disso, os analisadores Minimal LR (1) podem usar ações de redução de deslocamento, o que os torna mais rápidos do que os analisadores Canonical LR (1).

Visão geral

O analisador LR (1) é um autômato determinístico e, como tal, sua operação é baseada em tabelas de transição de estados estáticos . Eles codificam a gramática da linguagem que ele reconhece e são normalmente chamados de "tabelas de análise".

As tabelas de análise do analisador LR (1) são parametrizadas com um terminal lookahead. As tabelas de análise simples, como as usadas pelo analisador LR (0) representam as regras gramaticais do formulário

A1 → A, B

o que significa que se formos do estado A para o estado B , iremos para o estado A1 . Após parametrizar tal regra com um lookahead temos:

A1 → A, B, a

o que significa que a transição agora será realizada apenas se o terminal lookahead for a . Isso permite linguagens mais ricas em que uma regra simples pode ter significados diferentes, dependendo do contexto antecipado. Por exemplo, em uma gramática LR (1), todas as regras a seguir fazem a transição para um estado diferente, apesar de serem baseadas na mesma sequência de estados.

A1 → A, B, a
A2 → A, B, b
A3 → A, B, c
A4 → A, B, d

O mesmo não aconteceria se um terminal lookahead não estivesse sendo levado em consideração. Erros de análise podem ser identificados sem que o analisador precise ler toda a entrada, declarando algumas regras como erros. Por exemplo,

E1 → B, C, d

pode ser declarado um erro, fazendo com que o analisador pare. Isso significa que as informações de lookahead também podem ser usadas para detectar erros, como no exemplo a seguir:

A1 → A, B, a
A1 → A, B, b
A1 → A, B, c
E1 → A, B, d

Nesse caso, A, B será reduzido a A1 quando a antevisão for a, b ou ce um erro será relatado quando a antevisão for d.

A antecipação também pode ser útil para decidir quando reduzir uma regra. O lookahead pode ajudar a evitar a redução de uma regra específica se o lookahead não for válido, o que provavelmente significaria que o estado atual deve ser combinado com o seguinte em vez do estado anterior. Isso significa que no exemplo a seguir

  • Sequência de estado: A, B, C
  • Regras:
A1 → A, B
A2 → B, C

a sequência de estados pode ser reduzida a

A, A2

em vez de

A1, C

se a antecipação após o analisador ir para o estado B não fosse aceitável, ou seja, não existia nenhuma regra de transição. Os estados podem ser produzidos diretamente de um terminal como em

X → y

que permite que as sequências de estado apareçam.

Analisadores LR (1) têm o requisito de que cada regra deve ser expressa de uma maneira LR (1) completa, ou seja, uma sequência de dois estados com um lookahead específico. Isso torna regras simples, como

X → y

exigindo muitas regras artificiais que essencialmente enumeram as combinações de todos os estados possíveis e terminais antecipados que podem se seguir. Um problema semelhante aparece para a implementação de regras não antecipadas, como

A1 → A, B

onde todas as possíveis verificações à frente devem ser enumeradas. Essa é a razão pela qual os analisadores LR (1) não podem ser implementados de forma prática sem otimizações de memória significativas.

Construindo tabelas de análise sintática LR (1)

As tabelas de análise LR (1) são construídas da mesma maneira que as tabelas de análise LR (0) com a modificação de que cada Item contém um terminal de antevisão . Isso significa que, ao contrário dos analisadores LR (0), uma ação diferente pode ser executada, se o item a processar for seguido por um terminal diferente.

Itens do analisador

Partindo das regras de produção de um idioma, em primeiro lugar os conjuntos de itens para esse idioma devem ser determinados. Em palavras simples, um conjunto de itens é a lista de regras de produção, da qual o símbolo atualmente processado pode fazer parte. Um conjunto de itens tem uma correspondência de um para um com um estado do analisador, enquanto os itens dentro do conjunto, junto com o próximo símbolo, são usados ​​para decidir quais transições de estado e ação do analisador devem ser aplicadas. Cada item contém um marcador, para observar em que ponto o símbolo atualmente processado aparece na regra que o item representa. Para analisadores LR (1), cada item é específico para um terminal lookahead, portanto, o terminal lookahead também foi anotado dentro de cada item.

Por exemplo, suponha que uma linguagem que consiste nos símbolos terminais 'n', '+', '(', ')', os não-terminais 'E', 'T', a regra inicial 'S' e as seguintes regras de produção:

S → E
E → T
E → (E)
T → n
T → + T
T → T + n

Os conjuntos de itens serão gerados por analogia ao procedimento para analisadores LR (0). O conjunto de itens 0 que representa o estado inicial será criado a partir da regra inicial:

[S → • E, $]

O ponto '•' denota o marcador da posição de análise atual dentro desta regra. O terminal lookahead esperado para aplicar esta regra é indicado após a vírgula. O sinal '$' é usado para denotar que o 'fim da entrada' é esperado, como é o caso da regra de início.

No entanto, este não é o conjunto de itens completo 0. Cada conjunto de itens deve ser 'fechado', o que significa que todas as regras de produção para cada não terminal seguindo um '•' devem ser recursivamente incluídas no conjunto de itens até que todos esses não terminais sejam tratados. O conjunto de itens resultante é chamado de encerramento do conjunto de itens com o qual começamos.

Para LR (1), para cada regra de produção, um item deve ser incluído para cada terminal lookahead possível seguindo a regra. Para linguagens mais complexas, isso geralmente resulta em conjuntos de itens muito grandes, que é a razão para os grandes requisitos de memória dos analisadores LR (1).

Em nosso exemplo, o símbolo inicial requer o não terminal 'E' que por sua vez requer 'T', portanto, todas as regras de produção aparecerão no conjunto de itens 0. No início, ignoramos o problema de encontrar as verificações à frente e apenas olhamos para o caso de um LR (0), cujos itens não contêm terminais de antevisão. Portanto, o item definido como 0 (sem lookaheads) terá a seguinte aparência:

[S → • E]
[E → • T]
[E → • (E)]
[T → • n]
[T → • + T]
[T → • T + n]

Conjuntos FIRST e FOLLOW

Para determinar os terminais de lookahead, os chamados conjuntos FIRST e FOLLOW são usados. FIRST (A) é o conjunto de terminais que podem aparecer como o primeiro elemento de qualquer cadeia de regras correspondentes ao não terminal A. FOLLOW (I) de um Item I [A → α • B β, x] é o conjunto de terminais que podem aparecem imediatamente após o não terminal B, onde α, β são cadeias de símbolos arbitrárias e x é um terminal de lookahead arbitrário. SEGUIR (k, B) de um conjunto de itens k e um não terminal B é a união dos seguintes conjuntos de todos os itens em k onde '•' é seguido por B. Os primeiros conjuntos podem ser determinados diretamente a partir dos fechamentos de todos os não terminais em o idioma, enquanto os conjuntos FOLLOW são determinados a partir dos itens em uso dos conjuntos FIRST.

Em nosso exemplo, como se pode verificar na lista completa de conjuntos de itens abaixo, os primeiros conjuntos são:

PRIMEIRO (S) = {n, '+', '('}
PRIMEIRO (E) = {n, '+', '('}
PRIMEIRO (T) = {n, '+'}

Determinando terminais de lookahead

Dentro do conjunto de itens 0, os seguintes conjuntos podem ser:

SEGUIR (0, S) = {$}
SEGUIR (0, E) = {$, ')'}
SEGUIR (0, T) = {$, '+', ')'}

A partir disso, o conjunto de itens completo 0 para um analisador LR (1) pode ser criado, criando para cada item no conjunto de itens LR (0) uma cópia para cada terminal no conjunto a seguir do não terminal LHS. Cada elemento do conjunto a seguir pode ser um terminal lookahead válido:

[S → • E, $]
[E → • T, $]
[E → • T,)]
[E → • (E), $]
[E → • (E),)]
[T → • n, $]
[T → • n, +]
[T → • n,)]
[T → • + T, $]
[T → • + T, +]
[T → • + T,)]
[T → • T + n, $]
[T → • T + n, +]
[T → • T + n,)]

Criação de novos conjuntos de itens

O resto dos conjuntos de itens podem ser criados pelo seguinte algoritmo

1. Para cada terminal e símbolo não terminal A que aparece após um '•' em cada conjunto de itens já existente k, crie um novo conjunto de itens m adicionando a m todas as regras de k onde '•' é seguido por A, mas apenas se m não será o mesmo que um item já existente definido após a etapa 3.
2. deslocar todos os '•' s para cada regra no novo item definir um símbolo à direita
3. criar o fechamento do novo conjunto de itens
4. Repita a partir da etapa 1 para todos os conjuntos de itens recém-criados, até que não apareçam mais novos conjuntos

No exemplo, obtemos mais 5 conjuntos do conjunto de itens 0, conjunto de itens 1 para o não terminal E, conjunto de itens 2 para o não terminal T, conjunto de itens 3 para o terminal n, conjunto de itens 4 para o terminal '+' e conjunto de itens 5 para '(' .

Conjunto de itens 1 (E):

[S → E •, $]

Conjunto de itens 2 (T):

[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]
·
·
·

Conjunto de itens 3 (n):

[T → n •, $]
[T → n •, +]
[T → n •,)]

Conjunto de itens 4 ('+'):

[T → + • T, $]
[T → + • T, +]
[T → • n, $]
[T → • n, +]
[T → • + T, $]
[T → • + T, +]
[T → • T + n, $]
[T → • T + n, +]
·
·
·

Conjunto de itens 5 ('('):

[E → (• E), $]
[E → • T,)]
[E → • (E),)]
[T → • n,)]
[T → • n, +]
[T → • + T,)]
[T → • + T, +]
[T → • T + n,)]
[T → • T + n, +]
·
·
·

Dos conjuntos de itens 2, 4 e 5, vários outros conjuntos de itens serão produzidos. A lista completa é bastante longa e, portanto, não será mencionada aqui. O tratamento LR (k) detalhado desta gramática pode ser encontrado, por exemplo, em [1] .

Vamos para

A antecipação de um item LR (1) é usada diretamente apenas ao considerar ações de redução (ou seja, quando o • marcador está na extremidade direita).

O núcleo de um item LR (1) [S → a A • B e, c] é o item LR (0) S → a A • B e. Diferentes itens LR (1) podem compartilhar o mesmo núcleo.

Por exemplo, no conjunto de itens 2

[E → T •, $]
[T → T • + n, $]
[T → T • + n, +]

o analisador é necessário para realizar a redução [E → T] se o próximo símbolo for '$', mas para fazer uma mudança se o próximo símbolo for '+'. Observe que um analisador LR (0) não seria capaz de tomar essa decisão, pois considera apenas o núcleo dos itens e, portanto, relataria um conflito de mudança / redução.

Um estado contendo [A → α • X β, a] se moverá para um estado contendo [A → α X • β, a] com o rótulo X.

Cada estado tem transições de acordo com Goto.

Mudar ações

Se [A → α • b β, a] está no estado I k e I k se move para o estado I m com rótulo b, então adicionamos a ação

ação [I k , b] = "deslocar m"

Reduzir ações

Se [A → α •, a] está no estado I k , então adicionamos a ação

ação [I k , a] = "reduzir A → α"

Referências

links externos