Sobre Autómatos e Linguagens de Programação

Not 01(0+1)*

Em Autómatos e Linguagens de Programação faz-se uma introdução formal à teoria e às técnicas da análise e definição de linguagens de programação.

Os conceitos e as técnicas tratadas são ilustradas num capítulo final, onde é definida uma linguagem de programação simples e implementado um interpretador para essa linguagem.

Dado um programa python,

# file: guide.py
def resposta():
    return 42

print(f"The answer is {resposta()}.\n")

Quando este programa corre, por exemplo

> python guide.py <enter>
> The answer is 42.

o que acontece entre o <enter> na linha python guide.py e aparecer o texto The answer is 42. na consola?

O interpretador do python, entre outras coisas:

  1. Lê o ficheiro guide.py do sistema de ficheiros.
  2. Processa o conteúdo desse ficheiro de forma a determinar se corresponde a um programa válido (em python, claro).
  3. Executa as instruções desse programa, incluindo:
    1. A definição da função resposta() e respetivas "sub-instruções".
    2. O cálculo do valor da expressão "The answer is {resposta()}.\n".
    3. Escrever na consola o valor dessa expressão.

Outro exemplo: uma calculadora "básica".

Para programar uma calculadora para a linha de comandos, o programa deve receber uma string com uma conta e escrever o respetivo resultado. Por exemplo > calc "2+3*4" deve escrever 14.

Quais são as dificuldades de fazer este programa? Há várias:

  • Temos de saber verificar se o input está "bem formado". Por exemplo 2+3*4 está bem, mas +234** nem por isso...
  • Exatamente, o que "significa" cada "símbolo"? 2 é 2? E se aparecer em 20?
  • E como tratar "sequências" de símbolos? 2+3 é sempre 2+3? Mas então 2+3*4 não devia ser 14 mas 20...

Estas são exatamente as questões tratadas em ALP:

  • Quais são os símbolos (ou letras) e as palavras válidas (isto é, as sequências de símbolos que sabemos tratar)?
  • Como definir e representar todas as palavras válidas, isto é, a linguagem?
  • Como distinguir as palavras válidas das inválidas?
  • Como atribuir significado às palavras válidas? Isto é, como executar um programa?

Objetivos

Ao completar esta disciplina deve conseguir:

  1. Discutir máquinas de estados finitos.
  2. Construir expressões regulares, autómatos e gramáticas para aceitar/gerar linguagens especificadas; Converter entre representações equivalentes.
  3. Determinar o lugar de uma linguagem na Hierarquia de Chomsky e os principais problemas nas definições da sintaxe de linguagens de programação.
  4. Usar gramáticas formais para especificar a sintaxe de linguagens, ferramentas declarativas para gerar analisadores e scanners.
  5. Definir uma semântica formal e uma árvore de sintaxe abstrata para uma linguagem de programação simples.
  6. Explicar como os programas que processam outros programas tratam os outros programas e as vantagens de ter representações de programas.
  7. Escrever um programa para processar alguma representação de código.

Programa & Bibliografia

Programa

  • Sobre ALP
    • Objetivos
    • Programa & Bibliografia
    • Avaliação
  • Palavras, Linguagens e Expressões Regulares
    • Alfabetos, Palavras e Linguagens
    • Expressões Regulares
    • < Exercícios >
  • Autómatos Finitos
    • Autómatos Finitos Deterministas
    • Computação Não-Determinista
    • Minimização e Composição de AFD
    • O Pumping Lemma
    • < Exercícios >
  • Gramáticas e Autómatos de Pilha
    • Gramáticas Livres de Contexto
    • Autómatos de Pilha
    • < Exercícios >
  • Análise Sintática
    • Tipos de Análise Sintática
    • Limpeza de uma Gramática
    • < Exercícios >
    • Gramáticas LL
    • < Exercícios >
    • Gramáticas LR
    • < Exercícios >
  • Representação & Execução de Programas
    • Árvore de Sintaxe Abstrata
    • Análise Semântica
    • Suporte para um Interpretador
    • < Exercícios >

Bibliografia

  • Languages and Machines: An Introduction to the Theory of Computer Science, 2 ed. Thomas A. Sudkamp. Addison Wesley, 1997. (320 páginas)
  • Compilers: Principles, Techniques and Tools, Alfred V. Aho, Ravi Sethi e Jeffrey D. Ullman. Addison Wesley, 1986. (1038 páginas)

Recursos

Palavras, Linguagens e Expressões Regulares

Neste capítulo são fixadas bases rigorosas para a definição de linguagens de programação e a análise dos respetivos programas.

É necessário começar por definir rigorosamente e sem ambiguidades, isto é, matematicamente, certos conceitos fundamentais como "símbolo" (ou "letra"), "palavra" e "linguagem".

Também são definidas as "expressões regulares", que permitem representar certas linguagens formais de forma compacta.

Com as "expressões regulares" tem-se uma forma rigorosa de definir certas linguagens formais. É o primeiro passo no processo para representar linguagens de programação.

Alfabetos, Palavras e Linguagens

Era uma vez, num reino muito muito distante, ...

Símbolos e Alfabetos

Alfabeto, Símbolo. Um alfabeto é um conjunto finito de símbolos, também designados letras (em inglês: symbols, letters, tokens).

Os alfabetos são normalmente representados por maiúsculas gregas (sigma) e (gama) e os símbolos por minúsculas romanas .

Por exemplo:

  • O alfabeto do português tem os seguintes símbolos: .
  • Os símbolos e formam um alfabeto binário. Outro alfabeto binário muito usado em ALP é .
  • Os números naturais podem ser escritos em base 10 usando o alfabeto .
  • Para as expressões algébricas usa-se o alfabeto .

As linguagens de programação têm um conjunto de palavras reservadas, como while, if, etc. que são atómicas, isto é, não podem ser divididas.

O símbolo "if" não é, em termos da linguagem de programação, um "i" seguido de um "f", mas um símbolo que não pode ser decomposto.

Já fragmentos de programas como if (x == 42) { return "yes"; } else { return "no"; } são compostos. Nesta instrução condicional (x == 42) é o teste (ou guarda), { return "yes"; } o bloco positivo e { return "no"; } o bloco negativo. Neste caso a instrução resulta de uma regra do tipo

Condicional := if ( Condição ) { Instruções } else { Instruções }

Por sua vez a guarda (Condição) e os blocos de Instruções podem ser decompostos, até chegarmos a símbolos atómicos como (, ==, return, etc.

Palavras

Palavra. Uma palavra sobre um alfabeto é uma sequência finita de símbolos desse alfabeto (em inglês: word).

Formalmente, uma palavra de comprimento é uma função que a cada inteiro .

As palavras são normalmente representadas pelas minúsculas romanas .

Palavra Vazia. A palavra vazia (em inglês: empty word, null, nil) é a única palavra de comprimento 0 e representa-se pela letra grega (lambda). Também é comum usar-se ou (epsilon) para representar a palavra vazia.

Não confundir a palavra (que tem comprimento 0) com um símbolo. Estes, como palavras, têm comprimento um.

Propriedades do Comprimento das palavras

  • O comprimento da palavra é normalmente representado por .
  • Para a palavra vazia, . Em geral, se então . Isto é, .

Fecho de Kleene

Dado um alfabeto, interessa considerar todas as palavras que podem ser formadas com essas letras.

Por exemplo, para representar números em binário usam-se palavras sobre . Mas, depois de se definirem todas as palavras, há que determinar quais as que interessam. Por exemplo, embora e sejam palavras binárias (distintas), se interpretadas normalmente, ambas correspondem ao número e portanto há aqui uma ambiguidade. Será possível definir uma linguagem que continue a representar todos os números mas sem ambiguidades?

Para abordar estas questões tem de se começar por definir rigorosamente o conjunto de todas as palavras que se podem obter com um dado alfabeto.

Fecho de Kleene. O fecho do alfabeto é o conjunto de todas as palavras sobre , representa-se por e fica definido pelas seguintes condições:

  • base .
  • passo Se e então .
  • fecho Qualquer palavra só pode ser obtida por um número finito de aplicações do passo a começar na palavra vazia. E reciprocamente, qualquer palavra obtida a partir de por aplicações do passo em número finito está em .

Esta definição exclui a possibilidade de palavras infinitas. Mas isto não significa que exista um limite ao comprimento das palavras em . Pelo contrário, se então, para qualquer existe pelo menos uma palavra de comprimento .

Exercício: Porquê? E porque é que acima é referida a condição ""? O que é ?

No fecho de um alfabeto também ficam excluídas palavras formadas por símbolos de outros alfabetos. Por exemplo, a palavra não está em .

Logo a primeira condição na definição de inclui a palavra vazia. Como muitas vezes é conveniente excluir define-se

Exercício: Mostre que .

Operações com Palavras

Comprimento

Ainda não foi apresentada uma definição rigorosa de comprimento de uma palavra. Usando um esquema recursivo:

Comprimento. A função comprimento é calculada pelas seguintes regras:

  • base .
  • passo , com .

Por exemplo, para calcular :

  • Como , aplicar-se a regra do passo: fazendo tem de ser e , e obtem-se .
  • Ainda não está calculado o valor de . Tornando a aplicar o passo: .
  • Uma nova aplicação do passo: .
  • Finalmente, pela base: , portanto e, sucessivamente, obtém-se e .

Também é comum usar-se a notação para indicar o número de ocorrências do símbolo na palavra .

Por exemplo: .

Concatenação

O operação fundamental das palavras é a "concatenação". A concatenação de hello com world é helloworld. Para definir rigorosamente esta operação:

Concatenação. A concatenação (ou produto) de duas palavras representa-se por ou apenas e é uma operação binária definida por:

  • base Se então .
  • passo Se então
    1. Existe uma palavra e uma letra tal que .
    2. .

Por exemplo, para calcular a concatenação de com :

  • O comprimento de é 2, portanto temos de aplicar o passo: .
  • Precisamos de calcular . Pela regra do passo: .
  • Finalmente, é calculada pela regra base: .
  • Andando para trás: e, portanto, .

Potência

A repetição de concatenações define as potências, tal como a multiplicação dos números.

Potências. As potências da palavra são (informalmente):

Por exemplo, mas , seguindo as regras normais de precedência das operações.

Inversa

Finalmente, as palavras (enquanto sequências de símbolos) podem ser escritas "de trás para a frente":

Inversa. A inversa de , representada por (ou ) é calculada pelas seguintes regras:

  • base Se então .
  • passo Se então e .

Por exemplo, se então .

Propriedades das Operações de Palavras

O que acontece à inversa de duas palavras concatenadas?

Para quaisquer palavras ,

Demonstração (informal): Se a conclusão é evidente. Caso contrário e com todos os . Então:

O fecho também tem propriedades interessantes.

Se forem alfabetos,

  • .
  • .
  • .
  • Se então é infinito.
  • Se então .

Por fim, a concatenação tem propriedades semelhantes às do produto (de números).

Sejam .

  • associativa .
  • elemento neutro .
  • não comutativa Em geral, .
  • aditiva .
  • unicidade Cada palavra só pode ser escrita de uma única forma como concatenação de símbolos. Isto é, se e e então (mesmo comprimento) e para cada (mesmos símbolos) .

Ordenações de Palavras

Uma palavra pode "conter" outra. Por exemplo, palavra contém pala no início, ala no "meio" e lavra no fim. Estes três casos ilustram as definições que se seguem:

Subpalavra, prefixo, sufixo. Sejam .

  • subpalavra se .
  • prefixo se .
  • sufixo se .

Fica claro que os prefixos são casos particulares das subpalavras (quando ) e que cada palavra é subpalavra de si própria (quando ).

Outro caso importante é a ordem lexicográfica (dos dicionários), onde se usa a ordem das letras para ordenar as palavras.

Ordem Lexicográfica. Supondo que o alfabeto está ordenado, . Então se:

  • .
  • Caso contrário, e com .

Esta definição abrange dois casos:

  1. por < porque porque por é um prefixo de porque.
  2. porque < portugal porque, como porque = por_q_ue e portugal = por_t_ugal então portugal e porque têm um prefixo comum, por, e "divergem primeiro" nas letras q e t. Como q < t então porque < portugal.

A ordem lexicográfica tem um problema interessante: Quantas palavras existem entre e , num alfabeto binário?

Por exemplo [Exercício: porquê?]. Mas também . De facto, para qualquer . Portanto, seguindo a ordem lexicográfica, há infinitas palavras entre e .

Esta conclusão, embora dramática, mostra que a ordem lexicográfica é inútil na importante tarefa de enumerar (isto é, listar) todas as palavras por ordem. Para resolver este problema é necessária mais uma ordem entre palavras:

Ordem Mista. Dadas duas palavras , se ou ( e ).

Dito de outra forma, a ordem mista define o seguinte processo:

  1. Primeiro, as palavras são agrupadas por comprimentos iguais: todas as palavras de comprimento 0 antes das de comprimento 1, todas as de comprimento 1 antes das de 2, etc.
  2. Depois, em cada grupo, as palavras (todas com o mesmo comprimento) são ordenadas lexicograficamente.

Revisitando o exemplo anterior:

  • e têm o mesmo comprimento. Portanto, são comparadas lexicograficamente: porque .
  • O comprimento de é maior que o de . Portanto, .
  • e têm o mesmo comprimento. Lexicograficamente, portanto .

De facto a ordem mista é uma ferramenta essencial porque permite "avançar passo-a-passo" no conjunto de todas as palavras, sem deixar nenhuma de fora. Mais concretamente:

A ordem mista define uma sequência de todas as palavras. No caso do alfabeto binário, com :

Sucessor

A ordem mista permite começar na primeira palavra, avançar para a seguinte, depois para a seguinte, etc. da mesma forma são contados os números: 0, 1, 2, etc.

A passagem de um número para o seguinte (x++) tem nome, sucessor, que também se aplica às palavras:

Sucessor. Seja um alfabeto ordenado. A função sucessor tem assinatura e calcula-se pelas seguintes regras:

  • base .
  • passo Se então . Caso contrário, .

Voltando ao exemplo anterior:

Visto de outra forma, usando o sucessor obtém-se uma sequência que começa na palavra vazia e percorre todas as palavras:

Há uma clara relação entre a ordem mista e a função sucessor.

Seja a sequência de todas as palavras de que se obtém com a ordem mista e uma palavra qualquer.

  1. .
  2. Se então existe uma palavra tal que .
  3. .

O que este teorema afirma, especialmente na igualdade , é que a ordem mista e a função sucessor são aspetos diferentes da mesma enumeração das palavras.

Linguagens

Numa linguagem de programação nem todas as palavras possíveis correspondem a programas válidos. Por exemplo:

2 return) *
    : dobro def (x

é uma palavra que pode ser formada com o alfabeto do python, mas não é um programa.

É necessário, de alguma forma, distinguir as palavras que são "válidas" das outras que não o são. De novo, encontramos na matemática exatamente as ferramentas necessárias.

Linguagem. Uma linguagem é um conjunto de palavras sobre um certo alfabeto. Isto é, é uma linguagem sobre se .

Esta definição de linguagem parece dizer pouco, mas por enquanto serve exatamente para o que se pretende.

Por exemplo, se for a linguagem dos programas python então mas .

Mais tarde será enunciado e tratado o Problema Principal de ALP:

Problema Principal de ALP (versão 0). Dada uma linguagem e uma palavra no mesmo alfabeto, determinar se .

Entretanto, como uma linguagem é (apenas) um conjunto de palavras, tem um certo número de elementos, que pode ser infinito (quantos programas python existem?): Se for uma linguagem, representa o número de elementos de .

Outros exemplos de linguagens são:

  • binárias , , etc.
  • As palavras do português, sobre o alfabeto romano. Por exemplo, a, aba, abade, etc. mas não aa, prof, tásse, xkcd, etc.
  • Os programas de uma linguagem de programação.
  • As frases do português, sobre o alfabeto formado pelas palavras do português. Por exemplo bom dia, a aula é longa, etc. mas não dia dia dia, aula a é longa, etc.

Muitas vezes é útil visualizar-se uma linguagem de forma a explorar a estrutura das suas palavras. Isso pode ser feito através de árvores:

Árvore de uma Linguagem. Seja uma linguagem sobre .

Os vértices (ou nós) da árvore de (ou diagrama de ) são palavras de e cada aresta (ou arco) tem um símbolo de . Além disso, todas as arestas são da seguinte forma: se e então é uma aresta. A raíz da árvore é a palavra vazia.

Cada vértice é representado por um círculo com a respetiva palavra lá dentro. Uma palavra da linguagem é representada por um círculo duplo.

Por exemplo, tem a seguinte árvore (onde os vértices irrelevantes foram omitidos):

Árvore (parcial) de
Árvore de uma Linguagem
As palavras de estão em círculos duplos.

Operações com Linguagens

Como conjuntos, as linguagens podem ser combinadas pelas operações comuns: união, intersecção, etc. Além disso, como os seus elementos são palavras, podem ser definidas operações adicionais, específicas das linguagens (concatenação, fecho, etc).

Operações com Linguagens. Sejam linguagens sobre . Estão definidas as seguintes operações de conjuntos:

  • união .
  • intersecção .
  • subtração .
  • complemento .

Adicionalmente, usando as operações de palavras:

  • concatenação .
  • potências .
  • fechos .
  • inversão .

Alguns exemplos das operações específicas das linguagens: Sejam . Então:

  • .
    • As palavras de foram formadas escolhendo primeiro uma palavra de e depois uma palavra de .
    • A palavra pode ser obtida de suas formas: e .
  • .
  • .
  • .

Confusões com a palavra vazia, o conjunto vazio, etc.

  1. A palavra vazia, , não é um símbolo. Qualquer símbolo, como palavra, tem comprimento 1. A palavra vazia tem comprimento 0.
  2. O conjunto vazio, , tem 0 elementos. Para tornar este facto mais explícito também se escreve .
  3. O conjunto tem um elemento, . Portanto, não é o conjunto vazio.

Exemplo. Aqui (e só no âmbito deste exemplo) estamos a distinguir explicitamente os símbolos usando plicas, como em 'a', e as palavras usando aspas, como em "ab".

  1. O alfabeto {a, b} tem dois símbolos: 'a' e 'b'.
  2. Uma palavra é uma (qualquer) sequência finita de símbolos.
    • Por exemplo "abba", "baba", "aa", etc.
  3. Todas as palavras de comprimento 2 são "aa", "ab", "ba", "bb".
  4. Também poderíamos listar todas as palavras de comprimento 3 (num total de oito palavras), etc.
  5. Todas as palavras de comprimento 1 são "a" e "b".
    • Se quiséssemos ser terrivelmente rigorosos, teríamos de dizer que 'a' e "a" são diferentes porque 'a' é um símbolo e "a" é uma sequência de símbolos, tal como, por exemplo, o inteiro 1 é completamente diferente de [1], que é uma lista de inteiros.
    • Raramente é necessário distinguir explicitamente os símbolos das palavras de comprimento um.
  6. Só há uma palavra com comprimento zero. Como sequência, "" é a (única) com zero símbolos. Em vez de "" escreve-se λ (ou ε ou ϵ).
    • λ não é um símbolo mas uma palavra. Escrita por extenso é "".
  7. Usando a concatenação de palavras podemos escrever, por exemplo: "abba" = "ab" · "ba".
    • Outras formas de obter "abba" são "abba" = "a" · "bba", "abba" = "abb" · "a", etc.
    • Em particular também "abba" = "abba" · λ ou "abba" = λ · "abba" ou mesmo "abba" = λ · "a" · λ · "bba".
    • Nestes exemplos o λ nunca aparece entre "..." pois isso é o equivalente a um erro sintático. Também não escrevemos 2 */ 3 quando fazemos contas...
  8. Em geral não se escrevem os símbolos como 'a', as palavras como "abab" nem as concatenações como "aa" · "ba".
    • Portanto, em vez de "abba" = λ · "a" · λ · "bba" o que escrevemos é simplesmente abba = λaλbba.
    • Este abuso de notação pode facilitar a leitura errada de λ como um símbolo, à semelhança de a e b.

Linguagens e Expressões Regulares

Uma forma de especificação formal de linguagens.

Na secção anterior observou-se que para definir uma linguagem de programação o fecho, , não é adequado porque tem "demasiadas" palavras.

Mais precisamente, a situação é a seguinte:

Para definir uma linguagem de programação começa-se for escolher um certo alfabeto e, sobre esse alfabeto, define-se uma linguagem cujas palavras são exatamente os programas válidos da linguagem de programação.

O Problema Principal de ALP (versão 0)Dada uma linguagem e uma palavra no mesmo alfabeto, determinar se – não desenvolve condições para determinar . É necessário um "sistema" que permita definir linguagens formais e que seja:

  1. Computável: Existe um algoritmo que recebe como entrada uma palavra e ao fim de um número finito de passos produz uma resposta sim ou não conforme ou não.
  2. Eficiente: O número de passos referido no passo anterior não deve ser "muito maior" que o comprimento da palavra.
  3. Adequado: Deve ser possível definir (os programas de) qualquer linguagem de programação.

Portanto:

Problema Principal de ALP (versão 1): Determinar um sistema computável e eficiente para determinar se e que seja adequado (i.e., é uma linguagem de programação).

Linguagens Regulares

As operações entre linguagens (principalmente, a união, a concatenação e o fecho) permitem começar por linguagens muito simples e definir formalmente, rigorosamente, sem ambiguidades, linguagens mais complexas. Por exemplo, a partir do alfabeto binário , a linguagem das palavras com um número par de é .


O ênfase em "formal, rigoroso, não ambíguo" é necessário para resolver algoritmicamente o Problema Principal de ALP. Mais especificamente, pretende-se obter um programa que tem como entrada uma especificação formal de uma linguagem 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 é, pretende-se definir um programa Super tal que

  1. Se e for uma especificação formal de uma linguagem de programação L: PL = Super(e).
  2. Seja p uma palavra. PL(p) é verdade ou falso conforme p in L ou não.
  3. Tanto Super quanto PL devem ser eficientes.

O Problema Principal de ALP, nas suas várias versões, trata de encontrar uma "especificação formal" adequada e obter os programas Super e PL. De facto, a resolução seguida em ALP até vai mais longe: A resposta a é calculada de forma que quando for um programa válido (isto é, "" é verdade) também se obtém uma "representação intermédia" de , apta a ser executada.


Por enquanto define-se a classe das linguagens regulares:

Linguagem Regular (LR). Seja um alfabeto. Uma linguagem regular sobre define-se recursivamente pelas seguintes regras:

  • base Os conjuntos e, para cada são linguagens regulares.
  • passo Se e forem linguagens regulares então também são linguagens regulares.
  • fecho Um conjunto de palavras é uma linguagem regular se, e só se, pode ser definido através de um número finito de aplicações do passo a partir dos conjuntos da base.

Alguns exemplos de linguagens regulares:

  • .
  • Qualquer linguagem finita.
  • O conjunto das palavras que começam em é infinito mas regular: .

Expressões Regulares

A notação usual dos conjuntos, com , etc. torna difícil escrever e ler linguagens regulares. Para aliviar esse problema usa-se uma notação específica.

Expressão Regular (ER). Seja um alfabeto. Uma expressão regular sobre define-se recursivamente pelas seguintes regras:

  • base As expressões vazio , palavra vazia e, para cada são expressões regulares.
  • passo Se e forem expressões regulares então a união , a concatenação (ou produto) e a iteração também são expressões regulares.
  • fecho Uma expressão é uma expressão regular se, e só se, pode ser definida através de um número finito de aplicações do passo a partir das expressões da base.

Alguns exemplos de expressões regulares:

  • .
  • Qualquer palavra de .
  • .

Antes de avançar no estudo das ER e LR é importante esclarecer o seguinte ponto importante sobre a notação das expressões regulares:

Regras de Simplificação das Expressões Regulares. A escrita completa de uma expressão regular pode (ainda) ser confusa, por causa dos parêntesis:

Para simplificar esta escrita usam-se as seguintes regras de simplificação:

  1. Sempre que possível não se usa o símbolo da concatenação. Isto é, em vez de escreve-se .
  2. A iteração tem precedência sobre e sobre . Isto é, é , não . Igualmente, é , não .
  3. A concatenação tem precedência sobre a união . Isto é, é , não .

Com estas regras a ER acima fica com o seguinte aspeto:


Diagramas das Expressões Regulares

As expressões regulares podem ser representadas por um diagrama gráfico cuja visualização pode ajudar a entender a sua estrutura.

Diagrama de uma Expressão Regular (Diagrama de Wirth). O diagrama de uma expressão regular é um grafo orientado definido para as operações base e passo da seguinte forma:

Forma da Expressão RegularTipoSub-Grafo
símbolo ou re-symbol
concatenaçãore-concat
uniãore-union
iteraçãore-star

Por exemplo, o diagrama da expressão regular pode ser obtido da seguinte forma:

OperaçãoDiagrama
Iníciore-exemplo-01
Concatenaçãore-exemplo-02
Iteraçõesre-exemplo-03
Uniõesre-exemplo-04

No diagrama final há várias arestas que podem ser eliminadas e ainda continuar a representar a expressão regular inicial. Por exemplo, uma das duas arestas consecutivas, no cento do diagrama, pode ser eliminada.

OperaçãoDiagrama
Simplificaçãore-exemplo-05

Neste caso foi simples detetar uma aresta que podia ser eliminada. Em geral, quais são as arestas que podem ser eliminadas?

Teorema da Eliminação de Arestas Vazias. A aresta fig-teo-arestas-vazias pode ser eliminada se:

  • O vértice não é final e não saem mais arestas de ou
  • O vértice não é inicial e não entram mais arestas em .

Alternativamente, a aresta não pode ser eliminada se:

  • O vértice é final ou saem mais arestas de e
  • O vértice é inicial ou entram mais arestas em .

Usando o teorema da eliminação de arestas vazias:

OperaçãoDiagrama
Simplificação (II)re-exemplo-06

Semântica das Expressões Regulares

O número quatro pode ser referido de várias formas: IV, 100, 4, quatro, 2+2, etc. Todas essas formas são expressões – texto, sintaxe – cuja interpretação – significado, semântica – é um certo objeto abstrato.

Esta é também a relação entre as linguagens regulares e as expressões regulares: As linguagens são conjuntos (objetos matemáticos, abstratos) que podem ser representados por certas expressões. Isto é, a semântica das ER são as LR. Reciprocamente, as ER são uma sintaxe para as LR. Mais precisamente:

Linguagem Representada por uma Expressão Regular. Qualquer expressão regular sobre representa uma certa linguagem, definida pelas seguintes regras:

  • .
  • .
  • Para cada .
  • Se for uma expressão regular então .
  • Se forem expressões regulares então .
  • Se forem expressões regulares então .

Até aqui, e neste enunciado em particular, estão a ser usados os mesmos símbolos (sintaxe), por exemplo com significados (semântica) muito diferentes. Por exemplo, "" numa ER é apenas um símbolo que liga outras ERs — da mesma forma que + liga \quaddois números\quad duas expressões numéricas. Mas "" numa LR é uma operação entre conjuntos, que tem um valor bem definido — tal como 2 + 2 tem um valor bem definido (sob as convenções comuns).

Além disso, foi apenas definida uma função entre ERs e certos conjuntos de palavras – nada afirma, até aqui, que é regular. Isto é, se for uma expressão regular então é uma linguagem. A relação com as linguagens regulares fica esclarecida a seguir:

Equivalência de Expressões e Linguagens Regulares.

  • Cada expressão regular representa uma linguagem regular. Mais especificamente: Se for uma expressão regular sobre então é uma linguagem regular sobre .
  • Cada linguagem regular pode ser representada por uma expressão regular. Mais especificamente: Se for uma linguagem regular sobre então existe uma expressão regular sobre , , tal que .

Isto é, as expressões regulares denotam exatamente as linguagens regulares e a relação entre umas e outras é a função . Dito de outra forma, as LR são a semântica associada às ER e, reciprocamente, as ER proporcionam uma sintaxe para as LR.

Por exemplo, a linguagem dos inteiros sem sinal e sem à esquerda (isto é, a representação binária dos números inteiros positivos):


Há ainda outro tipo importante de equivalência: Depois de fixado o conjunto de símbolos e de operações, duas expressões (sintaxes) muito diferentes podem ter o mesmo valor (semântica).

Por exemplo o número quatro (o objeto matemático abstrato) pode ser representado pelas expressões , , , etc. Nestes casos escreve-se , etc. Mas em ALP é preciso cuidado com o sinal "". As expressões "" e "" são sintaticamente diferentes (por exemplo, porque "" tem apenas um símbolo e "" tem três) mas equivalentes (a mesma semântica).

Nas linguagens regulares "" representa a igualdade entre conjuntos, uma relação matemática. No caso das expressões regulares é necessário esclarecer se se trata de igualdade sintática ou de uma equivalência (isto é, uma igualdade semântica). Por exemplo, e são diferentes ao nível sintático: diferem logo no primeiro símbolo. Mas ambas representam a mesma linguagem regular, o conjunto . Isto é, .

Equivalência de Expressões Regulares. Duas expressões regulares, , sobre são equivalentes, , se .

No uso comum de expressões regulares pretende-se usar a equivalência, não a igualdade sintática, pelo que "" normalmente representa a equivalência, apesar de esta escrita ser um abuso da notação. Isto é, escreve-se em vez de , porque é mais conveniente. Os casos em que se trata a igualdade sintática devem ser explicitamente assinalados como tais.


Propriedades das Expressões Regulares

Sejam expressões regulares sobre o alfabeto . Considerando as operações de união e concatenação:

Para o fecho:

Com estas equivalências uma ER inicialmente complicada (isto é, comprida e/ou profunda) pode ser simplificada. Um exemplo imediato é . Outro exemplo:

Aplicando as regras de equivalência


As linguagens e expressões regulares são o passo atual para resolver o Problema Principal de ALP (versão 1)Determinar um sistema computável, eficiente e adequado para definir linguagens de programação.

Nesse sentido importa responder às seguintes questões:

  1. Dada uma linguagem regular , como obter um sistema computável e eficiente para determinar se ?
  2. As linguagens regulares são adequadas para definir todas as linguagens de programação? Por exemplo, será possível definir a sintaxe dos programas Python ou Java usando apenas expressões regulares?

Estas questões são resolvidas no próximo capítulo, Autómatos Finitos, onde é definido e estudado um modelo abstrato de computador simples e como este se relaciona com as ER e LR.

Palavras, Linguagens e Expressões Regulares — Exercícios


Otimização Prematura
O xkcd obrigatório.

Indicações gerais para os exercícios de implementação

Quase todos os exercícios de implementação descrevem uma função ou estrutura de dados sujeita a algumas condições. É da sua responsabilidade testar os casos suficientes para assegurar o comportamento esperado.

A linguagem de programação que usar é indiferente, desde que não dê tiros nos pés com opções aberrantes tipo "C" ou "COBOL". Ou "JavaScript". Principalmente "JavaScript".

Também não é fundamental a maneira como organiza o código, seja em classes ou de outra forma, desde que o organize logicamente.

Mais alguns princípios gerais importantes:

  • Os atributos das estruturas devem ter permissões tão restritas quanto possível. Se não for necessário alterar um atributo, não o permita. Se o atributo não tem de ser lido, esconda-o.
  • DRY, Don't Repeat Yourself, Não se repita. Se está a escrever código repetido está a fazer um disparate. Grande. Pare imediatamente e pense como vai evitar as repetições repetições.
  • Premature optimization is the root of all evil, A otimização prematura é a raiz de todos os males. O seu código pode ser sempre melhorado: mais rápido, mais geral, mais específico, mais isto e aquilo. Se a melhoria não for necessária não perca tempo com ela.
  • Use as ferramentas e adquira os conhecimentos do Engenheiro Informático que vai ser:
    • Escolha e use ferramentas com boas comunidades e suporte. Torne-se fluente no seu ambiente de trabalho, na linha de comandos, no editor/ide, a usar repositórios, debuggers, testes, linters, profilers, etc.
    • Se ainda não o fez, instale um sistema operativo no seu computador. Infelizmente, em geral, os computadores quando vêm da loja trazem instalada uma coisa que mal serve para utilizadores amadores. Instale e use um sistema operativo baseado em unix, como o linux, o bsd ou o macos.
  • Este curso é de Engenharia Informática. Não permita que se confunda com uma qualquer "furmassão avançada de web-bonecos e insta-qualquer-coisa" daquelas que abundam nos motores de pesquisa — basicamente porque GIGO: Garbage In, Garbage Out.
    • Invista tempo e esforço a identificar, compreender e resolver as dificuldades. Procure as melhores referências, fale com colegas e com professores — nada com valor é rápido ou fácil.

Os exercícios assinalados com "✓" serão resolvidos nas aulas práticas; Os assinalados com "†" têm elevada dificuldade. Todos os restantes devem ser resolvidos pelos alunos.

Alfabetos, Palavras e Linguagens

Exercício 01

  1. Defina alfabetos para:
    1. Escrever os números naturais em notação hexadecimal.
    2. Representar a configuração de um semáforo, no que diz respeito aos automóveis.
    3. Escrever as palavras da língua portuguesa.
    4. Escrever frases em português.
  2. Seja um alfabeto, e palavras sobre . Escreva por extenso as seguintes palavras:

Exercício 02

Liste todas as sub-palavras, todos o prefixos e todos os sufixos das seguintes palavras sobre o alfabeto :

Exercício 03

Seja . Construa definições recursivas dos seguintes conjuntos:

  1. . inclui, por exemplo, e mas não inclui nem .
  2. .
  3. .
  4. .
  5. .
  6. . Sugestão: Use a concatenação no passo recursivo.

Exercício 04

Encontre a menor palavra sobre o alfabeto que não está em .

Exercício 05

  • † Demonstre as propriedades do fecho de linguagens.
  • † Demonstre as propriedades da concatenação de expressões regulares.

Exercício 06

Na ordem lexicográfica, quantas palavras estão entre e ? E na ordem mista?

Exercício 07

Desenhe os diagramas das seguintes linguagens:

  1. .
  2. .
  3. .
  4. .

Exercício 08

Descreva recursivamente o conjunto das palavras sobre o alfabeto ...

  1. com número par de símbolos.
  2. com número par de ocorrências de .
  3. com número par de ocorrências de e número ímpar de ocorrências de .
  4. com número ímpar de símbolos ou com menos de símbolos.
  5. com número ímpar de símbolos ou com, pelo menos, símbolos.
  6. com número ímpar de símbolos e com menos de símbolos.
  7. com número ímpar de símbolos e com, pelo menos, símbolos.
  8. de comprimento menor do que e com numero par de ocorrências de .
  9. formadas por um certo número de , seguido de um único , seguido do mesmo número de .

Exercício 09

  1. Calcule e compare com . Enuncie o que observou como uma propriedade geral das operações de linguagens.
  2. É verdade que ?
  3. Sejam e . Calcule e .
  4. Verifique que é a linguagem das palavras binárias que não têm como subpalavra e que terminam em .
  5. † Confirme que se e só se .
  6. † Confirme que e que .

Exercício 10

Mostre que, se forem linguagens então .

Lembre-se que para provar que dois conjuntos são iguais tem de provar as duas inclusões e .

Exercício 11

Sejam . O que são e ?

Exercício 12

† Seja uma linguagem sobre e . Encontre condições necessária e suficientes para que se verifique .

Exercício 13

Verifique, com demonstrações ou contra-exemplos, quais das seguintes igualdades são válidas para todas as linguagens:

  1. .
  2. .
  3. .
  4. .
  5. .

Exercício 14

Mostre que para :

  1. .
  2. .
  3. Se então .

Exercício 15

Demonstre as seguintes igualdades:

  1. .
  2. .
  3. .
  4. .
  5. .

Expressões Regulares

Exercício 16

✓ Considere a expressão regular e o respetivo diagrama.

  1. Encontre uma palavra incompatível com esta expressão regular.
  2. O que acontece se remover a aresta central do diagrama simplificado?

Exercício 17

  1. Desenhe e simplifique o diagrama de .
  2. Encontre a mais curta palavra não vazia das linguagens das seguintes expressões:
    1. .
    2. .
    3. .
  3. Defina informalmente um algoritmo para encontrar a menor palavra numa linguagem regular definida por:
    1. Uma expressão regular.
    2. O diagrama de uma expressão regular.

Exercício 18

  1. Desenhe os diagramas das seguintes expressões regulares:

    1. .
    2. .
    3. .
  2. Determine as expressões regulares definidas pelos seguintes diagramas:

    Fig. Ex 18.1   Fig. Ex 18.2   Fig. Ex 18.3

  3. Determine o menor diagrama que representa .

  4. Encontre exemplos que mostram a necessidade de cada uma das condições do teorema da remoção das arestas .

Exercício 19

Construa uma expressão regular para representar os números reais sem sinal, de acordo com as seguintes regras:

  • Um número real tem sempre uma vírgula decimal.
  • Um número real começa por 0 se e só se a sua parte inteira é 0.
  • Um número real termina em 0 se e só se a sua parte decimal é 0.

Exercício 20

Encontre expressões regulares para representar as seguintes linguagens:

  1. ✓ A linguagem das palavras sobre em que todos os 's precedem todos os 's que, por sua vez, precedem todos os 's (donde que todos os 's precedem todos os 's), podendo não haver nem 's, nem 's, nem 's.
  2. ✓ A linguagem da alínea anterior sem a palavra vazia.
  3. As palavras sobre de comprimento inferior a 3.
  4. As palavras sobre que começam por , acabam em e têm exatamente dois 's.
  5. A linguagem das palavras sobre que têm e como subpalavras.
  6. As palavras sobre de que não é subpalavra.
  7. ✓ A linguagem das palavras sobre que não têm prefixo .
  8. ✓ A linguagem das palavras sobre que não têm como subpalavra.
  9. As palavras sobre em que não ocorre.
  10. As palavras sobre em que ocorre.
  11. As palavras sobre em que ocorre só uma vez.

Exercício 21

Descreva informalmente as linguagens representadas pelas seguintes expressões regulares:

  1. .
  2. .
  3. .
  4. .
  5. .

Exercício 22

Simplifique as seguintes expressões regulares:

Exercício 23

Encontre uma expressão regular para as seguintes linguagens binárias:

  1. Que representam as potências de .
  2. Com, pelo menos, uma ocorrência de .
  3. † Que não têm como subpalavra.
  4. Com, quanto muito, uma ocorrência de e, quanto muito, uma ocorrência de .
  5. Em que nenhum prefixo tem mais dois s que s nem mais dois s que s.

Exercício 24

Verifique as igualdades

Exercício 25

  1. Descreva em linguagem natural as linguagens das seguintes expressões regulares:

    1. .
    2. .
    3. .
    4. .
  2. Simplifique as seguintes expressões regulares:

    1. .
    2. .
    3. .
  3. Mostre que .

Exercício 26

Defina expressões regulares para as linguagens binárias das palavras que:

  1. O quinto símbolo a contar da direita é .
  2. Têm ou como subpalavra.
  3. Não têm nem como subpalavra.
  4. Não têm como subpalavra.
  5. Têm um número ímpar de s.
  6. Têm um número par de ocorrências de .

Exercício 27

Defina uma ER para as datas de acordo com a Norma ISO 8601. Considere só o caso YYYY-MM-DD:

  1. Permita que sejam representadas datas incorretas, como 2014-34-96.
  2. Restrinja os valores para os meses e para os dias, mas permita ainda dias inconsistentes com o mês. Por exemplo, 2014-02-31.
  3. Restrinja os valores para os dias de forma a serem consistentes com o mês, mas ignore o anos bissextos (isto é, assuma que fevereiro tem sempre 28 dias). Por exemplo 2004-02-29 não é válida.
  4. Trate dos anos bissextos.

Um ano bissexto é um ano múltiplo de 4 (por exemplo, 1948 é bissexto), exceto se também é múltiplo de 100 (por exemplo, 1900 não é bissexto) mas os múltiplos de 400 são sempre bissextos (por exemplo, 1600 é bissexto).

Implementação

Programa 00

Escreva uma função, listWords(fileName) que lê o ficheiro de texto fileName e produz a lista de palavras que ocorrem (sequencialmente) nesse ficheiro. Descarte os símbolos de pontuação e converta as letras para minúsculas. Sugestão: consulte a documentação de str e de string do python.

Programa 01

Escreva uma função, symbolsIn(word), que tem como entrada uma string e que devolve uma lista de símbolos. Assuma que, por omissão, os símbolos da string são separados por underscore (_) mas, opcionalmente, a função tem o argumento sep para usar um separador alternativo.

EntradaResultado
"a_b_color_b_a"["a", "b", "color", "b", "a"]
"single"["single"]
""[""]
"_"["", ""]

Programa 02

Escreva uma função, alphabetFor(word), que tem como argumento uma string e que devolve o menor alfabeto para gerar essa palavra. Assuma que, por omissão, os símbolos da string são separados por underscore (_) mas, opcionalmente, a função tem o argumento sep para usar um separador alternativo.

Note bem que no resultado não devem aparecer elementos repetidos.

EntradaResultado (sep="_")Resultado (sep="")
"a_b_color_b_a"["a", "b", "color"]["a", "_", "b", "c", "o", "l", "r"]
"single"["single"]["s", "i", "g", "l", "e"]
""[][]
"_"[]["_"]

Programa 03

Escreva uma função, generated(word, alphabet), em que word é uma string e alphabet uma lista de string e que determina se os símbolos de word estão todos em word (isto é, o resultado é booleano). Assuma que, por omissão, os símbolos da string são separados por underscore (_) mas, opcionalmente, a função tem o argumento sep para usar um separador alternativo.

Entrada wordEntrada alphabetResultado
"a_b_color_b_a"["a", "b", "color"]true
"single"["single"]true
""[]true

Programa 04

Use uma biblioteca de expressões regulares (do python3, por exemplo) e escreva expressões para reconhecer palavras que:

  1. Começam pela letra a; Não começam pela letra a; Terminam na letra a; Não terminam na letra a.
  2. Têm pelo menos uma ocorrência de a; Não têm ocorrências de a; O número de ocorrências de a não é 1; O número de ocorrências de a é exatamente 1.
  3. Têm um a ou um b; Têm um a e um b; Têm um a e, mais à frente, um b.
  4. Se têm um a então também têm um b; Se têm um a então também têm um b que ocorre antes do a; Se têm um a então também têm um b que ocorre depois do a; Se têm um a então não têm um b.

O pressuposto geral nas bibliotecas de ER é que vai ser feita uma pesquisa de subpalavras. Isto é, a ER é usada como um padrão que vai "percorrer" uma palavra "maior" para detetar subpalavras compatíveis com a ER dada.

Não é esse o pressuposto neste capítulo, onde as ER definem "palavras inteiras".

Programa 05

  1. Escreva uma função countRE(expr, words) em que expr é uma das funções acima e words uma lista de string e que devolve o número de palavras em words aceites pela ER de expr.
  2. Repita este exercício para a função filterRE(expr, words) que devolve a lista das palavras em words aceites por expr. Re-escreva countRE = len(filterRE).
  3. Escreva o predicado allRE(expr, words) para testar se todas as palavras de words são aceites por expr. O mesmo para anyRE(expr, words) para testar se alguma palavra é aceite.

Programa 06

  1. Use os comandos grep para substituir a função filter acima e wc para substituir len.
  2. Aplique os filtros e contagens às palavras portuguesas com as ER dos exercícios anteriores.
  3. Quantas palavras têm cal depois de um v sem que ocorra um o no meio? Quais estão em comum com british_english?

Na linha de comandos, em geral, tem a seguinte documentação sobre cada comando, aqui ilustrado com grep:

  • grep -h ou grep --help, um resumo curto das principais operações.
  • man grep, uma "página" com uma descrição curta do comando e uma lista das operações (a.k.a cheat sheet).
  • info grep, um "livro" com a descrição completa do comando e operações.

Programa 07

Se observar as contagens de palavras portuguesas (no ficheiro portuguese):

  • Há 431114 palavras.
  • Das quais 355762 com a letra a
  • E 75352 em que a não ocorre.

Use o grep e o wc para obter exatamente estes três números.

Autómatos Finitos

No capítulo anterior definiram-se as linguagens e expressões regulares com vista a resolver o Problema Principal de ALP (versão 1)Determinar um sistema computável, eficiente e adequado para definir linguagens de programação. – onde:

  1. Computável: Existe um algoritmo que recebe como entrada uma palavra e ao fim de um número finito de passos produz uma resposta sim ou não conforme ou não.
  2. Eficiente: O número de passos referido no passo anterior não deve ser "muito maior" que o comprimento da palavra.
  3. Adequado: Deve ser possível definir (os programas de) qualquer linguagem de programação.

As linguagens regulares são uma classe de linguagens formais. Será que resolvem o Problema Principal de ALP? É necessário esclarecer:

  • Como definir um algoritmo, Super, que dada uma ER e produza um programa PL = Super(e) tal que, para cada palavra p, o resultado PL(p) é sim ou não conforme p in L(e) ou não?
  • Se as computações Super(e) e PL(p) são eficientes?
  • Se as linguagens regulares são adequadas para definir (os programs de) qualquer linguagem de programação?

O programa Super tem como entrada uma ER e, que especifica uma certa linguagem regular, e devolve um programa PL, que reconhece as palavras da linguagem definida por e.

Isto é semelhante ao trabalho de um compilador. Por exemplo, javac é um programa que tem como entrada ficheiros que especificam um certo programa e devolve esse programa em bytecode.

Autómatos Finitos Deterministas

Um modelo computacional simples, com memória limitada.

Introdução

Exemplo de um Autómato Finito
Exemplo de um AFD
O que acontece quando a entrada é ?

Para resolver o Problema Principal de ALP é necessário formalizar a noção de "computador/programa", de forma a representar PL = Super(e).

Os Autómatos Finitos são modelos formais de "computadores/programas" simples de descrever mas capazes de resolver vários problemas teóricos e com algumas aplicações práticas (ver o artigo na wikipedia).

Um autómato tem como entrada uma palavra que é processada símbolo a símbolo até que termina num certo estado. Em certos estados do autómato a palavra, depois de completamente "lida", é aceite e noutros é rejeitada.

Um autómato pode ser representado por um grafo orientado. Os vértices "são" os estados do autómato e as "arestas" indicam como são "lidos" os símbolos.

Autómato Finito Determinista

Autómato Finito Determinista (AFD). Um Autómato Finito Determinista (AFD) ou Autómato de Estados Finitos (Em inglês: Determinist Finite State Machine (DFSM) ou Determinist Finite State Automaton (DFSA)) é um tuplo onde:

  • Estados de Controlo é um conjunto finito.
  • Alfabeto de Entrada é um alfabeto.
  • Transição é uma função.
  • Estado Inicial .
  • Estados Finais ou de Aceitação .

Intuitivamente, um AFD "anda" de estado em estado, conforme "processa" os símbolos de uma palavra, de acordo com a transição. Esse "passeio" começa no estado inicial e "consome" um símbolo da palavra de cada vez. Quando todos os símbolos estão processados, o AFD fica num certo estado. Se for um dos estados finais a palavra é aceite, caso contrário é rejeitada.

Por exemplo, seja em que a transição é definida pela seguinte tabela:

  • Os estados de controlo são os elementos de .
  • O alfabeto de entrada é .
  • A transição é a função em que está na linha e coluna da tabela acima.
  • O estado inicial é .
  • Os estados finais são os elementos de .

A função de transição de um AFD é quase sempre representada por uma tabela como no exemplo acima. Mas por vezes é conveniente apresentá-la como um conjunto de triplos:

A transição acima como um conjunto de triplos fica:

Configuração, Computação, Aceitação

A computação da palavra por este autómato é a sequência

A notação indica que o autómato passa do estado para lendo o símbolo . Concatenado todos esses símbolos, da esquerda para a direita, obtém-se a palavra processada, neste caso . Também é indicado que o último estado é final, pelo que a palavra é aceite pelo autómato .

Configuração. Computação. Palavra Aceite. Seja um AFD.

Uma configuração de é um par onde é o estado atual e é o sufixo restante.

A computação da palavra pelo AFD é a sequência de configurações em que:

  • base (configuração inicial) .
  • passo (processamento do símbolo ativo) .

Se a palavra é aceite pelo autómato . Caso contrário, é rejeitada por .

Por exemplo, aplicando estas definições ao autómato anterior:

  1. De acordo com a base, a configuração inicial é . O "símbolo ativo" está sublinhado.
  2. Aplicando o passo obtém-se a configuração porque .
  3. O passo é repetidamente aplicado, consumindo o símbolo ativo de cada vez, até que o sufixo restante é :
    1. .
    2. .

A computação pode ser visualizada numa tabela, com uma configuração por linha

ou de forma ainda mais compacta: ou ainda

A computação termina quando não é possível fazer mais transições. Neste exemplo o autómato fica no estado . Portanto é aceite por .

O que acontece com ? A computação é a sequência:

Neste caso a computação termina no estado . Portanto é rejeitada por .

Diagramas dos Autómatos Finitos Deterministas

Tal como com as expressões regulares, a visualização gráfica dos autómatos finitos deterministas é uma ferramenta útil.

Diagrama de um AFD. Seja um AFD. O diagrama de é um grafo orientado em que:

  • Os vértices são os estados de controlo .
  • Os arcos são definidos pela transição. Se então o diagrama tem o arco Fig: Diagrama AFD - transição
  • O (único) vértice com o estado inicial é assinalado por um arco órfã a entrar: Fig: Diagrama AFD - S
  • Os (vários) vértices com estados finais são assinalados por um círculo duplo: Fig: Diagrama AFD - F

Por exemplo, o AFD usado nos exemplos acima tem o seguinte diagrama:

Diagrama de um AFD
Fig: Diagrama AFD Exemplo

Transição Estendida

A transição de um AFD está definida para cada símbolo do alfabeto de entrada: . No entanto é mais conveniente estender as transições a palavras: .

Transição Estendida. Seja um AFD. A função de transição estendida tem assinatura e fica definida pelas seguintes regras recursivas:

  • base - palavra vazia .
  • base - símbolos Para cada .
  • passo Se então .

Intuitivamente, é o estado em que o AFD fica depois de processar a palavra a partir do estado .

Por exemplo, usando o AFD anterior: e

Com transições estendidas a escrita de certas definições e condições fica mais compacta e intuitiva:

  1. Computação .
  2. Aceitação é aceite pelo AFD se, e só se . Se então é rejeitada.

Linguagens Reconhecidas pelos AFD

É altura de começar a fazer a ligação entre as linguagens regulares e os AFD.

Linguagem Reconhecida por um AFD. Seja um AFD.

A linguagem reconhecida (ou aceite) por é

Dois AFD são equivalentes se aceitam a mesma linguagem.

Tal como com as expressões regulares, a definição de "equivalência" depende das linguagens associadas.

Conclusão

Nesta secção definiu-se um modelo de "computação" simples, os autómatos finitos deterministas e associou-se uma linguagem a cada AFD.

A intenção aqui é obter-se um modelo de computação das linguagens regulares. Portanto é preciso responder afirmativamente a estas duas questões:

  1. Qualquer linguagem regular é aceite por um AFD?
  2. Qualquer linguagem aceite por um AFD é regular?

Estas duas questões são tratadas na próxima secção.

Computação Não Determinista

Generalização dos autómatos deterministas.

Introdução

Com vista a obter-se um modelo de computação das linguagens regulares, estão por responder duas questões:

  1. Qualquer linguagem regular é aceite por um AFD?
  2. Qualquer linguagem aceite por um AFD é regular?

Formalmente, para responder a estas questões, mostra-se como obter um AFD "equivalente" a uma ER dada e, reciprocamente, como obter uma RE "equivalente" a um dado AFD.

Para construir estas equivalências é necessária estudar uma variante não determinista dos AFD.

Autómatos Finitos Não Deterministas

Nos AF deterministassempre exatamente uma transição para cada combinação . Isto é, no diagrama, de cada estado sai sempre exatamente uma aresta , para cada .

Diagrama de Um AFD.
Fig: Exemplo Diagrama AFD
De cada vértice sai exatamente uma aresta para cada símbolo.

Para os diagramas das expressões regulares o caso é diferente:

  • Algumas arestas "são" .
  • Não é necessário sair uma aresta para cada símbolo.
  • Podem sair várias arestas com o mesmo símbolo.

Por exemplo, para a expressão regular tem-se o diagrama

Diagrama de uma ER.
Fig: Exemplo Diagrama RE
Não se verificam as restrições dos AFD.

Intuitivamente, as arestas dos AFD são caminhos obrigatórios enquanto que as arestas das RE são caminhos possíveis.


Os Autómatos Finitos Não Deterministas generalizam os AFD com todos os tipos de arestas das ER. Desta forma obtém-se um modelo computacional das ER que pode "correr" e ser analisado em termos de desempenho.

Autómato Finito Não Determinista (AFND). Um Autómato Finito Não Determinista (AFND) é um tuplo em que

  • Estados de Controlo é um conjunto finito.
  • Alfabeto de Entrada é um alfabeto.
  • Transição é uma função.
  • Estado Inicial .
  • Estados Finais ou de Aceitação .

A diferença entre as definições de AFD e AFND está na assinatura da transição:

  1. A assinatura da transição dos AFD é .
  2. Nos AFND acrescenta-se a palavra vazia a . Desta forma, nos diagramas algumas arestas também podem ser , além de .
  3. Em vez de ser um único estado de controlo, nos AFND é um conjunto de possíveis estados, incluindo nenhum. Isto é, em vez de , nos AFND .

É necessário replicar nos AFND o percurso feito com os AFD. Em particular, definir para os AFND o que é uma configuração, computação, palavra e linguagem aceite. Porém, é mais útil começar por definir o diagrama de um AFND.

Diagrama de um AFND. Seja um AFND. O diagrama de define-se como no caso dos AFD, tendo em conta que algumas arestas podem ser .

Por exemplo, dado o AFND com estado inicial , estados finais e transição o diagrama que se obtém é

Exemplo de Diagrama de um AFND
Fig: Exemplo Diagrama AFND

Note-se que:

  • A tabela da transição tem uma coluna adicional, .
  • As "células" da tabela são subconjuntos de estados de controlo. Um valor possível é o conjunto vazio .
  • Neste primeiro exemplo os conjuntos foram denotados com mas sempre que possível será usada uma notação mais compacta:
    • Em vez de se escrever "" escreve-se apenas "", "" ou "" se a vírgula for mesmo necessária.
    • O conjunto vazio é representado por nada: em vez de "" escreve-se apenas "".
  • Os estados finais podem ser assinalados com o prefixo "" e o estado inicial com um prefixo "". Se nada for indicado o estado inicial é sempre ou e dispensa-se a indicação de que é inicial.

De acordo com estas convenções a tabela da transição acima fica e define completamente o AFND . Isto é, lendo a tabela determinam-se todos os atributos que definem um AFND.


Tal como observado para os AFD, a função de transição de um AFND é quase sempre representada por uma tabela mas por vezes é conveniente apresentá-la como um conjunto de triplos:

A transição acima, como um conjunto de triplos, fica:

Observação: No caso dos AFD os triplos são e para os AFND os triplos são . Enquanto que nos AFD , nos AFND , podendo ser vazio, ter zero, um, dois, elementos de .

Configuração. Computação AFND. Seja um AFND.

A definição de configuração como um par permanece igual ao caso dos AFD.

A computação da palavra pelo AFND é uma sequência de configurações em que:

  • base (configuração inicial) e .
  • passo (processamento do símbolo ativo): e .
  • passo (transição vazia): e .
  • fim ou não há mais passos possíveis.

Ao contrário do que acontece com os AFD, nos AFND cada palavra pode ter mais do que uma computação possível.

Por exemplo, a palavra tem três computações possíveis:

  • : rejeita?
  • : aceita?
  • : rejeita?

Esta situação, em que as computações de uma palavra podem terminar em vários estados, alguns finais e outros não, torna a definição de palavra aceite um pouco mais complicada do que para os AFD:

Palavra Aceite. Linguagem Reconhecida (AFND). Seja um AFND.

Uma palavra é aceite por se existe alguma computação de por que termina num estado final depois de terem sido lidos todos os símbolos de . Isto é, se entre todas as computações de por alguma termina numa configuração com .

A linguagem reconhecida (ou aceite) por é o conjunto de todas as palavras aceites por :


Neste ponto a situação em relação ao Problema Principal de ALP é a seguinte :

  1. As Linguagens e as Expressões Regulares são candidatas para formalizar rigorosamente as linguagens de programação. Idealmente, cada linguagem de programação poderia ser representada por uma ER.
  2. Os Autómatos Finitos Deterministas são candidatos para resolver computacionalmente a questão de saber se um palavra dada está, ou não, numa certa linguagem regular.
  3. Mas os AFD parecem ser demasiado restritivos para representar as ER. Comparando os respetivos diagramas, não há arestas vazias, etc.
  4. Os Autómatos Finitos Não Deterministas generalizam os AFD de forma a suportarem todos os tipos de arestas das ER.

De forma a resolver a questão da representação computacional das linguagens regulares, há que responder afirmativamente às seguintes duas questões;

  1. Qualquer linguagem regular é aceite por um AFND?
  2. Qualquer linguagem aceite por um AFND é regular?

Equivalência entre Expressões Regulares e Autómatos Finitos Não Deterministas

Para estabelecer a equivalência entre ER e AFND têm de ser resolvidos dois problemas:

  1. ER → AFND (Construção de Thompson): Dada uma ER qualquer, , encontrar um AFND tal que (isto é, Qualquer linguagem regular é aceite por um AFND?).
  2. AFND → ER (Algoritmo de Kleene): Dado um AFND qualquer, , encontrar uma ER tal que (isto é, Qualquer linguagem aceite por um AFND é regular?).

A resolução do primeiro problema usa a "Construção de Thompson" descrita já a seguir. Para resolver o segundo problema usa-se o "Algoritmo de Kleene", que remove um a um os vértices do diagrama do AFND.

Construção de Thompson

O primeiro problema é de resolução muito fácil, considerando os diagramas das ER e dos AFND:

Construção de Thompson. Dada uma ER sobre , o diagrama de pode ser interpretado como o diagrama de um AFND . Nesse caso .

Por exemplo, seja . Numerando os vértices do seu diagrama da esquerda para a direita (mas serve qualquer critério desde que cada vértice fique com um "nome" diferente dos restantes) obtém-se:

Exemplo de um Diagrama da ER
Fig: Exemplo Diagrama ER

Seja o AFND que se obtém deste diagrama, descrito pela tabela

A "equivalência" entre e depende de se verificarem as seguintes duas condições:

  • : Cada palavra de é aceite por ou, equivalentemente, : cada palavra rejeitada por não está em .
  • : Cada palavra aceite por está em ou, equivalentemente, : cada palavra que não está em é rejeitada por .

A demonstração completa e formal de cada um dos pontos anteriores sai do âmbito de ALP. Mas a verificação de alguns casos é um exercício importante.

  • Palavras de : . Estas palavras são aceites por ?
  • Palavras que não estão em : . Estas palavras são rejeitadas por ?

Para verificar que a palavra é aceite por , basta que uma computação de por processe todos os símbolos e termine num estado final.

Por exemplo, tem a seguinte computação por : . Portanto é aceite por .

Para há a seguinte computação: . Todos os símbolos de foram processados e a computação termina num estado final. Portanto é aceite.

Exercício. Verifique que as restantes palavras de listadas acima também são aceites por .

Para verificar que a palavra é rejeitada por é necessário que nenhuma computação de por processe todos os símbolos e termine num estado final.

Por exemplo, tem apenas uma computação por : (começa no estado inicial e não avança mais).

Embora esta computação processe todos os símbolos de , não termina num estado final. Como não há mais computações de por conclui-se que rejeita .

Se também só há uma computação possível: e daqui não é possível avançar mais. Neste caso, embora a computação tenha terminado num estado final, faltou processar todos os símbolos de . Portanto esta palavra é rejeitada.

Exercício. Verifique que as restantes palavras listadas acima que não estão em também são rejeitadas por .

Algoritmo de Kleene

Com a Construção de Thompson fica estabelecido que qualquer linguagem regular é aceite por um AFND. Falta verificar que qualquer linguagem aceite por um AFND é regular.

Para esse efeito apresenta-se um método, o "Algoritmo de Kleene", que transforma o diagrama de um AFND numa expressão regular "equivalente".

Neste processo o diagrama é transformado por uma sequência de passos onde se remove um vértice de cada vez. O vértice removido é substituído por certas ER. No fim do processo fica apenas o vértice inicial e um vértice final, ligados por uma aresta com a ER final.

Um exemplo, ainda informal

  1. Dado o seguinte AFND na forma de um diagrama:

    Fig: Exemplo AFND para RE  01

  2. Representa-se por a expressão da aresta que liga o vértice ao vértice . Por exemplo, .

  3. Neste diagrama:

    1. Nenhuma aresta entra no vértice inicial.
    2. Existe apenas um vértice final.
    3. Nenhuma aresta sai do vértice final.
  4. Para eliminar o vértice :

    1. Que caminhos "passam em "? Há dois: e .
    2. Seja um desses caminhos. Adiciona-se ao diagrama a aresta com .
    3. Repete-se o passo anterior para todos os caminhos que passam no vértice a eliminar.
  5. O novo diagrama, sem o vértice , é:

    Fig: Exemplo AFND para RE  02

  6. Eliminado o vértice , obtém-se:

    Fig: Exemplo AFND para RE  03

  7. Restam apenas o vértice inicial e o final. A expressão regular "equivalente" ao AFND é .


O núcleo do processo está no passo 4 mas antes de começar é preciso que o diagrama do AFND esteja "bem preparado", conforme as condições do passo 3.

Diagrama Bem Preparado. Um diagrama está bem preparado se

  1. Nenhuma aresta entra no vértice inicial.
  2. Existe apenas um vértice final.
  3. Nenhuma aresta sai do vértice final.

Nem todos os diagramas estão bem preparados mas é sempre possível transformar um diagrama de forma a obter-se outro equivalente e bem preparado:

Autómato Bem Preparado. Seja um AFND.

O AFND em que:

  • e .
  • .
  • para cada .
  • nos restantes casos.

está bem preparado e é equivalente a .

Por exemplo, se for dado pela tabela não está bem preparado porque o estado inicial, , recebe uma aresta de e, também, porque sai uma aresta do estado final. Um AFND equivalente e bem preparado é que está bem preparado. Em termos de diagramas:

Diagrama Mal PreparadoDiagrama Equivalente Bem Preparado
Fig: Exemplo Bem Preparado 01Fig: Exemplo Bem Preparado 02

Com autómatos bem preparados pode aplicar-se o processo de eliminação de vértices.

Algoritmo de Kleene. Sejam um AFND bem preparado e a ER da aresta no diagrama de .

O caminho passa no vértice se (pode ser ) e no diagrama existem arestas e .

A eliminação do vértice produz um novo diagrama idêntico ao anterior exceto:

  • O novo diagrama não tem o vértice .
  • Para cada caminho do diagrama original, o novo diagrama tem a aresta com valor

No diagrama que se obtém quando foram eliminados todos os vértices exceto o inicial e final, a expressão regular que está na aresta F é "equivalente" ao AFND no sentido em que

Um exemplo mais complicado, passo a passo. Seja o seguinte diagrama/AFND, que não está bem preparado:

Fig: Exemplo TK 01

Uma versão equivalente, bem preparada é

Fig: Exemplo TK 02

Eliminar . Caminhos que passam em :

  • . ER resultante: .
  • . ER resultante: .

Fig: Exemplo TK 03

Eliminar . Caminhos que passam em :

  • . ER resultante: .
  • . ER resultante: .

Fig: Exemplo TK 04

Eliminar . Caminhos que passam em :

  • . ER resultante: .
  • . ER resultante: .

Fig: Exemplo TK 05

Eliminar . Caminhos que passam em :

  • . ER resultante, e final:

A ER final pode ser um pouco simplificada:

Exercícios:

  • Aplique a Construção de Thompson à ER acima.
  • Escolha palavras de e verifique que as aceita.
  • Encontre palavras de e verifique que estão em .
  • O que se passa com a palavra ? Está em ? E em ?

Equivalência entre AFND e AFD

A Construção de Thompson e o Algoritmo de Kleene asseguram que os AFND são "equivalentes" às ER, no sentido em que os AFND e as ER definem exatamente as mesmas linguagens.

Mas os AFND são um mau modelo computacional porque pode ser necessário um número exponencial (no número de estados do autómato) para decidir se .

Para computar não se sabe, à partida, quantos "passos" vão ser necessários. No caso em que é preciso testar todas computações de por .

O problema da eficiência da computação não se coloca nos AFD: Demora sempre exatamente passos, o que é um desempenho ótimo (no sentido em que não há melhor).


Como os AFND generalizam os AFD, todas as linguagens aceites por AFD são também aceites por AFND.

Nesta secção mostra-se que os AFD e os AFND são equivalentes: As linguagens aceites pelos AFD são exatamente as linguagens aceites pelos AFND.

Com as transições vazias, um AFND pode percorrer vários estados sem processar símbolos, ao contrário do que acontece com os AFD. Esta situação fica representada com o fecho vazio e com a transição de entrada.

Fecho Vazio. Seja um AFND e .

O fecho vazio de , , é o conjunto de todos os estados que podem ser alcançados a partir de com zero ou mais transições vazias. Formalmente:

  • base .
  • passo Se e então também .

Também devido às transições vazias, não contém todos os estados que podem ser alcançados a partir de lendo o símbolo . Para esse efeito tem-se a transição de entrada:

Transição de Entrada. Seja um AFND.

A transição de entrada é a função de assinatura que, para cada , define o conjunto dos estados que podem ser alcançados a partir de lendo o símbolo . Isto é:


Por exemplo, seja o AFND definido pela tabela com o fecho vazio de cada estado já calculado e com o seguinte diagrama

Transição de Entrada: Diagrama do AFND acima
Fig: Exemplo Transição Entrada

A transição de entrada de alguns casos: Neste caso, por exemplo, porque é uma computação de . Já de duas maneiras diferentes: e .

Exercício: Calcule todas as transições de entrada deste exemplo.


Este "desvio" pelo fecho vazio e transição de entrada serve para formalizar as ferramentas que faltam para o objetivo desta secção: Mostrar que para cada AFND existe um AFD "equivalente" no sentido em que .

Simulação de Não Determinismo. Seja um AFND.

O AFD equivalente a é o AFD em que:

  • Estado Inicial .
  • Transição .
  • Estados de Controlo é definido recursivamente por
    • base .
    • passo Se então, para cada .
    • fecho Mais nenhum estado está em .
  • Estados Finais .

Neste caso

Por exemplo, para o AFND

Um AFND para
Fig: Exemplo Simulação

o cálculo de e de é feito em conjunto:

Os estados de são conjuntos de estados de . Para evitar uma notação muito pesada (por exemplo, ) omitem-se as chavetas e as vírgulas (e escreve-se apenas ). O texto vermelho representa estados "novos" na tabela e os estados finais de estão sublinhados. O respetivo diagrama é

Um AFD equivalente ao AFND para
Fig: Exemplo Simulação - AFD

O teorema/método da Simulação de Não Determinismo assegura que estes dois autómatos são equivalentes, isto é, reconhecem a mesma linguagem.

Conclusão

Uma vantagem dos AFD é que a computação é linear no comprimento da palavra pois executa exatamente passos para computar a resposta a enquanto que para o AFND a computação da resposta é exponencial.

Este ganho no número de passos tem um custo: se o AFND tem estados então , o AFD equivalente, pode ter até estados.

Estão determinadas três equivalências:

  • As ER e os AFND são equivalentes devido à Construção de Thompson e ao Algoritmo de Kleene.
  • Os AFND e os AFD são equivalentes devido à Definição de AFND e à Simulação de Não Determinismo.
  • Portanto, também as ER e os AFD são equivalentes.

Portanto

Os AFD proporcionam um bom modelo computacional para as ER.


Mas ainda há questões importantes a resolver. A próxima secção trata de formas de reduzir o tamanho dos AFD e de facilitar a construção automática de AFD e AFND antes de ser tratada a questão final, saber se "as linguagens regulares são adequadas para todas as linguagens de programação?"

Minimização e Composição de AFD

Operações com autómatos.

Introdução

Nas secções anteriores ficou provado que os AFD, AFND e as ER são equivalentes no sentido em que todos definem exatamente a classe das Linguagens Regulares.

Essa demonstração usa algoritmos para:

  • Converter uma ER num AFND (Construção de Thompson).
  • Converter um AFND numa ER (Algoritmo de Kleene).
  • Simular um AFND por um AFD (Teorema da Simulação).

Comparando os AFD com os AFND:

AutómatoNúmero de EstadosComprimento das Computações
DeterministaIneficienteEficiente
Não DeterministaEficienteIneficiente

Em termos de eficiência "absoluta" nenhum dos modelos (AFD e AFND) é superior. Mas enquanto não há nada a fazer em relação às computações não deterministas, em certos casos é possível reduzir o número de estados de um AFD.

Também interessa definir operações com autómatos que permitam acompanhar as operações das ER (união, concatenação, iteração) e também explorar outras possibilidades como a negação, a interseção e o processamento paralelo.

Minimização de AFD

Seja a linguagem das palavras binárias (sobre ) cujo quinto símbolo a contar do fim é . Esta linguagem é definida pela ER a que corresponde o diagrama e AFND seguinte:

AFND para
Figura Exemplo Minimização 01

Exercício: A aplicação direta do teorema da simulação determinista a este AFND produz um autómato com estados de controlo.

A simulação de um AFND com estados de controlo pode produzir até estados no autómato determinista equivalente (exercício: porquê?).

Estados Indistintos

Dois AFD são equivalentes se aceitam a mesma linguagem. Por exemplo, para a linguagem :

Autómato Autómato
Figura Exemplo AFD Equivalente 01Figura Exemplo AFD Equivalente 02

No Autómato os estados e são indistintos no seguinte sentido: Qualquer palavra processada a partir do estado é aceite SSE também for aceite se processada a partir do estado .

Por exemplo, se e o autómato estiver no estado então é "aceite". Também é "aceite" se o autómato estiver no estado . Por outro lado é rejeitada quer o autómato esteja no estado quer no .

Portanto, tanto como definem sempre os mesmos resultados em termos de aceitação/rejeição de palavras. Formalmente:

Estados Indistintos. Sejam um AFD e dois estados. Então é indistinto de se, para cada palavra , Em particular, se e não são indistintos.

Agrupando estados indistintos obtém-se um novo AFD com o número mínimo de estados para aquela linguagem regular, isto é, um Autómato Mínimo. Antes da respetiva definição formal é conveniente descrever um algoritmo para particionar os estados indistintos.


O objetivo é particionar o conjunto de estados em grupos de forma que dois estados estão no mesmo grupos se e só se são indistintos.

Partição dos Estados Indistintos. Seja um AFD:

  1. Iniciar a partição .
  2. Enquanto existirem grupos com e tais que ( é inconsistente):
    1. Retirar da partição : .
    2. Acrescentar os estados de concordantes com em : .
    3. Acrescentar os estados de discordantes de em : .

Os passos deste ciclo refinam de forma a eliminar discordâncias de sobre . O resultado é que a partição troca o grupo inconsistente por dois grupos mais pequenos mas "menos" inconsistentes, isto é, onde os estados estão "mais próximos" de serem indistintos.


A partição final é formada apenas por grupos consistentes, isto é, em que todos os estados são indistintos (no limite esses grupos têm apenas um estado). Os grupos dessa partição são os estados do AFD mínimo equivalente ao AFD inicial.

Autómato Mínimo. Sejam um AFD e a partição dos estados indistintos.

Para cada grupo e cada em que é o grupo que contém com .

O AFD Mínimo (ou reduzido) equivalente a é em que:

  1. O estado inicial, , é o grupo de que contém o estado inicial de .
  2. Os estados finais, , são os grupos de que estão contidos em . Isto é

A construção do autómato mínimo a partir da definição está sujeita a erros, pelo que são ilustrados de seguida dois métodos com vista a sistematizar e facilitar esse processo.


Dado o AFD pela seguinte tabela:

Construção do Autómato Mínimo por Tabelas de Transição

Iniciar grupos, detetar e assinalar inconsistências:

Separar inconsistências, detetar e assinalar novas inconsistências:

Não existem mais inconsistências: Agrupar e escrever a tabela do AFD mínimo:

Construção do Autómato Mínimo por Diagramas

O diagrama do AFD dado é:

AFD dado, com a partição inicial.
Diagrama do AFD Inicial
e discordam em .
Diagrama do AFD Passo 01
Todos os grupos são consistentes.
Diagrama do ADF Mínimo
Diagrama do AFD Passo 02

Foram descritos dois métodos para reduzir o número de estados de um AFD (minimizar). Ambos produzem o mesmo resultado: um autómato determinista com o menor número possível de estados e que seja equivalente a um AFD dado.

Embora isto não resolva completamente o potencial aumento exponencial do número de estados na passagem de AFND para AFD, produz um resultado ótimo, no sentido em que não existe melhor (isto é, por vezes o ótimo pode ainda ser "mau").

Composição

A representação é importante. Intuitivamente, a numeração romana é equivalente à árabe no sentido que representam os mesmos números. Considere o Problema A: "Multiplicar DXXXIX por XVII" e o Problema B: "Multiplicar 89 por 17". Embora os problemas A e B sejam o mesmo, é muito mais simples resolver B porque a representação árabe dos números "é compatível com" a multiplicação, ao contrário da representação romana.

As ER são construídas a partir da base () usando operações bem definidas (). Desta forma é possível decompor uma ER nas suas componentes, o que proporciona uma importante forma de análise com vista a explorar as suas propriedades.

Por outro lado, em geral, os autómatos "surgem" completamente definidos e é difícil relacionar um autómato com outro. Dado que as ER, os AFD e os AFND são "equivalentes", seria estranho que não fosse possível fazer também um estudo estruturado dos autómatos.


As operações com autómatos usam os Autómatos Bem Preparados pois estes têm uma forma adequada a serem "operados".

Começando pela concatenação, a ideia intuitiva para é "correr" primeiro e continuar em :

Concatenação de AFND. Sejam e dois AFND bem preparados sobre um alfabeto comum, , e com os estados de controlo disjuntos, .

Então, a concatenação de com é o AFND , definido por em que

A linguagem reconhecida por é a concatenação da linguagem reconhecida por com a linguagem reconhecida por :

Exercício: está bem preparado?

Por exemplo, se e (exercício: verifique que ambos são bem preparados e identifique as respetivas linguagens) então

Exercício: Traduza este exemplo para diagramas. Qual é a linguagem aceite por ?


A união de autómatos é semelhante à concatenação. Intuitivamente, o primeiro "passo" é decidir se "corre" ou . A computação da união termina a seguir a terminar a computação do autómato "escolhido" no início.

União de AFND. Sejam e dois AFND bem preparados sobre um alfabeto comum, , e com os estados de controlo disjuntos, .

Então, a união de com é o AFND , definido por em que

A linguagem reconhecida por é a união da linguagem reconhecida por com a linguagem reconhecida por :

Continuando com os autómatos do exemplo acima:

Exercício: Desenhe o diagrama do autómato acima.


Também a iteração segue o mesmo padrão:

Iteração de AFND. Sejam um AFND bem preparado.

Então, a iteração de é o AFND , definido por em que

A linguagem reconhecida por é o fecho da linguagem reconhecida por :

Exercício: Usando os exemplos acima, explicite as transições de e desenhe os respetivos diagramas.


A composição, união e iteração de AFND bem preparados são semelhantes em termos de requisitos e resultados. Para a negação e interseção é preciso sair desse padrão.

Intuitivamente, pensando em termos de autómatos deterministas, uma palavra é aceite se a computação termina num estado final e rejeitada se termina num estado não final. Portanto, basta trocar os estados finais com os não finais para se definir a linguagem complementar.

Quanto à interseção, uma vez definida a negação e a união, basta lembrar que para conjuntos, e a mesma igualdade é válida para as linguagens regulares. Mas este processo é pouco prático.

Começando pela negação, é importante destacar que se aplica a autómatos deterministas ao contrário do que foi feito para a concatenação, união e iteração.

Negação de AFD. Sejam um AFD.

Então, a negação de é o AFND , definido por .

A linguagem reconhecida por é o complementar da linguagem reconhecida por :

Um AFD e a sua negação
AFD para
Figura ADF A*
AFD para
Figura ADF A*

Paralelismo

É relativamente simples definir um autómato determinista que processa em paralelo outros dois (ou mais) autómatos também deterministas. Melhor, este método é suficientemente simples e geral para ter várias aplicações incluindo a união e interseção de AFD.

Em geral,

Autómato Paralelo. sejam e dois AFD sobre o mesmo alfabeto, .

Seja o AFD tal que:

  • Estados de Controlo: , isto é: um estado de controlo de é um par ordenado com um estado de e um estado de .
  • Transição: em que , isto é: a transição de um estado é feira componente a componente.
  • Estado Inicial: , isto é: o estado inicial é o par de estados iniciais.
  • Estados Finais: .

O conjunto dos estados finais fica como parâmetro porque proporciona uma grande flexibilidade aos autómatos paralelos. Por exemplo:

  • União: Sejam dois AFD com estados finais respetivamente. Fazendo tem-se . Note-se que uma palavra é aceite por se e só se é aceite por ou se é aceite por .
  • Interseção: Nas condições acima, seja . Então . Note-se que uma palavra é aceite por se e só se é aceite por e por .

Conclusão

Esta secção aprofundou o estudo dos AFD e AFND. Especificamente:

  1. Mostram-se dois métodos para minimizar um dado AFD, de modo a obter-se um AFD equivalente com o menor número possível de estados.
  2. Definiram-se as operações de concatenação, união e iteração de AFND, replicando as operações das ER.
  3. Definiu-se a negação e composição paralela de AFD. Com o processamento paralelo de AFD ficou trivial definir as operações de união e a interseção de AFD.

O Problema Principal de ALPDada uma linguagem e uma palavra no mesmo alfabeto, determinar se continua em aberto. As expressões regulares e os autómatos finitos (deterministas e não deterministas) verificam duas das três condições fundamentais:

  • São computáveis (existe um algoritmo que recebe uma palavra e num número finito de passos "responde" se essa palavra está ou não na linguagem pretendida) e eficientes (um AFD processa uma palavra com símbolos em exatamente passos).
  • Além disso é (relativamente) simples encontrar ER, AFND, AFD equivalentes.

Resta verificar se as linguagens regulares são adequadas para definir as linguagens de programação.

O Pumping Lemma

Os limites das linguagens regulares.

Introdução

Nas secções anteriores avançou-se na resolução do Problema Principal de ALPDada uma linguagem e uma palavra no mesmo alfabeto, determinar se com linguagens regulares.

As expressões regulares e os autómatos finitos (deterministas e não deterministas) são computáveis e eficientes mas ainda falta saber se são adequadas isto é, suficientemente expressivas para definir qualquer linguagem de programação.


As expressões algébricas, de uma forma ou outra, estão presentes em quase todas as linguagens de programação. Uma expressão algébrica é uma palavra como, por exemplo, 2 * (3 + 4) em que certas sub-palavras representam números (2, 3, 4), outras representam operações (+, *) e outras definem a estrutura da expressão ((, )).

A estrutura de uma expressão pode ser visualizada por uma árvore:

Árvore de uma Expressão Algébrica
Figura Árvore Expr Alg
Forma Alternativa
Figura Árvore Expr Alg Alt

Naturalmente, pretende-se que no lugar de 2, 3 e 4 possam estar outras expressões algébricas e que as operações incluam, pelo menos, - e /. Conforme as expressões ficam mais complexas, maior a necessidade e a importância dos parêntesis.

A estrutura de um programa é semelhante à estrutura de uma expressão algébrica: Organiza-se como uma árvore com certos vértices "recursivos". Em vez de números e operações, nas árvores dos programas os vértices têm instruções, expressões, diretivas, etc.

if x > 2:
    a = double(x)
    for i in range(a):
        a = a + i
else:
    a = 0
Árvore de um Fragmento de Programa
Figura Árvore Fragmento Programa

Uma propriedade importante das expressões algébricas é que "os parêntesis têm de estar equilibrados". Descartando os números e as operações, restam apenas os parêntesis e obtêm-se palavras como (), ()(), (())()(()()), que são "válidas" enquanto que as palavras )(, ()), etc devem ser rejeitadas.

