Capítulo 3

Descrevendo Sintaxe
e Semântica


Conceitos de Linguagens de Programação – Robert W. Sebesta

» 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

» 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

while (expressão_booleana) sentença

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Conceitos iniciais
– Uma linguagem, seja natural (como a língua inglesa) ou artificial
(como Java), é um conjunto de cadeias de caracteres formadas a
partir de um alfabeto
– Uma sentença é uma cadeia de caracteres formada a partir do
alfabeto da linguagem
– 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

» Sentença: index = 2 * count + 17;

6
Conceitos de Linguagens de Programação – Robert W. Sebesta

» 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

» Construção das Linguagens de Programação

– Estudar a teoria da computação providencia conceitos e princípios
que ajudam a entender a natureza geral da computação.
– Para estudar esses princípios básicos constroem-se modelos de
computadores abstratos para resolução de pequenos, mas não
fúteis, problemas.
– Para modelar o hardware de um computador é introduzido o
conceito de autômatos.
– Um autômato é uma construção que possui todas as características
indispensáveis de um computador digital: entrada, saída,
armazenagem temporária, tomadas de decisão.
8

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Construção das Linguagens de Programação (cont…)

– Um autômato é um reconhecedor da linguagem. Através dos
reconhecedores é possível identificar se a cadeia de símbolos pertence
ou não a uma linguagem.

– Linguagem formal é uma abstração das características gerais de uma

linguagem de programação. Assim, possui um conjunto de símbolos,
regras de formação de sentenças, etc.

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Construção das Linguagens de Programação (cont…)

– Estudar computação do ponto de vista teórico é sinônimo de
caracterizar o que é ou não é computável.

– Para tanto, é preciso obter um modelo matemático que represente o

que se entende por computação.

– Existem vários modelos. Nessa disciplina será dado enfoque nas

Máquinas de Turing. Com a Máquina de Turing podem-se verificar os
limites da computação e a complexidade computacional de um
sistema. A Máquina de Turing também é um reconhecedor.

10

Conceitos de Linguagens de Programação – Robert W. Sebesta

» 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
» Geradores
– Um dispositivo que gera sentenças de uma linguagem
– Pode determinar se a sintaxe de uma sentença em particular
está sintaticamente correta comparando à estrutura do gerador

11

Conceitos de Linguagens de Programação – Robert W. Sebesta

» 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

12

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Forma de Backus-Naur (1959)

– Inventada por John Backus para descriver Algol 58
– BNF é equivalente às gramáticas livres de contexto

13

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Uma definição informal de uma linguagem poderia ser dada como

sendo um sistema capaz de expressar ideias, fatos, conceitos e que
inclui um conjunto de símbolos e regras para sua manipulação. Ou
ainda, define-se linguagem como o uso da palavra articulada ou
escrita como meio de expressão e comunicação entre pessoas.

14
Conceitos de Linguagens de Programação – Robert W. Sebesta

» Um alfabeto é um conjunto finito de símbolos.

» Um símbolo de um alfabeto é uma entidade abstrata básica,
podendo representar números, letras, desenhos etc, por exemplo: 1,
0, a, b, c.
» Um alfabeto é representado por: Σ (lê-se sigma)
» Assim são alfabetos:
– Σ = {}
– Σ = {0, 1}
– Σ = {a, b}

15

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Uma cadeia de caracteres sobre um alfabeto á uma sequencia finita

de símbolos (do alfabeto) justapostos.
» Seja o alfabeto Σ = {a, b}
» Então as cadeias (w) possíveis são:
– w = λ representa a cadeia vazia, ou seja, não possui símbolos
– w=a
– w=b
– w = ab
– w = ba
– w = aab
16

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Uma linguagem é um conjunto de palavras sobre um alfabeto.

» Se Σ representa um alfabeto, então Σ* representa o conjunto de
todas as palavras possíveis sobre Σ.
» e Σ+ representa o conjunto de todas as palavras excetuando a
palavra vazia.
» Assim pode-se dizer que
– Σ* = { λ, a, b, ab, ba, aab, abb, aaaa, ....}
– Σ+ = Σ* - {λ} = {a, b, ab, ba, aab, abb, aaaa, ....}
» Uma linguagem (L) é geralmente definida como um subconjunto de
Σ*.

17

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Assim pode-se dizer que

– Σ* = { λ, a, b, ab, ba, aab, abb, aaaa, ....}
– Σ+ = Σ* - {λ} = {a, b, ab, ba, aab, abb, aaaa, ....}
» Uma linguagem (L) é geralmente definida como um subconjunto de
Σ*.
» Uma sentença é geralmente definida como uma cadeia pertencente
à linguagem L.

18

Conceitos de Linguagens de Programação – Robert W. Sebesta

» O tamanho ou comprimento de uma cadeia w, representado por |

w|, é o número de símbolos que compõem a cadeia.
» Por exemplo:
– w = λ |w| = 0
– w = a |w| = 1
– w = ab |w| = 2
– w = abb |w| = 3
– w = bbaa |w| = 4

19

Conceitos de Linguagens de Programação – Robert W. Sebesta

» O reverso de uma cadeia é obtido pela ordem inversa dos símbolos

da cadeia.
» Se w = a1a2...an
» Então o reverso, wR = an...a2a1

» Por exemplo:
– Seja w = ababab então wR = bababa
– Seja v = cdcdcdcd então vR = dcdcdcdc

20

Conceitos de Linguagens de Programação – Robert W. Sebesta

» A concatenação de duas cadeias w e v é a cadeia obtida pela adição

dos símbolos de v no final da cadeia w. Nenhum símbolo pode ser
mudado de lugar no momento da concatenação.
» Se w = a1a2...an e v = b1b2....bm
» Então a concatenação, w U v = a1a2...an b1b2....bm

» Por exemplo:
– Seja w = ababab e v = cdcdcdcd
– Então w U v = abababcdcdcdcd

21

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Símbolos não terminais:

– 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

Regra de abstração sintática da atribuição Lado direito (RHS)

Lado esquerdo (LHS)

22

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Regra de abstração:
– Tem um lado esquerdo (LHS), que representa um não terminal
– Tem um lado direito (RHS), que representa uma cadeia de não
terminais e terminais
– Podem representar mais de uma forma sintática da linguagem

Regra de abstração sintática da atribuição

1⃣

2
⃣
23

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Gramática: coleção de regras

» Um símbolo inicial é um elemento especial dos não terminais de
uma gramática

24



Conceitos de Linguagens de Programação – Robert W. Sebesta

» Listas de elementos sintáticos em BNF são descritas pelo uso de

recursão.
»

<ident_list> → ident | ident, <ident_list>

25

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Uma gramática . um dispositivo de geração para definir linguagens

» 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)

26

Conceitos de Linguagens de Programação – Robert W. Sebesta

» 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

27

Conceitos de Linguagens de Programação – Robert W. Sebesta

» ‘

28
Conceitos de Linguagens de Programação – Robert W. Sebesta

29
Conceitos de Linguagens de Programação – Robert W. Sebesta

» Representação hierárquica de uma derivação

» Cada nó interno de uma árvore de análise sintática é rotulado com
um símbolos não terminal;
» Cada folha é rotulada com um símbolo terminal.
» Cada subárvore de uma árvore de análise sintática descreve uma
instância de uma abstração da sentença.

30

Conceitos de Linguagens de Programação – Robert W. Sebesta

31
Conceitos de Linguagens de Programação – Robert W. Sebesta

» Uma gramática é ambígua se gera uma forma sentencial com duas

ou mais árvores de análise sintática distintas
» Determinar se uma gramática é ambigua:
– Se a gramática gera uma sentença com mais de uma derivação
mais à esquerda;
– Se a gramática gera uma sentença com mais de uma derivação
mais à direita;

32

Conceitos de Linguagens de Programação – Robert W. Sebesta

» Duas árvores para a expressão A = B + C * A

33
Conceitos de Linguagens de Programação – Robert W. Sebesta

» Se usarmos a árvore de análise sintática para indicar níveis de

precedência dos operadores, não podemos ter a ambiguidade

34
Conceitos de Linguagens de Programação – Robert W. Sebesta

» Se usarmos a árvore de análise sintática para indicar níveis de

precedência dos operadores, não podemos ter a ambiguidade

35
Conceitos de Linguagens de Programação – Robert W. Sebesta

36
 Conceitos de Linguagens de Programação – Robert W. Sebesta

» 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}

37

Conceitos de Linguagens de Programação – Robert W. Sebesta

» BNF
» <expr> → <expr> + <term>
» | <expr> - <term>
» | <term>
» <term> → <term> * <factor>
» | <term> / <factor>
» | <factor>
» EBNF
» <expr> → <term> {(+ | -) <term>}

38