Sintaxe e Semântica Prof.: Gláucya Carreiro Boechat glaucyacboechat@gmail.com Universidade Federal...

Sintaxe e Semântica

Prof.: Gláucya Carreiro Boechat glaucyacboechat@gmail.com

Universidade Federal Rural de PernambucoDepartamento de Estatística e Informática

Paradigmas de Programação - prof Gláucya Carreiro Boechat

2

Sintaxe e Semântica Provêm a definição da linguagem Sintaxe

A forma ou estrutura das expressões, das instruções e das unidades de programas Estrutura formada de acordo com Regras Gramaticais da

Linguagem. (Estruturas Sintáticas) Exemplo (condição diferente)

Pascal ( <> ) ; C = ( != ) ; Ada ( /= )

Semântica O significado das expressões, das instruções e das unidades

de programas Identificação das seqüências de símbolos validos que constituem

estruturas sintáticas

Paradigmas de Programação - prof Gláucya Carreiro Boechat

3

Sintaxe e Semântica

Exemplo: comando if na linguagem C Sintaxe

if (<expr>) <instrução>

Semântica Se o valor da expressão for verdadeiro, a instrução será

executada

Paradigmas de Programação - prof Gláucya Carreiro Boechat

4

Descrevendo a sintaxe: terminologia Uma linguagem é uma conjunto de sentenças Uma sentença é uma cadeia de tokens

Um lexema é a unidade sintática de mais baixo nível de uma linguagem Exemplos:

*, sum, begin, if

Um token é uma categoria dos lexemas Seqüência de caracteres sobre um alfabeto Exemplo:

identificador, op_mult

Paradigmas de Programação - prof Gláucya Carreiro Boechat

5

Descrevendo a sintaxe: terminologia Exemplo (C) Resultado = 45 + Cont * 5;

Lexema Token

resultado identificador

= sinal_igual

45 int_literal

+ op_soma

Cont Identificador

* op_mult

5 int_literal

; ponto_e_virgula

Paradigmas de Programação - prof Gláucya Carreiro Boechat

6

Definição formal de linguagens Reconhecedores de linguagens

Dispositivo que recebe um token como entrada e verifica se o mesmo pertence a linguagem

Exemplo: Análise Sintática (parte de um compilador)

Geradores de linguagens Dispositivo que gera sentenças da linguagem Determinando se a sintaxe de uma sentença em particular

está correta Através de comparações com a estrutura da linguagem gerada If <condição = true> then <instrução>

Paradigmas de Programação - prof Gláucya Carreiro Boechat

7

Métodos formais para descrever a sintaxe Forma de Backus-Naur (BNF)

Método mais usado para descrever a sintaxe das linguagens de programação

Uma metalinguagem é usada para descrever outras linguagens

Extended Backus Naur Form (EBNF) Por apresentar algumas inconveniências a BNF foi

estendida Aumenta Legibilidade e Capacidade escrita da BNF

Paradigmas de Programação - prof Gláucya Carreiro Boechat

8

Gramáticas Livres de Contexto Gramáticas Livres de Contexto

Desenvolvida por Noam Chomsky nos meados da década de 1950

Define uma classe de linguagens chamadas de linguagens livres de contexto

Objetivo Descrever a sintaxe das linguagens naturais São gramáticas onde as regras de produção são

definidas de forma mais livre

Paradigmas de Programação - prof Gláucya Carreiro Boechat

9

Backus-Naur Form (BNF)

Backus-Naur Form (1959) Inventada por John Backus para descrever o

Algol 58 (International Algorithmic Language) BNF é equivalente a gramáticas livre de contexto BNF é uma metalinguagem usada para descrever

outras linguagens Em BNF, abstrações são usadas para

representar classes de estruturas sintáticas Agem como variáveis sintáticas (também chamadas de

símbolos não-terminais)

Paradigmas de Programação - prof Gláucya Carreiro Boechat

10

BNF - Fundamentos Terminais: lexemas e tokens

Não-terminais: BNF abstrações Atual como variáveis

Gramática: uma coleção de regras Exemplos de regras BNF:

Atribuição em C(Representada pela abstração) <Atribuição>  -->  <var> = <expressão> 

<ident_list> -> identifier | identifier , <ident_list> <if_stmt> -> if <expr_logica> then <stmt> <if_stmt> -> if <expr_logica> then <stmt> else <stmt>

Paradigmas de Programação - prof Gláucya Carreiro Boechat

11

Regras BNF

Uma regra possui um lado esquerdo (LHS - Left Hand Side)

consiste de símbolos não-terminais um lado direito (RHS - Right Hand Side),

consiste de símbolos terminais e não-terminais

Uma gramática é um conjunto não vazio de regras

Uma abstração (ou símbolo não-terminal) pode ter mais de um RHS <stmt> -> <single_stmt> | begin <stmt_list> end

Paradigmas de Programação - prof Gláucya Carreiro Boechat

12

Listas Sintáticas

Listas sintáticas são descritas usando recursão <ident_list> -> ident

| ident , <ident_list>

Derivação Aplicação de regras repetidas vezes,

começando com um símbolo inicial finalizando com uma sentença (símbolos terminais)

Paradigmas de Programação - prof Gláucya Carreiro Boechat

13

Uma gramática para uma pequenalinguagem<program> -> begin <stmts> end

<stmts> -> <stmt> | <stmt> ; <stmts>

<stmt> -> <var> = <expr>

<var> -> a | b | c | d

<expr> -> <term> + <term> | <term> - <term>

<term> -> <var> | const

Paradigmas de Programação - prof Gláucya Carreiro Boechat

14

Exemplo gramática para uma pequena linguagem

<program> => <stmts>

=> <stmt>

=> <var> = <expr>

=> a = <expr>

=> a = <term> + <term>

=> a = <var> + <term>

=> a = b + <term>

=> a = b + const

<program>

<stmts>

<stmt>

<var> = <expr>

a <term> + <term>

<var> const

b

Paradigmas de Programação - prof Gláucya Carreiro Boechat

15

Uma gramática para instruções de

atribuição simples<assign> -> <id> = <expr>

<id> -> A | B | C

<expr> -> <id> + <expr>

| <id> * <expr>

| ( <expr> )

| <id>

Paradigmas de Programação - prof Gláucya Carreiro Boechat

16

Árvore de Análise (Parse Tree)

Paradigmas de Programação - prof Gláucya Carreiro Boechat

17

Ambigüidade em gramáticas

Uma gramática é ambígua se e somente se ela gera uma sentença que possui duas ou mais árvores de análise distintas

Paradigmas de Programação - prof Gláucya Carreiro Boechat

18

Uma gramática ambígua parainstruções de atribuição simples

<assign> -> <id> = <expr>

<expr> -> <expr> + <expr>

| <expr> * <expr>

| ( <expr> )

| <id>

<id> -> A | B | C

Paradigmas de Programação - prof Gláucya Carreiro Boechat

19

Duas árvores de análise para amesma sentença A = B + C * A

Paradigmas de Programação - prof Gláucya Carreiro Boechat

20

Uma gramática não-ambígua para expressões

indicar os níveis de precedência de operadores, não teremos ambigüidade

<assign> -> <id> = <expr><expr> -> <expr> + <term>

| <term><term> -> < term > * <factor>

| <factor><factor> -> ( <expr> )

| <id><id> -> A | B | C

Paradigmas de Programação - prof Gláucya Carreiro Boechat

21

A árvore de análise única para a expressão

A = B + C * A

Paradigmas de Programação - prof Gláucya Carreiro Boechat

22

Exemplo – Sintaxe para expressões

Calculadora simples

Com -> Expr

Expr -> Num | Expr + Num | Expr - Num | Expr * Num | Expr / Num

Num -> Dig |Num Dig

