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?