A "linguagem dos parêntesis equilibrados" é um excelente teste às linguagens regulares:

  • Se for regular, as linguagens regulares são adequadas para definir as linguagens de programação. De facto, o LISP (ver a página na wikipédia) é uma linguagem de programação que usa parêntesis e pouco mais.
  • Se não for regular, as linguagens regulares não permitem representar árvores de estruturas sintáticas como as expressões algébricas ou os programas python. Nesse caso será necessário tentar outra abordagem para as linguagens de programação.

O problema que se coloca agora é o seguinte: Como saber se uma dada linguagem é, ou não, regular?

Consideremos alguns exemplos (sobre o alfabeto ):

  • é regular.
  • também é regular porque é o complementar de uma linguagem regular (na secção anterior viu-se como fazer a negação de um AFD).
  • também é regular, assim como são , etc.

Neste casos o "exercício" é simples porque ou se encontra uma ER adequada ou são aplicados os resultados teóricos das secções anteriores para construir linguagens regulares.

Quanto a uma versão simples dos parêntesis equilibrados:

As palavras de são Esta linguagem é regular?

De facto, como se prova que uma linguagem não é regular? O problema é o seguinte: Supondo que é uma linguagem regular. Como se prova que é regular? Basta encontrar uma ER (ou AFD ou AFND), , adequada: .

Mas, se não for regular nenhuma ER é adequada. É preciso outro método para provar que não é regular.

Entra o Pumping Lemma.

O Pumping Lemma

Uma observação muito simples:

Um AFD com estados, quando processa uma palavra com mais do que símbolos, tem de "passar" mais do que uma vez em alguns estados, porque há mais símbolos do que estados.

Por exemplo, um AFD para , ilustrado abaixo, tem exatamente dois estados.

AFD para
Figura Exemplo AFD Equivalente 01

Contando as entradas nos estados deste autómato:

PalavraComprimentoEntradas em Entradas em
000
110
............
330
321
312
312
303
303
303
303
............

Todas as palavras de comprimento entram mais do que uma vez em algum estado do autómato. Claramente, o mesmo acontece para palavras de comprimento


Em geral, seja uma palavra que entra duas (ou mais) vezes no estado . Então pode escrever-se em que:

  • é o prefixo de que entra pela primeira vez em .
  • é uma sub-palavra de que parte de e entra de novo em .
  • é o restante sufixo de .

Como (o caminho de) começa e termina em , a sub-palavra pode ser indefinidamente repetida, inclusivamente eliminada, que o estado final da computação não se altera. Isto é, o estado final para é o mesmo que para .

Se for aceite, também são . E, se for rejeitada, também são

Formalmente:

Pumping Lemma. Seja uma linguagem regular e o número de estados de um AFD que a aceita.

Qualquer palavra com pode ser escrita como em que:

  1. .
  2. .
  3. Para qualquer também .

O Pumping Lemma é uma propriedade de todas as linguagens regulares. Dito de outra forma,

Se as conclusões do Pumping Lemma levarem a uma contradição é porque as hipóteses do Pumping Lemma não se verificam. Especificamente: a linguagem considerada não pode ser regular.


Revisitando a linguagem simplificada dos parêntesis equilibrados, .

  1. Supondo que é regular, também é aceite por um certo AFD.
  2. Seja o número de estados desse AFD.
  3. A palavra .
  4. Pelo Pumping Lemma, como então em que:
    1. . Portanto, só tem .
    2. . Portanto tem pelo menos um e nenhum .
    3. Para cada também .

Em , quando é repetido,o número de é alterado. Mas o número de continua a ser . Portanto, quando , o número de deixa de ser igual ao número de .

Isto é uma contradição. Por um lado, se então tem o mesmo número de e de mas por outro, ao repetir , fica com um número diferente de e de .

Portanto a suposição inicial, de que a linguagem é regular, é falsa. A única conclusão possível é que não é uma linguagem regular.

O facto de não ser uma linguagem regular tem consequências profundas:

  • Primeiro, encontrou-se uma linguagem que não é regular.
  • Segundo, as linguagens regulares não são adequadas para definir linguagens de programação.

A incapacidade das linguagens regulares para definir a linguagem simplificada dos parêntesis equilibrados implica a incapacidade para definir as estruturas recursivas (como árvores) necessárias nas linguagens de programação.

Conclusão

O Pumping Lemma aplicado à linguagem mostra que as linguagens regulares não são adequadas para definir linguagens de programação.

Portanto, é necessária outra abordagem para resolver o Problema Principal de ALPDada uma linguagem e uma palavra no mesmo alfabeto, determinar se de forma computável, acessível e adequada.

Nem tudo está perdido. De facto, os conceitos introduzidos até aqui, as ER, os AFD e os AFND, vão continuar presentes no resto do curso e nas suas aplicações. O que muda é a importância que têm: Perdem o título de "candidato preferido" e passam a "contribuição necessária".

O próximo capítulo define certas gramáticas formais que, como vai ser mostrado, generalizam as linguagens regulares e estão associadas aos autómatos de pilha, uma forma simples de autómato com memória ilimitada.

Autómatos Finitos — Exercícios

Os exercícios assinalados com "✓" serão resolvidos nas aulas práticas; Os assinalados com "†" têm elevada dificuldade. Todos os restantes devem ser resolvidos pelos alunos.

Autómatos Finitos Deterministas

Exercício 01

Para o AFD com a transição dada pela tabela

  1. Desenhe o diagrama de estados.
  2. Escreva as computações de para as palavras e referindo se são, ou não, aceites.
  3. Escreva uma expressão regular que represente a linguagem reconhecida por .

Exercício 02

AFD Exercício 02
AFD Exercício 02

Seja o AFD dado pelo diagrama acima.

  1. Qual é o estado inicial, e quais são os estados finais?
  2. As palavras , e são aceites?
  3. Que palavras de estão em ?

Exercício 03

Seja um AFD.

  1. desenhe o diagrama de estados
  2. ✓ escreva uma expressão regular que represente a linguagem reconhecida por
  3. ✓ repita a alínea anterior para o AFD que apenas difere de no conjunto dos estados de aceitação, que no caso de é

Exercício 04

Construa um autómato finito determinista que reconheça a linguagem das palavras...

  1. sobre em que todos os 's precedem todos os 's que, por sua vez, precedem todos os 's (donde que todos os 's precedem todos os 's), podendo não haver nem 's, nem 's, nem 's.
  2. sobre que não têm como subpalavra.
  3. sobre em que cada é seguido imediatamente por .
  4. não vazias sobre em que o número de 's é divisível por .

Exercício 05

Construa um autómato finito determinista que reconheça a linguagem da ER .

Exercício 06

Calcule ER das linguagens reconhecidas pelos autómatos seguintes.

a)b)
AFD Exercício 06AFD Exercício 06
c)d)
AFD Exercício 06AFD Exercício 06
e)
AFD Exercício 06

Exercício 07

Encontre um AFD que aceite a linguagem das palavras em ...

  1. com prefixo .
  2. com subpalavra .
  3. expansões binárias dos naturais congruentes zero módulo .
  4. com subpalavra e sufixo .
  5. com subpalavra e não têm sufixo .
  6. em que cada bloco de quatro letras consecutivas contém .

Exercício 08

Encontre um AFD que aceite a linguagem das palavras...

  1. com prefixo .
  2. com sufixo .
  3. com subpalavra ou .
  4. em que as últimas cinco letras têm três s.
  5. tais que é múltiplo de cinco.
  6. sobre o alfabeto onde a soma dos símbolos é múltiplo de cinco.

Computação Não Determinista

Exercício 09

Determine a linguagem (ER) dos AFND acima.

a)b)c)
AFND EXERC 09 AAFND EXERC 09 BAFND EXERC 09 C

Exercício 10

Considere a linguagem de todos os números inteiros sem sinal, escritos em base , em que o último algarismo ocorre anteriormente no número. Por exemplo, e pertencem a esta linguagem, mas e não. (Os números escritos em base só podem ter os algarismos e .)

  1. escreva uma expressão regular que a represente.
  2. defina um autómato finito que a reconheça.
  3. apresente um autómato finito determinista que a reconheça (Sugestão: tente construí-lo diretamente, sem recorrer a qualquer algoritmo).

Exercício 11

AFND EXERC 11

Considere o autómato definido no diagrama acima.

  1. Calcule o e o .
  2. Calcule e .
  3. Desenhe as árvores das computações de e , indicando se são aceites ou rejeitadas.

Exercício 12

Seja um autómato finito não determinista cuja função de transição é

Construa um autómato finito determinista equivalente a , usando o algoritmo dado nas aulas, e apresente uma ER que represente a linguagem por ele reconhecida.

Exercício 13

✓ Repita o exercício anterior para o autómato finito não determinista cuja função de transição é

Exercício 14

✓ Considere a linguagem de todas as palavras sobre em que o antepenúltimo símbolo é .

  1. defina um autómato finito (não determinista) que reconheça esta linguagem.
  2. aplicando o algoritmo dado nas aulas, construa um autómato finito determinista equivalente ao autómato finito da alínea anterior.

Exercício 15

Repita o exercício anterior para a linguagem de todas as palavras sobre em que o terceiro e o antepenúltimo símbolos são . São exemplos de palavras que pertencem a esta linguagem as palavras , , e .

Exercício 16

Sejam e dois autómatos finitos tais que e são disjuntos. Defina um autómato finito tal que .

Exercício 17

Defina um AFD equivalente ao AFND

em que

Minimização e Composição de AFD

Exercício 18

✓ Aplicando o algoritmo dado nas aulas, construa o autómato finito determinista mínimo equivalente a , com a função de transição

e apresente uma expressão regular que represente .

Exercício 19

Considere o autómato finito não determinista , com a função de transição

  1. construa o AFD equivalente a .
  2. construa o AFD mínimo equivalente a .

Exercício 20

✓ Considere a linguagem representada por reunida com .

  1. defina um autómato finito (não determinista) que reconheça aquela linguagem.
  2. construa um AFD equivalente ao autómato finito definido na alínea anterior.
  3. construa um AFD mínimo equivalente ao AFD obtido na alínea anterior.

Exercício 21

Repita o exercício anterior para a linguagem das palavras sobre que têm como subpalavra.

