Moacyr Francischetti Corrêa, Bacharel em Ciência da Computação, Licenciado em Computação, Especialista em Ciência de Dados e Inteligência Artificial, PhD em Biotecnologia in Silico
Conjunto finito e não vazio de símbolos, a partir do qual se formam as cadeias de uma linguagem. Escreve-se \Sigma.
Ambiguidade
Propriedade de uma gramática que admite, para alguma cadeia da linguagem que gera, duas ou mais árvores distintas — duas estruturas incompatíveis para o mesmo texto. Uma linguagem é inerentemente ambígua quando toda gramática que a gera tem essa propriedade.
Análise léxica
Primeira fase do tradutor: recebe uma sequência de caracteres e devolve uma sequência de unidades classificadas, descartando espaços e comentários pelo caminho.
Análise semântica
Fase que verifica o que a forma do texto não garante — nome usado sem declaração, operação com operandos de tipo incompatível, violação das regras de escopo — e enriquece a árvore com as informações que a tradução para código consome.
Análise sintática ascendente
Estratégia de reconhecimento que parte dos símbolos já lidos e constrói a árvore das folhas para a raiz, aplicando produções em sentido inverso ao da derivação. Executa-se por deslocamento e redução.
Análise sintática descendente
Estratégia de reconhecimento que constrói uma derivação mais à esquerda partindo do símbolo inicial e escolhendo, a cada passo, qual produção aplicar com base nos próximos símbolos da entrada.
Árvore de derivação
Árvore ordenada que registra a estrutura atribuída a uma cadeia por uma gramática: a raiz leva o símbolo inicial, cada nó interno leva um não terminal, os filhos de um nó interno correspondem ao corpo de uma produção aplicada a ele, e as folhas, lidas da esquerda para a direita, formam a cadeia.
Árvore sintática abstrata
Árvore rotulada que representa a estrutura de um texto segundo as construções escolhidas por quem projeta o tradutor, sem os símbolos que serviam apenas para delimitar. Não é determinada pela gramática: gramáticas distintas que geram a mesma linguagem podem produzir a mesma árvore.
Atributo herdado
Valor associado a um símbolo da gramática e calculado a partir do nó pai ou dos irmãos, descendo na árvore. O caso típico é o ambiente de nomes vigente num ponto do texto.
Atributo sintetizado
Valor associado a um símbolo da gramática e calculado a partir dos filhos do nó, subindo na árvore. O caso típico é o tipo de uma expressão, obtido dos tipos das subexpressões.
Autômato finito determinístico (AFD)
Máquina definida por um conjunto finito de estados, um alfabeto, um estado inicial, um conjunto de estados de aceitação e uma função que, para cada estado e cada símbolo, dá exatamente um destino. Aceita a cadeia que a leva do estado inicial a um estado de aceitação.
Autômato finito não determinístico (AFN)
Máquina com a mesma estrutura da determinística, exceto que um estado pode ter vários destinos pelo mesmo símbolo, nenhum destino, ou destinos alcançados sem consumir símbolo algum. Aceita a cadeia para a qual existe ao menos um caminho até um estado de aceitação, e reconhece a mesma família de linguagens que a versão determinística.
Autômato de pilha
Máquina de estados finitos acrescida de uma pilha de memória auxiliar, cujas transições dependem do estado corrente, do símbolo lido e do símbolo no topo dessa memória. É o modelo que reconhece exatamente a família livre de contexto.
Bloco básico
Sequência maximal de instruções consecutivas em que o fluxo de controle entra apenas pela primeira e sai apenas pela última. Começa num líder — a primeira instrução, o alvo de um desvio, ou a instrução seguinte a um desvio — e termina antes do líder seguinte.
Bloco (na construção de Thompson)
Par de estados, chamados entrada e saída, tal que as cadeias que levam de um ao outro são exatamente as denotadas pela subexpressão que o par representa. Nenhuma transição liga o interior desse par a estados fora dele.
Bloco (de uma partição)
Cada um dos subconjuntos não vazios e dois a dois disjuntos em que se divide um conjunto de estados. Refinar é quebrar ao menos um deles em pedaços menores.
Cadeia
Sequência finita de símbolos de um alfabeto. Seu comprimento é o número de símbolos que a compõem, contando repetições.
Cadeia vazia
Sequência de comprimento zero, escrita \varepsilon. Pertence ao conjunto de todas as sequências sobre qualquer alfabeto.
Casamento mais longo
Regra de desempate da fase de símbolos: entre os trechos que começam na posição corrente e satisfazem algum padrão, toma-se o mais comprido; entre trechos de igual comprimento, vence o padrão declarado primeiro na especificação.
Código de três endereços
Linguagem intermediária cujas instruções têm no máximo um operador e três operandos — dois de origem e um de destino —, de modo que toda expressão composta é desmontada em passos elementares ligados por temporários.
Compilador
Programa que traduz um texto escrito numa linguagem para outra preservando o significado. Organiza-se como encadeamento de programas pequenos, cada um de responsabilidade estreita, ligados por artefatos intermediários bem definidos.
Configuração
Registro instantâneo do que uma máquina tem em mãos durante o reconhecimento: o estado corrente, o sufixo da entrada ainda não consumido e, quando a máquina tem pilha, o conteúdo dela do topo para o fundo.
Conflito
Presença de duas ações possíveis na mesma célula da tabela de um analisador ascendente. Uma ação de deslocamento ao lado de uma de redução caracteriza o primeiro tipo; duas reduções por produções distintas, o segundo. É diagnóstico sobre a gramática, não avaria do gerador.
Conjunto dos primeiros
Coleção dos símbolos terminais que podem abrir alguma cadeia derivável de uma dada forma sentencial, acrescida da cadeia vazia quando esta também é derivável dela.
Conjunto dos seguidores
Coleção dos símbolos terminais que podem aparecer imediatamente após um dado não terminal em alguma forma sentencial derivável do símbolo inicial.
Construção de subconjuntos
Algoritmo que produz uma máquina determinística a partir de uma não determinística, tomando como estado do resultado cada conjunto de estados em que a original poderia estar simultaneamente.
Construção de Thompson
Algoritmo que traduz uma expressão regular em máquina não determinística compondo pares de estados por indução na estrutura da expressão, um caso para cada operador.
Contagem de referências
Técnica de recuperação de memória em que cada objeto guarda quantos apontadores o alcançam e é liberado quando esse número chega a zero. Não recupera estruturas circulares, e cobra o custo de atualizar o contador a cada cópia.
Derivação
Sequência de substituições que parte do símbolo inicial de uma gramática e, a cada passo, troca um não terminal pelo corpo de uma de suas produções, até restarem apenas terminais.
Derivação mais à direita
Sequência de substituições em que, a cada passo, o não terminal trocado é o mais à direita da cadeia corrente. É a ordem que a estratégia ascendente reconstrói de trás para a frente.
Derivação mais à esquerda
Sequência de substituições em que, a cada passo, o não terminal trocado é o mais à esquerda da cadeia corrente. É a ordem que a estratégia descendente segue.
Determinização
Transformação que produz, a partir de uma máquina com escolhas múltiplas, outra sem escolha alguma que reconhece a mesma linguagem. O preço é o número de estados, que no pior caso cresce exponencialmente.
Elo de acesso
Campo do registro de ativação que aponta o registro do procedimento imediatamente envolvente no texto do programa. Serve para achar as variáveis não locais, e reflete a estrutura do texto, não a história da execução.
Elo de controle
Campo do registro de ativação que aponta o registro de quem chamou. Serve para desfazer a chamada no retorno, e reflete a história da execução, não a estrutura do texto.
Escopo
Região do texto em que um dado ambiente de nomes vigora. O ambiente vigente num ponto é a composição dos ambientes abertos ali, do mais externo ao mais interno, prevalecendo o interno.
Estado absorvente
Estado de onde nenhuma leitura leva para fora: qualquer símbolo devolve a máquina a ele mesmo. Quando não é de aceitação, chama-se sumidouro, e é para onde vai toda entrada já condenada.
Estados indistinguíveis
Par de estados de uma máquina determinística tais que, para toda continuação da entrada, ambos levam a aceitação ou ambos levam a recusa. Fundi-los não altera a linguagem reconhecida.
Expansão
Sequência de instruções do repertório do alvo cujo efeito coincide com o de uma operação que esse repertório não oferece. O custo mede-se em instruções adicionais por ocorrência.
Expressão regular
Notação que descreve uma linguagem por indução: o vazio, a cadeia vazia e cada símbolo do alfabeto são casos base, e alternância, concatenação e repetição combinam descrições já formadas. Nada além do que essas regras produzem pertence à notação.
Fatoração à esquerda
Transformação que substitui produções de mesma cabeça com prefixo comum por uma que consome o prefixo e outra que decide o resto, de modo que a escolha possa ser adiada até haver informação para fazê-la.
Fecho de um conjunto de itens
Menor coleção que contém os itens dados e, sempre que um deles espera um não terminal, contém também os itens iniciais de todas as produções desse não terminal.
Fecho de Kleene
Operação que forma, a partir de uma linguagem, o conjunto de todas as concatenações de zero ou mais cadeias dela. Inclui sempre a cadeia vazia.
Fecho positivo
Operação que forma, a partir de uma linguagem, o conjunto de todas as concatenações de uma ou mais cadeias dela. Não inclui a cadeia vazia, salvo quando esta já pertencia à linguagem de partida.
Fecho vazio
Conjunto de todos os estados alcançáveis a partir de um conjunto dado percorrendo zero ou mais transições que não consomem símbolo.
Forma sentencial
Cadeia de terminais e não terminais obtida do símbolo inicial de uma gramática por zero ou mais substituições. É direita quando obtida trocando sempre o não terminal mais à direita.
Função de transição
Regra que, dado o estado corrente e o símbolo lido, determina para onde a máquina vai. Sua versão estendida faz o mesmo para uma cadeia inteira, aplicando a regra símbolo a símbolo.
Gramática
Descrição finita que gera cadeias por substituição, formada por um conjunto de não terminais, um alfabeto de terminais disjunto do primeiro, um conjunto de produções e um símbolo inicial.
Gramática de atributos
Gramática livre de contexto em que cada símbolo carrega valores associados e cada produção carrega regras que calculam esses valores em função dos valores dos símbolos da própria produção.
Gramática livre de contexto
Gramática em que toda produção tem um único não terminal do lado esquerdo, podendo o lado direito ser qualquer sequência de terminais e não terminais. A substituição não depende do que cerca o símbolo — daí o nome.
Handle
Ocorrência do corpo de uma produção numa forma sentencial direita cuja substituição pela cabeça desfaz exatamente o último passo da derivação mais à direita. Achá-lo é o problema central da estratégia ascendente.
Hierarquia de Chomsky
Classificação das linguagens em quatro classes encaixadas, obtida por restrição na forma das regras da gramática. A cada classe corresponde um tipo de máquina, e o que separa os tipos é a memória de que dispõem.
Item
Produção com uma posição marcada no corpo, escrita com um ponto. À esquerda do ponto está o que já foi reconhecido e se encontra na pilha; à direita, o que ainda se espera. Com o ponto no fim, indica que o corpo inteiro está na pilha.
Julgamento de tipo
Afirmação de que, sob determinado ambiente de nomes, uma expressão tem determinado tipo. É a unidade sobre a qual as regras de tipagem operam.
Lema do bombeamento
Resultado que estabelece uma repetição obrigatória em toda cadeia suficientemente longa de uma linguagem regular: ela se decompõe em três partes, e a central pode ser repetida ou suprimida sem sair da linguagem. Usa-se por contraposição, para provar que uma linguagem não é regular.
Lexema
Ocorrência concreta, no texto de origem, de um trecho pertencente à linguagem denotada por algum padrão. É uma cadeia de caracteres, e existe num lugar determinado do texto.
Linguagem
Qualquer subconjunto do conjunto de todas as cadeias sobre um alfabeto — inclusive o vazio e o total.
Linguagem denotada
Conjunto de cadeias que uma expressão regular descreve, obtido percorrendo a estrutura da expressão: cada caso base dá um conjunto imediato, e cada operador dá a operação correspondente sobre conjuntos.
Linguagem gerada
Conjunto das cadeias formadas só por terminais que se obtêm do símbolo inicial de uma gramática por alguma sequência de substituições.
Linguagem livre de contexto
Conjunto de cadeias gerado por alguma gramática cujas produções têm um único não terminal do lado esquerdo. Equivale à família reconhecida pelos autômatos de pilha, e contém estritamente a família regular.
Linguagem reconhecida
Conjunto das cadeias que levam uma máquina do estado inicial até um estado de aceitação.
Linguagem regular
Conjunto de cadeias reconhecido por algum autômato finito determinístico — o que equivale a ser descrito por alguma expressão regular, e a ser gerado por alguma gramática com a restrição de forma correspondente.
LL(1)
Critério de analisabilidade descendente. Uma gramática livre de contexto o satisfaz quando a produção a aplicar fica determinada pelo não terminal corrente e por um único símbolo de antecipação, o que torna possível reconhecer sem retroceder.
Máquina de pilha
Máquina virtual cujo estado de avaliação é uma sequência de operandos acessível apenas pelo topo. Cada instrução consome dali um número fixo de valores e produz zero ou um.
Máquina virtual
Especificação de repertório de instruções, estado e semântica de execução realizada por um programa interpretador em vez de por circuito.
Minimização
Transformação que produz, a partir de uma máquina determinística, a de menor número de estados que reconhece a mesma linguagem. O resultado é único a menos de renomeação dos estados.
Modo de pânico
Estratégia de recuperação depois de uma recusa: registra-se o erro, descartam-se símbolos até encontrar o primeiro pertencente a um conjunto de sincronização fixado de antemão, e a leitura recomeça dali. Serve para achar vários erros numa só passagem.
Não terminal
Símbolo de uma gramática que não aparece nas cadeias geradas e funciona como nome de uma construção da linguagem, a ser trocado pelo corpo de alguma de suas produções.
Padrão
Descrição da forma que os trechos de uma dada categoria podem assumir. Nesta obra é uma expressão regular sobre o alfabeto do texto de origem, e o conjunto que ela denota é o de todos os trechos daquela categoria.
Prefixo viável
Cadeia que pode ocupar a pilha de um analisador ascendente em algum ponto de alguma análise bem-sucedida, isto é, que não ultrapassa a extremidade direita de um handle.
Prefixos distinguíveis
Par de cadeias para o qual existe uma continuação que leva uma delas para dentro da linguagem e a outra para fora. Essa continuação chama-se testemunha, e cada par assim obriga a máquina a ter dois estados diferentes.
Produção
Regra de uma gramática que autoriza trocar uma cadeia de símbolos por outra. Na forma livre de contexto, o lado esquerdo é um único não terminal, chamado cabeça, e o direito é o corpo.
Recursão à esquerda
Propriedade de um não terminal que produz, em um ou mais passos, uma cadeia começada por ele mesmo. Faz laçar indefinidamente o analisador descendente, e remove-se reescrevendo as produções sem alterar a linguagem gerada.
Registro de ativação
Bloco de memória associado a uma chamada de procedimento, contendo o que aquela chamada precisa e não pode compartilhar com outras: endereço de retorno, parâmetros, espaço do valor de retorno, variáveis locais, temporários e os elos de controle e de acesso.
Representação intermediária
Linguagem interposta entre a fonte e o alvo, com uma tradução de cada fonte para ela e uma dela para cada alvo. Com M fontes e N alvos, custa M + N traduções, contra M \times N na tradução direta.
Seleção de instruções
Escolha, para cada operação da representação intermediária, da sequência de instruções do alvo que a realiza. Quando a operação não existe no repertório, a escolha é uma expansão.
Símbolo inicial
Não terminal a partir do qual começa toda derivação de uma gramática, e que nomeia a construção mais externa da linguagem.
Sistema de tipos
Conjunto finito de regras de inferência que atribuem tipos às expressões a partir dos tipos das subexpressões. Uma expressão é bem tipada quando alguma sequência de aplicações dessas regras lhe atribui um tipo.
Tabela de símbolos
Estrutura que associa cada nome declarado à sua descrição — natureza, tipo, posição da declaração — e oferece as operações de declarar, consultar e gerir a entrada e a saída de escopos. É a única estrutura que atravessa as duas metades do tradutor.
Tabela de transição
Representação da função de transição como matriz indexada por estado e por símbolo, em que cada célula guarda o destino. Dá acesso em tempo constante e ocupa espaço proporcional ao produto das duas dimensões, esteja a célula ocupada ou não.
Temporário
Nome criado pelo tradutor, sem correspondente no texto de origem, para guardar um resultado parcial da desmontagem de uma expressão composta.
Terminal
Símbolo de uma gramática que aparece nas cadeias geradas e não pode ser trocado por nada. No tradutor, corresponde às categorias que a fase de símbolos produz.
Token
Par formado pela categoria — o nome do padrão que reconheceu o lexema — e pelos atributos de que a fase seguinte precisa, tipicamente o próprio lexema, a posição de origem e, para nomes, a entrada correspondente na tabela de símbolos.
Transição vazia
Passagem de um estado a outro sem consumir símbolo da entrada. A posição na cadeia permanece a mesma, e a passagem pode ocorrer a qualquer momento em que a máquina esteja no estado de origem.
