Análise Léxica e Sintática

A análise léxica e sintática formam o front-end de um compilador, dividindo o texto-fonte em tokens e reconhecendo sua estrutura gramatical como uma árvore de análise ou sintaxe.

Definition

A análise léxica é a fase que agrupa caracteres de entrada em tokens, e a análise sintática (parsing) é a fase que determina se e como esses tokens formam um programa válido de acordo com uma gramática, produzindo uma árvore de sintaxe.

Scope

Este tópico abrange a análise léxica, que converte fluxos de caracteres em tokens usando linguagens regulares e autômatos finitos, e a análise sintática (parsing), que reconhece a estrutura de frase de um programa em relação a uma gramática livre de contexto. Inclui parsing top-down (LL) e bottom-up (LR), geradores de parser, ambiguidade e recuperação de erros, e a construção de árvores de sintaxe abstrata.

Core questions

• Como as linguagens regulares e livres de contexto são usadas para descrever a estrutura do programa?
• Quais são as vantagens e desvantagens entre o parsing LL e LR?
• Como a ambiguidade e os erros de análise são detectados e tratados?
• Como uma árvore de sintaxe abstrata é construída a partir de um fluxo de tokens?

Key theories

Parsing LR

Knuth introduziu o parsing LR, uma técnica bottom-up que analisa deterministicamente a ampla classe de gramáticas LR em tempo linear, formando a base de muitos geradores de parser.

Parsing geral livre de contexto

O algoritmo de Earley analisa gramáticas arbitrárias livres de contexto, incluindo as ambíguas, fornecendo um método geral quando parsers determinísticos restritos são insuficientes.

Fundamentos regulares e livres de contexto do front-end

O Dragon Book sistematiza o uso de expressões regulares e autômatos finitos para varredura e gramáticas livres de contexto para análise, incluindo os algoritmos padrão de construção LL e LR.

Clinical relevance

A análise léxica e sintática são fundamentais não apenas para compiladores, mas também para interpretadores, linters, formatadores, IDEs e processadores de formato de dados. Um parsing robusto com boa recuperação de erros é essencial para a experiência do desenvolvedor de qualquer ferramenta de linguagem.

History

A hierarquia de linguagens formais de Chomsky no final da década de 1950 forneceu a teoria das linguagens regulares e livres de contexto. Knuth formalizou o parsing LR em 1965, e Earley apresentou um algoritmo geral livre de contexto em 1970. Geradores de parser como o yacc tornaram o parsing LR prático, enquanto trabalhos posteriores exploraram gramáticas de expressão de parsing e parsers baseados em combinadores.

Debates

Parsers gerados versus escritos à mão

Profissionais debatem o uso de geradores de parser a partir de gramáticas formais, que são concisos e verificáveis, em oposição a parsers de descida recursiva escritos à mão, que frequentemente fornecem melhores mensagens de erro e controle, ao custo de mais código.

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

Qual é a diferença entre um lexer e um parser?

Um lexer agrupa caracteres brutos em tokens, como identificadores e operadores, enquanto um parser organiza esses tokens em uma árvore de sintaxe hierárquica de acordo com a gramática da linguagem.

Qual é a diferença entre o parsing LL e LR?

Parsers LL funcionam de cima para baixo, prevendo produções a partir do prefixo de entrada, enquanto parsers LR funcionam de baixo para cima, reduzindo substrings reconhecidas; LR lida com uma classe estritamente maior de gramáticas, mas é mais complexo de construir.