Na ciência da computação , a análise LL é uma análise sintática de cima para baixo para certas gramáticas não contextuais , chamadas gramáticas LL . Ele analisa uma palavra de entrada da esquerda para a direita ( L eft to right em inglês) e constrói uma derivação para a esquerda ( L eftmost derivation em inglês). A árvore de sintaxe é construída a partir da raiz e depois para dentro da árvore.
A análise LL executa uma única passagem na palavra de entrada. Uma análise LL é chamada de análise LL ( k ) quando usa uma janela de k lexemas para decidir como construir a árvore de sintaxe da palavra de entrada.
O seguinte descreve uma análise derivada esquerda de cima para baixo com base em uma tabela de análise . A noção de derivação à esquerda significa que, durante o processo de aplicação das regras, é o não terminal mais à esquerda que é escolhido e reescrito. Esse aspecto resulta na utilização de uma pilha no algoritmo do analisador.
O analisador é composto por:
O analisador aplica a regra encontrada na tabela, combinando o topo da pilha (linha) com o símbolo atual no buffer de entrada (coluna).
Quando a análise começa, a pilha contém dois símbolos:
[ S, $ ]Onde '$' é um símbolo para a parte inferior da pilha e o final do buffer de entrada, e 'S' é o axioma da gramática.
O analisador tentará reescrever o conteúdo de sua pilha para o que vê no buffer de entrada. No entanto, ele apenas mantém na pilha o que precisa ser reescrito.
Let Ser uma gramática algébrica (onde V denota o conjunto de variáveis não terminais ou símbolos, A o alfabeto terminal ou conjunto de símbolos terminais, P o conjunto de regras, S o axioma da gramática que é uma regra de P). A fim de calcular a tabela de análise , apresentamos as funções , e .
EpsPara qualquer expressão , é verdadeiro se for cancelável, o que equivale a dizer que é verdadeiro se (a expressão é reescrita na string vazia ) e, caso contrário, é falso. Este cálculo corresponde ao das regras ε , como no caso da conversão para a forma normal de Chomsky .
PrimeiroPara qualquer expressão , definimos como sendo o conjunto de terminais que provavelmente iniciarão uma palavra derivada de α. Mais formalmente:
.Se sim .
SeguePara qualquer expressão , definimos como sendo o conjunto de terminais que provavelmente seguirão uma palavra derivada de α. Mais formalmente:
.Sim então . Também adicionamos o símbolo '$' a todos , para poder indicar o fim do código.
Preenchimento da tabela de análiseA tabela de análise é uma matriz bidimensional, cujas linhas são indexadas por Não terminais e as colunas por Terminais . O enchimento é realizado como tal:
Pour toute règle de la forme X→α Pour tout a∈Premier(α) Ajouter X→α à la case d'indice (a,X) Si Eps(α) vaut vrai Alors Pour tout b∈Suivant(α) Ajouter X→α à la case d'indice (b,X) Fin pour Fin pour Fin pourPara explicar como funciona, usaremos a seguinte gramática:
e analisar a próxima string
(1 + 1)Calculamos Eps:
Nenhuma regra é fornecida, portanto, nenhum Eps (α) é sempre falso.
Calculamos o Prime:
Premier(F) = { 1 } Premier((S + F)) = { (} Premier(1) = { 1 }
Calculamos a tabela de análise:
( | ) | 1 | + | $ | |
S | - | - | - | ||
F | - | - | - | - |
Análise de Palavras |
---|
O analisador lê o primeiro '(' do buffer de entrada e do topo da pilha (o 'S'). Olhando para a tabela, ele sabe que precisa aplicar a regra ' '; agora ele deve reescrever o 'S' em '(S + F)' em sua pilha e escreva a regra aplicada à saída. A pilha torna-se (o topo da pilha está à esquerda, os símbolos são separados por vírgulas): [ (, S, +, F, ), $ ]Podemos notar que o S não-terminal será desempilhada e, portanto, reescrito antes de F. É de fato o não-terminal mais à esquerda no termo '(S + F)'. Isso ilustra a noção de derivação à esquerda . Na próxima etapa, como o topo da pilha e o buffer apresentam o terminal '(', este símbolo é exibido e removido do buffer de entrada. A pilha se torna: [ S, +, F, ), $ ]Agora o buffer tem o símbolo '1' e o topo da pilha é 'S'. De acordo com a tabela, o analisador aplica a regra ' ' que coloca 'F' no topo da pilha. O analisador exibe a regra aplicada na saída. A pilha se torna: [ F, +, F, ), $ ]Como o buffer sempre tem o símbolo '1', a regra a ser aplicada de acordo com a tabela é ' '. O analisador exibe a regra aplicada na saída. A pilha se torna: [ 1, +, F, ), $ ]Durante as próximas duas etapas (para os símbolos '1' e '+'), o símbolo da cabeça do buffer corresponde ao topo da pilha. Cada um é removido do buffer e desempilhados. A pilha se torna: [ F, ), $ ]Para as últimas 3 etapas, o 'F' será substituído na pilha por '1', a regra ' ' será, portanto, escrita na saída. Em seguida, o '1' e o ')' são removidos do buffer de entrada e da pilha. A análise, portanto, termina porque há apenas '$' restante na pilha e no buffer de entrada. Nesse caso, o analisador aceita a string e exibe a lista na saída: [ , , , ]O que é efetivamente uma derivação à esquerda da cadeia inicial. Vemos que uma derivação à esquerda da cadeia é: S → (S + F) → (F + F) → (1 + F) → (1 + 1) |
Como pode ser visto, o analisador executa três tipos de etapas, dependendo do topo da pilha (não terminal, terminal, símbolo '$'):
Essas etapas são repetidas até que o analisador pare; ele terá analisado a string corretamente e gravado uma derivada à esquerda da string na saída ou emitido um erro.
Para explicar como funciona, usaremos a seguinte gramática LISP / Scheme simplificada:
e analisar a próxima string
Calculamos Eps:
Apenas L pode ser cancelado, portanto verdadeiro e falso nos outros casos.
Calculamos o Prime:
Premier(a) = { a } Premier((L)) = { (} Premier(SL) = { (, a } Premier(ε) = ∅Calculamos o seguinte:
Suivant(S) = { $, a, (, ) } Suivant(L) = { ) }Calculamos a tabela de análise:
On prend S → (L), Premier((L)) = { (} donc on ajoute '' à la case (S , (). On prend S → a, Premier(a) = { a } donc on ajoute '' à la case (S , a). On prend L → SL, Premier(SL)={ (, a } donc on ajoute '' aux cases (L , () et (L, a). On prend L → ε, Premier(ε) = ∅ et Eps(ε) = vrai et Suivant(L)={ ) }, donc on ajoute '' à la case (L ,)).( | ) | no | $ | |
S | - | - | ||
eu | - |
Como um lembrete, o analisador lida com uma pilha e um buffer de entrada que pode fornecer os símbolos da sequência de caracteres. Ler o buffer não significa avançar para o próximo símbolo. Ler o buffer significa apenas acessar o símbolo atual. Avançaremos para o próximo símbolo no buffer apenas quando o símbolo desempilhado for um terminal igual ao símbolo atual do buffer. Essa igualdade traduz o fato de que, no estágio atual, a string lida está de acordo com a gramática. O avanço no buffer não é reversível (o analisador nunca volta na cadeia). Isso pode ser representado por uma cabeça de leitura fornecida com uma memória. À medida que esse cabeçote de leitura avança no buffer, a memória armazena o caractere lido. Esta memória pode ser consultada quantas vezes você quiser. Esta consulta corresponde à operação de leitura do buffer. O indicador de reprodução pode avançar para o seguinte símbolo: o que é conhecido como avanço no buffer.
Análise de Palavras |
---|
[ S, $ ]
O analisador lê o primeiro '(' do buffer de entrada e mostra o topo da pilha (o 'S'). Olhando para a tabela, ele sabe que precisa aplicar a regra 1; agora ele precisa reescrever o 'S' em '(L)' em sua pilha, então a pilha se torna: [ (, L,), $ ]No topo da pilha está o símbolo terminal '('. Como ele corresponde ao símbolo atual do buffer (então a string segue, por enquanto, a gramática) este símbolo é exibido e avança para o próximo símbolo em o buffer que é 'a' A pilha tornou-se: [ L,), $ ]Ele exibe 'L' e lê a letra 'a', deve aplicar a regra 3; ele reescreve o 'L' para 'SL': [S, L,), $ ]Ele exibe 'S' e lê a letra 'a', deve aplicar a regra 2; ele reescreve o 'S' para 'a' e, em uma etapa adicional, remove o 'a' por causa da correspondência com o topo da pilha. Depois disso, o símbolo do buffer atual é o segundo '(' e a pilha tornou-se: [ L,), $ ]Agora ele exibe o 'L' e lê a letra '(', ele reescreve o 'L' para 'SL' (regra 3) e o 'S' para '(L)' (regra 1), para que possa remover o '('. O símbolo atual é o primeiro ')' e a pilha tornou-se: [ L,), L,), $ ]Ele exibe o 'L' e lê a letra ')', de modo que pode remover o 'L' usando a regra 4 e, em seguida, pode remover o ')'. O símbolo atual é o segundo ')' e a pilha tornou-se: [ L,), $ ]Da mesma forma que antes, a Regra 4 permite que ele remova o 'L' e ele pode remover o ')'. A pilha ficou vazia: [ $ ]O algoritmo, portanto, conclui positivamente e aplicando a sequência derivada esquerda: . |