Exercício 22

✓ Construa um AFND que aceita a linguagem das palavras

  1. binárias com, pelo menos, três ocorrências de ;
  2. binárias com subpalavras e ;
  3. binárias (com subpalavra ou ) e (com sufixo ou );
  4. binárias em que o -ésimo símbolo é , para ;
  5. binárias, de tamanho , e em que, para cada , algum dos , ou -ésimo símbolo é ;
  6. em que ;

Exercício 23

Encontre um AFND que aceite as palavras...

  1. com prefixo ou sufixo .
  2. com pelo menos, duas ocorrências de e sufixo .
  3. em que .

Exercício 24

  1. Sejam e dois AFND. Encontre um AFND tal que .
  2. Seja um AFND. Encontre um AFND tal que .

Exercício 25

Seja um AFND em que

Construa um AFND que aceite a linguagem complementar de .

Exercício 26

  1. Construa um AFD que aceite a linguagem binária das palavras em que o quinto símbolo a partir do fim é .
  2. Converta (simule) cada um dos AFND seguintes num AFD:
    1. com transição

    2. Dados nos diagramas abaixo:

26.2 A26.2 B26.2 C
AFND EXERC 26 BAFND EXERC 26 BAFND EXERC 26 B

Exercício 27

Construa um AFD que aceite a linguagem das palavras que:

  1. Contêm as sub-palavras e ;
  2. Com sufixo ou ou (de duas maneiras);
  3. Ou (contêm as sub-palavras e ) ou (não contêm nem nem );
  4. A quarta letra a partir do fim, e a quarta letra a partir do princípio são ambas (nota: e estão nesta linguagem);

O Pumping Lemma

Exercício 28

Mostre que as seguintes linguagens não são regulares:

  1. .
  2. A linguagem das palavras capicua sobre .
  3. .
  4. .
  5. .
  6. .

Implementação

As indicações gerais para os exercícios de implementação são válidas aqui.

Uma Biblioteca para AFD

A biblioteca para AFD tem de verificar as condições indicadas a seguir.

  • Os estados são números inteiros, os símbolos de entrada são string e as palavras são listas de símbolos.
  • Represente. Um AFD é representado por uma estrutura de dados FSA (pode ser uma classe, uma struct, etc) com os seguintes atributos, que devem ser visíveis mas não modificáveis:
    • initialState o estado inicial.
    • finalStates o conjunto dos estados finais.
    • delta uma lista de triplos (q, s, p) que define a transição .
  • Construção. Um AFD é construidos pela função/método makeFSA(t,i,f) em que:
    • t é uma lista de triplos (q, s, p) como acima.
    • i é o estado inicial.
    • f é a lista dos estados finais.
  • Sanidade. A função wellFormed(fsa) ou fsa.wellFormed() testa se os atributos t,i,f do argumento definem, de facto, um AFD. Quais são essas condições?
  • Implemente. A função step(fsa, q, s) ou fsa.step(q, s) devolve o estado p quando fsa está no estado q e lê s.

    Se não existe transição para (q, s) esta função devolve "não definido".

    Em python "não definido" é None, em java/kotlin é null, em rust é Option::None, outras linguagens podem ou não definir "não definido" :D

  • Implemente. A função proc(fsa, q, w) ou fsa.proc(q, w) devolve o estado em que fsa termina se começar em q e ler a palavra w. Use o critério de step se a computação não continuar até ao fim.
  • Implemente. A função accepts(fsa, q, w) ou fsa.accepts(q, w), testa se w é aceite por fsa. Esta função deve devolver sempre um booleano.
  • Escrita. A função repr(fsa) ou fsa.repr() devolve uma string com várias linhas:
    • A primeira linha tem o formato i <Q>; em que <Q> é o estado inicial.
    • A segunda linha tem o formato f <Q1> ... <Qn>; em que os <Qi> são os estados finais.
    • As restantes linhas têm o formato <Q> <S> <P>; para representar a transição do fsa. Deve existir uma linha destas para cada "aresta" do autómato.
    • N.B. todas as linhas terminam em ";" e valores na mesma linha são separados por espaços.
  • Leitura. A função parseFSA(s) tem como argumento uma string no formato acima e devolve o FSA correspondente. A leitura do argumento deve descartar carateres "espaço" (\n\r\t) mas com cuidado.
  • Escrita. Consulte a documentação da linguagem dot usada para definir grafos. Implemente uma função reprDOT(fsa) ou fsa.reprDOT() para gerar um grafo numa string em dot.
  • Sanidade. As funções repr e parseFSA devem ser "inversas" uma da outra, no sentido em que parseFSA(s).repr() == s e parseFSA(fsa.repr()) == fsa. Embora estas igualdades não sejam exatamente igualdades, nem fáceis de implementar, teste-as com alguns casos simples.

Gramáticas e Autómatos de Pilha

O Pumping Lemma aplicado à linguagem mostra que as linguagens regulares não são adequadas para definir linguagens de programação.

Portanto, é necessária outra abordagem para resolver o Problema Principal de ALPDada uma linguagem e uma palavra no mesmo alfabeto, determinar se de forma computável, acessível e adequada.

Neste capítulo definem-se certas gramáticas formais que generalizam as linguagens regulares e estão associadas aos autómatos de pilha, uma forma simples de autómato com memória ilimitada.

Gramáticas Independentes de Contexto

Uma especificação formal de linguagens mais capaz do que as expressões regulares.

Introdução

Nos capítulos anteriores desenvolveu-se, para as ER, AFD e AFND, um conjunto de técnicas computacionais eficientes, com vista a resolver o Problema Principal de ALP. Porém, com o Pumping Lemma, conclui-se que é necessária uma forma mais geral de definir linguagens.


As linguagens naturais têm uma certa estrutura que resulta de regras gramaticais. Por exemplo, "O gato bebe leite." é válida em português mas "bebe. gato leite O" não. (N.B: neste exemplo os símbolos do alfabeto são as palavras da língua portuguesa — por exemplo, de um dicionário — e as palavras são sequências desses símbolos.)

Como descrever essas regras gramaticais? Por exemplo:

Frase       : Sujeito Predicado
Sujeito     : Artigo Substantivo
Predicado   : Verbo Advérbio
Artigo      : "o"
            | "as"
Substantivo : "gato"
            | "galinhas"
Verbo       : "bebe"
            | "voam"
Advérbio    : "devagar"
            | "baixinho"

Os termos Assim são variáveis e "entre aspas" são terminais.

Aplicando estas regras, obtém-se, por exemplo:

Frase   : Sujeito Predicado
        : Artigo Substantivo Predicado
        : o Substantivo Predicado
        : o gato Predicado
        : o gato Verbo Advérbio
        : o gato bebe Advérbio
        : o gato bebe devagar

Também se obtêm frases com pouco sentido, como as gato voam devagar. Esses problemas, em princípio, podem ser tratados com regras mais sofisticadas. No entanto, também este exemplo sem sentido mantém a estrutura entre as diferentes partes da palavra: o Artigo está no início, etc. Isto é, usando aquelas regras nunca se obtém, por exemplo, devagar bebe o gato.

Gramáticas e Linguagens Independentes de Contexto

As Gramáticas Independentes do Contexto são uma forma simples de representar rigorosamente regras gramaticais como as ilustradas acima.

Gramática Independente do Contexto (GIC). Uma Gramática Independente do Contexto é um tuplo em que:

  • Variáveis (ou Não Terminais): é um conjunto de símbolos, designados variáveis ou não terminais.
  • Terminais: é um conjunto de símbolos, disjunto de (isto é, ), designados terminais.
  • Produções (ou Regras): é um conjunto finito. Os seus elementos são pares da forma com e , designados produções ou regras e denotados .
  • Símbolo Inicial: .

Numa GIC há dois tipos de símbolos: Os terminais, sem produções associadas e as variáveis, com produções associadas. Intuitivamente, as variáveis vão ser sucessivamente transformadas, até restarem apenas símbolos terminais.

É importante notar que o alfabeto das palavras é isto é, as palavras têm terminais e variáveis.

Esta mistura justifica a definição seguinte:

Prefixo (resp. Sufixo) Terminal. Seja uma palavra formada por (zero ou mais) terminais e (zero ou mais) variáveis. Então, escrevendo em que e começa e termina por variáveis.

  • O prefixo terminal de é .
  • O sufixo terminal de é .

Isto é, é o maior prefixo só de terminais de e é o maior sufixo só de terminais.

Por exemplo, em o prefixo terminal é e o sufixo terminal é .

A aplicação de regras de uma GIC transforma palavras. Formalmente:

Derivação. Sejam uma GIC, .

  • Se , então deriva diretamente e escreve-se .
  • Se existem tais que então deriva em passos e escreve-se .
  • Se existe tal que então deriva e escreve-se .

As regras de uma gramática são aplicadas às variáveis de uma palavra e o resultado é uma nova palavra. A esse processo chama-se "derivação direta". Se forem aplicadas derivações diretas obtém-se uma "derivação em passos". Por fim, se o número exato de passos não for importante, tem-se uma "derivação".

Por exemplo, dada a gramática :

  • pela regra .
  • Também pela regra .
  • pela regra .

Em certas circunstâncias é necessário especificar a GIC de onde estão a ser usadas as derivações. Nesse caso acrescenta-se o índice e a notação das derivações fica para indicar que são usadas apenas produções de .


Para escrever uma GIC é comum usarem-se as seguintes regras para simplificar a notação:

  • Os terminais são representados por minúsculas e as variáveis por maiúsculas.
  • Se nada for dito, é o símbolo inicial.
  • As produções de cada variável ficam agrupadas e, entre si, separadas por "".

Por exemplo, a gramática acima fica completamente definida por


As produções de uma gramática transformam palavras noutras palavras. Essa transformação tem a designação técnica de derivação e é a base para associar uma linguagem a uma GIC.

Linguagem Gerada. Seja uma GIC.

  • O conjunto das palavras deriváveis a partir de é .
  • A linguagem gerada por é .
    • Neste caso diz-se que é uma Linguagem Independente do Contexto.
  • Duas gramáticas são equivalentes se geram a mesma linguagem.

Observação. As palavras da linguagem gerada são só de terminais. Isto é: .

Tal como foi feito para as ER, os AFD e AFND, a equivalência entre GIC assenta na linguagem associada.

Por exemplo, qual é a linguagem gerada por ?

  1. Da produção resulta a derivação . Portanto .
  2. Da derivação resulta que .
  3. Igualmente, de conclui-se que .
  4. Sucessivamente, .

Portanto, gera a linguagem simplificada dos parêntesis equilibrados, .

A linguagem , usada para mostrar que as linguagens recursivas não são adequadas para definir linguagens de programação é a linguagem gerada por uma GIC com apenas duas produções.

Este exemplo é um sinal positivo para resolução do Problema Principal de ALP, pelo menos em termos da adequação. Falta ainda aprofundar casos mais complexos de adequação e tratar dos aspetos da computação e da eficiência.

Recursividade

Donde vem a capacidade das GIC para gerar tão facilmente , quando as ER falharam?

Olhando de novo para a GIC em questão, , destaca-se a regra . O "" em "" permite "repetir indefinidamente" o , como um ciclo.

Esta possibilidade de "repetições indefinidamente" está além da capacidade expressiva das ER. Porém, é uma espada de dois gumes, que levanta problemas novos. Por exemplo, que palavras são geradas pela GIC ?

Formalmente, a produção é "diretamente recursiva" e a recursão pode surgir de várias formas:

Produção Recursiva. Não Terminal Recursivo, Derivação Recursiva. Sejam uma GIC, e .

  1. Uma produção da forma é diretamente recursiva.
  2. Uma variável é recursiva se (isto é, em um ou mais passos).
  3. Uma derivação da forma onde não ocorre em é indiretamente recursiva.

Por exemplo,

  • é uma produção diretamente recursiva.
  • No exemplo anterior, é uma variável recursiva.
  • Na gramática , a derivação é indiretamente recursiva.

Mais tarde serão tratadas várias situações relacionadas com a recursividade mas por enquanto importa aprofundar mais aspetos das derivações.


Em primeiro lugar importa assegurar que, numa derivação , as sub-derivações de uma variável em não são afetadas pelas sub-derivações de outras variáveis também em .

Por exemplo, supondo que numa certa CIG , é intuitivamente evidente que os resultam de e apenas de e que os resultam apenas do e que, no total, fizeram-se derivações.

Mas a evidência intuitiva precisa de um apoio rigoroso:

Independência das Sub-Derivações. Seja uma GIC e uma derivação em onde

com os (portanto, palavras só de terminais) e os .

Então existem palavras tais que:

  • Para cada , .
  • .
  • .

A independência está na afirmação de que o resultado é obtido isoladamente em cada variável, .

Por exemplo, dada a gramática , a derivação em passos tem sub-derivações:

  • com dois passos; .
  • com três passos;
  • .

Derivação Esquerda/Direita

Considerando a GIC , a partir do símbolo inicial, , há três opções para "escolher a produção". Se a escolha for , fica-se com a derivação , se for a derivação é e também é uma derivação possível.

Em há duas opções para "escolher a variável". A primeira ou a segunda? Se for a primeira, obtém-se , e mas se for a segunda os resultados possíveis são , e .

As regras das derivações permitem duas escolhas:

  1. Que variável substituir?
  2. Com que produção dessa variável?

Se por um lado estas escolhas permitem "capacidade expressiva" (o que é bom: as ER não são suficientemente expressivas) por outro lado as escolhas têm um custo elevado (exponencial) na eficiência computacional de futuros algoritmos sobre CIG e LIC.

Uma boa solução para este dilema restringe as escolhas sem sacrificar a "capacidade expressiva".

Derivação Esquerda. Derivação Direita.

  • Numa derivação esquerda é escolhida a variável mais à esquerda em todos os passos. Nas derivações esquerdas o símbolo é substituído por .

  • Numa derivação direita é escolhida a variável mais à direita em todos os passos. Nas derivações direitas o símbolo é substituído por .

Seja uma GIC. Para cada ,

Isto é, numa derivação esquerda escolhe-se sempre a primeira variável e numa derivação direita escolhe-se sempre a última. A "capacidade expressiva" não fica prejudicada porque qualquer palavra só de terminais que seja gerada pela GIC também é gerada por uma derivação esquerda e também é gerada por uma derivação direita.

Por exemplo, continuando com a gramática , como derivar ?

  • Sem restrições, uma solução é . Nuns passos foi escolhida a primeira variável, noutros a última.
  • Derivação esquerda: .
  • Derivação direita: .

Árvore de Derivação

As derivações podem ser representadas graficamente por diagramas em árvore.

Árvore de Derivação. Seja uma GIC e uma derivação de .

A árvore da derivação é formada por:

  • Raiz: O símbolo inicial .
  • Filhos: Se a produção , com for a produção usada para substituir a variável então o vértice tem filhos por essa ordem.
  • Folhas Vazias: Se for a produção usada para substituir a variável então o vértice tem como único filho.

Uma palavra tem árvore de derivação se for a concatenação das folhas de lidas da esquerda para a direita.

Por exemplo, a derivação tem a seguinte árvore:

Exemplo de Árvore de Derivação
Figura Exemplo Árvore Derivação

Lendo as folhas da esquerda para a direita obtém-se , a palavra derivada.

Ambiguidade

Um problema (ver Dangling Else na wikipedia) que ocorre frequentemente em várias linguagens de programação, e que é responsável por erros difíceis de detetar e com consequências graves, pode ser ilustrado no seguinte exemplo:

if (a) if (b) s1; else s2;

Este fragmento tanto pode ser tratado como

if (a) {
    if (b) s1;
    else s2;
}

ou como

if (a) {
    if (b) s1;
}
else s2;

No primeiro caso, se a for falso não corre nem s1 nem s2. No segundo caso, se a for falso corre s2. O que acontece se a for "inimigo detetado", s2 "lançar mísseis" e b testa "cenário simulado"?

Este problema resulta diretamente da gramática porque a palavra if (a) if (b) s1; else s2; tem duas derivações diferentes, uma que associa o else ao primeiro if e outra que o associa ao segundo.

Formalmente,

Gramática Ambígua. Linguagem Inerentemente Ambígua.

  • Uma gramática é ambígua se alguma palavra de tem:
    • duas árvores de derivação distintas ou
    • duas derivações esquerdas distintas ou
    • duas derivações direitas distintas.
  • Uma linguagem é inerentemente ambígua se não for gerada por uma gramática não ambígua.

Nesta definição é importante lembrar e distinguir o seguinte:

  • Uma linguagem pode ser gerada por várias gramáticas equivalentes. Algumas dessas gramáticas podem ser ambíguas e outras não. Por isso, "ambígua" é uma propriedade que diz respeito às gramáticas.
  • Também pode acontecer que todas as gramáticas que geram uma certa linguagem sejam ambíguas. Esta situação é uma caraterística da linguagem, não das gramáticas que a geram. Por isso "inerentemente ambígua" é uma propriedade que diz respeito às linguagens.

Um exemplo de uma linguagem inerentemente ambígua é:

A gramática é ambígua porque e são duas derivações direitas de . Esta gramática é equivalente a que não é ambígua (exercício: porquê?).


Como é que as LIC se relacionam com as LR? O que foi feito nos capítulos anteriores está "perdido" ou as GIC estendem as ER?

Gramáticas Regulares e Simulação de AFND

Como definir linguagens regulares com GIC?

Gramática Regular. Uma gramática é regular se todas as suas produções têm uma das formas seguintes: com e .

O interesse desta definição é que

Se é uma GIC regular então é uma linguagem regular.

A demonstração desta afirmação está fora do âmbito de ALP. A consequência das gramáticas regulares é que as GIC podem gerar algumas linguagens regulares*. Será que podem gerar todas?

Simulação de AFND por GIC. Seja um AFND. A GIC equivalente a é em que:

  • variáveis - estados. .
  • símbolo inicial - estado inicial. .
  • produções - estados finais. Se então .
  • produções - transições . Para cada , se então .
  • produções - transições . Se então .

Neste caso .

Dado um AFND qualquer, aplicando este método, obtém-se uma GIC equivalente no sentido em que a linguagem aceite pelo AFND é gerada pela GIC. Portanto as LIC incluem todas as LR.

Por exemplo, dado o AFND antes usado para ilustrar o Algoritmo de Kleene:

AFND equivalente a
Fig: Exemplo TK 01

vai construir-se a GIC em que:

  1. As variáveis são .
  2. O símbolo inicial é .
  3. As transições e os estados finais definem as seguintes produções:

A palavra abaabb é aceite pelo AFND, pela computação

Será gerada pela GIC?

Este exemplo também ilustra como a produção da GIC representa a transição do AFND.

Conclusão

As GIC foram introduzidas depois de se ter constatado, no capítulo anterior, que as linguagens regulares são insuficientes para definir as linguagens de programação.

  • Logo um dos primeiros exemplos de GIC permitiu definir a linguagem simplificada dos parêntesis equilibrados, o que é um indicador positivo para as GIC.
  • Outro exemplo, as expressões algébricas, permitiu ilustrar como tratar o problema da ambiguidade.
  • A questão da relação entre as LR e as LIC ficou resolvida com a simulação de AFND por uma GIC regular.

Embora as GIC pareçam um candidato razoável para descrever as linguagens de programação, falta tratar as questões da computação: Como responder algoritmicamente, de forma eficiente, à questão ?

Autómatos de Pilha

Um modelo computacional simples com memória ilimitada.

Introdução

Embora as GIC pareçam um candidato razoável para descrever as linguagens de programação, falta tratar as questões da computação: Como responder algoritmicamente, de forma eficiente, à questão ?

Intuitivamente, nos AFD e AFND a "memória" está representada pelos estados e portanto é limitada à priori, independentemente da palavra que vai ser processada. Por isso é que a linguagem "escapa" ao reconhecimento pelos AFD e AFND — "é preciso memorizar quantos foram lidos" e esse número é arbitrariamente grande.

As "pilhas" são uma forma simples de "memória ilimitada". Numa pilha podem ser colocados e retirados símbolos no "topo". A transição depende não só do estado e do símbolo da palavra mas também do símbolo que está no topo da pilha.

Autómatos de Pilha e Gramáticas Independentes de Contexto

Tal como foi feito para os AFD e AFND, depois da definição de autómato segue-se a configuração e computação e palavra aceite e linguagem reconhecida.

Autómato de Pilha (AP). Um Autómato de Pilha (AP) é um tuplo em que:

  • Estados de Controlo, Alfabeto de Entrada, Estado Inicial, Estados Finais são como nos AFD.
  • Alfabeto da Pilha é um conjunto finito de símbolos.
  • Transição é uma função com assinatura

Importa notar o seguinte:

A transição depende do estado de controlo, do símbolo de entrada e do símbolo no "topo" da pilha e define o novo estado de controlo e o novo símbolo no "topo" da pilha.

As computações dos AP são não deterministas, como resulta da assinatura da transição, na parte "". Formalmente:

Configuração. Computação. (AP). Seja um AP.

  • Uma Configuração é um triplo .

  • A Configuração Inicial para é .

  • Uma Computação é uma sequência de passos dos seguintes tipos:

    • AFND se e .
    • Remove se e .
    • Acrescenta se e .
    • Troca se e .

Informalmente, os tipos de passos de uma computação são

TipoAnteriorSeguinteCondiçãoObservação
AFNDA pilha não é "usada".
Remove no topo é substituído por .
Acrescenta no topo é substituído por .
Troca no topo é substituído por .

O critério de aceitação de uma palavra depende da configuração final.

Palavra Aceite. Linguagem Reconhecida. (AP) Seja um AP. A palavra é aceite por se existe uma computação

A linguagem reconhecida (ou aceite) por é o conjunto das palavras aceites por .

A condição especifica que:

  1. A computação chegou a um estado final,
  2. Todos os símbolos de foram processados e
  3. A pilha está vazia.

Além disso, a condição de aceitação depende de existir uma computação naquelas condições. Outras computações podem não ser assim. Portanto, para uma palavra ser rejeitada é necessário que nenhuma computação verifique todas.

Diagramas de AP

Os diagramas dos AP seguem as mesmas regras dos AFD e AFND, sendo apenas necessário indicar as operações na pilha.

Por exemplo, o AP por

  • Estados de Controlo .
  • Alfabeto de Entrada .
  • Alfabeto da Pilha .
  • Estado Inicial .
  • Estados Finais .
  • Transição

tem o seguinte diagrama

Diagrama de AP para
Figura Diagrama AP

Note-se que na tabela da transição as colunas descrevem não só todas as possibilidades como também os casos com .

Descrevendo os passos das computações por algumas computações deste AP são:

  1. De : . Como é final e a entrada e a pilha estão vazias, é aceite.
  2. De :
    1. . Esta computação poderia ter parado em , que não aceita tal como a última configuração.
    2. Em alternativa, que não aceita .
    3. Como não há mais computações de esta palavra é rejeitada.
  3. De : é a única possibilidade e rejeita .
  4. De : aceita.
  5. De : é semelhante à computação de .

A computação de ilustra bem o uso da pilha como dispositivo de memória. Por cada lido da entrada é acrescentado uma "conta" à pilha. Quando se passa do estado para cada desconta a "conta" do topo. Se o número de for igual ao número de então no fim de processar todos os a pilha fica vazia.

Aquele AP tem mais "estrutura" do que apenas a contagem de e . Por exemplo, tem um e um mas é rejeitada devido à forma como o AP proíbe ler depois de começar a ler .

Árvore das Computações

As computações dos AP, em geral, não são deterministas. Isto significa que, dada uma palavra para processar, o AP "gera uma árvore", em vez de uma única sequência.

Árvore das Computações. Seja um AP e . A árvore das computações de por é formada por:

  • Raíz: A configuração .
  • Filhos: Se for um vértice da árvore, para cada configuração tal que por então é um filho de .

Por exemplo, no AP acima, a palavra tem a seguinte árvore de computação:

Árvore das Computações de Autómato de Pilha
Árvore das ComputaçõesFigura Diagrama AP

Variantes de AP

O tipo de transições permitidas pela definição de AP é um caso intermédio entre:

  • Autómato Atómico é um AP que só tem transições do tipo
    • : AFND.
    • : Remove, mas não lê da entrada.
    • : Acrescenta, mas não lê da entrada.
  • Autómato Estendido é um AP que também permite transições do tipo em que o topo da pilha é substituído por mais do que um símbolo ().

Estas variantes são equivalentes, no sentido em que um AP de uma variante pode ser transformado num AP doutra.

GIC e AP

Os AP definem o aspeto computacional das CIG mas essa ligação ainda não foi definida:

Simulação de GIC por AP. Seja uma GIC.

O AP em que a transição é definida por

  • Para cada variável ,

  • Para cada terminal ,

é equivalente a no sentido em que se a pilha for iniciada com .

Esta definição/transformação/teorema define como obter um AP equivalente a uma GIC dada. Embora o processo inverso fique fora do âmbito de ALP, para os efeitos pretendidos isto é suficiente.

Embora a condição sobre a inicialização da pilha contradiga a definição de AP, pode ser facilmente contornada. Basta definir um novo estado inicial e acrescentar a transição .

Por exemplo, dada a GIC o AP equivalente é

AP da GIC
Diagrama AP de aSb

As arestas associadas aos terminais e a cada variável são normalmente agrupadas de forma a facilitar a leitura do diagrama.

Este AP é equivalente ao anterior e à GIC da linguagem simplificada dos parêntesis equilibrados. Neste caso as produções da GIC podem ser "lidas" diretamente das arestas do AP.

Algumas computações deste AP:

  1. De : aceita.
  2. De :
    1. . não aceita.
    2. . não aceita.
    3. . não aceita.
    4. Não há mais computações de , que é rejeitada.
  3. De : aceita.

A derivação de uma palavra na GIC é replicada na computação do AP.

Por exemplo, a palavra tem a seguinte derivação: A mesma palavra tem a seguinte computação:

Hierarquia de Chomsky

As GIC não são o único tipo de gramática:

  • Tipo 0 ou sem restrições as produções são da forma em que e . Isto é, o lado esquerdo pode ser qualquer palavra não vazia. A substituição de um símbolo depende da "vizinhança" desse símbolo, o seu contexto.
  • Tipo 1 ou dependente de contexto são como as de tipo 0 mas . Tal como no Tipo 0 a substituição de símbolos depende do contexto mas, adicionalmente, as substituições contraem a palavra.
  • Tipo 2 ou independente de contexto são as gramáticas usadas aqui. A substituição de um símbolo não depende do contexto em que este ocorre.
  • Tipo 3 ou regular impõe ainda mais restrições às produções e geram as linguagens regulares.

Conclusão

Os AP são um modelo computacional das GIC. Especificamente, há um algoritmo que transforma uma GIC num AP equivalente. Além disso, as derivações na GIC são replicadas pelas computações do AP.

Ficam assim resolvidas as questões da adequação e da computação no Problema Principal de ALP — Dada uma linguagem e uma palavra no mesmo alfabeto, determinar se .

Falta ainda tratar da eficiência. Os AP não são deterministas e, ao contrário dos AFND, não se conhece nenhuma simulação determinista que seja geral e eficiente. A esperança que resta é condicionar as gramáticas de forma a que os AP associados sejam, em termos práticos, deterministas mas sem estragar a "capacidade expressiva" das gramáticas.

O próximo capítulo começa por visitar os principais tipos de Análise Sintática (o termo técnico do Principal Problema de ALP) e segue para métodos e tipos de gramáticas adequados à sua resolução eficiente.

Exercícios — Gramáticas e Autómatos de Pilha

Os exercícios assinalados com "✓" serão resolvidos nas aulas práticas; Os assinalados com "†" têm elevada dificuldade. Todos os restantes devem ser resolvidos pelos alunos.

Gramáticas Independentes do Contexto

Exercício 01

Escolha três ou quatro linguagens de programação (como C, python, Java ou outras mais recentes como go ou swift) ou apenas formais (como o XML) e encontre (online) gramáticas que as definam.

Exercício 02

Defina uma gramática independente do contexto que gere a linguagem:

  1. .
  2. .
  3. .
  4. .
  5. dos números naturais sem zeros não significativos.

Exercício 03

Defina uma gramática independente do contexto que gere os reais (incluindo os negativos) em que: a parte inteira é não vazia e não tem zeros não significativos; a parte decimal é não vazia e só termina em zero se for constituída por um único 0; e as partes inteira e decimal são separadas por uma vírgula.

Exercício 04

✓ Seja a linguagem de todas sequências de parêntesis, curvos - ‘’ e ‘’ - e rectos - ‘’ e ‘’ -, bem emparelhados. Pertencem a esta linguagem palavras como , “”, “”, “”, “” e “”. Não pertencem a palavras como “”, “”, “”, “”, “” e “”.

  1. Mostre que não é regular;
  2. Defina uma gramática independente do contexto que gere .

Exercício 05

✓ Considere um conjunto de variáveis e um conjunto de símbolos de função, cada um com uma aridade maior que ou igual a zero. Um termo é definido como:

  • uma variável é um termo.
  • um símbolo de função de aridade 0 é um termo.1
  • se são termos, então, para todos os símbolos de função de aridade , é um termo;
  • nada mais é um termo.

Defina uma gramática independente do contexto que gere os termos descritos — use os símbolos e como representantes das variáveis e dos símbolos de função, respetivamente. Exemplos de termos são , , e .

Exercício 06

Considere a gramática .

  1. Construa uma derivação esquerda para a palavra e a respetiva árvore de derivação.
  2. Construa uma derivação direita para a palavra e a respetiva árvore de derivação.
  3. Determine se G é ambígua. † Em caso afirmativo, apresente uma gramática não ambígua equivalente.

Exercício 07

✓ Considere a gramática independente do contexto

  1. Mostre que esta gramática é ambígua.
  2. † Apresente uma gramática equivalente não ambígua.
  3. Apresente uma gramática regular equivalente.
  4. Apresente uma expressão regular que represente a linguagem gerada pela gramática.

Exercício 08

Resolva o exercício anterior para a gramática

Exercício 09

Defina uma gramática livre do contexto que gere a linguagem …

  1. . Usando essa gramática, derive a palavra .
  2. . Usando essa gramática, derive a palavra .

Exercício 10

† Defina uma gramática livre do contexto que gere todas a expressões regulares sobre o alfabeto .

