Linguagens Formais e Autômatos - Léxico, Sintaxe e Semântica

Linguagens Formais

O artigo Linguagens Formais e Autômatos – Introdução nos apresentou que as Linguagens Formais preocupam-se com os problemas sintáticos das linguagens. Assim, inicialmente, é importante introduzir os conceitos de léxico, sintaxe e semântica de linguagens.

Historicamente, no estudo do entendimento das linguagens de programação, o problema sintático foi reconhecido antes do problema semântico e foi o primeiro a receber um tratamento adequado. Adicionalmente, os problemas sintáticos são de tratamento mais simples que os semânticos. Como consequência, foi dada uma grande ênfase à sintaxe, ao ponto de levar a ideia de que as questões das linguagens de programação resumiam-se às questões da sintaxe. Atualmente, a teoria da sintaxe possui construções matemáticas bem definidas e universalmente reconhecidas como, por exemplo, as Gramáticas de Chomsky.

Gramáticas de Chomsky é uma teoria que discute aspectos linguísticos, como a criatividade do falante e a sua capacidade de emitir e de compreender frases inéditas.

Uma linguagem de programação, de acordo com Menezes (2000), pode ser vista de duas formas. Primeiro, como uma entidade livre, ou seja, sem qualquer significado associado. Segundo, como uma entidade juntamente com uma interpretação do seu significado.

A sintaxe trata das propriedades livres da linguagem como a verificação gramatical de programas. A semântica objetiva dar uma interpretação para a linguagem como um significado ou valor para um determinado programa. Consequentemente, a sintaxe basicamente manipula símbolos sem considerar os seus correspondentes significados.

Enquanto que a sintaxe cuida do modo de como a informação é transmitida (estrutura) e a semântica zela pelo significado das palavras, o léxico é responsável por verificar o acervo de palavas pertencentes a determinada linguagem. Tendo em vista que toda língua tem como característica básica a mutabilidade, o léxico de um idioma não é finito.

Sintaticamente falando, não existe uma noção de programa "errado". Neste caso, simplesmente não é um programa. Por outro lado, um programa sintaticamente válido, pode ser o programa que o programador esperava escrever. Assim, a questão de considerar um programa "correto" ou "errado" deve considerar se o mesmo modela adequadamente o comportamento desejado.

Nem sempre os limites entre a sintaxe e a semântica são claros. Um exemplo é a ocorrência de um nome em um programa o qual pode ser tratado de forma igualmente fácil como um problema sintático ou semântico.

Aplicabilidade

Até aqui, sabemos que o léxico lida com o acervo de palavras pertencentes a determinada língua, a sintaxe trata da estrutura da palavra e a semântica é responsável pelo significado. Mas onde isso tudo é usado?! Um exemplo clássico é o compilador de uma determinada linguagem de programação.

Enquanto programava, você nunca se perguntou como o compilador sabe que o "if" é uma palavra reservada e "carro" não? Que entre o símbolo "+" deve ter dois operandos e que "9.5" deve ser atribuído a uma variável do tipo ponto flutuante?

Resumidamente, o compilador faz três tipos de análise (léxica, sintática e semântica). Veja a imagem abaixo:

Arquitetura de um Compilador

A análise léxica varre caractere por caractere, onde os símbolos especiais (espaço em branco, símbolos de pontuação (;) e nova linha) são utilizados para estabelecer os limites das palavras. Durante a análise, as palavras ou lexemas são guardados na tabela de símbolos e classificados de acordo com a linguagem, palavras reservadas, comandos, variáveis e tipos básicos. Ela divide o programa em tokens e faz uma classificação rápida dos mesmos quanto ao seu tipo, de forma que o analisador léxico saiba que "if" é uma palavra reservada, que "carro" é uma variável, que "84" é um literal inteiro e que "{" é um símbolo especial. É na análise léxica que os comentários são ignorados.