Dig -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Paradigmas de Programação - prof Gláucya Carreiro Boechat

23

Exemplo2 – Priorização em linguagens de Programação

1ª Prioridade : *, /, and, ... 2ª Prioridade : +, -, or, ... 3ª Prioridade : =, >, <, ...

Expr -> tExpr

| tExpr = tExpr

| tExpr < tExpr

| tExpr > tExpr

Paradigmas de Programação - prof Gláucya Carreiro Boechat

24

Exemplo2 – Priorização em linguagens de Programação

tExpr -> sExpr | tExpr + sExpr | tExpr - sExpr | tExpr or sExpr

sExpr -> pExpr | sExpr * pExpr | sExpr / pExpr | sExpr and pExpr

pExpr -> Lit | Var | (Exp)

Paradigmas de Programação - prof Gláucya Carreiro Boechat

25

Associatividade de Operadores

Associatividade de operadores podem ser indicados pela gramática

Exemplo A = B + C + A (adição é associativa) A = B / C / A   (divisão não é associativa)

Paradigmas de Programação - prof Gláucya Carreiro Boechat

26

Associatividade de Operadores Exemplo

<expr> -> <expr> + <expr> | const (ambígua) <expr> -> <expr> + const | const (não-ambígua)

Paradigmas de Programação - prof Gláucya Carreiro Boechat

27

Árvore de análise associatividade da adição

A = B + C + A

Paradigmas de Programação - prof Gláucya Carreiro Boechat

28

BNF estendida

Adição de novas extensões

Uso de Colchetes [ ] no RHS Partes opcionais

<proc_call> -> ident [ ( <expr_list> ) ] <seleção> -> if ( <expressão> ) <instrução> [else <instrução>]; 

Paradigmas de Programação - prof Gláucya Carreiro Boechat

29

BNF estendida

Uso de parenteses ( ) no RHS Opções de múltipla escolha, são colocadas dentro de

parênteses e separadas por barras verticais <term> -> <term> ( + | - ) const <for_stmt> -> for <var> = <expr> ( to | downto ) <expr> do <stmt>

Uso de chaves { } no RHS Indica zero ou repetição indefinida

<ident> -> letter { letter | digit } <lista_ident> -> <identificador> { , <identificador> } 

Paradigmas de Programação - prof Gláucya Carreiro Boechat

30

BNF e EBNF

BNF

<expr> -> <expr> + <term> | <expr> - <term> | <term>

<term> -> <term> * <factor> | <term> / <factor> | <factor>

<factor> -> <exp> ** <factor> | <exp>

<exp> -> ( <expr> ) | id

EBNF

<expr> -> <term> { (+ | -) <term> }

<term> -> <factor> { (* | / ) <factor> }

<factor> -> <exp> { ** <exp> }

<exp> -> ( <expr> )

| id

Paradigmas de Programação - prof Gláucya Carreiro Boechat

31

Exercícios

Traduzir as seguintes seqüências 5 – 6 – 7 5 * 6 * 7 5 * 6 – 7 5 – 3 * 2 – 7 A and B = C A or B = C

Paradigmas de Programação - prof Gláucya Carreiro Boechat

32

Exercícios

Modificar a sintaxe previamente estabelecida para as expressões sejam avaliadas tendo as comparações com maior precedência (Ex.: A and (B=C)). Refaça a tradução das expressões considerando a nova sintaxe estabelecida.

Paradigmas de Programação - prof Gláucya Carreiro Boechat

33

Exercícios Adicionar os operadores unários ‘++’, ‘--’ e

‘not’. Os operadores ‘++’ e ‘--’ devem ter a mesma prioridade dos seus correspondentes binários, e devem ser permitidos como ‘pré’ ou ‘pós’. O operador ‘not’ deve possuir uma prioridade mais alta do que todos os operadores já definidos. Represente as expressões ‘--a+b’, ‘a+b--’, ‘++a*b’

e ‘not A and B’