Exercício 11

Considere a gramática livre do contexto

  1. Derive .
  2. † Mostre que esta gramática é não ambígua.

Exercício 12

Considere a gramática livre do contexto ;

  1. Mostre que esta gramática é ambígua.
  2. Encontre uma gramática equivalente, não ambígua.

Autómatos de Pilha

Exercício 13

✓ Defina um autómato finito que reconheça a linguagem gerada pela gramática .

Exercício 14

✓ Defina um autómato de pilha que reconheça a linguagem . Será possível definir um autómato de pilha determinista que reconheça esta linguagem? Justifique a sua resposta.

Exercício 15

✓ Considere a linguagem de todas as palavras sobre em que o número de é igual ao número de :

  1. defina um autómato de pilha não determinista que a reconheça.
  2. † defina um autómato de pilha determinista que a reconheça.

Exercício 16

Defina um autómato de pilha que reconheça e indique se esse autómato é, ou não, determinista.

Exercício 17

Defina um autómato de pilha que reconheça .

Exercício 18

Construa um autómato de pilha que reconheça a linguagem das expressões aritméticas com o operador e com parêntesis. Use o símbolo para representar os operandos atómicos, i.e., as expressões terão o seguinte aspeto: , , , etc.

Implementação

As indicações gerais para os exercícios de implementação são válidas aqui.

Uma biblioteca para GIC e AP

Para esta biblioteca são adotadas as seguintes convenções e orientações:

  1. Um símbolo é uma string válida: uma string não vazia em que não ocorre ' '.
  2. Uma variável é um símbolo que começa por uma maiúscula.
  3. Um terminal é um símbolo que não é uma variável.
  4. Estão implementadas funções is_symbol(s), is_variable(s) e is_terminal(s).
  5. Uma palavra é uma lista de símbolos.
  6. As regras são representadas pela classe Rule, com:
    1. O construtor Rule(var, word).
    2. Os métodos básicos variables(), terminals(), equals(other).
    3. Os métodos analíticos is_nil(), is_recursive(), is_wellformed().
    4. Os métodos operacionais dderive_left(word), dderive_right(word).
    5. O método auxiliar __repr__() com "→" para a seta e usando "λ" quando adequado.
    6. A função auxiliar parse_grammar(s). Assume-se que s é uma string com os símbolos separados por espaços, que o primeiro desses símbolos define o lado esquerdo da regra e os restantes a palavra do lado direito. Por exemplo, "A a A b" define a regra A→aAb.
  7. As gramáticas são representadas pela classe Grammar, com:
    1. O construtor Grammar(rules).
    2. Os métodos básicos variables(), terminals(), rules_of(symbol) e set_start(symbol).
    3. Os métodos analíticos is_wellformed(), start() (o símbolo inicial), is_nil(symbol), nil_symbols(), is_recursive(symbol), recursive_symbols().
    4. Os métodos operacionais derive_left(sequence, word), derive_right(sequence, word) onde sequence é uma lista com indíces das regras e word é um parâmetro opcional com valor por omissão igual ao símbolo inicial da gramática (start()).
    5. O método auxiliar __repr__().
    6. A função auxiliar parse_grammar(s). Assume-se que s é uma string com blocos de regras separados por ';' e em que cada bloco de regras é da forma V : P1 | P2 | ...| Pn. Por exemplo "S:a A b|;A:S|c" define a gramática . Note bem que as regras de uma variável podem estar "espalhadas" por vários blocos e que eventuais repetições de regras devem ser descartadas.
  8. O símbolo inicial (start) de uma gramática é calculado da seguinte forma:
    1. Se for usado o método set_start(symbol) é o valor do parâmetro symbol.
    2. Caso contrário, se 'S' é uma variável na gramática ou se a gramática tem zero regras, o símbolo inicial é 'S'.
    3. Por fim, se nenhuma das outras situações se verifica, é o lado esquerdo da primeira regra da gramática.
  9. As linhas das transições, , são representadas pela classe TrLine, com:
    1. O construtor TrLine(state_0, symbol, stack_0, state_1, stack_1) onde (state_0, symbol, stack_0, state_1, stack_1) é .
  10. As configurações, , são representadas pela classe Configuration, com:
    1. O construtor Configuration(state, tape, stack) onde (state, tape, stack) é .
    2. Os métodos analíticos is_final(final_symbols), is_fitting(trline) e all_fitting(transition).
    3. Os métodos operacionais next(trline, check) e tree(delta, max_depth, check) em que check é um parâmetro opcional que por omissão vale False e, sendo verdadeiro, ativa a verificação is_fitting(trline). Note bem que o resultado de aplicar uma linha a uma configuração incompatível é a configuração inicial.

Exercício 19

Sempre que possível teste a sua biblioteca com as gramáticas e os autómatos dos exercícios anteriores.

Análise Sintática

A Análise Sintática trata de relacionar uma palavra com uma gramática. Especificamente, pretende-se saber se a palavra é gerada pela gramática e, se sim, qual a sua derivação.

Portanto,

A Análise Sintática é uma versão do Problema Principal de ALP quando a linguagem é gerada por uma GIC.

No capítulo anterior definiram-se as gramáticas independentes de contexto e os autómatos de pilha, para ultrapassar os limites das linguagens regulares e dos autómatos finitos no que diz respeito à definição de linguagens de programação.

Ficaram assim resolvidas as necessidades sobre um esquema formal adequado para representar as linguagens de programação e dum modelo de computação para determinar se .

Mas mantém-se o problema da eficiência porque, embora os autómatos de pilha proporcionem um modelo computacional para as linguagens independentes de contexto, não se conhecem formas gerais para garantir que as suas computações sejam eficientes.

Restam duas possibilidades: Ou condicionar as gramáticas de forma a reduzir a ramificação durante as derivações ou "espreitar" os símbolos por processar para "guiar" as computações,

Este capítulo começa por visitar os principais métodos de pesquisa geral em grafos, de forma a avaliar o problema da eficiência nalguns casos concretos.

De seguida é primeiro apresentado um processo (sequência de passos) que permite transformar uma GIC noutra equivalente e melhor adaptada ao algoritmos de pesquisa geral (a Forma Normal de Greibach). Por fim são apresentadas as classes de gramáticas e , que "espreitam" os próximos símbolos "por processar" para definir algoritmos deterministas de análise sintática.

Análise Sintática

Pesquisar o Grafo de uma GIC ou uma Árvore das Computações de um AP de forma a encontrar a derivação de uma palavra e construir uma árvore de sintaxe abstrata.

Introdução

A eficiência computacional da análise sintática tem um problema, manifesto no não determinismo dos autómatos de pilha (que, ao contrário dos AFND, deles não se conhece nenhuma simulação determinista, geral e eficiente) e, equivalentemente, nas múltiplas produções das gramáticas independentes do contexto. Ambos estes casos têm representações gráficas: o Grafo da Gramática nas GIC e as Árvores das Computações nos AP.

Nesta situação é necessário fazerem-se pesquisas, abrangendo (no pior cenário) todas as possibilidades. Este é um processo inerentemente (demasiado) demorado pelo que importa encontrar formas de o melhorar.

Conteúdo

Do Problema Principal de ALP — Dada uma linguagem e uma palavra , determinar se . resta resolver a questão da eficiência computacional, já que a adequação ficou resolvida com as GIC e a computação com os AP.

Intuitivamente, para determinar se usando um AP, , é necessário explorar a árvore das computações de com entrada . Especificamente:

O problema de determinar se pode ser resolvido por pesquisa na árvore das computações do AP .

Além disso, como os AP e as GIG são equivalentes, esta observação também sugere que

As derivações de uma GIC podem ser representadas por um grafo orientado.

Mais abaixo vai ser definida rigorosamente a representação das derivações da GIC por um grafo e como é que o problema pode ser resolvido por pesquisa quer no grafo (das derivações) da GIC quer no grafo (das computações) do AP.


Entretanto, interessa fazer uma breve revisão sobre pesquisa em grafos orientados. O problema pode ser definido como:

Pesquisa em Grafos Orientados. Dado um grafo orientado, descobrir se existe algum caminho desde um vértice inicial, , até um vértice final, .

A resolução geral deste problema segue o seguinte código:

def pesquisa(grafo, a, b):
  candidatos = [ a ]
  visitados = []
  while len(candidatos) > 0:
    candidato = candidatos.pop(0)
    visitados.append(candidato)
    if candidato == b:
      return True
    else:
      proximos = expande(grafo, candidato)
      proximos_novos = remove(proximos, visitados)
      candidatos = junta(candidatos, proximos_novos)
  return False

N.B. Este código é muito geral e, portanto, não otimizado. Melhorias significativas podem incluir, por exemplo, um resuldado mais descritivo, com o caminho de a até b.

Há quatro variantes da resolução geral deste problema, que correspondem às combinações da seguintes opções para expande e para junta:

  • Se expande(G, v) segue a direção das arestas — devolve os filhos de v em G — a pesquisa é descendente, com a = inicial e b = final.
  • Se expande(G, v) segue contra a direção das arestas — devolve os pais de v em G — a pesquisa é ascendente, com a = final e b = inicial.
  • Se junta(x, y) devolve x + y (x seguido de y) — a pesquisa é em largura.
  • Se junta(x, y) devolve y + x (y seguido de x) — a pesquisa é em profundidade.

Resumidamente:

abexpandejunta(x, y)Pesquisa
filhosy + xDescendente Profundidade
filhosx + yDescendente Largura
paisy + xAscendente Profundidade
paisx + yAscendente Largura

A função remove exclui dos candidatos os vértices já visitados e não depende do tipo de pesquisa.

Grafo de uma Gramática

Todas as possíveis derivações de uma gramática podem ser organizadas num grafo orientado, que começa no símbolo inicial e "percorre" sucessivamente as produções aplicadas durante as derivações. Neste grafo "caminhos" diferentes representam derivações diferentes. Os vértices "são" as palavras intermédias e as arestas as produções aplicadas:

Grafo Esquerdo (resp. Direito) de uma GIC. Seja uma GIC. O grafo esquerdo de (resp. direito) é o digrafo com:

  • Vértices: as palavras do conjunto (resp. ).
  • Arestas: os elementos de (resp. ).

Por exemplo, para a GIC parte do grafo esquerdo é

Grafo Esquerdo de (parcial)
Grafo Esquerdo Exemplo 1

O grafo (esquerdo/direito) de uma GIC representa todas as possíveis derivações (esquerdas/direitas) dessa GIC. Este grafo não tem de ser uma árvore porque no grafo de uma gramática ambígua há vários "caminhos" para o mesmo vértice.

Exemplo/Exercício: Desenhe o grafo de .

As árvores e as gramáticas não ambíguas estão relacionadas:

O grafo esquerdo (resp. direito) de uma GIC não ambígua é uma árvore. Recíprocamente, se o grafo esquerdo (resp. direito) de uma GIC for uma árvore, então a GIC é não ambígua.

O grafo da GIC não deve ser confundido com as árvores de derivação, que ilustram uma possível derivação de uma palavra.

Qualquer palavra de terminais gerada pela GIC é um vértice sem filhos. Isto é, se, e só se, é um vértice sem filhos no grafo de .

Isto é a reformulação do Problema Principal de ALP como um problema de pesquisa em grafos: Dada uma GIC e uma palavra , existe algum caminho no grafo (esquerdo) de ? Nesse caso ; caso contrário .

Exemplos com Expressões Algébricas Simplificadas

Para ilustrar melhor os grafos esquerdos e direitos, assim como os algoritmos de pesquisa, considere-se a seguinte gramática, para expressões algébricas simplificadas (EAS):

Os inícios dos grafos (esquerdo e direito) são

Grafo Esquerdo de EASGrafo Direito de EAS
Grafo Esquerdo EASGrafo Direito EAS

Portanto, para já, a análise sintática pode ser feita em oito tipos de pesquisa:

DireçãoEstratégiaGrafo
DescendenteLarguraGrafo da GIC
DescendenteLarguraÁrvore das Computações do AP
DescendenteProfundidadeGrafo da GIC
DescendenteProfundidadeÁrvore das Computações do AP
AscendenteLarguraGrafo da GIC
AscendenteLarguraÁrvore das Computações do AP
AscendenteProfundidadeGrafo da GIC
AscendenteProfundidadeÁrvore das Computações do AP

Análise Sintática Descendente em Largura no Grafo da GIC

Intuitivamente, mantém-se uma lista de candidatos, iniciada com e aplicam-se sucessivamente produções, sempre ao primeiro elemento dessa lista, o "candidato". Há três hipóteses:

  1. O candidato é o alvo ou não há candidatos. A pesquisa termina.
  2. O candidato é incompatível com o alvo. Passa-se ao próximo candidato.
  3. O candidato é compatível com o alvo, mas diferente. Os filhos do candidato atual são acrescentados ao fim da lista.

Compatível significa que o prefixo terminal do candidato é um prefixo do alvo.

Por exemplo, nas EAS, a pesquisa DL de é:

Análise Sintática Descendente em Profundidade no Grafo da GIC

Intuitivamente, mantém-se uma lista de candidatos, iniciada com e aplicam-se sucessivamente produções, sempre ao primeiro elemento dessa lista, o "candidato". Há três hipóteses:

  1. O candidato é o alvo ou não há candidatos. A pesquisa termina.
  2. O candidato é incompatível com o alvo. Passa-se ao próximo candidato.
  3. O candidato é compatível com o alvo, mas diferente. Os filhos do candidato atual são acrescentados ao início da lista.

Por exemplo, nas EAS, a pesquisa DP de é:

Análise Sintática Ascendente e as Computações do AP

As pesquisas anteriores percorrem o grafo da gramática, gerado pelas suas produções. Por outro lado, os autómatos de pilha, sendo equivalentes às GIC, também podem ser usados para a análise sintática.

No caso dos AP o não determinismo ocorre sempre que uma configuração tem dois ou mais sucessores. Por outro lado a própria palavra proporciona informação que pode ser usada para guiar a pesquisa.

As computações nos AP "consomem" a palavra na entrada e este processo é semelhante às pesquisas ascendentes, que começam no "alvo" e "andam para trás" até chegarem a um vértice "inicial".

O processo de pesquisa nas computações é essencialmente descrito pelas operações de transferência e de redução de um certo AP derivado da GIC.

N.B. que este AP não foi ainda formalmente definido.

Intuitivamente, a palavra da entrada é passada para a pilha, transferindo um símbolo de cada vez. Também a palavra que está na pilha pode ser reduzida, isto é, "desfeito" o resultado de aplicar uma produção. No fim, a entrada deve ficar vazia e a pilha só com o símbolo inicial.

Redução é o inverso da aplicação de uma produção. Por exemplo, se for uma produção então uma possível redução da palavra será porque .

Por exemplo, escolhendo convenientemente as operações "transferência", , da entrada para a pilha e "redução", , duma subpalavra na pilha, uma computação possível de é

Um resultado interessante deste método é que as reduções aplicadas mostram uma derivação direita da palavra, lida "de baixo para cima" na coluna "Produção":

Este esquema não só determina se a palavra é gerada pela gramática como, nesse caso, encontra uma derivação da palavra.

No entanto, tem algumas fontes de não determinismo:

  • Quando fazer uma redução ou uma transferência?
  • Numa redução podem ser escolhidos várias subpalavras da pilha e várias produções da gramática.

Por exemplo, dada a GIC como reduzir na pilha? Pode escolher-se:

SubpalavraProduçãoNova Pilha

Análise Sintática Ascendente em Largura

Intuitivamente, mantém-se uma lista de candidatos, iniciada com e aplicam-se todas as reduções possíveis, sempre ao primeiro elemento dessa lista, o "candidato". Há duas hipóteses:

  1. O candidato é a produção inicial ou não há candidatos. A pesquisa termina.
  2. O candidato admite reduções. Os pais desse candidato são acrescentados ao fim da lista.

Por exemplo, nas EAS, a pesquisa AL de é:

Análise Sintática Ascendente em Profundidade

Intuitivamente, mantém-se uma lista de candidatos, iniciada com e aplicam-se todas as reduções possíveis, sempre ao primeiro elemento dessa lista, o "candidato". Há duas hipóteses:

  1. O candidato é a produção inicial ou não há candidatos. A pesquisa termina.
  2. O candidato admite reduções. Os pais do candidato atual são acrescentados ao início da lista.

Por exemplo, nas EAS, a pesquisa AP de é:

Conclusão

Depois de resolvidas as questões da adequação e da computação, está-se a tratar da eficiência no Problema Principal de ALP/Análise Sintática.

A análise sintática é representada como um problema de pesquisa em grafos orientados que, em geral, pode ser resolvido por quatro estratégias diferentes: (ascendente ou descendente) x (largura ou profundidade). Por outro lado a pesquisa tanto pode ser feita no grafo da gramática como na árvore das computações do autómato de pilha.

Nenhuma destas estratégias gerais é eficiente. Para melhorar este problema e guiar as pesquisas na análise sintática colocam-se duas possibilidades: ou se condiciona a gramática, de forma reduzir as produções aplicáveis em cada passo ou, então, consultam-se os símbolos por processar para guiar as transições dos autómatos de pilha.

Formas Normais

Gramáticas Adaptadas para Análise Sintática por Pesquisa Geral.

Introdução

A análise sintática é representada como um problema de pesquisa em grafos orientados que, em geral, pode ser resolvido por quatro estratégias diferentes: (ascendente ou descendente) x (largura ou profundidade). Nenhuma destas estratégias gerais é eficiente.

Nesta secção é apresentado um processo (a normalização de uma gramática) que, numa sequência de passos, transforma numa gramática noutra, equivalente, e adaptada (tanto quanto possível) aos algoritmos de pesquisa: uma forma normal.

Conteúdo

O bom funcionamento (mínimo número de passos) da pesquisa no grafo de uma GIC depende da própria gramática.

Problemas como:

  • Pesquisas infinitas quando a palavra não é derivada pela gramática.
  • Exploração repetida de ramos quando a gramática é ambígua.

reduzem significativamente o desempenho da pesquisa.

Em certos caso é possível transformar a gramática dada noutra equivalente mas que "favorece" a pesquisa, reduzindo o número de ramificações, desambiguando, e/ou detetando "cedo" se a palavra não é gerada pela gramática.

Esta secção descreve um processo algorítmico de transformação de gramáticas. No fim a gramática que se obtém proporciona pesquisas gerais mais eficientes.

Todo este processo vai ser ilustrado com um exemplo de uma GIC (especialmente desenhada) para ilustrar a aplicação de cada passo:

1. Símbolo Inicial Não Recursivo

A recursividade é a "vantagem" das GIC sobre as ER, mas é também, uma fonte de dificuldades. Embora não seja desejável, nem sequer possível, remover completamente a recursividade das produções de uma GIC esta pode ser, em certos casos, controlada.

Símbolo Inicial Não Recursivo. Seja uma GIC. Existe uma GIC equivalente a e onde o símbolo inicial não é recursivo.

Porque:

  • Se o símbolo inicial de não for recursivo então .
  • Se o símbolo inicial de for recursivo então, fazendo uma variável nova:

Exemplo. Em o símbolo inicial é recursivo porque é uma produção de . Portanto esta gramática é transformada em

Em o símbolo inicial já não é recursivo. Além disso, .

2. Eliminação de Produções Vazias

Antes de tratar do segundo passo na normalização de uma gramática é necessário definir alguns conceitos e técnicas.


Quase todas as produções "aumentam" o tamanho da palavra. Por exemplo faz com que passe para , isto é de comprimento três para quatro. E esta é uma propriedade desejável pois permite cortar "filhos demasiado grandes" durante a pesquisa.

Há duas exceções de nota: as produções vazias e as produções unitárias . Formalmente:

Produções Vazias. Produções Unitárias. Gramática Contraível. Seja uma GIC.

  • Uma produção vazia tem a forma .
  • Uma produção unitária tem a forma .
  • O conjunto dos geradores da palavra vazia é
  • Numa gramática não contraível não existem geradores da palavra vazia. Isto é .
  • Numa gramática essencialmente não contraível o único gerador de vazio é o símbolo inicial. Isto é .

O interesse das gramáticas essencialmente não contraíveis é que:

Numa gramática essencialmente não contraível os passos intermédios de uma derivação só podem diminuir de tamanho por aplicação de .

Não é possível, nem desejável, descartar completamente os geradores de vazio. Por exemplo, se então em qualquer gramática equivalente a tem de existir pelo menos uma produção vazia. Neste caso, o melhor que se pode fazer é "concentrar" todas as produções vazias em .


A transformação de uma gramática noutra equivalente envolve a introdução de novas produções e a substituição de uma produção por outras, de forma a manter a linguagem gerada.

Introdução de Produções. Substituição de Produções. Seja uma CIG.

  • Se então é equivalente a .
  • Se e são todas as produções de então a gramática em que é equivalente a .

Intuitivamente, estas duas regras permitem "saltar" passos intermédios numa derivação.


O primeiro passo para retirar as produções que reduzem o comprimento das palavras trata das produções vazias.

Eliminação de Produções Vazias. Sejam uma GIC em que o símbolo inicial não é recursivo. e em que as produções são, em conjunto:

  • As produções de que não são produções da palavra vazia.
  • A produção se .
  • Todas as produções que se obtêm eliminando um ou mais símbolos de do corpo de cada produção , desde que o resultado, , tenha pelo menos um símbolo.

Então é equivalente a e essencialmente não contraível.

Exemplo. Na gramática o símbolo inicial não é recursivo. Além disso, os seus geradores da palavra vazia são

A gramática , que resulta de por eliminação das produções vazias é:

Note-se que:

  1. Foram retiradas as produções e .
  2. Como , foi acrescentada .
  3. De cada produção em cujo corpo ocorrem geradores da palavra vazia foram acrescentadas variantes sem esses símbolos. Por exemplo:
    1. Em no corpo, , ocorre . Portanto é acrescentada a produção , que resulta de removendo .
    2. Mais interessante, no corpo da produção tanto como são geradores da palavra vazia. As combinações possíveis sem algum desses elementos são .

Sem os cálculos auxiliares:

3. Eliminação de Produções Unitárias

As produções unitárias substituem uma variável por outra variável e podem ser eliminadas usando cadeias.

Cadeia. Seja uma GIC essencialmente não contraível.

Para cada , a cadeia de é o conjunto .

Qualquer gramática cujas produções são tais que:

  1. .
  2. Existe tal que .

é equivalente a .

Este enunciado pode ser difícil de interpretar. O primeiro ponto afirma que na gramática não existem produções unitárias. O segundo ponto permite substituir a produção unitária por para cada .

Exemplo. As cadeias de são

e as produções unitária são e . As respetivas substituições são:

  • de , dado que : .
  • de , dado que : .

A gramática que se obtém, equivalente a , é:

4. Eliminação de Símbolos Inúteis

A definição de linguagem gerada pela GIC é

Uma inspeção rápida a mostra que a recursividade desta variável impede-a de gerar palavras só de terminais. Portanto, em termos de linguagem gerada, este é um símbolo que pode ser retirado da gramática. Também podem ser retirados os símbolos que não podem ser atingidos a partir do símbolo inicial.

Símbolo Útil. Símbolo Acessível. Gramática Limpa. Seja uma GIC.

Um símbolo é:

  • Útil se existe uma derivação .
  • Inútil se não é útil.
  • Acessível se existe uma derivação .
  • Inacessível se não é acessível.

Uma variável é:

  • Produtiva se .
  • Improdutiva se não é produtiva.

Uma variável é útil se e só se for acessível e produtiva.

Uma gramática sem símbolos inúteis e inacessíveis diz-se limpa (ou reduzida).

Para limpar uma gramática de símbolos inúteis e inacessíveis:

  1. Eliminar as variáveis improdutivas:
    1. Encontrar as variáveis produtivas (por exemplo, derivando delas uma palavra só de terminais).
    2. Remover as produções onde ocorrem as variáveis improdutivas.
  2. Eliminar as variáveis inacessíveis:
    1. Encontrar os símbolos acessíveis (por exemplo, fazendo uma derivação a partir do símbolo inicial onde o símbolo ocorra).
    2. Remover as produções das variáveis inacessíveis.

Exemplo. Como foi observado acima, é inútil. Portanto as produções onde ocorre podem ser removidas. As novas produções são:

Como resultado destas remoções deixou de ser acessível: Nenhuma derivação "contém" . Portanto, também as produções de podem ser removidas e o resultado é:

Note-se que, removendo as produções de , o terminal ficou inacessível, pelo que foi retirado de , tal como , que nunca constou nas produções.

Finalmente, é fácil de verificar que e são produtivos e acessíveis. Também e são acessíveis.

Numa gramática limpa todos os símbolos "contam". Além disso, e de se ter tratado das produções vazias e unitárias, pouco se fez para melhorar o processo de pesquisa no grafo da gramática. Para esse efeito é preciso "controlar a forma" das produções.

5. Forma Normal de Chomsky

O corpo das produções de uma CIG é uma palavra de , pelo que pode ter vários terminais e variáveis misturados. Aqui pretende-se "arrumar" as formas possíveis que as produções podem ter.

Forma Normal de Chomsky (FNC). Uma GIC está na forma normal de Chomsky se cada uma das suas produções tem uma das formas seguintes:

  1. com .
  2. com .
  3. .

A forma normal de Chomsky é bastante fácil de obter, substituindo terminais "inconvenientes" por variáveis e usando novas variáveis para "agrupar" cadeias três ou mais símbolos.

Exemplo. Na gramática

acrescentam-se e para retirar estes terminais das outras produções:

Para se obter a FNC ainda falta tratar das produções e . Para tal acrescenta-se a produção e substitui-se . O resultado final é:

6. Forma Normal de Greibach

Uma forma de reduzir o número de ramificações durante a pesquisa consiste em "olhar para o próximo símbolo" da palavra e escolher apenas produções que colocam esse símbolo no início.

Por exemplo, dadas a GIC e a palavra , é simples de ver que a única derivação possível é porque em cada passo há só um candidato possível.

Neste caso, em cada passo da pesquisa é muito simples descartar todos os candidatos que não começam pelo terminal correto. Esta observação motiva a seguinte definição:

Forma Normal de Greibach (FNG). Uma GIC está na forma normal de Greibach se cada uma das suas produções tem uma das formas seguintes:

  1. com .
  2. com .
  3. .

Note-se que, em relação à forma normal de Chomsky, a única diferença na primeira forma das produções: em vez de .

As gramáticas na FNG são úteis para:

  • evitar recursões infinitas nos algoritmos de pesquisa.
  • guiar (com o primeiro símbolo) a escolha das regras a expandir.
  • produzir AP equivalente à gramática dada.

Construção de uma GIC na FNG

Ao contrário da construção da FNC, que é simples de obter, a construção de uma GIC na FNG requer alguma orientação.

Construção da FNG. Dada uma GIC na FNC:

  1. Ordenar as variáveis. Define-se uma ordem total nas variáveis de com uma única condição: é o primeiro elemento.
  2. Passo Descendente. Segue-se essa ordem para transformar todas as produções de modo que, se então .
  3. Passo Ascendente. Segue-se essa ordem invertida para substituir cada produção por para cada produção .

Exemplo. Continuando com , que está na FNC:

Ordenar as variáveis. A única condição é " é o primeiro elemento". Por exemplo

Passo Descendente. Ordenar as produções seguindo essa ordem.

As produções de e de não verificam a condição do passo descendente. No caso de esse problema resolve-se facilmente substituindo o no início da produções de por (porque ).

Resta o problema com a produção . Segue-se também o método anterior:

Só que desta vez o problema não ficou resolvido e resultou numa Recursão Direta à Esquerda da variável .


Eliminação da Recursividade Direta à Esquerda. Se

são as produções de , organizadas de forma que:

  • Cada começa por e
  • Nenhuma começa por .

Então obtém-se uma gramática equivalente:

  1. Acrescentando uma nova variável, por exemplo .
  2. Substituindo as produções de por

Uma mnemónica para este processo é a seguinte:

Substituir por e .

Intuitivamente percebe-se porque esta substituição é válida observando que a linguagem gerada por é:

Agora, outra forma de descrever esta linguagem é "Um seguido de zero ou mais ." Neste caso:

  • gera um ou mais .
  • gera um seguido de zero ou um .

A eliminação da RDE de

define as produções

pelo que a ordem inicialmente definida para as variáveis tem de ser estendida de forma que . Por exemplo:

A nova gramática equivalente fica:

No fim do passo descendente cada produção ou é vazia ou começa por um terminal ou começa por uma variável "mais abaixo".

Passo Ascendente. Substituir, "de baixo para cima" a primeira variável de cada produção:

Sem anotações, a GIC final, está na Forma Normal de Greibach e é equivalente à GIC inicial

Embora tenha muito mais produções do que e ainda por cima aparentemente redundantes (mas não o são) o facto de estar na FNG torna-a mais adequada e eficiente do que em termos de pesquisa. Por exemplo:

  • A derivação de uma palavra com símbolos tem, no máximo, passos porque cada produção "produz" um terminal.
  • O primeiro símbolo "filtra" as possíveis produções aplicáveis.
  • A pesquisa de uma palavra não gerada pela GIC, , "falha cedo", no máximo em passos.

Ver o exemplo no código deste capítulo.

Processo de Normalização de uma Gramática

Resumindo todos os passos, a normalização de uma GIC consiste em:

  1. Eliminar a recursividade do símbolo inicial.
  2. Eliminar as produções vazias exceto, se necessário, do símbolo inicial.
  3. Eliminar as produções unitárias.
  4. Eliminar os símbolos inúteis.
  5. Transformar na Forma Normal de Chomsky.
  6. Transformar na Forma Normal de Greibach.

Conclusão

O problema da Análise Sintática, que se está a tentar resolver, é uma reformulação do Problema Principal de ALP para as GIC e pergunta "como determinar se " quando é uma palavra/programa e é uma linguagem gerada por uma gramática independente de contexto.

Inicialmente tentou-se formalizar as linguagens usando expressões regulares mas o Pumping Lemma mostrou a necessidade de uma abordagem mais geral — as gramáticas independentes de contexto.

Embora as GIC resolvam a adequação (com as expressões algébricas) e os autómatos de pilha proporcionem um modelo computacional, este não é eficiente.