A fase de análise sintática verifica e forma os comandos da linguagem, de acordo com as regras especificadas pela gramática aplicada, ou seja, reconhece onde estão as instruções, classes, expressões, funções, métodos, procedimentos, parâmetros, operações etc. Entretanto, a fase sintática não é responsável por verificar se a estrutura faz sentido, pois ela apenas reconhece a mesma.

No fim da análise sintática, tem-se a representação do programa original de forma hierárquica, onde o programa é representando por uma árvore sintática (PARSE). Veja um exemplo na imagem abaixo:

Árvore Sintática

Observação: se você acompanha a série de artigos Lógica Proposicional, deve ter percebido uma certa semelhança entre a árvore sintática e a árvore de decomposição e composição de uma fórmula. Além da semelhança com a árvore de decomposição e composição de uma fórmula, a árvore sintática é vista no artigo contraste entre recursão e iteração - entendo diferenças e aplicações.

Até este momento, o compilador conhece a estrutura do código e sabe quais são palavras reservadas, comandos, variáveis e tipos básicos. Com tudo isso em "mãos" a análise semântica verifica a consistência de tipos dos operando envolvidos, ou seja, verifica se o código, como um todo, faz sentido.

Um exemplo utilizando a linguagem C:

...
if (n == 0) {
   return 1;
}
else {
   return 0;
}

Esse trecho de código verifica se o valor contido na variável n é igual a zero. Caso verdadeiro, retorna 1. Caso falso, retorna 0.

O analisador léxico irá percorre caractere por caractere, consultando a tabela de símbolos, para verificar e classificar cada um de acordo com a linguagem. Após a análise léxica, o trecho do código ficará assim:

Lexemas	Token
if	cod_if
(	cod_lpar
n	id, n
==	cod_equals
0	intLit, 0
)	cod_rpar
{	cod_lcur
return	cod_return
1	intLit, 1
;	cod_comm
}	cod_rcur
else	cod_else
{	cod_lcur
return	cod_return
0	intLit, 0
;	cod_comm
}	cod_rcur

Observação: os tokens não fazem parte do compilador do C. Eles servem para ilustrar a ideia da análise léxica.

O analisador sintático recebrá o código classificado pelo analisador léxico, para que seja construída a árvore sintática. Após a análise sintática, a árvore ficará assim:

Árvore sintática do bloco condicional "if"

Árvore sintática do bloco condicional "else"

Com a árvore sintática, o analisador semântico verificará se as expressões fazem sentido. Por exemplo, ele irá verificar se a expressão está abrindo e fechando parênteses. Se uma variável do tipo inteiro está recebendo um número inteiro e não uma letra ou um número de ponto flutuante.

O que você aprendeu

Este artigo teve o objetivo de sanar a dúvida entre o que é léxico, sintaxe e semântica, e suas responsabilidades. Citamos uma aplicabilidade do léxico, da semântica e da sintaxe. Especificamente, você aprendeu:

• O que é léxico.
• O que é sintaxe.
• O que é semântica.
• Aplicabilidade do léxico, sintaxe e semântica.
• Os analisadores de um compilador.

Antes de prosseguir o estudo de linguagens formais e autômatos, é necessário que o leitor tenha conhecimento, mesmo que básico, em Lógica Proposicional e Teoria dos Conjuntos.

Continua em
Linguagens Formais e Autômatos – Alfabetos, Palavras, Linguagens e Gramáticas

Continuação de
Linguagens Formais e Autômatos – Introdução

Referência Bibliográfica
HOPCROFT, J. E; ULLMAN, J. D; MOTWANI, R. Introdução à Teoria de Autômatos, Linguagens e Computação. 02. ed. Nova York: Elsevier, 2002. 584 p.

MENEZES, P. B. Linguagens Formais e Autômatos. 03. ed. Porto Alegre: Sagra Luzzatto, 2000. 165 p.

PINHEIRO, A. F. Revista Fundamentos da Engenharia de Software: autômatos, Recife, v. 5, 2017.

Para citar esse artigo: