sebesta 9ed_Linguagem_Programacao

Prévia do material em texto

Capítulo 1
Aspectos Preliminares
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 1
• Razões para estudar conceitos de linguagens de programação
• Domínios de programação 
• Critérios de avaliação de linguagens
• Influências no projeto de linguagens
• Categorias de linguagens
• Trade-offs no projeto de linguagens
• Métodos de implementação
• Ambientes de programação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Razões para estudar conceitos 
de linguagens de programação
• Capacidade aumentada para expressar ideias
• Embasamento melhorado para escolher linguagens apropriadas
• Habilidade aumentada para aprender novas linguagens
• Melhor entendimento da importância da implementação
• Melhor uso de linguagens já conhecidas
• Avanço geral da computação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Domínios de programação
• Aplicações científicas
– Grande número de computações de aritmética de ponto flutuante; uso de matrizes
– Fortran
• Aplicações empresariais
– Produz relatório, usa números decimais e caracteres
– COBOL
• Inteligência artificial
– Símbolos em vez de números manipulados; uso de listas ligadas
– LISP
• Programação de sistemas
– Precisa de eficiência por causa do uso contínuo
– C
• Software para a Web
– Eclética coleção de linguagens: de marcação (como XHTML), de scripting (como PHP), 
de propósito geral (como Java)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Critérios de avaliação de linguagens
• Legibilidade: facilidade com a qual os programas podem ser lidos e 
entendidos
• Facilidade de escrita: facilidade com a qual uma linguagem pode ser 
usada para criar programas para um dado domínio
• Confiabilidade: conformidade com as especificações
• Custo: o custo total definitivo de uma linguagem
Conceitos de Linguagens de Programação – Robert W. Sebesta
Critério de avalição: legibilidade
• Simplicidade geral
– Um conjunto controlável de recursos e construções
– Mínima multiplicidade de recursos
– Mínima sobrecarga de operadores
• Ortogonalidade
– Um conjunto relativamente pequeno de construções primitivas pode ser combinado a 
um número relativamente pequeno de formas
– Cada possível combinação é legal
• Tipos de dados
– Mecanismos adequados para definir tipos de dados
• Projeto da sintaxe
– Formato dos identificadores
– Palavras especiais e métodos de formar sentenças compostas
– Forma e significado: construções autodescritivas, palavras-chave significativas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Critério de avaliação: facilidade de escrita
• Simplicidade e ortogonalidade
– Poucas construções, número pequeno de primitivas e um pequeno 
conjunto de regras para combiná-las
• Suporte à abstração
– A habilidade de definir e usar estruturas ou operações complicadas de 
forma a permitir que muitos dos detalhes sejam ignorados
• Expressividade
– Um conjunto de formas relativamente convenientes de especificar as 
operações
– Força e número de operadores e funções pré-definidas 
Conceitos de Linguagens de Programação – Robert W. Sebesta
Critério de avaliação: confiabilidade
• Verificação de tipos
– Testes para detectar erros de tipos
• Tratamento de exceções
– Interceptar erros em tempo de execução e tomar medidas corretivas
• Utilização de apelidos
– Nomes distintos que podem ser usados para acessar a mesma célula de 
memória
• Legibilidade e facilidade de escrita
– Uma linguagem que não oferece maneiras naturais para expressar os 
algoritmos requeridos irá necessariamente usar abordagens não naturais, 
reduzindo a confiabilidade
Conceitos de Linguagens de Programação – Robert W. Sebesta
Critério de avaliação: custo
• Treinar programadores para usar a linguagem
• Escrever programas (proximidade com o propósito da aplicação em 
particular)
• Compilar programas
• Executar programas
• Sistema de implementação da linguagem: disponibilidade de 
compiladores gratuitos
• Confiabilidade baixa leva a custos altos
• Manter programas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Critério de avaliação: outros
• Portabilidade
– A facilidade com a qual os programas podem ser movidos de uma 
implementação para outra
• Generalidade
– A aplicabilidade a uma ampla faixa de aplicações
• Bem definida
– Em relação à completude e à precisão do documento oficial que define a 
linguagem
Conceitos de Linguagens de Programação – Robert W. Sebesta
Influências no projeto de linguagens
• Arquitetura de computadores
– Linguagens são projetadas considerando a principal arquitetura de 
computadores, chamada de arquitetura de von Neumann
• Metodologias de projeto de programas
– Novas metodologias de desenvolvimento de software (por exemplo, 
desenvolvimento de software orientado a objeto) levaram a novos 
paradigmas de programação e, por extensão, a novas linguagens de 
programação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Influências na arquitetura de computadores
• Principal arquitetura de computadores: von Neumann 
• Linguagens imperativas, mais populares, por causa dos computadores 
von Neumann
– Dados e programas armazenados na memória
– A memória é separada da CPU
– Instruções e dados são canalizadas a partir da memória para CPU
– Base para linguagens imperativas
• Variáveis modelam as células de memória
• Sentenças de atribuição são baseadas na operação de envio de dados 
e instruções
• Iteração é eficiente
Conceitos de Linguagens de Programação – Robert W. Sebesta
Arquitetura Von Neumann
Conceitos de Linguagens de Programação – Robert W. Sebesta
Arquitetura Von Neumann
• Ciclo de obtenção e execução (em um computador com arquitetura 
von Neumann)
inicialize o contador de programa
repita para sempre
obtenha a instrução apontada pelo contador de programa
incremente o contador de programa
decodifique a instrução
execute a instrução
fim repita
Conceitos de Linguagens de Programação – Robert W. Sebesta
Influências na metodologia de programa
• Anos 1950 e começo dos 1960: Aplicações simples; preocupação com 
a eficiência da máquina
• Final dos anos 60: Eficiência das pessoas se tornou importante; 
legibilidade, melhores estruturas de controle
– Programação estruturada
– Projeto descendente (top-down) e de refinamento passo a passo
• Final dos anos 70: Da orientação aos procedimentos para uma 
orientação aos dados 
– Abstração de dados
• Meio dos anos 80: Programação orientada a objetos
– Abstração de dados + herança + vinculação dinâmica de métodos
Conceitos de Linguagens de Programação – Robert W. Sebesta
Categorias de linguagens
• Imperativa
– Características centrais são variáveis, sentenças de atribuição e de iteração
– Inclui linguagens que suportam programação orientada a objeto
– Inclui linguagens de scripting
– Inclui as linguagens visuais
– Exemplos: C, Java, Perl, JavaScript, Visual BASIC .NET, C++
• Funcional
– Principais meios de fazer os cálculos é pela aplicação de funções para determinados 
parâmetros
– Exemplos: LISP, Scheme
• Lógica
– Baseada em regras (regras são especificadas sem uma ordem em particular)
– Example: Prolog
• De marcação/programação híbrida 
– Linguagens de marcação estendida para suportar alguma programação
– Exemplos: JSTL, XSLT
Conceitos de Linguagens de Programação – Robert W. Sebesta
Trade-Offs no projeto de linguagens
• Confiabilidade x custo de execução
– Exemplo: Java exige que todas as referências aos elementos de um vetor 
sejam verificadas para garantir que os índices estão em suas faixas legais
• Legibilidade x facilidade de escrita
– Exemplo: APL inclui um poderoso conjunto de operadores (e um grande 
número de novos símbolos), permitindo que computações complexas 
sejam escritas em um programa compacto, com o custo de baixa 
legibilidade
• Facilidade de escrita (flexibilidade) x confiabilidade
– Exemplo: Ponteiros de C++ são poderosos e flexíveis, mas não são 
confiáveis
Conceitos de Linguagens de Programação – Robert W. SebestaMétodos de implementação
• Compilação
– Programas são traduzidos para linguagem de máquina
• Interpretação pura
– Programas são interpretados por outro programa chamado interpretador
• Sistemas de implementação híbridos
– Um meio termo entre os compiladores e os interpretadores puros
Conceitos de Linguagens de Programação – Robert W. Sebesta
Visão em camadas de um computador
O Sistema operacional e as 
implementações de 
linguagem são colocados 
em camadas superiores à 
interface de linguagem de 
máquina de um 
computador
Conceitos de Linguagens de Programação – Robert W. Sebesta
Compilação
• Traduz programas (linguagem de fonte) em código de máquina 
(linguagem de máquina)
• Tradução lenta, execução rápida
• Processo de compilação tem várias fases: 
– análise léxica: agrupa os caracteres do programa fonte em unidades 
léxicas
– análise sintática: transforma unidades léxicas em árvores de análise 
sintática (parse trees), que representam a estrutura sintática do programa
– análise semântica: gera código intermediário
– geração de código: código de máquina é gerado
Conceitos de Linguagens de Programação – Robert W. Sebesta
O processo de compilação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Terminologias de compilação adicionais
• Módulo de carga (imagem executável): o código de usuário e de 
sistema juntos
• Ligação e carga: o processo de coletar programas de sistema e ligá-los 
aos programas de usuário
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gargalo de Von Neumann
• A velocidade de conexão entre a memória de um computador e seu 
processador determina a velocidade do computador
• Instruções de programa normalmente podem ser executadas mais 
rapidamente do que a velocidade de conexão, o que resulta em um 
gargalo
• Conhecido como gargalo de von Neumann; é o fator limitante primário 
na velocidade dos computadores
Conceitos de Linguagens de Programação – Robert W. Sebesta
Interpretação pura
• Sem tradução
• Fácil implementação de programas (mensagens de erro em tempo de 
execução podem referenciar unidades de código fonte)
• Execução mais lenta (tempo de execução de 10 a 100 vezes mais lento 
do que nos sistemas compilados)
• Geralmente requer mais espaço
• Raramente usada em linguagens de alto nível
• Volta significativa com algumas linguagens de scripting para a Web 
(como JavaScript e PHP)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Processo de interpretação pura
Conceitos de Linguagens de Programação – Robert W. Sebesta
Sistemas de implementação híbridos
• Um meio termo entre os compiladores e os interpretadores puros
• Uma linguagem de alto nível é traduzida para uma linguagem 
intermediária que permite fácil interpretação
• Mais rápido do que interpretação pura
• Exemplos
– Programas em Perl eram parcialmente compilados para detectar erros 
antes da interpretação
– As primeiras implementações de Java eram todas híbridas; seu formato 
intermediário, byte code, fornece portabilidade para qualquer máquina que 
tenha um interpretador de bytecodes e um sistema de tempo de execução 
associado (juntos, são chamados de Máquina Virtual Java)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Sistema de implementação híbrido
Conceitos de Linguagens de Programação – Robert W. Sebesta
Sistemas de implementação Just-in-Time
• Inicialmente traduz os programas para uma linguagem intermediária
• Então, compila os métodos da linguagem intermediária para linguagem 
de máquina quando esses são chamados
• A versão em código de máquina é mantida para chamadas 
subsequentes
• Sistemas JIT são agora usados amplamente para programas Java
• As linguagens .NET também são implementadas com um sistema JIT
Conceitos de Linguagens de Programação – Robert W. Sebesta
Pré-processadores
• As instruções de pré-processador são comumente usadas para 
especificar que o código de outro arquivo deve ser incluído
• Um pré-processador é um programa que processa um programa 
imediatamente antes de o programa ser compilado para expandir 
macros embutidos
• Um exemplo conhecido: pré-processador de C
– expande #include, #define e macros similares
Conceitos de Linguagens de Programação – Robert W. Sebesta
Ambientes de programação
• Coleção de ferramentas usadas no desenvolvimento de software
• UNIX
– Um ambiente de programação mais antigo
– Agora bastante usado por meio de uma interface gráfica com o usuário 
(GUI) que roda sobre o UNIX
• Microsoft Visual Studio .NET
– Grande e complexo
• Usado para desenvolver software em qualquer uma das cinco 
linguagens .NET
• NetBeans
– Usado primariamente para o desenvolvimento de aplicações Web usando 
Java, mas também oferece suporte a JavaScript, Ruby e PHP
Conceitos de Linguagens de Programação – Robert W. Sebesta
Resumo
• O estudo de linguagens de programação é valioso por diversas razões:
– Aumenta nossa capacidade de usar diferentes construções ao escrever 
programas
– Permite que escolhamos linguagens para os projetos de forma mais 
inteligente
– Torna mais fácil o aprendizado de novas linguagens
• Critérios mais importantes para a avaliação de linguagens:
– Legibilidade, facilidade de escrita, confiabilidade e custo geral
• As principais influências no projeto de linguagens são a arquitetura de 
máquina e as metodologias de projeto de software
• Os principais métodos de implementar linguagens de programação são 
a compilação, a interpretação pura e a implementação híbrida
Capítulo 2
Evolução das Principais 
Linguagens 
de Programação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 2
• Plankalkül de Zuse
• Programação de hardware mínima: pseudocódigos
• O IBM 704 e Fortran
• Programação funcional: LISP
• O primeiro passo em direção à sofisticação: ALGOL 60
• Informatizando os registros comerciais: COBOL
• O início do compartilhamento de tempo: BASIC
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 2
• Tudo para todos: PL/I
• Duas das primeiras linguagens dinâmicas: APL e SNOBOL
• O início da abstração de dados: SIMULA 67
• Projeto ortogonal: ALGOL 68
• Alguns dos primeiros descendentes dos ALGOLs
• Programação baseada em lógica: Prolog
• O maior esforço de projeto da história: Ada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 2
• Programação orientada a objetos: Smalltalk
• Combinando recursos imperativos e orientados a objetos: C++
• Uma linguagem orientada a objetos baseada no paradigma imperativo: 
Java
• Linguagens de scripting
• Uma linguagem baseada em C para o novo milênio: C#
• Linguagens híbridas de marcação/programação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Genealogia das principais linguagens 
de programação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Plankalkül de Zuse
• Desenvolvida em 1945, mas não publicada até 1972
• Nunca foi implementada
• Estruturas de dados avançadas
– Ponto flutuante, vetores, registros
• Invariante
Conceitos de Linguagens de Programação – Robert W. Sebesta
Sintaxe de Plankalkül
• Uma sentença de atribuição que atribui o valor da expressão A[4] + 1 
para A[5]
| A + 1 => A
V | 4 5 (índices)
S | 1.n 1.n (tipos de dados)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Programação de Hardware Mínima: 
Pseudocódigos
• O que estava errado ao usar código de máquina?
– Baixa legibilidade
– Modificações de programas tediosas e passíveis de erros
– Deficiências de máquina – sem indexação ou ponto-flutuante
Conceitos de Linguagens de Programação – Robert W. Sebesta
Pseudocódigos: Short Code 
• Short Code foi desenvolvida por John Mauchly em 1949 para o 
computador BINAC
– Expressões foram codificadas
– Exemplo de operações:
01 – 06 abs value 1n (n+2)nd power
02 ) 07 + 2n (n+2)nd root
03 = 08 pause 4n if <= n
04 / 09 ( 58 print and tab
Conceitos de Linguagens de Programação – RobertW. Sebesta
Pseudocódigos: Speedcoding
• Speedcoding foi desenvolvido por John Backus em 1954 para 
o IBM 701
– Pseudoinstruções para operações aritméticas e funções matemáticas
– Desvios condicionais e incondicionais
– Facilidade para incrementar os registradores de endereço 
automaticamente
– Memória usável restante após carregar o interpretador de apenas 700 
palavras
Conceitos de Linguagens de Programação – Robert W. Sebesta
Pseudocódigos: Related Systems
• O sistema de “compilação” da UNIVAC
– Devenvolvido por uma equipe liderada por Grace Hopper
– Pseudocódigo expandido em código de máquina
• David J. Wheeler (Universidade de Cambridge) 
– desenvolveu um método de usar blocos de endereços realocáveis para 
resolver parcialmente o problema do endereçamento absoluto
Conceitos de Linguagens de Programação – Robert W. Sebesta
IBM 704 e Fortran
• Fortran 0: 1954 – não implementado
• Fortran I: 1957
– Desenvolvido para o IBM 704, que tinha registros de indexação e 
hardware de ponto-flutuante
– Levou à ideia de linguagens de programação compiladas, porque não 
havia o esconderijo para o custo da interpretação
– Ambiente de desenvolvimento
• Computadores com memórias pequenas e não confiáveis
• Aplicações eram científicas
• Não havia maneiras eficientes de programar computadores
• Velocidade do código objeto era o objetivo principal
Conceitos de Linguagens de Programação – Robert W. Sebesta
Processo de projeto do Fortran
• Impacto do ambiente no processo do Fortran I
– Não há necessidade de armazenamento dinâmico
– Precisa de boa manipulação de vetores e sentenças de repetição
– Sem manipulação de cadeias, aritmética decimal ou sentenças de entrada 
e saída (para aplicações de negócios)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Visão geral de Fortran I
• Primeira versão implementada do Fortran
– Nomes de variáveis podem ter até seis caracteres
– Sentença de repetição (DO)
– Formatação de entrada e saída
– Sub-rotinas definidas pelos usuários
– Sentença de seleção IF
Conceitos de Linguagens de Programação – Robert W. Sebesta
Visão geral de Fortran I
• Primeira versão implementada do FORTRAN 
– Sem compilação separada
– Compilador lançado em abril de 1957, depois de 18 anos de trabalho
– Programas com mais de 400 linhas raramente são compilados 
corretamente, especialmente devido à pouca confiabilidade do 704
– O código era muito rápido
– Rapidamente se tornou amplamente usado
Conceitos de Linguagens de Programação – Robert W. Sebesta
Fortran II
• Distribuído em 1958
– Compilação independente
– Corrigiu falhas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Fortran IV
• Evoluiu entre 1960-62
– Declarações de tipo explícitas
– Sentenças de controle de laços lógicos
– Nomes de subprogramas podem ser parâmetros
– Padrão ANSI em 1966
Conceitos de Linguagens de Programação – Robert W. Sebesta
Fortran 77
• Tornou-se o novo padrão em 1978
– Manipulação de caracteres de cadeias
– Sentenças de controle de laços lógicos
– Um If com uma cláusula opcional Else
Conceitos de Linguagens de Programação – Robert W. Sebesta
Fortran 90
• Drasticamente diferente do Fortran 77
– Módulos
– Vetores dinâmicos
– Ponteiros
– Registros
– Sentença CASE
– Parâmetro de verificação de tipo
Conceitos de Linguagens de Programação – Robert W. Sebesta
Últimas versões de Fortran
• Fortran 95 – apenas algumas mudanças
• Fortran 2003 - idem
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação de Fortran
• Compiladores altamente otimizados (todas as versões antes de 90)
– Tipos e armazenamento para todas as variáveis são fixados antes 
da execução
• Mudou drasticamente para sempre a forma como os computadores 
são usados
• Caracterizada como a língua franca do mundo da computação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Programação funcional: LISP
• List Processing Language
– Projetada no MIT por McCarthy
• Pesquisa de inteligência artificial (IA) precisava de uma linguagem para
– Processar dados em listas (em vez de vetores)
– Computação simbólica (em vez de numérica)
• Apenas dois tipos de dados: átomos e listas
• Sintaxe é baseada em lambda calculus
Conceitos de Linguagens de Programação – Robert W. Sebesta
Representação interna de duas listas 
em LISP
Representando as listas (A B C D)
e (A (B C) D (E (F G)))
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação de LISP
• Pioneira na programação funcional
– Sem necessidade de variáveis ou atribuição 
– Controle por recursão e expressões condicionais
• Ainda a linguagem dominante em IA
• COMMON LISP e Scheme são dialetos contemporâneos de LISP
• ML, Miranda e Haskell são linguagens relacionadas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Scheme
• Desenvolvida no MIT no meio dos anos 1970
• Pequena
• Uso de escopo estático
• Funções como entidades de primeira classe
• Sintaxe simples (e tamanho pequeno) o que a torna ideal para 
aplicações educacionais
Conceitos de Linguagens de Programação – Robert W. Sebesta
COMMON LISP
• Um esforço para para combinar características de diversos dialetos de 
LISP em uma só linguagem
• Grande, complexa
Conceitos de Linguagens de Programação – Robert W. Sebesta
O Primeiro Passo em Direção à Sofisticação: 
ALGOL 60
• Ambiente de desenvolvimento
– FORTRAN chegou (apenas) para IBM 700
– Várias outras linguagens foram desenvolvidas, todas para máquinas 
específicas
– Nenhuma linguagem portátil; todas eram dependentes das máquinas
– Nenhuma linguagem universal para comunicação de algoritmos
• ALGOL 60 foi o resultado dos esforços para criar uma linguagem 
universal
Conceitos de Linguagens de Programação – Robert W. Sebesta
Processo do projeto inicial
• ACM e GAMM se reuniram por quatro dias (De 27 de maio a 1º de 
junho de 1958)
• Objetivos da linguagem
– Ser o mais próxima possível da notação padrão matemática
– Boa para a descrição de algoritmos
– Ser traduzível em código de máquina
Conceitos de Linguagens de Programação – Robert W. Sebesta
ALGOL 58
• Formalizou conceito de tipo de dados
• Identificadores podiam ter qualquer tamanho
• O limite inferior dos vetores podia ser especificado pelo programador
• Parâmetros eram separados por modo
• Sentenças de seleção aninhadas eram permitidas
• Declarações compostas (begin ... end)
• Vírgula como separador de declarações
• Operador de atribuição era :=
• if tinha uma cláusula else-if
Conceitos de Linguagens de Programação – Robert W. Sebesta
Implementação do ALGOL 58
• Não pretendia ser um produto finalizado para implementação, mas 
variações dele foram (MAD, JOVIAL)
• Embora a IBM tenha sido inicialmente entusiasta, todo o suporte foi 
descontinuado em meados de 1959
Conceitos de Linguagens de Programação – Robert W. Sebesta
Visão geral do ALGOL 60
• Modificação do ALGOL 58 em seis dias de encontros em Paris
• Novos recursos
– Estrutura de bloco (escopo local)
– Duas formas diferentes de passagem de parâmetros a subprogramas
– Procedimentos recursivos
– Vetores dinâmicos na pilha
– Ainda sem sentenças de entrada e saída e sem manipulação de cadeias
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação do ALGOL 60
• Sucessos
– Única maneira formal aceitável de comunicar algoritmos por mais 
de 20 anos
– Todas as linguagens de programação imperativas desde 60 são 
baseadas nela
– Primeira linguagem independente de máquina 
– Primeira linguagem cuja sintaxe foi formalmente descrita (BNF)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação do ALGOL 60
• Fracassos
– Nunca atingiu uso disseminado, especialmente nos Estados Unidos
– Motivos
• Entrada e saída dependentes fizeram com que os programas tivessem uma 
portabilidade ruim
• Muito flexível – difícil de implementar
• Forte estabelecimento do Fortran
• Descrição formal de sintaxe
• Falta de apoio da IBM
Conceitos de Linguagens de Programação – Robert W. Sebesta
Informatizando os Registros Comerciais:COBOL
• Ambiente de desenvolvimento
– UNIVAC estava começando a usar FLOW-MATIC
– USAF estava começando a usar AIMACO
– IBM estava desenvolvendo COMTRAN
Conceitos de Linguagens de Programação – Robert W. Sebesta
Perspectiva história do COBOL
• Baseado em FLOW-MATIC
• Características de FLOW-MATIC 
– Nomes com mais de 12 caracteres, com hifens
– Nomes em inglês para operações aritméticas (sem expressões 
aritméticas)
– Dados e código eram completamente separados
– A primeira palavra em cada sentença era um verbo
Conceitos de Linguagens de Programação – Robert W. Sebesta
O processo do projeto do COBOL
• Primeira reunião (no Pentágono) – Maio de 1959
• Objetivos
– Utlizar o inglês o máximo possível
– Ser fácil de usar, mesmo ao custo de ser menos poderosa
– Ampliar a base de usuários de computador
– Não ser orientada pelos problemas atuais do compilador
• Membros da comissão do projeto foram de fabricantes de 
computadores e membros do Departamento de Defesa Americano 
(DoD)
• Problemas de projeto: expressões aritméticas? subscripts? Disputas 
entre os fabricantes
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação do COBOL
• Contribuições
– Primeira construção para macros de uma linguagem de alto nível
– Estruturas de dados hierárquicas (registros)
– Sentenças de seleção aninhadas
– Nomes longos (até 30 caracteres), com hifens
– Divisão de dados
Conceitos de Linguagens de Programação – Robert W. Sebesta
COBOL: influência do DoD
• Primeira linguagem requerida pelo DoD
– Teria falhado sem o DoD
• Ainda assim, o idioma mais utilizado em aplicações de negócios
Conceitos de Linguagens de Programação – Robert W. Sebesta
O Início do compartilhamento de tempo: BASIC
• Projetado por Kemeny e Kurtz em Dartmouth
• Objetivos:
– Ser fácil para estudantes que não são de ciências básicas aprenderem 
– Ser prazerosa e amigável
– Agilizar os deveres de casa
– Permitir acesso livre e privado
– Considerar o tempo do usuário mais importante do que o tempo 
do computador
• Dialeto popular à época: Visual BASIC 
• Primeira linguagem amplamente utilizada com o tempo de 
compartilhamento
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tudo para todos: PL/I
• Desenvolvida por IBM e SHARE
• Situação da computação em 1964 (do ponto de vista da IBM)
– Aplicação científica
• Computadores IBM 1620 e 7090
• FORTRAN
• Grupo de usuário SHARE
– Aplicação de negócios
• Computadores IBM 1401 e 7080
• COBOL
• Grupo de usuário GUIDE
Conceitos de Linguagens de Programação – Robert W. Sebesta
Perspectiva histórica
• Em 1963 
– Programadores científicos passaram a precisar de recursos mais 
elaborados de entrada e saída, como COBOL tinha; as aplicações de 
negócios precisavam de dados de ponto-flutuante e vetores para sistemas 
de informação de gerenciamento
– Começou a parecer que as instalações de computação logo precisariam 
de duas equipes técnicas e de computadores diferentes 
• A solução óbvia 
– Construir um novo computador para fazer os dois tipos de aplicações
– Projetar uma nova linguagem para as aplicações
Conceitos de Linguagens de Programação – Robert W. Sebesta
O processo de projeto
• Desenvolvido em cinco meses pelo Comitê 3 x 3
– Três membros da IBM, três membros do SHARE
• Projeto inicial
– Uma extensão do Fortran IV
• Inicialmente chamado de NPL (New Programming Language - Nova 
Linguagem de Programação)
• Nome mudado para PL/I em 1965
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação de PL/I
• Contribuições
– Permitido aos programas criar subprogramas executados 
concorrentemente
– Possível detectar e manipular exceções
– Permitida a utilização de subprogramas recursivamente
– Ponteiros foram incluídos como um tipo de dados
– Porções de uma matriz podiam ser referenciadas
• Preocupações
– Muitos dos novos recursos foram mal concebidos
– Muito grande e muito complexo
Conceitos de Linguagens de Programação – Robert W. Sebesta
Duas das primeiras linguagens dinâmicas: APL 
e SNOBOL
• Caracterizadas por tipagem dinâmica e alocação dinâmica de 
armazenamento
• Variáveis são essencialmente não tipadas
– Uma variável adquire um tipo quando é atribuído um valor a ela
• O armazenamento é alocado a uma variável apenas quando é atribuído 
um valor a ela
Conceitos de Linguagens de Programação – Robert W. Sebesta
APL: uma linguagem de programação
• Projetada na IBM por Ken Iverson, em torno de 1960, como uma 
linguagem para descrever arquiteturas de computadores
– Alta expressividade (grande número de operadores, grande número 
de operações unitárias em vetores)
– Programas difíceis de ler
• Ainda em uso; mudanças mínimas
Conceitos de Linguagens de Programação – Robert W. Sebesta
SNOBOL
• Projetada para processamento de texto, no Bell Labs, por Farber, 
Griswold e Polensky em 1964
• Operações poderosas para o casamento de padrões de cadeias
• Mais lenta do que linguagens alternativas (e não mais usada para 
editores de texto)
• Ainda em uso para uma variedade de tarefas de processamento 
de textos 
Conceitos de Linguagens de Programação – Robert W. Sebesta
O Início da abstração de dados: SIMULA 67
• Projetada inicialmente para simulação, na Noruega, por Nygaard e Dahl
• Baseada no ALGOL 60 e no SIMULA I
• Contribuições
– Corrotinas – espécie de subprograma
– Classes, objetos e herança
Conceitos de Linguagens de Programação – Robert W. Sebesta
Projeto ortogonal: ALGOL 68
• A partir do desenvolvimento continuado do ALGOL 60
• Fonte de uma série de novas ideias (embora a própria linguagem nunca 
tenha alcançado grande uso)
• Projeto baseado no conceito de ortogonalidade
– Alguns conceitos primitivos mais o uso irrestrito de mecanismos de 
combinação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação do ALGOL 68
• Contribuições
– Estruturas de dados definidas pelo usuário
– Tipos de referência
– Vetores dinâmicos (vetores flex)
• Comentários
– Menos uso do que o ALGOL 60
– Teve forte influência nas linguagens subsequentes, especialmente Pascal, 
C e Ada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Pascal - 1971
• Projetada por Wirth (ex-membro do comitê do ALGOL 68)
• Projetada para ser usada como veículo educacional
• Pequena, simples, nada realmente novo
• O maior impacto foi no ensino de programação
– Do meio dos anos 1970 até o fim dos 1990, foi a linguagem mais usada 
para o ensino de programação
Conceitos de Linguagens de Programação – Robert W. Sebesta
C - 1972
• Projetada para a programação de sistemas (no Bell Labs, por Dennis 
Richie)
• Evoluída a partir de BCLP, B e ALGOL 68
• Poderoso conjunto de operadores, mas verificação de tipos pobre
• Primeira linguagem de alto padrão implementada no UNIX
• Muitas áreas de aplicação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Programação baseada em lógica: Prolog
• Projetada, por Comerauer e Roussel (Universidade de Aix-Marseille), 
com ajuda de Kowalski (Universidade de Edimburgo)
• Baseada em lógica formal
• Não procedural
• Pode ser resumida como sendo um tipo de base de dados inteligente
• Altamente ineficiente, pequenas áreas de aplicação
Conceitos de Linguagens de Programação – Robert W. Sebesta
O maior esforço de projeto da história: Ada
• Enorme esforço de projeto, envolvendo centenas de pessoas, muito 
dinheiro e cerca de oito anos
– Strawman (abril de 1975)
– Woodman (agosto de 1975)
– Tinman (1976)
– Ironman (1977)
– Steelman (1978)
• Chamada de Ada em homenagem de Augusta Ada Byron, a primeira 
programadora
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação de Ada
• Contribuições
– Pacotes - suporte para abstração de dados
– Recursos elaborados para manipulação de exceções
– Unidades de programas genéricas
– Concorrência de unidades de programas especiais
• Comentários
– Projeto competitivo
– Agrupa a maioria dos conceitos de engenharia de software e projeto de 
linguagem do final dos anos 1970
– Primeiros compiladores eramdifíceis; apenas em 1985, quase quatro 
anos após o projeto da linguagem estar completo, compiladores usáveis 
começaram a aparecer
Conceitos de Linguagens de Programação – Robert W. Sebesta
Ada 95
• Ada 95 (começou em 1988)
– Suporte para programação orientada a objeto por meio de derivação 
de tipos
– Melhor controle de mecanismos para dados compartilhados
– Novos recursos para concorrência
• Popularidade sofreu porque o Departamento de Defesa não exigiu mais 
seu uso e por causa da popularidade de C++
Conceitos de Linguagens de Programação – Robert W. Sebesta
Programação orientada a objetos: Smalltalk
• Projetada na Xerox PARC, inicialmente por Alan Kay, depois por Adele 
Goldberg
• Primeira linguagem de programação a oferecer suporte completo à 
programação orientada a objetos
• Pioneira no design da interface gráfica do usuário
Conceitos de Linguagens de Programação – Robert W. Sebesta
Combinando recursos imperativos e 
programação orientada a objetos: C++
• Projetada no Bell Labs por Stroustrup em 1980
• Desenvolvida a partir de C e SIMULA 67 
• Facilidades para programação orientada a objetos, emprestadas 
do SIMULA 67
• Fornece manipulação de exceções
• Linguagem grande e complexa, em parte porque suporta programação 
procedural e orientada a objetos
• Cresceu rapidamente em popularidade
• Padrão ANSI aprovado em novembro de 1997
• Versão da Microsoft (lançado com .NET em 2002): Managed C++
Conceitos de Linguagens de Programação – Robert W. Sebesta
Linguagens relacionadas
• Eiffel (projetada por Bertrand Meyer - 1992)
– Não diretamente derivada de outra linguagem
– Menor e mais simples do que C++
– Não teve a popularidade de C++, porque muitos entusiastas de C++ já 
eram programadores de C
• Delphi (Borland)
– Pascal mais recursos para suporte de programação orientada a objeto
– Mais elegante e seguro do que C++
Conceitos de Linguagens de Programação – Robert W. Sebesta
Uma linguagem orientada a objetos baseada 
no paradigma imperativo: Java
• Projetada na Sun no início dos anos 1990
– C e C++ não eram satisfatórios para dispositivos eletrônicos embarcados
• Baseada em C++
– Significantemente simplificada
– Suporta apenas programação orientada a objetos
– Tem referências, mas não tem ponteiros
– Inclui forma simples de controle de concorrência
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação de Java
• Eliminou muitos recursos inseguros de C++
• Suporta concorrência
• Bibliotecas de classes para interfaces gráficas com o usuário, acesso a 
bases de dados e redes
• Portabilidade: Máquina Virtual Java (JVM), compiladores Just-in-Time
(JIT)
• Amplamente usado para programação Web
• Uso aumentou mais rapidamente do que qualquer linguagem anterior
• Versão mais recente, 5.0, lançada em 2004
Conceitos de Linguagens de Programação – Robert W. Sebesta
Linguagens de Scripting para Web
• Perl
– Desenvolvida por Larry Wall — lançada primeiro em 1987
– Variáveis são estaticamente tipadas e implicitamente declaradas
– Três espaços de nomes distintos para variáveis, denotados pelo primeiro caractere de nomes de variáveis
– Teve uso difundido para programação CGI na Web
– Também usado como ferramenta de administração de sistema em UNIX
• JavaScript
– Começou na Netscape, mas depois se tornou um projeto conjunto da Netscape com a Sun Microsystems
– Permitia aos documentos HTML requisitarem a execução de programas no servidor; usado na criação de 
documentos HTML dinâmicos
– Puramente interpretada
– Relacionado ao Java somente por meio de sintaxe similar
• PHP
– PHP: Hypertext Preprocessor (Processador de Hipertexto), projetado por Rasmus Lerdorf
– Linguagem de scripting do lado do servidor embutida em HTML, geralmente utilizados para processamento 
de formulários e acesso de dados pela Web
– Puramente interpretada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Linguagens de Scripting para Web
• Python
– Linguagem de scripting orientada a objetos
– Com verificação de tipos, mas tipada dinamicamente
– Usada para programação em CGI e administração de sistemas
– Suporta listas, tuplas e dicionários
• Lua
– Linguagem de scripting que oferece suporte para programação procedural 
e funcional com extensibilidade como objetivo primário
– Com verificação de tipos, mas tipada dinamicamente
– Usada para programação em CGI e administração de sistemas
– Suporta listas, tuplas e dicionários, todos com a sua única estrutura de 
dados, a tabela
Conceitos de Linguagens de Programação – Robert W. Sebesta
Linguagens de Scripting para Web
• Ruby
– Projetada no Japão por Yukihiro Matsumoto (também conhecido como 
“Matz”)
– Começou como um substituto para Perl e Python
– Linguagem de scripting orientada a objetos pura
• Todos os dados são objetos
– A maioria dos operadores são implementados como métodos, que podem 
ser redefinidos pelo código do usuário
– Puramente interpretada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Uma Linguagem baseada em C Para o Novo 
Milênio: C#
• Parte da nova plataforma de desenvolvimento .NET (2000)
• Baseada em C++ , Java e Delphi
• Fornece uma linguagem para o desenvolvimento de software baseado 
em componentes
• Todas as linguagens do .NET usam o chamado Common Type System 
(CTS – Sistema de Tipos Comum), que fornece uma biblioteca de 
classes comum
Conceitos de Linguagens de Programação – Robert W. Sebesta
Linguagens híbridas de marcação/programação
• XSLT
– XML (eXtensible Markup Language – Linguagem de Marcação Extensível) é uma 
linguagem de metamarcação
– XSLT (eXtensible Stylesheet Language Transformations – Transformações em 
Linguagem de Folhas de Estilo Extensível) transforma documentos XML para 
visualização
– Contrutores de programação
• JSP
– Java Server Pages: coleção de tecnologias projetadas para oferecer suporte 
a documentos Web dinâmicos 
– servlet: programa que roda no processo do servidor Web, que controla a execução 
dos servlets
– JSTL define uma coleção de elementos de ações XML que controlam 
o processamento do documento JSP no servidor Web
Conceitos de Linguagens de Programação – Robert W. Sebesta
Resumo
• Desenvolvimento, ambiente de desenvolvimento e avaliação de 
importantes linguagens de programação
• Perspectivas em relação as questões atuais do projeto de linguagens
Capítulo 3
Descrevendo Sintaxe 
e Semântica
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 3
• Introdução
• O problema geral de descrever sintaxe
• Métodos formais para descrever sintaxe
• Gramáticas de atributos
• Descrevendo o significado de programas: semântica dinâmica
Conceitos de Linguagens de Programação – Robert W. Sebesta
Introdução
• Sintaxe: a forma de suas expressões, sentenças e unidades de 
programas
• Semântica: o significado dessas expressões, sentenças e unidades de 
programas
• Sintaxe e semântica fornecem uma definição da linguagem
– Usuários de uma definição de linguagem
• Outros desenvolvedores de linguagem
• Implementadores
• Programadores (os usuários da linguagem)
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema geral de descrever sintaxe: 
terminologia
• Uma sentença é uma cadeia de caracteres formada a partir do alfabeto 
da linguagem
• Uma linguagem é uma cadeia de sentenças
• Um lexema é a unidade sintática de mais baixo nível de uma linguagem 
(por exemplo, *, sum, begin)
• Um token é uma categoria de lexemas (por exemplo, identificador)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Definição formal de linguagens
• Reconhecedores
– Um dispositivo de reconhecimento lê cadeias de caracteres a partir do 
alfabeto da linguagem e indica se a cadeia pertence ou não à linguagem
– Exemplo: parte de análise sintática de um compilador
• A discussão detalhada sobre análise sintática aparece no Capítulo 4
• Geradores
– Um dispositivo que gera sentenças de uma linguagem
– Pode determinar se a sintaxe de uma sentença em particular está 
sintaticamente corretaa comparando à estrutura do gerador
Conceitos de Linguagens de Programação – Robert W. Sebesta
BNF e gramáticas livres de contexto
• Gramáticas livres de contexto
– Desenvolvido por Noam Chomsky no meio dos anos 1950
– Geradores de linguagem, feitos para descrever a sintaxe de linguagens 
naturais
– Define uma classe de linguagens chamadas de livres de contexto
• Forma de Backus-Naur (1959)
– Inventada por John Backus para descriver Algol 58
– BNF é equivalente às gramáticas livres de contexto
Conceitos de Linguagens de Programação – Robert W. Sebesta
Fundamentos de BNF
• Em BNF, abstrações são usadas para representar classes de estruturas 
sintáticas – elas agem como variáveis sintáticas (também chamadas de 
símbolos não terminais, ou simplesmente não terminais)
• Terminais são lexemas ou tokens
• Uma regra tem um lado esquerdo (LHS), que é um não terminal, e um 
lado direito (RHS), que é uma cadeia de terminais e não terminais
– Exemplos das regras de BNF:
<ident_list> → identifier | identifier, <ident_list>
<if_stmt> → if <logic_expr> then <stmt>
• Gramática: coleção de regras
• Um símbolo inicial é um elemento especial dos não terminais de 
uma gramática
Conceitos de Linguagens de Programação – Robert W. Sebesta
Regras de BNF
• Uma abstração (ou símbolo não terminal) pode ter mais de um RHS
<stmt> → <single_stmt> 
| begin <stmt_list> end
Conceitos de Linguagens de Programação – Robert W. Sebesta
Descrevendo listas
• Listas sintáticas são descritas usando recursão
<ident_list> → ident
| ident, <ident_list>
• Uma derivação é uma aplicação de regras repetida, começando com 
um símbolo inicial e terminando com uma sentença (todos símbolos 
terminais)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Um exemplo de gramática
<program> → <stmts>
<stmts> → <stmt> | <stmt> ; <stmts>
<stmt> → <var> = <expr>
<var> → a | b | c | d
<expr> → <term> + <term> | <term> - <term>
<term> → <var> | const
Conceitos de Linguagens de Programação – Robert W. Sebesta
Um exemplo de derivação
<program> => <stmts> => <stmt> 
=> <var> = <expr> 
=> a = <expr> 
=> a = <term> + <term>
=> a = <var> + <term> 
=> a = b + <term>
=> a = b + const
Conceitos de Linguagens de Programação – Robert W. Sebesta
Derivações
• Cada cadeia de símbolos em uma derivação é chamada de forma 
sentencial 
• Uma sentença é uma forma sentencial que tem apenas símbolos 
terminais
• Uma derivação mais à esquerda é uma em que o não terminal mais à 
esquerda em cada forma sentencial é expandido
• Uma derivação pode ser nem mais à esquerda nem mais à direita
Conceitos de Linguagens de Programação – Robert W. Sebesta
Árvore de análise sintática
• Representação hierárquica de uma derivação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Ambiguidade em gramáticas
• Uma gramática é ambígua se gera uma forma sentencial com duas ou 
mais árvores de análise sintática distintas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Uma gramática de expressão ambígua
<expr> → <expr> <op> <expr> | const
<op> → / | -
Conceitos de Linguagens de Programação – Robert W. Sebesta
Uma gramática de expressão não ambígua
• Se usarmos a árvore de análise sintática para indicar níveis de 
precedência dos operadores, não podemos ter a ambiguidade
<expr> → <expr> - <term> | <term>
<term> → <term> / const| const
Conceitos de Linguagens de Programação – Robert W. Sebesta
Associatividade de operadores
• Associatividade de um operador também pode ser indicada por uma 
gramática
<expr> -> <expr> + <expr> | const (ambígua)
<expr> -> <expr> + const | const (não ambígua)
Conceitos de Linguagens de Programação – Robert W. Sebesta
BNF estendida
• Partes opcionais são delimitadas por colchetes [ ]
<proc_call> -> ident [(<expr_list>)]
• Partes alternativas de RHSs são colocadas entre parênteses e 
separadas com barras verticais
<term> → <term> (+|-) const
• Repetições (0 ou mais) são colocadas entre chaves { }
<ident> → letter {letter|digit}
Conceitos de Linguagens de Programação – Robert W. Sebesta
BNF e EBNF
• BNF
<expr> → <expr> + <term>
| <expr> - <term>
| <term>
<term> → <term> * <factor>
| <term> / <factor>
| <factor>
• EBNF
<expr> → <term> {(+ | -) <term>}
<term> → <factor> {(* | /) <factor>}
Conceitos de Linguagens de Programação – Robert W. Sebesta
Recentes variações em EBNF
• RHSs alternativas são colocadas em linhas separadas
• Uso de dois pontos em vez de =>
• Uso de opt para partes opcionais
• Uso de oneof para escolhas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semânticas estáticas
• Não têm a ver com o significado
• Gramáticas livres de contexto (CFGs) não podem descrever todas as 
sintaxes de linguagens de programação
• Categorias de construtores que são problemas:
– Livres de contexto (por exemplo, tipos de operandos em expressões)
– Não livres de contexto (por exemplo, variáveis precisam ser declaradas 
antes de serem usadas)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gramáticas de atributos
• Uma gramática de atributos (AG) é uma extensão de uma gramática 
livre de contexto (CFG) 
• Valores primários de gramáticas de atributos:
– Especificação de semânticas estáticas
– Compilação (verificação de semânticas estáticas)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gramáticas de atributos: definição
• Def: Uma gramática de atributo é uma gramática com os seguintes 
recursos adicionais:
– Associado a cada símbolo X da gramática está um conjunto de atributos 
A (X)
– Associado a cada regra gramatical está um conjunto de funções 
semânticas e um conjunto possivelmente vazio de funções de predicado 
sobre os atributos dos símbolos na regra gramatical
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gramáticas de atributos: definição
• Deixe X0 → X1 ... Xn ser uma regra
• Funções semânticas da forma S(X0) = f(A(X1), ... , A(Xn)) definem 
atributos sintetizados
• Funções da forma I(Xj) = f(A(X0), ... , A(Xn)), for i <= j <= n, definem 
atributos herdados
• Atributos intrínsecos são atributos sintetizados de nós folha cujos 
valores são determinados fora da árvore de análise sintática
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gramáticas de atributos: um exemplo
• Sintaxe
<assign> -> <var> = <expr>
<expr> -> <var> + <var> | <var>
<var> A | B | C
• actual_type: sintetizado para <var> e <expr>
• expected_type: herdado para <expr>
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gramática de atributos
• Regra sintática: <expr> → <var>[1] + <var>[2]
Regra semântica: 
<expr>.actual_type ← <var>[1].actual_type
Predicado: 
<var>[1].actual_type == <var>[2].actual_type
<expr>.expected_type == <expr>.actual_type
• Regra sintática : <var> → id
Regra semântica:
<var>.actual_type ← lookup (<var>.string)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gramática de atributos
• Como são computados os valores dos atributos?
– Se todos os atributos forem herdados, a árvore pode ser decorada na 
ordem decrescente.
– Se todos os atributos forem sintetizados, a árvore pode ser decorada na 
ordem crescente.
– Em muitos casos, ambos os tipos de atributos são usados, e uma 
combinação de crescente e decrescente precisa ser usada.
Conceitos de Linguagens de Programação – Robert W. Sebesta
Gramática de atributos
<expr>.expected_type ← inherited from parent
<var>[1].actual_type ← lookup (A)
<var>[2].actual_type ← lookup (B)
<var>[1].actual_type =? <var>[2].actual_type
<expr>.actual_type ← <var>[1].actual_type
<expr>.actual_type =? <expr>.expected_type
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semânticas
• Não há nenhuma notação única amplamente aceitável ou formalismo 
para descrever semântica
• Diversas necessidades de uma metodologia e notação para 
a semântica
– Programadores precisam saber o que a sentença de uma linguagem 
significa
– Desenvolvedores de compiladores devem saber exatamente o queas 
construções da linguagem significam
– Geradores de compilação seriam possíveis
– Projetistas poderiam detectar ambiguidades e inconsistências
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica operacional
• Semântica Operacional
– Descrever o significado de uma sentença ou programa pela especificação 
dos efeitos de rodá-lo em uma máquina. A mudança no estado de 
máquina (memória, registros, etc.) define o significado da sentença
• Para usar semântica operacional em uma linguagem de alto nível, é 
necessária uma máquina virtual
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica operacional
• Um interpretador puro de hardware seria muito caro
• Um interpretador puro de software também tem problemas
– As características detalhadas de um computador em particular deixaria 
ações difíceis de entender
– Uma definição semântica seria dependente da máquina
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica operacional
• Uma melhor alternativa: uma completa simulação
• O processo:
– Construir um interpretador (transforma código de origem em código de 
máquina de um computador idealizado)
– Construir um simulador para o computador idealizado
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semânticas operacionais
• Usos de semânticas operacionais:
– Manuais de linguagem e livros-texto de programação
– Ensino de linguagens de programação
• Dois níveis diferentes de uso de uma semântica operacional:
– Semântica operacional natural
– Semântica operacional estrutural
• Avaliação
– Boa se usada informalmente
– Extremamente complexa se usada formalmente
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semânticas denotacionais
• Baseada na teoria de funções recursivas
• O método de descrição semântica mais abstrato
• Originalmente desenvolvida por Scott e Strachey (1970)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semânticas denotacionais
• O processo de construir uma especificação denotacional para uma 
linguagem:
– Define um objeto matemático para cada entidade da linguagem
– Define uma função que mapeia as instâncias dessa entidade de 
linguagem para instâncias do objeto matemático correspondente
• O significado da construção de linguagem é definido apenas pelos 
valores das variáveis de programas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semânticas denotacionais: o estado de 
um programa
• O estado de um programa são os valores atuais de todas as suas 
variáveis
s = {<i1, v1>, <i2, v2>, …, <in, vn>}
• Considere VARMAP uma função que, quando dado um nome de 
variável e estado, retorna o atual valor da variável
VARMAP(ij, s) = vj
Conceitos de Linguagens de Programação – Robert W. Sebesta
Números decimais
<dec_num> → '0' | '1' | '2' | '3' | '4' | '5' | 
'6' | '7' | '8' | '9' | 
<dec_num> ('0' | '1' | '2' | '3' |
'4' | '5' | '6' | '7' | 
'8' | '9')
Mdec('0') = 0, Mdec ('1') = 1, …, Mdec ('9') = 9
Mdec (<dec_num> '0') = 10 * Mdec (<dec_num>)
Mdec (<dec_num> '1’) = 10 * Mdec (<dec_num>) + 1
…
Mdec (<dec_num> '9') = 10 * Mdec (<dec_num>) + 9
Conceitos de Linguagens de Programação – Robert W. Sebesta
Expressões
• Expressões formam o conjunto Z ∪ {error}
• Assumimos que expressões são números decimais, variáveis ou 
expressões binárias tendo um operador aritimético e dois operando, 
cada um pode ser uma expressão
Conceitos de Linguagens de Programação – Robert W. Sebesta
Expressões
Me(<expr>, s) ∆=
case <expr> of
<dec_num> => Mdec(<dec_num>, s)
<var> => 
if VARMAP(<var>, s) == undef
then error
else VARMAP(<var>, s)
<binary_expr> => 
if (Me(<binary_expr>.<left_expr>, s) == undef
OR Me(<binary_expr>.<right_expr>, s) =
undef)
then error
else
if (<binary_expr>.<operator> == '+' then
Me(<binary_expr>.<left_expr>, s) + 
Me(<binary_expr>.<right_expr>, s)
else Me(<binary_expr>.<left_expr>, s) * 
Me(<binary_expr>.<right_expr>, s)
...
Conceitos de Linguagens de Programação – Robert W. Sebesta
Sentenças de atribuição
• Funções de mapeamento mapeiam listas de sentenças e estados para 
estados ∪ {error}
Ma(x := E, s) ∆=
if Me(E, s) == error
then error
else s’ = 
{<i1,v1’>,<i2,v2’>,...,<in,vn’>},
where for j = 1, 2, ..., n,
if ij == x
then vj’ = Me(E, s) 
else vj’ = VARMAP(ij, s)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Laços lógicos com pré-teste
• Funções de mapeamento mapeiam listas de sentenças e estados para 
estados U {error}
Ml(while B do L, s) ∆=
if Mb(B, s) == undef
then error
else if Mb(B, s) == false
then s
else if Msl(L, s) == error
then error
else Ml(while B do L, Msl(L, s))
Conceitos de Linguagens de Programação – Robert W. Sebesta
Significado do laço
• O significado do laço é o valor das variáveis do programa após as 
sentenças no laço terem sido executadas o número de vezes 
necessário, assumindo que não ocorreram erros 
• Essencialmente, o laço foi convertido de iteração para recursão, onde o 
controle da recursão é definido matematicamente por outras funções 
recursivas de mapeamento de estado
– A recursão é mais fácil de descrever com rigor matemático do que 
a iteração
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação de semântica denotacional
• Pode ser usada para provar a corretude de programas
• Sugere uma maneira rigorosa para pensar nos programas
• Pode ser uma ajuda ao projeto de linguagem
• Tem sido usada em sistemas de geração de compilador
• Devido a sua complexidade, é de pouco uso para usuários de 
linguagem
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica axiomática
• Baseada em lógica matemática
• Propósito original: verificação de programas
• Axiomas ou regras de inferência são definidas para cada tipo de 
sentença da linguagem (a fim de permitir transformações de expressões 
de lógica em expressões de lógica mais formais)
• As expressões lógicas são chamadas de asserções
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica axiomática
• Uma asserção que precede imediatamente uma sentença (uma 
pré-condição) descreve as restrições nas variáveis do programa 
naquele ponto.
• Uma asserção imediatamente após uma sentença é uma pós-condição
• Uma pré-condição mais fraca é a menos restritiva que garantirá 
a validade da pós-condição associada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Forma da semântica axiomática
• Forma sentencial: {P} statement {Q}
• Um exemplo
– a = b + 1 {a > 1}
– Uma pré-condição possível: {b > 10}
– Pré-condição mais fraca: {b > 0}
Conceitos de Linguagens de Programação – Robert W. Sebesta
Provas de programas
• A pós-condição para o programa completo é o resultado desejado
– Volte até a primeira sentença do programa. Se a pré-condição na primeira 
sentença é a mesma da especificação do programa, ele está correto.
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica axiomática: axiomas
• Um axioma para sentença de atribuição 
(x = E): {Qx->E} x = E {Q}
• A Regra de Consequência:
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica axiomática: axiomas
• Uma regra de inferência para sequências da forma S1; S2
{P1} S1 {P2}
{P2} S2 {P3}
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica axiomática: axiomas
• Uma regra de inferência para um laço de repetição
{P} while B do S end {Q}
onde I é a invariante de laço de repetição
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica axiomática: axiomas
• Características da invariante de laço de repetição: I deve satisfazer os 
seguintes requisitos:
– P => I -- a invariante de repetição precisa ser verdadeira inicialmente 
– {I} B {I} -- avaliação de B não pode mudar a validade de I
– {I and B} S {I} -- I não é mudado pela execução do corpo da repetição
– (I and (not B)) => Q -- se I é verdadeiro e B é falso, Q é incluído
– A repetição termina -- pode ser difícil de provar
Conceitos de Linguagensde Programação – Robert W. Sebesta
Invariante de repetição
• A invariante de repetição é uma versão enfraquecida da pós-condição 
de repetição e é também uma pré-condição.
• I deve ser fraco o suficiente para estar preenchido antes do início do 
ciclo, mas quando for combinado com a condição de saída do laço deve 
ser suficientemente forte para forçar a verdade da pós-condição
Conceitos de Linguagens de Programação – Robert W. Sebesta
Avaliação da semântica axiomática
• Desenvolver axiomas ou regras de inferência para todas as sentenças 
de uma linguagem é difícil
• É uma boa ferramenta para provas de corretude, mas não é útil para 
usuários de linguagens e escritores de compiladores
Conceitos de Linguagens de Programação – Robert W. Sebesta
Semântica denotacional × semântica 
operacional
• Na semântica operacional, as mudanças de estado são definidas por 
algoritmos codificados
• Na semântica denotacional, as mudanças de estado são definidas por 
funções matemáticas rigorosas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Resumo
• BNF e gramáticas livres de contexto são metalinguagens equivalentes
– Bastante adequadas para a tarefa de descrever a sintaxe de linguagens 
de programação
• Uma gramática de atributos e um formalismo descritivo que pode 
descrever tanto a sintaxe quanto a semântica estática de uma 
linguagem
• Três métodos principais de descrição semântica
– Operacional, denotacional e axiomática
Capítulo 4
Análise Léxica 
e Sintática
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 4
• Introdução
• Análise léxica
• O problema da análise sintática
• Análise sintática descendente recursiva
• Análise sintática ascendente
Conceitos de Linguagens de Programação – Robert W. Sebesta
Introdução
• Sistemas de implementação de linguagem devem analisar o código 
de origem, independentemente da abordagem de implementação 
específica
• Quase todas as análises sintáticas são baseadas em uma descrição 
formal da sintaxe da linguagem de origem (BNF)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática
• A porção de análise sintática de um processador de linguagem quase 
sempre consiste em duas partes:
– O analisador léxico (construções de linguagem de pequena escala, como 
nomes e literais numéricos)
– O analisador sinático, ou parser (construções de larga escala como 
expressões, sentenças e unidades de programas)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Vantagens de usar BNF para descrever 
uma sintaxe
• Fornece uma descrição da sintaxe clara e concisa, tanto para humanos 
quanto para os sistemas de software
• Pode ser usada como a base direta para o analisador sintático
• Implementações baseadas em BNF são relativamente fáceis de manter
Conceitos de Linguagens de Programação – Robert W. Sebesta
Razões para separar análises léxica e sintática
• Simplicidade - técnicas para análise léxica são menos complexas do 
que aquelas para análise sintática; o processo pode ser mais simples se 
for realizado separadamente
• Eficiência – separação permite otimização do analisador léxico
• Portabilidade - partes do analisador léxico podem não ser portáteis, mas 
o analisador sintático sempre é
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
• Um analisador léxico é essencialmente um casador de padrões para 
cadeias de caracteres
• Um analisador léxico serve como o passo inicial de um analisador 
sintático
• Coleta caracteres e os agrupa logicamente, atribuindo códigos internos 
de acordo com sua estrutura - lexemas
– Lexema casa um padrão de caracteres, que é associado à categoria 
léxica chamada token
– sum é um lexema; seu token pode ser IDENT
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
• O analisador léxico é normalmente uma função chamada pelo 
analisador sintático quando esse precisa de um token
• Três abordagens para construir um analisador léxico:
– Escrever uma descrição formal dos tokens e usar uma ferramenta de 
software que constrói analisadores léxicos dirigidos por tabela que 
recebem essa descrição
– Projetar um diagrama de transições de estado que descreva os padrões 
de tokens da linguagem e escrever um programa que implemente o 
diagrama
– Descrever um diagrama de transições de estado que descreva os padrões 
de tokens da linguagem e construir manualmente uma implementação 
dirigida por tabela do diagrama de estados
Conceitos de Linguagens de Programação – Robert W. Sebesta
Diagrama de estados
• Um diagrama de transição de estados, ou apenas diagrama de estados, 
é um grafo dirigido 
• Os nós de um diagrama de estados são rotulados com nomes de 
estados 
• Os arcos são rotulados com os caracteres de entrada que causam as 
transições entre os estados
• Um arco pode também incluir ações que o analisador léxico deve 
realizar quando a transição ocorrer
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
• Em muitos casos, transições podem ser combinadas para simplificar o 
diagrama de estado
– Ao reconhecer um identificador, todas as letras maiúsculas e minúsculas 
são equivalentes
• Use uma classe de caracteres que inclui todas as letras
– Ao reconhecer um literal inteiro, todos os dígitos são equivalentes - usar 
uma classe dígitos
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
• As palavras reservadas e identificadores podem ser reconhecidos 
juntos (em vez de haver uma parte do diagrama para cada palavra 
reservada)
– Use uma tabela para determinar se um possível identificador é uma 
palavra reservada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise léxica
• Subprogramas utilitários:
– getChar - obtém o próximo caractere de entrada do programa de entrada 
e o coloca na variável nextChar, determina a classe do caractere de 
entrada e a coloca na variável charClass
– addChar – coloca o caractere de nextChar no lugar em que o lexema 
está sendo acumulado, lexeme
– lookup – determina se a sequência de caracteres lexeme é uma palavra 
reservada
Conceitos de Linguagens de Programação – Robert W. Sebesta
Diagrama de estados
Conceitos de Linguagens de Programação – Robert W. Sebesta
Analisador léxico
Implementação: 
 Mostrar front.c (pp. 195-199)
– A seguir, temos a saída do analisador léxico de
front.c quando usado com (sum + 47) / total
Next token is: 25 Next lexeme is (
Next token is: 11 Next lexeme is sum
Next token is: 21 Next lexeme is +
Next token is: 10 Next lexeme is 47
Next token is: 26 Next lexeme is )
Next token is: 24 Next lexeme is /
Next token is: 11 Next lexeme is total
Next token is: -1 Next lexeme is EOF
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
• Objetivos da análise sintática:
– Encontrar erros de sintaxe; para cada um, produzir uma mensagem de 
diagnóstico e se recuperar
– Produzir uma árvore de análise sintática completa, ou ao menos percorrer 
a estrutura da árvore, para uma entrada sintaticamente correta
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
• Duas categorias de análise sintática
– Descendente – constrói a árvore a partir da raiz em direção às folhas
– Ascendente – constrói a árvore a partir das folhas em direção à raiz
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
• Analisadores sintáticos descendentes
– Dada uma forma sentencial, xAα , a análise sintática precisa escolher 
a regra sentencial correta para obter a próxima forma sentencial em 
uma derivação mais à esquerda, usando apenas o primeiro token
produzido por A
• Os algoritmos de análise sintática mais comuns:
– Descendente recursivo - implementação codificada
– Algoritmos LL- implementação dirigida por tabela
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
• Analisadores sintáticosascendentes
– Dada uma forma sentencial direita α, o analisador sintático deve 
determinar que subcadeia de α e a RHS da regra na gramática que deve 
ser reduzida para seu LHS para produzir a forma sentencial anterior na 
derivação mais à direita
– Os algoritmos mais comuns de análise sintática ascendente estão na
família LR
Conceitos de Linguagens de Programação – Robert W. Sebesta
O problema da análise sintática
• A complexidade da análise sintática
– Os algoritmos de análise sintática que trabalham para qualquer gramática 
não ambígua são complicados e ineficientes (O(n3), onde n é o 
comprimento da entrada)
– Compiladores usam análises sintáticas que trabalham para apenas um 
subconjunto de todas as gramáticas possíveis (O(n), onde n é o 
comprimento da entrada)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Um analisador sintático descendente recursivo é chamado assim 
porque consiste em uma coleção de subprogramas, muitos dos quais 
são recursivos, e produz uma árvore de análise sintática em uma ordem 
descendente 
• A EBNF é idealmente adequada para analisadores sintáticos 
descendentes recursivos
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Uma gramática para expressões simples:
<expr> → <term> {(+ | -) <term>}
<term> → <factor> {(* | /) <factor>}
<factor> → id | int_constant | ( <expr> )
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Assume que temos um analisador léxico chamado lex, que coloca seu 
código de token na variável global nextToken
• O processo de código quando há apenas um RHS:
– Para cada símbolo terminal na RHS, o símbolo terminal é comparado com 
nextToken; se eles casam, o analisador léxico é chamado para obter o 
próximo token de entrada
– Para cada não terminal, o subprograma de análise sintática para o não 
terminal é chamado
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
/* Função expr 
Analisa sintaticamente cadeias na linguagem gerada pela regra:
<expr> → <term> {(+ | -) <term>}
*/
void expr() {
/* Analisa sintaticamente o primeiro termo */
term(); 
/* Desde que o próximo token seja + ou -, obtenha 
o próximo token e analise sintaticamente o próximo termo */
while (nextToken == ADD_OP || 
nextToken == SUB_OP){
lex();
term(); 
}
}
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Essa rotina em particular não detecta erros
• Convenção: Cada rotina de análise sintática deixa o próximo token de entrada 
em nextToken
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Um não terminal que tenha mais de uma RHS requer um processo 
inicial para determinar qual RHS deve analisar
– A RHS correta é escolhida com base no próximo token da entrada
– O próximo token é comparado com o primeiro token que pode ser gerado 
por cada RHS
– Se eles não casam, é um erro sintático
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
/* term
Analisa sintaticamente cadeias na linguagem gerada pela regra:
<term> -> <factor> {(* | /) <factor>)
*/
void term() {
printf("Enter <term>\n");
/* Analisa sintaticamente o primeiro termo */
factor();
/* Desde que o próximo token seja * ou /,
obtenha o próximo token e analise sintaticamente o próximo termo */
while (nextToken == MULT_OP || nextToken == DIV_OP) {
lex();
factor();
}
printf("Exit <term>\n");
} /* Fim da função term */
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
/* Função factor
Analisa sintaticamente cadeias na linguagem
gerada pela regra: 
<factor> -> id | (<expr>) */
void factor() {
/* Determina qual RHS */
if (nextToken) == ID_CODE || nextToken == INT_CODE)
/* Para o id de RHS id, chama lex */
lex();
/* Se a RHS is (<expr>) – chame lex para passar o parêntese esquerdo, 
chame expr e verifique pelo parêntese direito */
else if (nextToken == LP_CODE) {
lex();
expr();
if (nextToken == RP_CODE)
lex();
else
error();
} /* Fim do else if (nextToken == ... */
else error(); /* Neither RHS matches */
}
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
- Saída da análise sintática da expressão de exemplo(sum + 47) / total 
Next token is: 25 Next lexeme is ( Next token is: 11 Next lexeme is total
Enter <expr> Enter <factor> 
Enter <term> Next token is: -1 Next lexeme is EOF
Enter <factor> Exit <factor>
Next token is: 11 Next lexeme is sum Exit <term>
Enter <expr> Exit <expr>
Enter <term>
Enter <factor>
Next token is: 21 Next lexeme is +
Exit <factor>
Exit <term>
Next token is: 10 Next lexeme is 47
Enter <term>
Enter <factor>
Next token is: 26 Next lexeme is )
Exit <factor>
Exit <term>
Exit <expr>
Next token is: 24 Next lexeme is /
Exit <factor>
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• A classe de gramáticas LL
– O Problema da Recursão à Esquerda
• Se uma gramática tem recursão à esquerda, ela não pode ser a base para 
uma análise sintática descendente
– Uma gramática pode ser modificada para remover a recusão à esquerda
Para cada não terminal, A, 
1. Agrupe as regras-A como A → Aα1 | … | Aαm | β1 | β2 | … | βn
onde nenhum dos β’s começa com A
2. Substitua as regras-A originais por
A → β1A’ | β2A’ | … | βnA’
A’ → α1A’ | α2A’ | … | αmA’ | ε
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Outra característica da gramática que desabilita a análise sintática 
descendente é o teste de disjunção par a par
– A incapacidade de determinar o RHS correto na base de um token
– Definição: FIRST(α) = {a | α =>* aβ }
(Se α =>* ε, ε está em FIRST(α))
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Teste de Disjunção Par a Par:
– Para cada não terminal, A, na gramática que tem mais de uma RHS, para 
cada par de regras, A → αi e A → αj, deve ser verdadeiro que
FIRST(αi) ⋂ FIRST(αj) = φ
• Exemplos:
A → a | bB | cAb
A → a | aB
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática descendente recursiva 
• Fatoração à esquerda pode resolver o problema
As duas regras podem ser substituídas por 
<variable> → identifier | identifier [<expression>]
com
<variable> → identifier <new>
<new> → ε | [<expression>]
ou
<variable> → identifier [[<expression>]]
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• O problema da análise sintática é encontrar a RHS correta em uma 
forma sentencial à direita para obter a forma sentencial anterior na 
derivação
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Intuição acerca dos manipuladores:
– Definição: β e o manipulador da forma sentencial direita γ = αβw se, e 
somente se, S =>*rm αAw =>rm αβw
– Definição: β e uma frase da forma sentencial a direita γ se, e somente se, 
S =>* γ = α1Aα2 =>+ α1βα2
– Definição: β é uma frase simples da forma sentencial à direita γ se, e 
somente se, S =>* γ = α1Aα2 => α1βα2
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Intuição acerca dos manipuladores:
– O manipulador de uma forma sentencial mais à direita é sua frase 
sentencial mais à esquerda
– Dada uma árvore de análise sintática, é fácil encontrar o manipulador
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Algoritmos de deslocamento e redução
– Uma ação de redução (reduce) substitui uma RHS (o manipulador) no 
topo da pilha do analisador sintático por sua LHS correspondente
– A ação deslocar (shift) move o próximo símbolo de entrada para a pilha do 
analisador sintáticoConceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Vantagens dos analisadores sintáticos LR:
– Eles podem ser construídos para todas as linguagens de programação.
– Eles podem detectar erros de sintaxes o mais cedo possível em uma 
varredura da esquerda para a direita.
– A classe de gramáticas LR é um superconjunto da classe analisável 
sintaticamente por analisadores LL (por exemplo, muitas gramáticas 
recursivas à esquerda são LR, mas nenhuma é LL).
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Analisadores sintáticos LR precisam ser construídos com uma 
ferramenta
• Descoberta de Knuth: uma análise sintática ascendente pode usar sua 
história inteira, até o ponto atual, para fazer tomar decisões de análise
– Havia apenas um número relativamente pequeno de situações diferentes, 
então a história poderia ser registrada por um estado, em uma pilha de 
análise
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Uma configuração de um analisador sintático LR é um par de cadeias 
(pilha, entrada), com a forma detalhada
(S0X1S1X2S2…XmSm, aiai+1…an$)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Uma tabela de análise sintática LR tem duas partes, ACTION e GOTO
– A parte ACTION especifica a maioria das ações do analisador sintático
• Rótulos de linhas são símbolos de estado; rótulos das colunas são símbolos 
terminais
– A parte GOTO indica qual símbolo de estado deve ser inserido na pilha da 
análise sintática após uma redução ser completada
• Rótulos são símbolos de estado; rótulos de coluna são não terminais
Conceitos de Linguagens de Programação – Robert W. Sebesta
A estrutura de um analisador sintático LR
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Configuração inicial: (S0, a1…an$)
• Ações do analisador sintático:
– Se ACTION[Sm, ai] = Deslocar S, a próxima configuração é: 
(S0X1S1X2S2…XmSmaiS, ai+1…an$)
– Se ACTION[Sm, ai] = Reduzir A → β e S = GOTO[Sm-r, A], onde r = 
tamanho de β, a próxima configuração é
(S0X1S1X2S2…Xm-rSm-rAS, aiai+1…an$)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Ações do analisador sintático:
– Se ACTION[Sm, ai] = Aceita, a análise sintática está completa e nenhum 
erro foi encontrado.
– Se ACTION[Sm, ai] = Erro, o analisador sintático chama uma rotina de 
tratamento de erros.
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tabela de análise sintática LR
Conceitos de Linguagens de Programação – Robert W. Sebesta
Análise sintática ascendente
• Tabelas de análise sintática LR podem ser facilmente construídas 
usando uma ferramenta de software como o yacc
Conceitos de Linguagens de Programação – Robert W. Sebesta
Resumo
• A análise sintática é uma parte comum da implementação de linguagens
• Um analisador léxico é um casador de padrões que isola as partes de 
pequena escala de um programa
– Detecta erros sintáticos
– Contrói uma árvore de análise sintática
• Um analisador sintático descendente recursivo é um analisador 
sintático LL
– EBNF
• Problema da análise sintática para analisadores sintáticos ascendentes: 
achar a subcadeia da forma sentencial atual
• A família LR de analisadores sintáticos de deslocamento e redução é 
a abordagem de análise sintática ascendente mais usada
Capítulo 5
Nomes, Vinculações 
e Escopos
Conceitos de Linguagens de Programação – Robert W. Sebesta
Tópicos do Capítulo 5
• Introdução
• Nomes
• Variáveis
• O conceito de vinculação
• Escopo
• Escopo e tempo de vida
• Ambientes de referenciamento
• Constantes nomeadas
Conceitos de Linguagens de Programação – Robert W. Sebesta
Introdução
• As linguagens de programação imperativas são abstrações da 
arquitetura de computadores subjacente de von Neumann
– Memória
– Processador
• Variáveis caracterizadas por atributos
– Para projetar um tipo, deve-se considerar escopo, tempo de vida das 
variáveis, inicialização e compatibilidade
Conceitos de Linguagens de Programação – Robert W. Sebesta
Nomes
• Questões de projeto primárias para nomes:
– Os nomes são sensíveis a capitalização?
– As palavras especiais da linguagem são palavras reservadas ou 
palavras-chave?
Conceitos de Linguagens de Programação – Robert W. Sebesta
Nomes
• Formato
– Se for muito pequeno, não pode ser conotativo
– Exemplos:
• FORTRAN 95: máximo de 31
• C99: sem limitação, mas apenas os 63 são significativos; nomes externos são 
restritos a 31 caracteres
• C#, Ada e Java: sem limite e todos os caracteres são significativos
• C++: sem limite, mas os implementadores às vezes o impõem
Conceitos de Linguagens de Programação – Robert W. Sebesta
Nomes
• Caracteres especiais
– PHP: todos os nomes de variáveis devem começar com cifrão ($)
– Perl: todos os nomes de variáveis começam com caracteres especiais, 
que especificam o seu tipo
– Ruby: nomes de variáveis que começam com @ são variáveis de 
instância; as que começam com @@ são variáveis de classe
Conceitos de Linguagens de Programação – Robert W. Sebesta
Nomes
• Sensibilidade à capitalização
– Desvantagem: legibilidade (nomes que são parecidos, mas são diferentes)
• Nomes em linguagens baseadas com C são sensíveis à capitalização
• Nomes em outras não são
• Em C++, Java e C#, o problema não pode ser evitado porque muitos dos 
nomes pré-definidos incluem tanto letras maiúsculas quanto minúsculas
(por exemplo, IndexOutOfBoundsException)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Nomes
• Palavras especiais
– São usadas para tornar os programas mais legíveis ao nomearem as 
ações a serem realizadas
• Uma palavra-chave é uma palavra especial apenas em alguns contextos – por 
exemplo, em Fortran
– Real VarName (Real é um tipo de dado acompanhado de um nome, portanto 
Real é uma palavra-chave)
– Real = 3.4 (Real é uma variável)
– Uma palavra reservada é uma palavra especial que não pode ser usada 
como um nome
– Problema em potencial com as palavras reservadas: se houver muitas, 
o usuário tem dificuldade para inventar nomes (por exemplo, COBOL tem 
300 palavras reservadas!)
Conceitos de Linguagens de Programação – Robert W. Sebesta
Variáveis
• Uma variável é uma abstração de uma célula de memória
• Uma variável pode ser caracterizada como um conjunto de 
seis atributos:
– Nome
– Endereço
– Valor
– Tipo
– Tempo de vida
– Escopo
Conceitos de Linguagens de Programação – Robert W. Sebesta
Atributos de variáveis
• Nome – nem todas as variáveis têm
• Endereço - é o endereço de memória de máquina ao qual ela está 
associada
– Uma variável pode ter diferentes endereços em diferentes momentos 
durante a execução
– Uma variável pode ter diferentes endereços em diferentes lugares em um 
programa
– Quando dois nomes de variáveis podem ser usados para acessar a 
mesma posição de memória, elas são chamadas de apelidos (aliases)
– Apelidos são criados por ponteiros, variáveis de referência, tipos de união 
C e C++
– Apelidos são um problema para a legibilidade (um leitor do programa deve 
sempre se lembrar de todos eles) 
Conceitos de Linguagens de Programação – Robert W. Sebesta
Atributos de variáveis
• Tipo - determina a faixa de valores que a variável pode armazenar e o 
conjunto de operações definidas para valores do tipo
• Valor - é o conteúdo da(s) célula(s) de memória associada(s) a ela 
– O lado esquerdo (l-value) de uma variável é seu endereço
– O lado direito (r-value) de variável é seu valor
• Célula abstrata de memória – célula física ou coleção de células 
associadas a uma variável
Conceitos de Linguagens de Programação – Robert W. Sebesta
O conceito de vinculação
• Uma vinculação é uma associação, como entre um atributo e uma 
entidade ou entre uma operação e um símbolo
• Tempo de vinculação é o momento no qual uma vinculação ocorre
Conceitos de Linguagens de Programação