A Normalização de uma GIC é um processo que começa com uma GIC e que, ao longo de vários passos, produz outras GIC equivalentes, de forma a obter-se uma gramática "adequada" aos algoritmos de pesquisa geral. A Forma Normal de Greibach impõe restrições fortes às produções, que podem ser bem aproveitadas para reduzir a complexidade/ramificação da pesquisa.

Mesmo com a FNG a ajudar na pesquisa, a resposta a "" ainda permite ramificações ao pesquisar a árvore das derivações. Portanto o problema do não determinismo persiste e, com ele, a eficiência fica por resolver.

Os algoritmos deterministas são o próximo assunto e assentam, tanto quanto possível, nas propriedades das gramáticas e das derivações.

Gramáticas LL(k)

Análise Sintática Descendente Determinista.

Introdução

A Análise Sintática por pesquisa geral não é eficiente, mesmo após a transformação para a FNG porque continua a ser possível encontrarem-se várias produções para expandir um vértice.

Na situação acima o não determinismo resulta as possíveis múltiplas expansões quando se consideram as variáveis em isolamento. Por exemplo, dada a GIC abaixo, o vértice tem dois filhos possíveis: e .

Mas uma observação mais cuidadosa da pesquisa, considerando o primeiro símbolo do sufixo que falta derivar mostra uma situação interessante:

Pesquisa Descendente de com Avanço
Exemplo de Pesquisa Descendente com Avanço
Em cada vértice podam-se os ramos "incompatíveis".

Neste exemplo, olhando para o próximo terminal durante a pesquisa por obtém-se uma pesquisa determinista.

Nesta secção exploram-se pesquisas deterministas com o auxílio dos "símbolos seguintes".

Conteúdo

A apresentação intuitiva acima precisa de uma representação mais formal. Por exemplo, a derivação de pode ser obtida pela seguinte tabela:

Em cada linha:

  • Há uma variável ativa, que inicialmente é .
  • É escolhida a única produção cujo primeiro símbolo coincide com o símbolo de avanço.
  • O avanço é "transferido" para o prefixo processado e a variável ativa é a primeira que ocorre na produção escolhida na linha anterior.

Interessa formalizar esta exploração com vista a definir métodos rigorosos para:

  1. Determinar se uma GIC é adequada, ou não, a este processo.
  2. Definir algoritmos eficientes baseados na pesquisa com avanço.

Começando pela definição de gramática "adequada" à pesquisa com avanço:

Gramática LL(1). A GIC com terminador é LL(1) se dadas duas derivações esquerdas em que e então .

N.B. "LL" significa "Left-to-right Leftmost derivation". Em português: "derivação esquerda da esquerda-para-a-direita". Note-se que "derivação esquerda" especifica qual é a variável a tratar enquanto que "da esquerda-para-a-direita" indica que a palavra é processada sequencialmente do primeiro símbolo para o último.

N.B. O terminador ocorre exatamente uma vez nas palavras geradas e é sempre o último símbolo. A sua função é garantir que há sempre um símbolo de avanço na palavra analisada. Fica como exercício encontrar um algoritmo que transforma uma GIC qualquer, , noutra, com terminador , de forma que .

Intuitivamente a definição de GIC LL(1) diz que não há duas produções distintas de que produzem sufixos terminais que começam pelo mesmo terminal. Ou seja, os resultados finais da aplicação de duas produções de distintas difere logo no primeiro símbolo.

As gramáticas LL(1) têm algumas propriedades interessantes:

Propriedades das Gramáticas LL(1). Seja uma GIC:

  1. Se é LL(1) então não é ambígua,
  2. Se alguma variável de for recursiva à esquerda então não é LL(1).

A generalização de LL(1) para mais do que um símbolo de avanço é representada por . Este caso é pouco interessante em termos teóricos porque torna a notação mais críptica sem progredir na resolução da análise sintática.


Note-se que uma gramática na FNG quase que é LL(1). O problema está na possibilidade de várias produções começarem pelo mesmo terminal. Para ajudar a ultrapassar esta situação é preciso "arrumar" as produções que começam pelo mesmo símbolo.

Fatorização à Esquerda. Seja uma GIC. Supondo que as produções de são

em que então a GIC obtida de

  1. Acrescentando uma nova variável, .
  2. Substituindo as produções de por .
  3. Acrescentado as produções .

é equivalente a .

Com a fatorização as várias produções de que começam pelo mesmo prefixo, ficam agrupadas numa só produção, e a nova variável, , gera os restantes sufixos.

Por exemplo, recuperando a gramática que ilustrou da construção da FNG:

A fatorização pode ser aplicada repetidas vezes até que o resultado seja adequado, por exemplo uma GIC LL(1).


Para determinar se uma GIC é LL(1) a partir da definição pode ser confuso. Para ajudar neste problema mas também para definir um algoritmo determinista de análise sintática para gramáticas LL(1) usam-se os primeiros, seguintes e os diretores.

Primeiros. Seguintes. Seja uma GIC.

Os primeiros de são os terminais que ocorrem na primeira posição das palavras derivadas de :

Os seguintes de são os terminais que ocorrem imediatamente a seguir a nalguma derivação de :

Por exemplo, para a GIC

O conjunto dos ...... é ...
primeiros de
primeiros de
seguintes de

A partir da definição não é simples calcular os conjuntos dos primeiros e dos seguintes. Para esse cálculo há dois algoritmos gráficos:

Grafo dos Primeiros. Seja uma GIC. O grafo dos primeiros é um grafo em que os vértices são os símbolos de e para cada produção :

  1. Acrescenta-se a aresta .
  2. Se , acrescenta-se a aresta .
  3. Assim sucessivamente até se esgotarem os ou .

O grafo dos primeiros tem um caminho se e só se .

Continuando com a GIC anterior, obtém-se

Exemplo de Grafo dos Primeiros
Exemplo de Grafo dos Primeiros
N.B. Os "cantos" das arestas são arredondados.

e, portanto, os primeiros de cada variável são:

ou simplificando a notação:

Este método mostra apenas os primeiros das variáveis. Para as restantes palavras:

Em geral, calculam-se recursivamente os :

  • .
  • Para .
  • Para usa-se o grafo dos primeiros.
  • Para :

Depois dos primeiros (das variáveis) podem calcular-se os seguintes.

Grafo dos Seguintes. Seja uma GIC. O grafo dos seguintes é um grafo em que os vértices são os símbolos de e para cada produção com :

  1. Acrescenta-se uma aresta para cada .
  2. Se , acrescenta-se a aresta .

O grafo dos seguintes tem um caminho se e só se .

Continuando com o mesmo exemplo:

Exemplo de Grafo dos Seguintes
Exemplo de Grafo dos Seguintes

donde resulta

O próximo passo consiste em determinar os primeiros símbolos que cada produção gera.

Diretores. Seja uma GIC e . O conjunto dos diretores de é:

Depois de calculados os primeiros e os seguintes, os diretores são facilmente encontrados:

Os diretores permitem facilmente verificar se uma GIC é LL(1):

Teorema dos Diretores. Seja uma GIC. Se, para qualquer variável quaisquer duas produções de tiverem os respetivos diretores distintos, isto é, se para quaisquer duas produções de , então é LL(1)

Exemplos de Aplicação do Teorema dos Diretores


A GIC definida por não é LL(1):

e Como conclui-se que esta gramática não é LL(1).


Um caso mais interessante é a seguinte variante das expressões algébricas, que ilustra a aplicação de algumas transformações:

Para verificar se esta última gramática é LL(1), passo a passo:

Geradores de Vazio

Primeiros

Grafo dos Primeiros
Grafo dos Primeiros

Seguindo as arestas:

Seguintes

Grafo dos Seguintes
Grafo dos Seguintes

Seguindo as arestas:

Diretores

Analisador Sintático

Com os diretores de cada produção calculados, se a gramática for LL(1), é simples implementar manualmente um Analisador Sintático para essa gramática:

def S():
    if seguinte in "(a":
        E()
        consome("#")
    else:
        erro()

def E():
    if seguinte in "(a":
        T()
        X()
    else:
        erro()

def Z():
    if seguinte in "+":
        consome("+")
        T()
        X()
    else:
        erro()

def X():
    if seguinte in "+":
        Z()
    elif seguinte in "#)":
        return
    else:
        erro()

def T():
    if seguinte in "(":
        consome("(")
        E()
        consome("(")
    elif seguinte in "a":
        consome("a")
    else:
        return erro()

def consome(terminal):
    if terminal == seguinte:
        # AVANÇA
        seguinte = ...
    else:
        erro()

def erro():
    # Para o processamento
    ...

Um exemplo deste programa a correr, para analisar a palavra a+a#, é:

"pilha"seguinteresto
S()a+a#
E(); consome(#)a+a#
T(); X(); consome(#)a+a#
consome(a); X(); consome(#)a+a#
X(); consome(#)+a#
Z(); consome(#)+a#
consome(+); T(); X(); consome(#)+a#
T(); X(); consome(#)a#
consome(a); X(); consome(#)a#
X(); consome(#)#(vazio)
consome(#)#(vazio)
(vazio)(nenhum)(vazio)

O resultado deste analisador sintático é "verdade" ou "falso" conforme a palavra dada é, ou não, gerada pela gramática. Este é o resultado esperado mas insatisfatório pois nada diz sobre a derivação, isto é a estrutura, da palavra.

Por exemplo, dada a palavra a+a# é desejável saber, além de que , que a sua derivação esquerda é na gramática inicial.

Conclusão

Este último exemplo mostra que a Análise Sintática está quase resolvida:

As GIC LL(1) são adequadas para representar as linguagens de programação. Além disso, é possível definir algoritmos eficientes para determinar computacionalmente se uma palavra é, ou não, gerada por essa gramática.

No entanto... ainda há por onde melhorar esta situação:

  1. A transformação de uma GIC noutra que seja LL(1) é um passo Ad hoc, que depende de muitas escolhas específicas.
  2. Nessa transformação perde-se a ligação à gramática inicial. Em concreto, olhando para a computação de a+a# não se percebe como a palavra é gerada pelas produções da gramática inicial.
  3. Este processo implica a implementação "manual" das "produções" (human in the middle) mas seria muito melhor que fosse totalmente automático. Isto é, pretende-se definir um programa "geral" Super que aceita como entrada uma gramática G e devolve um certo programa P que, por sua vez, aceita como entrada uma palavra p e calcula se esta é, ou não, gerada por G:
    1. P = Super(G).
    2. P(p) é equivalente a "p é gerada por G".

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.

Gramáticas LR(0)

Tal como antes para as gramáticas LL, o interesse aqui está nas gramáticas LR(1) porém o caso LR(0) é importante como introdução para o processo de construção do analisador sintático.

Contextos LR(0)

Problema. Quando é que uma produção pode ser aplicada numa derivação "válida"?

Isto é, será possível determinar quando a aplicação de uma produção numa derivação contribui para uma palavra gerada pela gramática das outras aplicações, em que o resultado não é gerado pela gramática?

No caso das derivações direitas

Contexto-LR(0). Prefixo Viável. Seja uma GIC com terminador e em que não é recursivo.

  • A palavra é um Contexto-LR(0) da produção se existir uma derivação direita

    • Isto é, há uma redução que começa por .
  • Um prefixo viável é um prefixo de um contexto-LR(0).

  • Dada uma produção, o conjunto dos seus contextos-LR(0) é uma linguagem regular.

N.B. Na definição acima é importante ter presente que se tratam de derivações direitas. Portanto, quando é aplicada em :

  • O sufixo é formado só por terminais.
  • O prefixo é o "contexto" para a aplicação da regra .

Intuitivamente pretende-se que os Contextos-LR(0) tenham informação suficiente para determinar que produção aplicar em cada passo de uma derivação. Isto é, se os Contextos-LR(0) forem disjuntos tem-se um método determinista para fazer derivações direitas.


Por exemplo, dada a GIC

As derivações direitas têm uma das seguintes formas

pelo que os Contextos-LR(0) das produções são:

Neste caso, é um contexto-LR(0) tanto de como de (com em ambos os casos).

O que é que isto significa? Quando se procura descobrir como poderá ter sido derivada à esquerda, há duas possibilidades:

  • Ou .
  • Ou .

Isto é, em não "há informação suficiente" para saber qual foi a última produção aplicada, ou .


Considerando agora a GIC

os contextos-LR(0) são:

Os contextos-LR(0) podem ser descobertos explorando a árvore das derivações direitas:

Árvore das Derivações Direitas
Árvore das Derivações Direitas
Os contextos-LR(0) estão sublinhados.

Agora, para encontrar uma derivação de :

  1. O maior prefixo de que é um contexto-LR(0) é , de .
  2. Portanto, a produção aplicada foi , à palavra .
  3. O maior prefixo de que é um contexto-LR(0) é , de .
  4. Portanto, foi aplicada a .
  5. O maior prefixo de que é um contexto-LR(0) é , de .
  6. Portanto, foi aplicada a .
  7. O maior prefixo de que é um contexto-LR(0) é , de .
  8. Portanto, foi aplicada a .
  9. O maior prefixo de que é um contexto-LR(0) é , de .
  10. Portanto, foi aplicada a .
  11. O maior prefixo de que é um contexto-LR(0) é , de .
  12. Portanto, foi aplicada e a derivação está encontrada:

Note-se que:

  1. Foi encontrada uma derivação direita (rightmost derivation).
  2. A "pilha" é lida da esquerda-para-a-direita (left-to-right).
  3. O processo encontra a derivação em reverso (in reverse).

A derivação anterior pode ser organizada numa tabela com quatro tipos de ações:

  • Reduzir quando a pilha tem um Contexto-LR(0) de .
  • Transferir o primeiro símbolo da palavra para a pilha, quando a pilha tem um prefixo viável que não é um Contexto-LR(0).
  • Aceitar quando a pilha é e a palavra .
  • Rejeitar quando a pilha não é um prefixo viável.

O resultado é:

A derivação de pode ser recuperada da coluna "ação", lida em reverso.

Para procurar uma derivação de , que não é gerada pela gramática:


Itens LR(0)

Os exemplos acima ilustram a utilidade dos contextos-LR(0) para a análise sintática. Embora não sejam facilmente encontrados a partir da definição, o conjunto dos Contextos-LR(0) de uma produção é uma linguagem regular que pode ser definida por um certo autómato finito determinista.

Para definir esse AFD é preciso começar pelos seus estados:

Item LR(0). Seja uma GIC.

  • Os itens LR(0) de são as "produções" que se obtêm de acrescentado um em todas as posições possíveis:
    • Se então é um item LR(0) de .
    • Se então é um item LR(0) de .
  • Um item completo é um item em que o está o mais à direita possível.
  • Um item é válido para o prefixo viável se é um contexto LR(0); Isto é, se é candidato a reduzir.

Usando a gramática do exemplo anterior, os seus itens LR(0) são com os itens completos assinalados assim: .

Fecho. Seja um conjunto de itens. O fecho de , denotado define-se recursivamente por:

  • base .
  • passo Se com então, para cada produção , também .

Por exemplo, usando a gramática anterior,

Autómato Finito dos Itens LR(0) Válidos

Os fechos dos itens são usado para construir um autómato finito que determina a ação nas tabelas acima.

Autómato dos Itens Válidos (AIV). Seja uma GIC. O autómato dos itens válidos, que reconhece os prefixos viáveis de é o AFD em que:

  • estado inicial .
  • transição Para cada e

Continuando com a gramática anterior, o seu autómato dos itens válidos tem os seguintes estados e transição:

Note-se que há mais um estado, , que não se representa e que recebe todas as transições que não estão especificadas.


Este AFD pode ser representado numa tabela mais convencional (todas as transições não assinaladas vão para ):

Porém, pode ser mais simples calcular graficamente os estados e a transição do autómato dos itens válidos.

Diagrama do Autómato dos Itens Válidos
Diagrama do Autómato dos Itens Válidos
Em cada estado os itens completos são assinalados com . O estado não está representado.

Neste diagrama cada estado tem dois ou três "andares". De cima para baixo:

  1. O "nome" do estado, um inteiro
  2. A "raiz" dos itens, que resultam da transição.
  3. Restantes itens, para se obter o fecho da "raiz".

Analisador Sintático LR(0)

O Autómato dos itens válidos serve para determinar a ação na derivação. Em cada passo o AIV processa a pilha e a ação é:

  • Aceitar se a pilha tem apenas .
  • Reduzir se terminar num estado com um item completo. Nesse caso a redução é da produção do item completo.
  • Transferir o próximo símbolo da palavra se terminar num estado sem itens completos.
  • Rejeitar se não puder processar a palavra (isto é, vai parar a ).

Recuperando o exemplo anterior, o processamento de é:

enquanto que para , que não é gerada pela gramática:

Tabela de Análise Sintática LR(0)

A tabela de análise sintática (TAS) estende a transição do AIV com as ações associadas aos respetivos estados. Tem uma linha para cada estado e uma coluna para cada símbolo de . Além disso tem também uma coluna, , que indica que ação corresponde a um prefixo que termine nesse estado.

Para a gramática que tem vindo a servir de exemplo, a TAS é:

Nesta tabela:

  • O estado , a que corresponde a ação "rejeitar", não é representado e portanto todos os estados mostrados na TAS são finais.
  • As transições não representadas levam ao estado .
  • Por convenção, o estado é o inicial.
  • Nos estados com itens completos do símbolo inicial da GIC (no exemplo acima, o estado ) a ação é "aceitar", , em vez de ser "reduzir", .

Dado que a coluna determina se no analisador sintático é feita uma transferência ou uma redução (e nesse caso, de que produção), se essa informação for ambígua não é possível fazer análise sintática determinista LR(0).

Portanto é necessário que cada estado defina exatamente uma ação.

Como as reduções são feitas em estados com itens completos (por exemplo, os estados acima) e as transferência são feitas em estados de que sai alguma "aresta com um terminal" (os estados acima), as ambiguidades (conflitos) possíveis são:

  • Conflito Redução/Redução LR(0): Se num estado estiverem dois itens completos então esse estado define duas reduções possíveis.
  • Conflito Redução/Transferência LR(0): Se num estado com um item completo sair uma aresta "com um terminal" então esse estado define uma redução e uma transferência.

Estas condições permitem caraterizar as gramáticas LR(0):

Teorema das Gramáticas LR(0). Uma GIC é LR(0) se e só se o seu AIV não tem conflitos redução/redução LR(0) nem redução/transferência LR(0).

Autómato de Pilha LR(0)

Pretende-se não só fazer análise sintática determinista mas também que esta seja livre de passos manuais (human in the middle). O AIV proporciona dois passos desse processo:

  • Determina se a GIC dada é LR(0).
  • Define a ação em cada passo do analisador sintático.

Falta definir formalmente o processamento do próprio analisador sintático, o que será feito com um autómato de pilha.

Autómato de Pilha Reconhecedor LR(0). Seja uma GIC LR(0) e o seu AIV. O Autómato de Pilha Reconhecedor (APR) de , que reconhece a linguagem gerada por , é em que a transição, , é definida pelos seguintes elementos:

  • iniciar: .
  • transferir: se com .
  • reduzir: Para cada estado com um item completo com e , quando no AIV existe a computação
  • aceitar: Para cada estado com um item completo do símbolo inicial da GIC, quando no AIV existe a computação

Intuitivamente a pilha do APR intercala estados do AIC com símbolos de de forma a descrever "fragmentos de computação do AIV". Por exemplo, a computação de enquanto que de é:

Estes exemplos ilustram como o topo da pilha determina a transição do APR: O primeiro símbolo identifica o estado do AIV e este define ou uma transferência ou uma redução (incluindo o caso particular da aceitação).

  • No caso de reduzir (ou aceitar) são considerados mais símbolos da pilha, de forma a "capturar" todo o lado direito da produção, que é substituído pela respetiva variável.
  • No caso da operação ser uma transferência o terminal da palavra é comparado com a parte correspondente na pilha e, se coincidirem, ambos são "consumidos".

Neste processo é mantido o registo dos estados do AIV percorridos pelas respetivas computações.

Alternativamente as transições do APR podem ser definidas pela seguinte tabela:


Por exemplo para a GIC anterior, com a TAS (calculada acima, repetida aqui)

as transições do APR são:

  • iniciar é a única transição .

  • transferir Estas transições são :

  • reduzir Estas transições são :

  • aceitar Estas transições são :

O diagrama do APR é:

Diagrama do APR
Diagrama do APR
As transições para transferir estão no ciclo superior, aceitar no direito e reduzir no inferior.

O APR replica os passos (informais) do analisador sintático. A computação de pelo APR é:

e pára porque atinge uma configuração sem transições definidas (o topo é e o símbolo da entrada é ). Por outro lado a computação de é: e termina numa configuração com um estado final e com a pilha e a entrada ambas vazias. Neste caso, lendo em reverso as produções obtém-se a derivação direita da palavra dada:

Este exemplo ilustra o tratamento "automático" da análise sintática das gramáticas LR(k).

  • Dada uma GIC, a construção do AIV e a respetiva TAS permite determinar se a GIC é, ou não LR(0).
  • Se o for, a TAS é usada para construir o APR que reconhece a linguagem gerada pela GIC.
  • Além disso, o processamento de uma palavra aceite pelo APR permite encontrar a derivação direita dessa palavra.
  • Em todo este processo, desde a construção do AIV e da TAS, do APR e a computação de palavras os algoritmos são eficientes (isto é, o número de passos é polinomial no tamanho do input.)

Resta saber se as gramáticas LR(0) são adequadas.

Considerando a seguinte gramática de expressões algébricas simplificadas:

Na construção do AIV desta GIC o estado inicial tem os seguintes itens:

Deste estado sai uma aresta que leva a um novo estado com os seguintes itens onde existe um conflito redução/transferência (a redução de com a transferência de ).

Este exemplo mostra que as gramáticas LR(0) são demasiado simples para definir expressões algébricas e portanto não são adequadas para definir as linguagens de programação.

A solução para este problema consiste em "adaptar" a ideia das gramática LL(1), considerando os símbolos de avanço, ao processo das gramáticas LR(0).

Conclusão

  • O que conseguimos resolver
  • O que falta resolver.

Gramáticas LR(1)

Gerador de Analisador Sintático a partir da GIC.

Embora as gramáticas LR(0) proporcionem um algoritmo completo e eficiente para a análise sintática, as linguagens abrangidas não incluem expressões algébricas, pelo que é necessário considerar um esquema mais adequado.

Aqui que entram as gramáticas LR(1), que usam informação sobre o "proximo terminal não processado" (o avanço) para guiar o processo da análise sintática.

Item LR(1)

Seguindo a estrutura da apresentação das gramáticas LR(0), define-se:

  1. Itens, Itens Válidos e Fecho de um conjunto de itens.
  2. Autómato dos itens válidos.
  3. Condições LR(1).
  4. Tabela de Análise Sintática.
  5. Autómato de Pilha Reconhecedor.

Item LR(1). Item LR(1) Válido. Seja uma GIC.

Um Item LR(1) de tem a forma onde:

  • núcleo é um item LR(0).
  • símbolos de avanço .

O item LR(1) é válido para se, para cada existe uma derivação com .

O fecho de um conjunto de itens afeta os símbolos de avanço.

O Fecho LR(1) de um conjunto de itens LR(1) define-se recursivamente:

  • base .
  • passo Se então, para cada produção também onde
  • fecho nada mais pertence a .

Por exemplo, dada a GIC tem-se

Autómato Finito dos Itens LR(1) Válidos

Tal como nas gramáticas LR(0), os itens LR(1) válidos são reconhecidos por um AFD.

Autómato dos Itens LR(1) Válidos (AIV). Seja uma GIC qualquer e

O autómato dos itens LR(1) válidos de é o AFD tal que:

  • estado inicial .
  • transição Para cada ,

Por exemplo, para a GIC dada acima:

Diagrama do Autómato dos Itens LR(1) Válidos
Diagrama do Autómato dos Itens Válidos
Em cada estado os itens completos são assinalados com . O estado não está representado.

O cálculo de passo-a-passo:

  1. Como ocorre , é necessário adicionar os itens iniciais de . O núcleo é .
  2. Para calcular o avanço deste item, note-se que inicialmente portanto, pela definição de , .
  3. Portanto, o item LR(1) a acrescentar em é .
  4. Agora, de é preciso acrescentar os itens iniciais de . Os núcleos são e . O cálculo dos avanços é idêntico para estes dois itens.
  5. Estes itens resultam de . Pela definição de , .
  6. Portanto, são acrescentados dois itens LR(1): e .
  7. Do item , pelas razões anteriores, é necessário acrescentar dois itens LR(1): e .
  8. Torna a acontecer mas os itens que resultam já constam no e nada mais é acrescentado.
  9. Finalmente o fecho tem vários itens com o mesmo núcleo e que diferem apenas no avanço. Neste caso esses itens "fundem-se" num único, unindo os avanços:
    1. e fundem-se em .
    2. e fundem-se em .

Tabela de Análise Sintática LR(1)

Tal como no caso das gramáticas LR(0), os estados do AIV LR(1) permitem determinar se o processo da análise sintática pode, ou não, ser aplicado.

Para que a análise sintática seja determinista é necessário que os estados sejam livres de conflitos (redução/redução e redução/transferência). No caso das gramáticas LR(0), sem informação sobre os avanços, cada estado do AIV pode determinar ou uma única redução ou uma transferência. Nos AIV das gramáticas LR(1) os itens têm avanços, que proporcionam decisões mais informadas em cada caso.

No AIV acima, visto como um AIV LR(0), o estado tem um conflito redução/transferência. Mas o avanço do item restringe a aplicação da redução apenas quando o avanço na entrada é . Portanto não há conflito com uma eventual transferência de .

Em cada estado, cada avanço identifica a ação (reduzir, transferir, aceitar, rejeitar) no processo da análise sintática.

Portanto, a tabela de análise sintática LR(1) tem uma ação possível para cada símbolo terminal. Especificamente:

Tabela de Análise Sintática LR(1). (TAS LR(1)) Dada uma GIG e o seu AIV LR(1), a tabela de análise sintática LR(1) tem:

  • Para cada estado do AIV LR(1), uma linha, exceto para o estado .
  • Para cada símbolo , uma coluna que descreve a transição do AIV.
  • Para cada símbolo , uma coluna que, cruzada com a linha do estado , determina a ação:
    • aceitar (ou ) se contém um item completo de e se .
    • transferir (ou ) se contém um item .
    • reduzir (ou ) se contém o item completo , e .
    • rejeitar (omitido).

Por exemplo, A TAS LR(1) do exemplo acima é:

Comparando esta tabela com as obtidas nas TAS LR(0), a coluna ação é mais específica, considerando agora os símbolos de avanço e, portanto, a ação depende não só do estado no AIV mas também do próximo símbolo na entrada.

Numa TAS LR(1) mantém-se a necessidade de determinar, sem ambiguidade, cada ação no processo da análise sintática. Em relação ao caso LR(0), a escolha da ação depende não só do estado do AIV mas também do símbolo de avanço.

Quando esta informação (estado AIV + símbolo de avanço) não é suficiente para determinar uma única ação tem-se um conflito, que pode ser de dois tipos:

  • Conflito Redução/Redução LR(1): Num estado com dois itens completos em que os avanços se intersetam. Formalmente, se no AIV LR(1) existe um estado com dois itens completos distintos e e .
  • Conflito Redução/Transferência LR(1): Num estado com um item completo em que sai uma aresta "com um terminal" que está no avanço desse item completo. Formalmente, se no AIV LR(1) existe um item completo e um item e .

Teorema das Gramáticas LR(1). Uma GIC é LR(1) se e só se o seu AIV não tem conflitos redução/redução LR(1) nem redução/transferência LR(1).

Autómato de Pilha Reconhecedor LR(1)

Quando o AIV LR(1) de uma GIC está livre de conflitos é possível definir-se um autómato de pilha para reconhecer a linguagem gerada pela GIC. Além disso, para as palavras geradas/aceites, a observação da computação permite recuperar a derivação direita da respetiva palavra.

Autómato de Pilha Reconhecedor LR(1). Seja uma GIC LR(1) e o seu AIV LR(1). O Autómato de Pilha Reconhecedor LR(1) (APR LR(1)) de , que reconhece a linguagem gerada por , é com

  • estados de controlo: .
  • estados finais: .

e em que a transição, , é definida pelos seguintes elementos:

  • iniciar: .
  • avançar: Para cada então .
  • transferir: Para cada com um item em que e então .
  • reduzir: Para cada estado com um item completo com e para cada , quando no AIV existe a computação e então .
  • aceitar: Para cada estado com um item completo do símbolo inicial da GIC, se e quando no AIV existe a computação então

Alternativamente as transições do APR LR(1) podem ser descritas pela seguinte tabela:

Intuitivamente os estados do APR LR(1) refinam os do APR LR(0) com informação sobre o avanço. O estado "consulta" o símbolo de avanço (por exemplo, ) e encaminha a computação para o respetivo estado , onde os passos são feitos sob o pressuposto "o avanço é ".

A computação fica em até ser transferido da entrada para a pilha. Depois dessa transferência é necessário tornar a consultar o avanço (em ) e proceder de acordo com o novo avanço.

O símbolo marca o fím da entrada e é processado de acordo com esse pressuposto. Por exemplo, não há transições de para e só neste estado pode ocorrer a ação aceitar.

Continuando o exemplo anterior, a transição do APR LR(1) tem as seguintes arestas:

  • iniciar transições : .
  • avançar
  • transferir
  • reduzir
  • aceitar

que corresponde ao diagrama

Diagrama do APR LR(1)
Diagrama do APR
As arestas são avançar, reduzir e aceitar e são transferir.

Como é que este APR processa palavras? Por exemplo, é gerada pela GIC, enquanto que não.

Para o APR tem a computação que aceita e mostra a derivação . Quando à computação de , rejeita:


Com este exemplo termina a resolução do Problema Principal de ALP — Dada uma linguagem e uma palavra no mesmo alfabeto, determinar se de forma computável, eficiente e adequada.

  1. A linguagem é adequada se for formalmente definida por uma GIC LR(1).
  2. Dada uma GIC que gere a linguagem, a construção algorítmica do seu AIV LR(1) é eficiente.
  3. Pode-se verificar algoritmicamente e de forma eficiente se a GIC é LR(1), confirmando que nenhum estado do seu AIV LR(1) tem contradições. Nesse caso a linguagem é adequada.
  4. A construção do APR LR(1) a partir do AIV LR(1) é, também, algorítmica e eficiente.
  5. Dada uma palavra sobre o alfabeto da linguagem, o processamento pelo APR LR(1) é eficiente (e, claro, algorítmico). Adicionalmente, se a palavra está na linguagem, é possível recuperar a sua derivação na GIC para efeitos de processamento semântico.

Problema Principal de ALP

Resumindo, este processo define um algoritmo (qua pode ser implementado em qualquer linguagem de programação comum) que é eficiente e resolve o Problema Principal de ALP.

Gramáticas LALR(1)

Neste ponto é fácil melhorar o seguinte problema: a construção do AIV gera muitos estados, o que pode ter um efeito negativo no desempenho dos restantes passos.

Quando dois estados do AIV têm os mesmos núcleos e, eventualmente, avanços distintos, a fusão consiste em juntar esses dois estados num único, cujos itens são obtidos:

  • os núcleos são os mesmos;
  • cada avanço é a união dos avanços dos itens correspondentes.

Usando um exemplo anterior

Diagrama do Autómato dos Itens LR(1) Válidos
Núcleos Repetidos
Os estados e têm exatamente os mesmos núcleos.

O amalgamento deste AIV é

Autómato Amalgamado
Autómato Amalgamado
O estado resulta de fundir com . Neste exemplo não há mais fusões possíveis.

Formalmente:

Autómato Amalgamado. Seja um AIV LR(1).

Se for um conjunto de estados de com os mesmos núcleos, a fusão destes estados é o estado com os itens tais que .

Seja uma partição de tal que:

  • todos os estados de têm os mesmos núcleos e
  • se os núcleos dos estados de e são disjuntos. então

O autómato amalgamado é o autómato que resulta de fundir os estados com o mesmo conjunto de núcleos: com

  • estados de controlo .
  • transição se existe tal que .

Os autómatos amalgamados definem uma classe de gramáticas distinta de LR(1):

Gramática LALR(1). Uma GIC é LALR(1) se o seu autómato amalgamado satisfaz as condições LR(1): não tem conflitos redução/redução nem redução/transferência.

O principal interesse das gramáticas LALR(1) é, essencialmente, prático: Intuitivamente, são as gramáticas com "bons" AIV depois de amalgamados.

Exercícios — Análise Sintática

Os exercícios assinalados com "✓" serão resolvidos nas aulas práticas; Os assinalados com "†" têm elevada dificuldade. Todos os restantes devem ser resolvidos pelos alunos.

Limpeza de uma Gramática

Exercício 01

Considere a gramática independente do contexto com produções

  1. Escreva uma expressão regular que represente a linguagem gerada por .
  2. Construa uma gramática (essencialmente) não contraível equivalente.
  3. Elimine as produções unitárias da gramática obtida na alínea anterior.

Exercício 02

Repita o exercício anterior para a gramática:

  1. com produções

  2. com produções

Exercício 03

Construa uma gramática equivalente a , com produções que não contenha produções unitárias e escreva uma expressão regular que represente a linguagem gerada por esta gramática.

Exercício 04

Construa uma gramática equivalente a , com produções sem símbolos inúteis e encontre uma expressão regular que represente a linguagem gerada por esta gramática.

Exercício 05

Construa uma gramática equivalente a , com produções na forma normal de Chomsky.

Exercício 06

✓ Construa uma gramática equivalente a , com produções na forma normal de Greibach.

Exercício 07

Repita o exercício anterior para a gramática

  1. Com produções
  2. Com produções

Gramáticas LL(k)

Exercício 08

Calcule os símbolos diretores e determine se as seguintes gramáticas são :

Exercício 09

†✓ Modifique a gramática de modo a obter uma gramática equivalente. As produções de são: Sugestão: Comece por determinar .

Exercício 10

Repita o exercício anterior para a gramática

Exercício 11

Defina uma gramática que gere a linguagem das expressões aritméticas com subtração, multiplicação e parêntesis. (Use o símbolo para representar os inteiros.)

Gramáticas LR(0)

Exercício 12

Determine os da gramática com produções

  1.  

Exercício 13

✓ Considere a gramática .

  1. Construa o autómato dos itens válidos de .
  2. Diga, justificando, se é .
  3. Construa a tabela de análise sintática para .
  4. Defina o autómato de pilha reconhecedor para .

Exercício 14

Repita as duas primeiras alíneas do exercício anterior para a gramática Se concluir que a gramática não é , enumere os conflitos encontrados.

Exercício 15

Repita o exercício anterior para a gramática

Gramáticas LR(1)

Exercício 16

✓ Considere a gramática , com o conjunto de produções:

  1. Construa o autómato dos itens válidos de .
  2. Diga, justificando, se é .
  3. Construa o autómato amalgamado e diga, justificando, se é .
  4. Construa a tabela de análise sintática para .
  5. Com base no autómato dos itens válidos de , defina o autómato de pilha reconhecedor .
  6. Construa a computação do autómato de pilha para a palavra .

Resolução em Banda Desenhada

AIVTASAPR
Passo 1Passo 2Passo 4

Exercício 17

✓ Repita o exercício anterior com a gramática , com o conjunto de produções:

Exercício 18

✓ Repita as primeiras 4 alíneas do exercício anterior com a gramática , com o conjunto de produções: (Se não é , não faça as alíneas que não se aplicam.)

Exercício 19

Repita o exercício anterior com as gramáticas

  1. , com o conjunto de produções:

  1. , com o conjunto de produções:

  1. , com o conjunto de produções:

Implementação

As indicações gerais para os exercícios de implementação são válidas aqui.

Uma biblioteca para Grafos Orientados, com Pesquisas

Para este grupo de exercícios pode usar, entre outros, os grafos indicados a seguir.

# Grafos para testar as implementações.
simples = [
  (0, 2),
  (1, 3),
  (2, 0),
  (3, 1),
]

cubo = [
  (0, 1), (0, 4),
  (1, 2), (1, 5),
  (2, 3), (2, 6),
  (3, 0), (3, 7),
  (4, 5), (5, 6), (6, 7), (7, 4)
]

cubo_inclinado = [
  (0, 1), (0, 3), (0, 4),
  (1, 2), (1, 5),
  (2, 6),
  (3, 7),
  (4, 5), (4, 7),
  (5, 6),
  (7, 6)
]
  • Represente. Uma aresta orientada por um tuplo (a, b).
  • Represente. Um Grafo (orientado) por uma lista de arestas.
  • Implemente. A função nodes(graph) que devolve o conjunto do vértices do grafo.
  • Implemente. A função children(graph, node) que devolve o conjunto dos filhos do vértice node.
  • Implemente. A função parents(graph, node) que devolve o conjunto dos pais do vértice node.
  • Implemente. A função is_path(graph, path) que testa se path é um caminho no grafo graph. Um caminho é uma lista de vértices em que dois consecutivos estão ligados por uma aresta.
  • Implemente. A função has_loop(graph, path) que testa se path tem algum ciclo no grafo graph. Um ciclo é um caminho que começa e termina no mesmo vértice.
  • Implemente. A função search(graph, a, b) de acordo com os apontamentos teóricos. Considere uma variante em que as funções expand e join são passadas como argumentos opcionais. Verifique o que acontece se não controlar os vértices visitados.
  • Teste. Pesquisas ascendentes, descendentes, em largura e em profundidade.

Uma biblioteca para Árvores, com Pesquisas

  • Represente. Um nó/vértice é representado pela estrutura Node com atributos:
    • value: Qualquer "coisa" que pode estar no nó.
      • Obs. nem todas as linguagens permitem isto facilmente. Em python e kotlin, por exemplo, é direto.
    • children: Uma lista de Node.
      • Obs. esta recursividade também levanta problemas em algumas linguagens. Por exemplo, em rust terá de fazer algo do género Vec<Box<Node>>. Em python não terá qualquer dificuldade.
  • Implemente. A função leaf(value) cria uma folha (isto é, um nó sem filhos).
  • Implemente. A função binop(op, lhs, rhs) cria um nó com value op e dois filhos: lhs e rhs. Considere variantes em que lhs, rhs são Node ou são um tipo qualquer.
  • Implemente. A função node(value, children) aceita um número variável de valores em children. Por exemplo node("plus", 3, 4, 5) e não node("plus", [3, 4, 5]).
  • Escrita. A função repr(node) devolve uma string com a representação de uma árvore, um valor por linha. Indente os descendentes. Por exemplo:
plus
- 3
- times
  - 4
  - 5

Alternativamente, as árvores podem ser representadas por listas de listas. Por exemplo:

("plus" 3 ("times" 4 5)) =
("plus"
    3
    ("times"
        4
        5
))

Desta forma, em geral n = Node(value, children) define a lista [n.value] + CHILDREN em que CHILDREN é a lista das representações dos nós em n.children.

N.B. usando a notação do python, tree.children = tree[1:] e tree.value= tree[0]. Além disso, a representação das folhas é o próprio valor, não uma lista.

Pesquisa:

  • Implemente. A função search para pesquisas (em profundidade e em largura).
    • Começe com pesquisas por valor exato: Por exemplo, search(tree, value) procura em tree um nó n tal que n.value == value. No caso de existir um nó nessas condições, devolve o caminho para esse nó.

Caminhos para nós descendentes. Por exemplo, se tree for o exemplo acima, o caminho para chegar ao nó com o valor 4 é a lista [1, 0] porque começando na raiz (o nó com valor plus) escolhe-se o filho na posição 1 (o nó com valor times e filhos [4, 5]) e, desse nó escolheu-se o filho na posição 0; Isto é, o caminho [0, 1] indicas os indices dos filhos escolhidos, quando se "desce" a árvore.

O caminho para chegar ao valor 5 seria [1, 1] e para chegar a times seria apenas [1]. Finalmente [0] dá o valor 3 e o caminho [] leva ao valor ... (exercício).


  • Implemente. A função subtree(tree, path) devolve o nó que corresponde ao caminho path. Se não existe tal nó, devolve "não definido".

  • Generalize. Há várias generalizações interessantes:

    • Use um predicado em vez de um valor. Por exemplo, para encontrar um nó com o valor par: tree.searchD(lamba x: x.value % 2 == 0).
    • Encontre todas as ocorrências em vez de apenas uma. Ou encontre até n ocorrências. Por exemplo: tree.search(lambda x: len(x.children) > 2, n=42) para encontrar 42 nós com mais do que dois filhos. Convencione que, se n for "não definido" procura todas as ocorrências.
      • A pesquisa de todas as soluções também tem um tratamento interessante que consiste em implementar a pesquisa como uma stream que produz um novo nó sempre que solicitada. No caso do python pode usar yield. Noutras linguagens, ymmv.
    • Implemente outras estratégias de pesquisa. Por exemplo a Iterative deepening depth-first, é uma forma melhorada de pesquisas em profundidade.

Analisadores LL(1)

  • Considere a GIC

em que os terminais são e .

Verifique (manualmente) se é LL(1) e, nesse caso, implemente um analisador sintático LL(1). A função parse(s) tem como argumento a string s e devolve uma árvore.

  1. Comece por separar (tokenize) a palavra numa lista de símbolos.
  2. Precisa de um "contexto" de processamento com:
    1. O símbolo seguinte: next.
    2. A lista dos símbolos que faltam processar.
    3. A função consume(symbol).
  3. Processe a lista de tokens usando as funções proc_Expr(token, tokens, tree) e proc_Seq(token, tokens, tree):
    • token é o símbolo de avanço.
    • tokens são os restantes símbolos da palavras (incluindo token).
    • tree é a árvore que resulta do processamento da função.
  4. Vai precisar de funções auxiliares como consume(token, tokens)

Uma biblioteca para GIC LL(1)

Se resolver sozinho estas alíneas ganha o direito de se gabar nas aulas de ALP durante uma semana. E o dever de ajudar os seus colegas.

  • Implemente. O método firsts() que devolve um mapa do tipo symbol: set<symbol> que associa a cada símbolo (variável ou terminal) da gramática o conjunto dos seu primeiros.
  • Implemente. O método follow() que devolve um mapa do tipo symbol: set<symbol> que associa a cada símbolo (variável ou terminal) da gramática o conjunto dos seu seguintes.

Análise Sintática LL(1)

  • Implemente. O método firsts_of(symbol) devolve o conjunto dos primeiros de symbol.
  • Implemente. O método follow_of(symbol) devolve o conjunto dos seguintes de symbol.
  • Implemente. O método directors(rule) devolve o conjunto de diretores da regra rule.
  • Teste. O método is_LL1() testa se grammar é LL(1).

Uma biblioteca para GIC LR

Itens

  • Represente. Um item LR(1) é representado pela classe Item com atributos:
    • rule uma regra.
    • lookahead uma lista de símbolos.
    • position um inteiro, que indica a posição do "ponto".
  • Teste. O método is_complete() testa se o item é completo.
  • Implemente. O método active_prefix() devolve o prefixo até à posição do "ponto".
  • Implemente. O método active_symbol() devolve o símbolo imediatamente a seguir ao ponto se o item não for completo e "não definido" caso contrário.
  • Implemente. O método active_suffix() devolve o sufixo desde a posição a seguir ao "ponto".
    • N.B: active_prefix + active_symbol + active_suffix deve reconstruir o lado direito da produção.
  • Implemente. O método transition(symbol) devolve o item que resulta de "ler" symbol. Isto é, se symbol == active_symbol no novo item o "ponto" avança uma posição. Caso contrário devolve "não definido".
  • Escrita. O método __repr__() devolve uma string da forma C〈V → P · A S ⎅ L〉 em que:
    • C é "'★'" quando o item é completo e vazia ('') caso contrário.
    • V é o lado esquerdo da produção.
    • P, A e S são o prefixo, símbolo e sufixo ativos.
    • L é a lista dos símbolos de avanço, separados por espaços. Se for vazia, use .
    • Use mesmo os símbolos indicados: ★〈→·⎅∅〉

Análise Sintática, Autómato dos Itens Válidos

Na biblioteca para os AFD estes são construídos com uma lista de transições, o estado inicial e uma lista de estados finais. Além disso, os estados são inteiros.

Mas, na construção do Autómato dos Itens Válidos os estados "contêm" conjuntos de itens. Esta diferença é resolvida mantendo uma associação (mapa, dicionário) dos estados do AFD para os conjuntos de itens. A vantagem é que não é preciso mudar a implementação dos AFD. A desvantagem é que se torna necessário fazer alguma "manutenção" dessa associação.

  • Representação. Uma classe VIA com atributos:

    • grammar a gramática.
    • fsa o autómato dos itens válidos calculado para grammar.
    • states a associação dos estados do autómato para os conjuntos de itens.
    • table a tabela de análise sintática, uma associação dos estados+avanços do autómato para reduções/transferências.
    • phase um inteiro (ou enum) para marcar a fase de processamento: INITIAL = 0GRAMMAR_OKSTART_OKVIA_OKTABLE_OK. Se algum destes passos correr mal → ERROR.
  • Construção. O método make_VIA(). Se grammar.is_valid() incrementa phase.

  • Implemente. O método calc_startCore() que calcula o núcleo do estado inicial de via. Devolve um conjunto de itens.

  • Implemente. O método close(itens) que calcula o fecho de um conjunto de itens. Devolve um conjunto de itens.

  • Implemente. O método build_START() que calcula o estado inicial de via. Se correr bem incrementa phase.


Se resolver sozinho todas as alíneas seguintes ganha o dever de ajudar os seus colegas. E o direito de se gabar nas aulas de ALP durante uma semana.

  • Implemente. O método build_FSA() processa grammar para definir o autómato fsa, a associação states e is_built. Se correr bem incrementa phase.
  • Implemente. O método build_TABLE() processa grammar, fsa e states para definir table. Se correr bem incrementa phase.

  • Implemente. O método derive(word) para encontrar uma derivação de word pela gramática via.grammar. N.B. não é necessário implementar autómatos de pilha.
  • Implemente. O método derivation_tree(word) que calcula a Árvore de Derivação de word.
  • Controlo. Use phase para evitar computações repetidas, precoces ou desnecessárias. Por exemplo, suponha que houve um erro a calcular o estado inicial. Então quando "chama" build_FSA deve evitar calcular o AFD. Por outro lado, se já calculou fsa com sucesso e "acidentalmente" chama build_FSA não há razão para repetir esses cálculos.
    • Também pode usar phase para implementar cálculos build--- "inteligentes" (Ah! Ah!). Suponha que "chama" build_TABLE mas phase < VIA_OK. Nesse ponto pode chamar build_VIA que por sua vez faz uma análise semelhante.

Representação e Processamento de Programas


Este capítulo inspira-se em grande parte (e copia pontualmente) no artigo (How to Write a (Lisp) Interpreter (in Python)) de Peter Norvig, cuja leitura se recomenda.


Introdução

Procura-se ilustrar uma das principais aplicações da análise sintática: A implementação de linguagens de programação.

Antes de se definir a própria linguagem de programação e considerar os aspetos da implementação do respetivo analisador sintático e do interpretador faz-se uma revisão dos termos e processos envolvidos.

Alguns termos relevantes, alguns já familiares, são:

  • Símbolos: "entidades" indivisíveis e distintas entre si. Um conjunto de símbolos é um alfabeto.
  • Palavra: sequência finita de símbolos.
  • Linguagem: conjunto de palavras.
  • Gramática: regras que permitem especificar certas linguagens.
  • Representação: descrição da estrutura duma palavra, de acordo com uma gramática.

Também é importante recapitular alguns processos:

  • A análise sintática consiste em decidir de uma palavra está, ou não, numa linguagem : "?". No caso da linguagem ser gerada por uma certa gramática , isto é, se , a questão da análise sintática passa a ser "?" em que é o símbolo inicial de .
  • Para o processamento de programas, em particular para a interpretação e/ou compilação, não basta saber que ; É mais importante representar a estrutura de de acordo com as regras de . Essa representação pode ser, por exemplo, a árvore da derivação de ou a sua própria derivação, isto é a sequência de regras aplicadas passo-a-passo em .
  • A representação do programa é processada pelo interpretador, que mantém uma configuração interna, atualizada conforme a computação avança nas instruções.
  • A evolução da computação depende, por um lado, dos tipos das instruções e, por outro, dos valores das expressões.

Representação de Programas e/ou Expressões

É necessária uma estrutura de dados adequada à representação e ao processamento de programas.

Começando pelas expressões algébricas:

Árvore de DerivaçãoÁrvore SimplificadaValoração da Expressão
Figura Exemplo Árvore DerivaçãoFigura Árvore Derivação SimplificadasFigura Árvore Derivação Simplificadas
  • A palavra 2 + (3 * 4) representa a expressão algébrica mas, como "simples" sequência de símbolos, perde-se a estrutura da expressão que representa.

  • As sequências (isto é, listas) não são adequadas para processar expressões ou programas. Por exemplo, para calcular o valor de primeiro avalia-se a parte e depois esse resultado é somado a .

  • A estrutura da expressão algébrica resulta de uma certa gramática, implícita na respetiva definição formal.

  • A linguagem das expressões algébricas resulta, por exemplo, da seguinte GIC:

    E → E + T | E - T | T
    T → T * U | T / U | U
    U → N | V | ( E )
    

    em que N define números (-1, 2.45E-5, 42.021, etc) e V variáveis (a, Largura, etc).

  • De acordo com esta GIC a palavra 2 + (3 * 4) tem a Árvore de Derivação acima.

  • Na Árvore Simplificada a representação em árvore permite calcular o valor da expressão, propagando os valores das folhas para a raíz e, em cada nó, aplicando a operação adequada conforme o tipo do nó.

  • A implementação de árvores por uma estrutura de dados é assunto doutras disciplinas. Aqui estamos interessados numa representação simples de árvores, de preferência sem a introdução de novos tipos, operações, etc

  • A árvore simplificada fica representada (em Python) pelo tuplo ('+', 2, ('*', 3, 4)).

  • Em geral, cada nó tem um conteúdo X e descendentes D1, ..., Dn. Este nó é representado pelo tuplo (X, D1, ..., Dn) com a convenção de que as folhas (Z) são representadas apenas por Z.

  • Subindo a árvore de 2 + (3 * 4) temos:

    1. Folhas 2, 3 e 4 (e não (2) por exemplo).
    2. A multiplicação é o tuplo ('*', 3, 4) porque o respetivo conteúdo é '*' (uma string Python) e tem dois descendentes, 3 e 4.
    3. O nó da soma tem conteúdo '+' e dois descendentes, a folha 2 e a sub-árvore ('*', 3, 4). Fica representado por ('+', 2, ('*', 3, 4)).

Esta forma de representar as (estruturas das) expressões vai ser aplicada à representação (das estruturas) dos programas.

Também o exemplo do cálculo do valor da expressão algébrica orienta a implementação do interpretador.

Desenho de uma Linguagem de Programação

Como já está esboçado um esquema geral para representar programas, agora pode-se tratar da linguagem propriamente dita.

O que se pretende e/ou necessita numa linguagem de programação?

Em geral, numa linguagem de programação encontra-se:

  • Expressões e Variáveis.
  • Instruções e Sequências.
  • Condicionais.
  • Ciclos.
  • Funções.
  • Entrada/Saída.

Mais especificamente,

  • Expressões e Variáveis. As expressões definem os valores que os programas processam e as variáveis "mantêm" esses valores para uso posterior.

Por exemplo, a instrução a = 2 + (3 * 4) em Python define um certo valor que fica guardado na variável a e que pode ser usado posteriormente, como em a % 2 == 0.

  • Instruções e Sequências. Um programa é uma sequência (ou bloco) de instruções. "Correr" um programa significar avançar uma instrução de cada vez ao longo dessa sequência.

São comuns certas convenções sobre as sequências que "efetivamente" definem um programa. Por exemplo, em C o programa é o bloco de instruções que está na função main e tudo o resto é "auxiliar".

  • Condicionais. Um condicional permite certas condições ativarem e desativarem blocos de instruções.

A sintaxe mais comum dos condicionais é if (C) A else B com pequenas variantes conforme a linguagem.

  • Ciclos. Um ciclo repete um certo bloco de instruções em função de uma condição.

Quando o número de repetições é conhecido de antemão é comum usar-se a sintaxe for(i = 0; i < n; i++) A para repetir n vezes as instruções de A.

Quando as repetições estão dependentes de uma condição, a forma while (C) A, que testa C e repete A enquanto a condição C for verdadeira, é comum.

Também se usa a forma do A while (C), que corre A pelo menos uma vez, antes de testar C.

  • Funções. As funções são uma forma simples de evitar repetição de código e de acrescentar instruções "novas" a uma linguagem de programação.

Se for necessário calcular 2 + 2, 2 + 3, 2 + 4, ..., 2 + 42 não se escrevem 40 instruções quase iguais. Define-se uma função que mantém a parte comum do código repetido e usa variáveis locais para os valores que variam. Sendo possível, a função pode ser evocada num ciclo.


Funções Anónimas. Formalmente, uma função não precisa de ter um nome. Nalgumas linguagens mais arcaicas, como o C, as funções anónimas (ou lambdas) não são suportadas diretamente. Com a maior disponibilidade do processamento de coleções têm ganho popularidade. Por exemplo, em Java foi introduzido o operador ->, o Javascript e o C# têm o =>, no Python usam-se expressões lambda e no Rust a sintaxe é |var| instr, etc. TL/DR: As funções anónimas são fixes.

  • Entrada/Saída. Um programa, enquanto processador de informação precisa de canais de entrada e de saída de dados.

As formas mais simples de entrada e saída de dados pressupõem uma consola onde o utilizador digita e lê os dados que, respetivamente, dão entrada no, ou são escritos pelo, programa.

Lisp

O Lisp é uma das mais antigas, influentes e avançadas linguagens de programação.

Tanto que há, não um mas, dois xkcd obrigatórios!!
Dois xkcd sobre o mesmo assunto é... incomum.

Além disso, all the programming languages converge to Lisp e any sufficiently complicated program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

Aspeto de um programa Lisp (especificamente, Common Lisp):

(defun fib (x)
    (if (< x 2)
        1
        (+ (fib (- x 1)) (fib (- x 2)))
    )
)
(fib 6) ; resultado: 13

A "excecionalidade" do Lisp está nas possibilidades que resultam da sua simplicidade. "Elegant weapons" significa que certas ideias muito simples são extremamente efetivas. Por exemplo, (+ 41 1) é uma lista com três elementos, uma expressão que vale 42 e uma (instrução de) evocação da função +.

  • Lisp significa LISt Processor. Além dos tipos básicos (inteiros, doubles, strings) tem listas. Ao contrário dos array em muitas linguagens, uma lista do Lisp pode ter elementos de tipos diferentes. Por exemplo, (42 3.14 "fourty-two" ("sub" lista)).

  • No Lisp as instruções também são expressões. Isto é, (+ 2 (* 3 4)) é simultaneamente uma expressão (com valor 12) e uma instrução (neste caso, evocar a função "+").

    • Por exemplo, um condicional é (if C A B) e, como C, A e B são expressões, o valor do condicional é o valor do ramo que foi seguido.
  • A sintaxe segue fielmente a representação das árvores feita acima (as vírgulas são descartadas). Isto é: Um programa Lisp é a sua própria representação! É possível um programa Lisp ler, analisar e modificar o seu próprio código enquanto corre. Em particular, o Lisp é homoicónico.

No resto deste capítulo define-se uma linguagem de programação, ALisP, inspirada no Lisp. Além das propriedades acima, acresce ainda que a gramática para a sintaxe é extremamente simples e LL(1), o que permite implementar (quase) diretamente um analisador sintático.

Semântica Informal da ALisP

Uma antevisão daALisP.

  • Variáveis e Expressões: (set a (+ 30 12)) define a variável a e dá-lhe o valor 42. A expressão completa também fica com esse valor.

  • Instruções e Sequências: (seq (set a (+ 40 10)) (set a (- a 8))) executa as duas instruções. Fica com o mesmo valor que a última sub-expressão.

  • Condicionais: (if (== a 42) CERTO (> 0 1)) calcula o valor de (== a 42); Se for True calcula e fica com o mesmo valor que CERTO; Caso contrário calcula (> 0 1) e fica com esse valor.

  • Ciclos: (while (< a 42) (set a (+ a 1))) repete o "passo" (set a (+ a 1)) enquanto a condição (< a 42) for verdadeira. Quando (se) termina fica com o valor do "passo".

  • Funções (anónimas): (fn (x) (== x 42)) define uma função anónima com argumentos x e "corpo" (== x 42). A variável x está limitada ao "corpo" da função. Devolve o valor do "corpo" quando x tem o valor com que a função é evocada. Por exemplo, em

    (seq
        (set dobro (fn (x)
            (* 2 x)
        ))
        (dobro 21)
    )
    

    a evocação (dobro 21) define o valor de x como 21 e, portanto, a função devolve (surpresa!) 42.

  • Entrada/Saída: (read) é uma forma especial. Tem o valor que o utilizador escrever na consola; (write 42) esteve 42 na consola. Tem o valor da expressão que é escrita.

Um programa ALisP simples, que pergunta o nome do utilizador e o cumprimenta:

(seq
    (write (What is your name?))
    (set name (read))
    (Hello name .)
)

Um defeito semântico da atual versão da ALisP é que os símbolos, como em What is your name? são tratados como string, o que simplifica a implementação mas torna o código mais imprevisível. Por exemplo, o valor de (Hello name .) varia conforme name é, ou não, uma variável e esse facto não pode ser deduzido olhando apenas para esta expressão.

Analisador Sintático com Representação

Embora a função principal da análise sintática seja determinar se p ∈ L(G), aqui pretende-se ir além dessa resposta e obter a representação de p em termos da sua árvore (simplificada) de derivação na gramática G.

Gramática ALisP

Em termos de sintaxe a linguagem é a linguagem dos parêntesis equilibrados, com átomos, definida pela seguinte gramática, que designamos ALisP:

Expr -> atom | ( Seq )
Seq -> λ | Expr Seq 

onde atom representa um terminal átomo isto é, uma "palavra contígua": uma string não vazia sem espaços nem parêntesis.

Os átomos podem (devem!) ser representados pela sua própria sub-gramática. Para o efeito pretendido (análise sintática com representação) esse exercício iria apenas acrescentar ruído. Em vez disso, é implementado o teste is_atom(x), posteriormente usado pelo analisador sintático.

Para implementar o analisador sintático LL(1) é preciso calcular os diretores de cada produção.

Geradores de λ

Λ
Seq

Primeiros e Seguintes

VariávelPrimeirosSeguintes
Expratom, (atom, (, )
Seqatom, ()

Diretores

ProduçãoDiretores
Expr -> atomatom
Expr -> ( Seq )(
Seq -> λ)
Seq -> Expr Seqatom, (

A tabela dos Diretores indica que a gramática ALisP é LL(1), pelo que pode ser aplicado o método dado no respetivo capítulo para construir um analisador sintático. Porém, também se pretende obter a representação da (árvore simplificada da derivação da) palavra.

Representação de Árvores

Como já foi tratado acima, qualquer árvore pode ser representada em Python por tuple aninhados. Mais especificamente:

Representação de nós em Python. O nó com com conteúdo x e descendentes d1, ..., dn, em que x e os di são valores Python, é representado pelo tuple

(x, d1, ..., dn)

Por convenção a representação das folhas não usa parêntesis. Em vez de (x) usa-se apenas x.

Por exemplo, a árvore de 2 + (3 * 4) é representada por

('+', 2, ('*', 3, 4))

Analisador Sintático com Representação

O analisador sintático com representação é implementado a partir da base definida no capítulo sobre a análise sintática LL(1). Acrescenta-se uma forma de se obter a representação em árvore e de tratar da especificidade dos átomos.

Para a implementação do analisador sintático compensa considerar com algum detalhe o contexto em que a análise LL(1) decorre. Em particular, importa tratar rigorosamente o processamento do avanço, de consumir e dos erros.

Contexto LL(1) Especificamente, uma instância c da classe ContextLL1:

  • É construída com a palavra a ser analisada.
  • c.next() devolve o próximo símbolo da palavra, se existir; caso contrário devolve None.
  • c.consume(x) consome o próximo símbolo se o valor deste for x; caso contrário levanta uma exceção.
  • c.error(m) levanta uma exceção com a mensagem m.
  • Adicionalmente, c.is_complete() testa se não existe seguinte.
class ContextLL1:
    """Tracks and supports the state of a LL1 parsing process."""
    def __init__(self, word):
        self.word = word
        self.pos = 0

    def is_complete(self):
        """Checks if the parsing process is complete."""
        return self.pos >= len(self.word)

    def next(self):
        """Returns the next (unread) token."""
        if not self.is_complete():
            return self.word[self.pos]
        else:
            return None

    def consume(self, symbol):
        """'Consumes' symbol, advancing if possible."""
        if not self.is_complete() and self.next() == symbol:
            self.pos += 1
        else:
            self.error(f"** ERROR ** Can't CONSUME '{symbol}' while expecting '{self.next()}'.")

    def error(self, message):
        """Error handling."""
        raise Exception(f"{message}\nWord: {self.word}\nRead: {self.word[self.pos:]}\nUnread: {self.word[:self.pos]}")

    def __repr__(self):
        """String representation."""
        return f"\"{' '.join(self.word[:self.pos])}\" | \"{' '.join(self.word[self.pos:])}\""

Suporte. São necessárias algumas funções de suporte. Em particular

  • tokenize(text) aceita uma string e devolve a lista das sub-palavras separadas por espaços, com tratamento especial dos parêntesis.
  • is_atom(symbol) testa se symbol é um átomo: uma string não vazia e sem ocorrências de espaços ou parêntesis.
  • atom_value(atom) devolve o "valor" do átomo atom, conforme atom pode ser convertido num ìnt senão num float senão no próprio atom.
def tokenize(text):
    """
    Converts a string to a list of tokens.
    """
    text = ''.join(ch for ch in text if ch.isprintable())
    text = text.replace("(", " ( ").replace(")", " ) ")
    tokens = text.split(" ")
    tokens = [tok.strip() for tok in tokens]
    tokens = [tok for tok in tokens if len(tok) > 0]
    return tokens

def is_atom(symbol):
    """
    Tests if a symbol is an atom.
    """
    return isinstance(symbol, str) and \
        len(symbol) > 0 and \
        (not ' ' in symbol) and \
        (not '(' in symbol) and \
        (not ')' in symbol)

def atom_value(atom):
    """
    Gets the value of an atom. BAD BAD NOT GOOD CODE.
    """
    value = None
    try:
        value = float(atom)
        (d, i) = math.modf(value)
        value = int(i) if d == 0 else value
    except:
        value = atom
    return value
  • A implementação do analisador sintático, segundo o processo LL(1), consiste em definir uma função para cada variável da gramática ALisP e, em cada uma dessas funções, usar o avanço e os diretores para "percorrer" a regra adequada.
  • A implementação LL(1) base é aumentada de forma se obter uma representação parcial em cada função associada.
  • Todo o processo da análise sintática com representação é concretizado em parse(text). Esta função aceita como argumento text, uma string, e, se corresponder a uma palavra gerada pela gramática, devolve a respetiva representação em árvore.
#
# Rule            | Dir
# ----------------|-------
# Expr -> ( Seq ) | (
# Expr -> atom    | atom
#
def proc_Expr(context):
    next_symbol = context.next()
    if next_symbol == "(":
        context.consume("(")
        seq = proc_Seq(context)
        context.consume(")")
        return seq
    elif is_atom(next_symbol):
        context.consume(next_symbol)
        return atom_value(next_symbol)
    else:
        context.error(f"** ERROR ** Can't use Expr with next '{next_symbol}'.")
#
# Rule            | Dir
# ----------------|-------
# Seq -> Expr Seq | atom (
# Seq -> nil      | )
#
def proc_Seq(context):
    next_symbol = context.next()
    if is_atom(next_symbol) or next_symbol == "(":
        e = proc_Expr(context)
        s = proc_Seq(context)
        return (e,) + s
    elif next_symbol == ")":
        return tuple()
    else:
        context.error(f"** ERROR ** Can't use Seq with next '{next_symbol}'.")

def parse(text):
    word = tokenize(text)
    if all(is_atom(x) or x in "()" for x in word):
        context = ContextLL1(word)
        expr = proc_Expr(context)
        return expr
    else:
        return None

A implementação do processo de análise sintática chega ao fim da aplicação dos capítulos anteriores.

Recapitulando o que foi feito até aqui:

  • Definiu-se uma gramática para especificar a sintaxe da ALisP.
  • Essa gramática é LL(1) e implementou-se um analisador sintático que devolve uma representação em árvore da palavra dada.

Se tivesse sido escolhida uma linguagem com sintaxe mais complexa poderia ser necessário um analisador LR(1). Porém, o objetivo aqui é ir além da matéria anterior, implementando um interpretador da ALisP.

Interpretador

A análise sintática (da ALisP) fica isolada na função parse(text), que devolve uma árvore com a estrutura de text de acordo com a gramática ALisP. Por exemplo, parse("(+ 2 (* 3 4))") devolve ('+', 2, ('*', 3, 4)).

O passo seguinte consistem em associar um valor (a semântica) a cada representação (à sintaxe), de forma a construir a ALisP com as caraterísticas pretendidas. Nomeadamente, pretende-se que a ALisP tenha:

  • Expressões e Variáveis.
  • Instruções e Sequências.
  • Condicionais.
  • Ciclos.
  • Funções.
  • Entrada/Saída.

além de, é claro, certas funções base.


Para correr da forma esperada, um programa precisa de um certo "contexto" onde é mantida e atualizada informação sobre as variáveis. Por exemplo, no programa

(
    (set a 42)
    (set b (- a 2))
    (write (b a))
)

na primeira instrução é criada uma variável com nome a e valor 42 e na segunda instrução o valor de a é consultado, operado e o resultado define o valor da recém-criada variável b. Por fim, tanto o valor de b como de a são consultados para definir a lista (b a) que será escrita na consola.

Funções Base

As funções base definem cálculos "diretos" que dependem apenas dos valores dos argumentos e não afetam o contexto do programa.

Entre as funções base estão incluidas as operações aritméticas +, -, * e /; as relações de ordem <, >, <= e >=; de igualdade == e !=; as operações booleanas and, or e not; as funções trigonométricas sin e asin; e as funções para decompor listas head, tail e nth. A escolha das funções básicas deve corresponder às necessidades que levam ao desenvolvimento da linguagem de programação. Por exemplo, o octave é uma linguagem de manipulação de matrizes numéricas e tem pré-definidas as respetivas operações.

No âmbito da ALisP é suficiente definir as funções base como um dicionário Python onde o nome da função está associado a um tuple com a aridade e uma expressão lambda (isto é, a versão Python das funções anónimas):

import math
BASE_FUNCTIONS = {
    #
    # Aritméticas
    #
    '+': (2, lambda x, y: x + y),
    '-': (2, lambda x, y: x - y),
    '*': (2, lambda x, y: x * y),
    '/': (2, lambda x, y: x / y),
    #
    # Ordem
    #
    '>': (2, lambda x, y: x > y),
    '>=': (2, lambda x, y: x >= y),
    '<': (2, lambda x, y: x < y),
    '<=': (2, lambda x, y: x <= y),
    #
    # Igualdade
    #
    '==': (2, lambda x, y: x == y),
    '!=': (2, lambda x, y: x != y),
    #
    # Booleanas
    #
    'not': (1, lambda x: not x),
    'and': (2, lambda x, y: x and y),
    'or': (2, lambda x, y: x or y),
    #
    # Trigonométricas
    #
    'sin': (1, lambda x: math.sin(x)),
    'asin': (1, lambda x: math.asin(x)),
    #
    # Listas
    #
    'head': (1, lambda x: x[0]),
    'tail': (1, lambda x: x[1:]),
    'nth': (2, lambda n, x: x[n]),
}

Esta representação das funções base pode ser facilmente modificada de forma a proporcionar, à partida, instruções adequadas ao domínio que se pretende trabalhar. Por exemplo, para computação gráfica 2D as funções base podem incluir os controlos de uma "tartaruga", forward, turn, up, down e set_color.

Contexto

O contexto é, essencialmente, um dicionário que associa o nome de cada variável ao respetivo valor. Além disso, é necessário considerar que as funções definem variáveis locais mas também têm acesso às variáveis externas.

Em

(seq
    (set x 21)
    (set dobro (fn (x)
        (* x 2)
    ))
    (set x (- x 1))
    (x (dobro 10))
)

a variável x é local e externa em dobro. Na última linha, (x (dobro 10)), tem o valor 20 no primeiro elemento e, quando a função dobro é evocada, é usado o valor local, 10, passado como argumento. O papel da instrução seq é esclarecido mais tarde.

A implementação do contexto é:

class ALisPContext:
    def __init__(self, outer):
        self.outer = outer
        self.local = dict()

    def defines(self, key):
        return key in self.local.keys() or key in self.outer.keys()

    def set(self, var_name, var_value):
        self.local[var_name] = var_value

    def keys(self):
        return self.local.keys() | self.outer.keys()

    def __getitem__(self, key):
        return self.value(key)

    def value(self, name):
        result = None
        #
        if name in self.local.keys():
            result = self.local[name]
        elif name in self.outer.keys():
            result = self.outer[name]
        elif name == 'True':
            return True
        elif name == 'False':
            return False
        elif is_atomic(name): # 42, -4.2, ola
            result = atom_value(name)
        #
        return result

ALisPContext Uma instância c de ALisPContext :

  • É construída em relação a um contexto "externo" (que pode ser o dicionário vazio, {}).

  • c.set(var_name, var_value) define uma associação da variável var_name ao valor var_value.

  • c.defines(key) testa se o nome key tem uma associação, local ou externa.

  • c.keys() devolve o conjunto das chaves, locais ou externas, conhecidas.

  • c[atom] ou c.value(atom) devolve, por ordem:

    1. O valor associado a name se existe essa associação a) local ou b) no contexto externo.
    2. Se name é "True" ou "False" os valores booleanos correspondentes.
    3. Se name é atómico (de acordo com is_atom) o respetivo valor calculado por atom_value.
    4. None.

O método interessante de ALisPContext é value que, além de obter os valores associados a uma variável local ou externa, ainda proporciona os valores dos átomos e das constantes booleanas.

Valoração

A valoração consiste em calcular o valor de uma representação, isto é, definir uma semântica da (representação) sintaxe.

Esse cálculo depende de um contexto, que mantém e atualiza os valores das variáveis.

Por exemplo, A palavra 2 + (3 * 4) tem representação ('+', 2, ('*', 3, 4)), obtida pelo analisador sintático. A esta representação corresponde o valor 14, que resulta de aplicar as respetivas operações aritméticas em cada nó, a começar pelas folhas.

Resumidamente, 14 é a semântica da sintaxe 2 + (3 * 4) e é calculada usando a representação intermédia ('+', 2, ('*', 3, 4)).

Em cada nó o conteúdo (daqui em diante representado por op) define a operação e os descendentes vão definir os valores dos argumentos (daqui em diante, args) dessa operação:

eval(('+', 2, ('*', 3, 4))) = 
    soma(eval(2), eval(('*', 3, 4))) =
    soma(2, mult(eval(3), eval(4))) =
    soma(2, mult(3, 4)) =
    soma(2, 12) =
    14

A valoração é uma função recursiva que, em cada nó (op, *args), calcula o valor dos argumentos *args e, depois, conforme o valor de op, combina esses valores no resultado correspondente.

Porém, um programa a correr define e consulta variáveis, escolhe ramos num condicional, etc.

O cálculo da valoração depende do contexto e das funções base. Um esquema incompleto da implementação segundo esses pressupostos será, por exemplo:

def eval(expr, context=None, ops=BASE_FUNCTIONS):
    if context is None:
        context = ALisPContext({})
    #
    #   expr is ATOM
    #
    context_value = context.value(expr)
    if context_value is not None:
        return context_value
    #
    #   expr is LIST
    #
    elif is_list(expr) and expr != NIL:
        #
        #   expr = (op args...)
        #
        op = head(expr)
        args = tail(expr)
        #
        # Use op and len(args) to do the right step
        # 
        if op in ops.keys():
            # BASE FUNCTIONS
        elif op == 'write' and len(args) == 1:
            # WRITE: (write MESSAGE)
        elif op == 'read' and len(args) == 0:
            # READ: (read)
        elif op == 'fn' and len(args) == 2:
            # FUNCTIONS: (fn ARGS INSTR)
        elif op == 'set' and len(args) == 2:
            # DEFINE/UPDATE VARIABLES: (set VAR VALUE) 
        elif op == 'while' and len(args) == 2:
            # CYCLES: (while GUARD INSTR)
        elif op == 'if' and len(args) == 3:
            # CONDITIONALS: (if COND TRUE_INSTR FALSE_INSTR)
        elif op == 'seq': 
            # SEQUENCE OF INSTRUCTIONS (LAST VALUE)
            # (seq *INSTR)
        elif is_list(op):
            # DEFER: (OP *ARGS)
        elif context.defines(op):
            # CONSULT VARIABLE: VAR
        else:
            # FALLBACK: (TERMINAL *REST)
    #
    #   expr is ALIEN... maybe raise error?
    #
    else:
        return expr

Funções Base

As funções base proporcionam alguma funcionalidade inicial e também uma ponte à linguagem hospedeira, o Python neste caso.

Para calcular o valor de uma função base como, por exemplo, (+ 2 3), fica op == "+", args == (2, 3) e os passos são:

  1. Verificar se op (neste caso, +) é uma chave no dicionário das funções base (ops).
  2. Validar a aridade (if len(args) >= arity).
  3. Chamar recursivamente eval nos argumentos: val_args = tuple(eval(x, context, ops) for x in args[:arity]).
  4. Devolver o valor da função associada a op quando aplicada aos valores dos argumentos: return func(*val_args).
#
# BASE FUNCTIONS
#
if op in ops.keys():
    arity, func = ops[op]
    if len(args) >= arity:
        val_args = tuple(eval(x, context, ops) for x in args[:arity])
        return func(*val_args)
    else:
        return None

Entrada/Saída

As funções de entrada e saída permitem interações com o utilizador via uma consola.

A sintaxe é:

  • (write MESSAGE) em que MESSAGE é um valor qualquer a ser escrito na consola.
  • (read) para ler um valor da consola.
  • A "real" interação ocorre via as funções correspondentes no Python: print para write e input para read.
  • No caso da saída (write):
    • É admitido exatamente um argumento.
    • Recursivamente, é calculado o valor desse argumento.
    • O valor, que é um tuple, é enviado para a consola (print) numa sintaxe compatível com ALisP (expr_repr).
  • Para a entrada (read):
    • Não são admitidos argumentos.
    • É lido o texto da consola via input.
    • Esse texto é analisado (parse).
    • Recursivamente, é calculado o valor da representação obtida na análise anterior.
#
# WRITE
#
elif op == 'write' and len(args) == 1:
    value = eval(args[0], context, ops)
    print(expr_repr(value))
    return value
#
# READ
#
elif op == 'read' and len(args) == 0:
    user_input = input()
    user_prog = parse(user_input)
    value = eval(user_prog, context, ops)
    return value

Funções

As funções, em ALisP são valores como as listas, números ou textos.

A sintaxe é (fn ARGS INSTR) em que fn é a instrução, ARGS é uma lista de variáveis e INSTR é uma lista de instruções.

Depois de criada uma função pode ser guardada numa variável para uso posterior.

Por exemplo:

(
    (set succ (fn (x) (+ x 1)))
    (succ 41)
    (succ 0)
)

As funções são o único caso em que eval não é recursiva. No exemplo acima:

  • Em (fn (x) (+ x 1)) é definido um certo valor.
  • No interpretador esse valor é uma instância da classe Lambda.
  • Essa instância é construída com os argumentos (x,) e ('+', 'x', 1) que são as representações de "(x)" e "(+ x 1)" respetivamente.
  • O valor do passo anterior é guardado na variável succ.
  • Mais tarde, na linha seguinte, (succ 41):
    • É criado um contexto local, onde x fica com o valor 41.
    • Nesse contexto é calculado o valor de (+ x 1), usando eval.
  • Na linha (succ 0) estes passos são repetidos, mas num novo contexto local em que x tem valor 0.

A criação do valor Lambda ocorre nas seguintes linhas:

#
# FUNCTIONS
#
elif op == 'fn' and len(args) == 2:
    fn_args = args[0]
    fn_expr = args[1]
    return Lambda(fn_args, fn_expr)

O cálculo das evocações é tratado mais tarde, com as variáveis.

Copiar

Um valor é copiado para uma variável que fica registada no contexto atual. Mais tarde esse valor pode ser recuperado como o valor da variável.

A sintaxe é (set VAR VALUE) em que VAR é um identificador e VALUE uma qualquer expressão ALisP.

  • Por exemplo, o seguinte programa tem valor 42:
(seq
    (set bad-answer 20)
    (set almost-good-answer (* 2 bad-answer))
    (+ almost-good-answer 2)
)

No lado do interpretador as instruções set atualizam o contexto da seguinte forma:

#
# DEFINE/UPDATE VARIABLES
#
elif op == 'set' and len(args) == 2:
    var_name = uq(args[0]) # Inelegant "dequotation" :(
    var_value = eval(args[1], context, ops)
    context.set(var_name, var_value)
    return var_value

Ciclos

Um ciclo repete um bloco de instruções enquanto uma certa condição é verdadeira.

A sintaxe é (while GUARD INSTR) em que GUARD é uma condição e INSTR um bloco de instruções.

  • Note bem que a ALisP tem valores booleanos True e False mas a condição pode ser qualquer valor. Os valores que também valem como False são 0, 0.0 e (). Todos os restantes valores valem como True.
  • Por exemplo, o ciclo seguinte escreve a "tabela" dos quadrados de 0 a 10:
(
    (set i 0)
    (while (<= i 10) (
        (write (i (* i i)))
        (set i (+ i 1))
    ))
)

A implementação dos ciclos ALisP usa os ciclos do Python:

#
# CYCLES
#
elif op == 'while' and len(args) == 2:
    guard = args[0]
    statements = args[1]
    last = NIL
    while eval(guard, context, ops):
        last = eval(statements, context, ops)
    return last

Condicionais

Um condicional corre um certo bloco de instruções, ou outro, conforme uma condição é verdadeira ou falsa.

A sintaxe é (if COND TRUE_INSTR FALSE_INSTR) em que COND é uma condição e TRUE_INSTR e FALSE_INSTR são blocos de instruções.

  • Note bem que a sintaxe "força" três argumentos.
  • Por exemplo, o valor de (seq (set a 10) (if (> a 0) positivo negativo)) é positivo.

Tal como nos ciclos, os condicionais do ALisP usam os do Python:

#
# CONDITIONALS
#
elif op == 'if' and len(args) == 3:
    cond, seq_true, seq_false = args
    if eval(cond, context, ops):
        return eval(seq_true, context, ops)
    else:
        return eval(seq_false, context, ops)

Com esta implementação apenas é percorrido, e calculado o valor do bloco que corresponde ao valor da condição.

Sequências

Uma sequência de instruções corre cada uma, por ordem, e devolve o valor da última instrução. A sequência vazia, (seq) vale a lista vazia, (), designada NIL.

A sintaxe é (seq *INSTR) em que *INSTR é uma sequência de instruções.

  • Note bem que *INSTR não é uma lista, mas os seus elementos.
  • Por exemplo:
    • O valor de (seq 0 1 2 3) é 3.
    • O valor de (seq (0 1 2 3)) é (0 1 2 3).
    • O valor de (seq (set a 40) (+ a 2)) é 42.

A implementação do valor para as sequências é:

#
# SEQUENCE OF INSTRUCTIONS (RETURNS ONLY THE LAST VALUE)
#
elif op == 'seq':
    if len(args) == 0:
        return NIL
    else:
        seq = eval(args, context, ops)
        return seq[-1]

Diferimento

Na ALisP o primeiro elemento de uma lista determina como é calculado o valor dessa lista. Pode-se evocar uma função, executar uma instrução ou apenas definir a lista dos valores.

Quando o primeiro elemento é também uma lista é preciso começar por determinar o seu valor para seguir no cálculo do valor da lista parente.

Isto é, cálculo do valor da lista parente é diferido pelo valor da lista que é o primeiro elemento.

Por exemplo, o valor de:

  1. (1 2 3) é (1 2 3).
  2. (+ 2 3) é 5.
  3. (if True 42 24) é 42.
  4. ((1 2 3) 2 3) é ((1 2 3) 2 3).
  5. ((if True + *) 2 3) é 5.
  6. ((if False + *) 2 3) é 6.

Nos três últimos exemplos, 4., 5. e 6., o primeiro elemento da lista é uma lista que vai definir o modo de calcular o valor da lista parente.

No caso ((1 2 3) 2 3) o valor do primeiro elemento é (1 2 3) que não é nem uma função nem uma instrução. Tal como no exemplo 1., a lista parente tem apenas valores.

Nos exemplos 5. e 6. o valor do primeiro elemento é, respetivamente, + e *. Portanto, o valor da lista parente vai ser diferido, respetivamente, para (+ 2 3) e (* 2 3).

A implementação do cálculo diferido é:

#
# LIST OF INSTRUCTIONS (RETURNS ALL THE VALUES)
#
elif is_list(op):
    op_val = eval(op, context, ops)
    args_vals = tuple([eval(xi, context, ops) for xi in args])
    expr2 = (op_val,) + args_vals
    if op_val == op:
        return expr2
    else:
        return eval(expr2, context, ops)

O teste if op_val == op deteta se o cálculo (não) vai ser diferido.

Variáveis e Evocação de Funções

Uma variável pode referir qualquer valor ALisP, guardado no contexto atual.

Quando esse valor é um tipo básico, inteiro, double, lista, string ou booleano, basta consultar o respetivo valor, guardado no contexto.

Quando a variável refere uma função é preciso calcular o valor da função com os argumentos dados.

Por exemplo, o valor de:

  1. (seq (set a 2) (+ a 40) é 42.
  2. (seq ((set a +)) (a 2 40) é 42. O duplo ((set a +)) é um hack para isolar o valor de (set a +), que é +, uma operação.
  3. (seq (set a (fn (x y) (+ x y))) (a 2 40)) é 42. Esse valor resulta de aplicar a função (fn (x y) (+ x y)) aos argumentos (2 40). O corpo e os argumentos desta função forma guardados no contexto, com nome a.

A implementação:

#
# CONSULT VARIABLE
#
elif context.defines(op):
    val = eval(op, context, ops)
    #
    #   Function evocation
    #
    if isinstance(val, Lambda):
        arity = len(val.args)
        if arity <= len(args):
            local_context = AlispContext(context)
            for i in range(arity):
                local_context.set(
                    val.args[i],
                    eval(args[i], context, ops))
            return eval(val.expr, local_context, ops)
        else:
            return None
    #
    #   Other types (number, text, list...)
    #
    else:
        expr2 = (val, ) + args
        return eval(expr2, context, ops)

Fallback

Se a "operação" não é um dos casos anteriores deve ser um terminal.

Por exemplo, (4 (+ 1 1)). Neste caso o resultado será (4 2).

A implementação:

#
# FALLBACK
#
else:
    return (op,) + eval(args, context, ops)

Exemplos

Funções Recursivas

O seguinte código ALisP define uma pequena biblioteca de funções que ilustram cálculos recursivos.

(
    (set fib (fn (x) 
        (if (<= x 1) 
            1 
            (+ 
                (fib (- x 1))
                (fib (- x 2)) )
        )
    ))

    (set fact (fn (n)
        (if (<= n 1)
            1
            (*  
                n 
                (fact (- n 1))
            )
        )
    ))
)

Guarde este código em, por exemplo, recursivas.lisp e experimente:

  • alisp.py -l recursivas.lisp -e "(fact 100)" e deve obter imediatamente o resultado, que é um número com 246 dígitos ;)
  • alisp.py -l recursivas.lisp -e "(fib 20)" demora um tempo considerável (alguns segundos) e o resultado é 10946.
  • Exercício. A implementação de fib é muito pouco eficiente (porque o mesmo cálculo é feito duas vezes em cada passo!). Modifique-a (substituindo a recursão por um ciclo) de forma a ter um desempenho melhor. Deve conseguir calcular rapidamente (fib 10000), que tem 2090 dígitos. Já fib 100000) demora alguns segundos e é um número com 20899 dígitos :D

Adivinhar o Número

O jogo Adivinha o número é um problema simples que permite testar várias caraterísticas de uma linguagem de programação.

  1. O programa define um número secreto, entre 0 e 100 e o jogador tem de adivinhar esse segredo.
  2. O programa pede um palpite ao jogador.
  3. Se a resposta do jogador está certa, o jogo termina. O programa dá os parabéns e diz quantas tentativas foram necessárias.
  4. Caso contrário, o programa responde maior ou menor conforme o segredo é maior ou menor que o palpite e volta a pedir um palpite.

Uma implementação do Adivinha o Número em ALisP:

(seq
    (set greet (fn (name)
        (Hello name . Welcome to the Guess-the-Number game.)
    ))

    (set ord (fn (n)
        (if (== 1 n)
            first
            (if (== 2 n)
                second
                (if (== 3 n)
                    third
                    (n -th)
                )
            )
        )
    ))

    (set main (fn ()
        (write (What is your name?))
        (set name (read))
        (write (greet name))
        (set my-secret 42)
        (set answer 50)
        (set count 0)
        (while (!= answer my-secret) (
            (set count (+ count 1))
            (write (Guess the secret number [(ord count) tentative]))
            (set answer (read))
            (write
                (if (== answer my-secret)
                    (Very well name . You found that the secret is ** my-secret ** using only count guesses.)
                    (Not yet, name . The secret is **
                        (if (< my-secret answer)
                            smaller
                            greater
                        )
                        ** than answer . Try again.
                    )
                )
            )
        ))
    ))

    (main)
    BYE
)

Conclusão

Definiu-se uma linguagem de programação, a ALisP, com sintaxe e a semântica largamente inspiradas/copiadas do Lisp, e implementou-se um interpretador:

  1. A sintaxe é definida por uma gramática LL(1).
  2. O processo da análise sintática produz uma representação intermédia do programa.
  3. A ALisP tem valores inteiros, double, string, booleanos, listas e funções anónimas.
  4. Os valores podem ser guardados em variáveis e consultados posteriormente.
  5. As instruções proporcionam ciclos e condicionais.
  6. A interação com o utilizador é feita através da consola.
  7. O interpretador pode ser inicializado com um conjunto de funções base adequadas a tarefas específicas de um determinado domínio.

Além da interpretação de expressões/instruções/programas são convenientes algumas utilidades, proporcionadas pelo programa alisp.py:

  • Uma forma de calcular diretamente o valor de uma expressão: alisp.py -e "(+ 40 2)".
  • Uma forma de correr um programa definido num ficheiro: alisp.py -l guess-the-number.lisp.
  • Uma forma de usar interativamente a linguagem: alisp.py --repl.
  • Estas formas pode ser combinadas, de forma a que, por exemplo, uma biblioteca de funções possa ser carregada para calcular uma expressão e/ou usada numa sessão interativa:
alisp.py -l functions.list -e "(set answer (dobro 21))" --repl

Exercícios

Em Construção

Exercício 01

Para cada um dos pares palavra/gramática seguintes, obtenha a estrutura simplificada da palavra na forma de uma árvore apenas com terminais nos nós.

  1. Emparelhe E → E + T | E - T | T ; T → T × F | T ÷ F | F ; F → N | ( E ), em que N representa qualquer número inteiro, com:
    1. 2, (2), 2 + 3, 2 × 3, (2 + 3).
    2. 2 + (3 × 4), 2 + 3 × 4 e (2 + 3) × 4.
    3. 2 + (3 + 4), 2 + 3 + 4 e (2 + 3) + 4.
    4. (2 + 3) × (3 + 4), 2 + (3 × 3) + 4, 2 + 3 × 3 + 4.
    5. (2 × 3) + (3 × 4), 2 × (3 + 3) × 4, 2 × 3 + 3 × 4.
  2. sequências; lisp;

Exercício 02

Os nós de árvores podem ser representadas por listas heterogéneas (suportadas diretamente, por exemplo, em Python) em que o primeiro elemento é o conteúdo do nó e os seguintes elementos são os descendentes. Por convenção, as folhas representam-se apenas pelo conteúdo (isto é, pelo valor 42 em vez da lista [42]). Implemente:

  • degree(a) o número de descendentes de a.
  • size(a) o número de nós em a.
  • tree_degree(a) o maior grau dos nós em a.
  • is_leaf(a) se a não tem descendentes.
  • is_inner(a) se a tem descendente.
  • is_parent(a, b) se a é ascendente direto de b.
  • is_neighbor(a, b) se a é ascendente direto de b ou vice-versa.
  • is_antecessor(a, b) se a é ascendente (direto, ou não) de b.
  • is_descendant(a, b) se a é descendente (direto, ou não) de a.
  • level(a, b): se b descende de a, o número de arestas do caminho que liga a a b; caso contrário, None.
  • width(a, n) o número de descendentes de a no nível n.
  • breadth(a) o número de folhas de a.
  • pesquisas; inserir; remover; podar; menor ascendente comum de dois nós;

Exercício 03

  • Revisitar exercícios de Python?
  • Funções anónimas (???)
    • Aplicações: map, filter, reduce

Exercício 04

  • Lisp (sbcl)

Exercício 05

E → T E₁
E₁ → + T E₁ | - T E₁ | λ
T → F T₁
T₁ → * F T₁ | / F T₁ | λ
F → ( E ) | N
N → D N₁
N₁ → λ | D N₁
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  • Verifique que a gramática acima é LL(1) e implemente uma calculadora na linha de comandos para efetuar contas simples como 2 + (3 * 4).

Exercício 06

  • Melhorar ALisP:
    • Incluir um gerador de números aleatórios nas funções base.
    • Corrigir atom_value de forma a prever o tipo do valor, em vez de levantar exceções.
    • Tratar adequadamente as string, delimitadas por ".
    • Suportar quote, de forma a suspender a valoração de uma expressão.
    • Mudar ALisP.value de forma a que True e False sejam sempre booleanos (não é o caso agora!)
  • Extensões ALisP
    • (range start end) (fechado-aberto).
    • (for var list instr)
    • (native "Python expr") como?
    • (pair key val), (update key val map), (get key map), (keys map)
    • (fn-map fn list), (filter pred list),