View
221
Download
0
Category
Preview:
Citation preview
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �1
Faculdade de Ciências e TecnologiaDepartamento de Matemática e Computação
Bacharelado em Ciência da Computação
Conceitos de Linguagens de Programação
Aula 02
Rogério Eduardo Garcia(rogerio@fct.unesp.br)
Linguagens de Programação
� Representação formal de regras sintáticas
� Representação formal da semântica
04/0
5/20
17R
ogér
io E
duar
do G
arci
a2
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �2
04/0
5/20
17R
ogér
io E
duar
do G
arci
a3
Gramática: Conceito básico que formaliza anotação de definições indutivas
G=(T,NT,P,S)
T = alfabeto denominado vocabulário terminal de G
NT = alfabeto denominado NÃO-TERMINAL de G
∑ = T ∪ NT é o vocabulário de G
P = uma relação finita de N para ∑* (todas as cadeiasde ∑ )
S = um elemento de N, raiz ou símbolo inicial de G
Gramáticas e Linguagens
04/0
5/20
17R
ogér
io E
duar
do G
arci
a4
Arquitetura Básica de um Compilador
Análise Léxica
Análise Sintática
Análise Semântica
Análise
Otimização Global
Geração de Código
Otimização Local
Tabelas
Tratamento de Erros
Síntese
Análise Sintática
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �3
04/0
5/20
17R
ogér
io E
duar
do G
arci
a7
Funções do Analisador Léxico
� Extração e Classificação de Átomos
� Eliminação de comentários
� Conversão Numérica
� Tratamento de Identificadores
� Identificação de Palavras Reservadas
� Recuperação de Erros
� Listagens
� Geração de Tabelas de Referências Cruzadas
� Definição e Expansão de Macros
� Interação com o Sistema de Arquivos
� Compilação Condicional
� Controle de listagens
04/0
5/20
17R
ogér
io E
duar
do G
arci
a8
Extração e Classificação de Átomos
� Classes de átomos mais comuns:– identificadores;
– palavras reservadas;
– números inteiros sem sinal;
– números reais;
– cadeias de caracteres;
– sinais de pontuação e de operação;
– caracteres especiais;
– símbolos compostos de dois ou mais caracteres especiais;
– comentários;
– etc.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �4
04/0
5/20
17R
ogér
io E
duar
do G
arci
a9
Análise Léxica
� Tokens – são padrões de caracteres com umsignificado específico em um código fonte.Definida por um alfabeto e um conjunto dedefinições regulares
– Cada token é normalmente formado por seu tipo (seé um operador lógico, um identificador, um númerointeiro, etc.) e pelo seu valor. Este valor vaidepender do tipo do token e normalmentecorresponde à seqüência de caracteres realmentelida da entrada.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
Análise Léxica
� Exemplos de tokens que podem serreconhecidos em uma linguagem deprogramação como C
palavras reservadas if else while do identificadoresoperadores relacionais < > <= >= == !=operadores aritméticos + * / -operadores lógicos && || & | !operador de atribuição =delimitadores ; ,caracteres especiais ( ) [ ] { }
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �5
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
Análise Léxica
� Lexemas – são ocorrências de um token emum código fonte, também são chamados deátomos por alguns autores– Lexemas podem ter atributos como número da
linha em que se encontra no código fonte e o valorde uma constante numérica ou um literal
� Normalmente utiliza-se um único atributo que éum apontador para a Tabela de Símbolos quearmazena essas informações em registros.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a12
Tokens, Lexemas e Padrões
Tokens Lexemas Padrão
literal “compiladores” Caracteres entre aspas
num 3.14159, 0, 6.0E23 Constante numérica
id Pi, contador, X1 letra seguida por letras ou
dígitos
relation <,<=,=,<>,>, >= < ou <= ou = ou <> ou ...
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �6
04/0
5/20
17R
ogér
io E
duar
do G
arci
a13
Especificação de uma LP
� Sintaxe– conjunto de regras que determinam quais
construções são corretas– Forma de expressões, instruções e unidades de
programa
� Semântica– descrição de como as construções sintaticamente
corretas são interpretadas ou executadas– significado dos três elementos
É preciso descrever formalmente!!!
04/0
5/20
17R
ogér
io E
duar
do G
arci
a14
Gramática: Conceito básico que formaliza anotação de definições indutivas
G=(T,NT,P,S)
T = alfabeto denominado vocabulário terminal de G
NT = alfabeto denominado NÃO-TERMINAL de G
∑ = T ∪ NT é o vocabulário de G
P = uma relação finita de N para ∑* (todas as cadeiasde ∑ )
S = um elemento de N, raiz ou símbolo inicial de G
Gramáticas e Linguagens
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �7
04/0
5/20
17R
ogér
io E
duar
do G
arci
a15
Definições formais das linguagens
� Reconhecedores– dispositivos de filtragem;– projetados para análise das entradas;– funcionam por tentativas;– método exaustivo e ineficiente (linguagens são infinitas);– exemplo: compilador (analisa se o programa faz parte da
linguagem).
� Geradores– dispositivos geradores de seqüências;– fácil entendimento;– funcionam por comparação.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a16
Métodos formais de descrever a sintaxe
� Sintaxe– definida formalmente através de uma gramática.
� Gramática– conjunto de definições que especificam uma seqüência válida
de caracteres.
Duas classes de gramáticas são úteis na definiçãoformal das gramáticas:
– Gramáticas livres de contexto;
– Gramáticas regulares.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �8
04/0
5/20
17R
ogér
io E
duar
do G
arci
a17
Forma de Backus-Naur
A notação inicialmente criada por John Backus eNoam Chomsky, foi modificada posteriormente porPeter Naur dando origem à forma de Backus-Naur ouBNF.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a18
Forma de Backus-Naur
� Metalinguagem– A BNF é uma metalinguagem para descrever as linguagens
de programação
� Abstrações– Símbolos Não-terminais
� Lexemas ou Tokens– Símbolos Terminais
� Produção– É uma definição de uma abstração;
– O lado esquerdo corresponde à abstração;
– O lado direito pode ser uma definição ou um conjunto dedefinições.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �9
Metalinguagens
� Uma metalinguagem é uma linguagem usadapara definir outra linguagem
� Por exemplo, é possível usar Inglês para comosua própria metalinguagem (descrevendogramáica do Inglês em Inglês)
� É importante diferenciar entre os termos dametalinguagem e os termos da linguagemR
ogér
io E
duar
do G
arci
a
Gramática Livre de Contexto
Uma gramática é dita Livre de Contexto se todasregras de sintaxe são aplicadas independente desímbolos anteriores ou posteriores (o contexto).
Exemplo:
20
(1) <sentence> :: = <noun-phrase > <verb-phrase > .
(2) <noun-phrase> ::= <article> <noun>
(3) <article> ::= a | the
(4) <noun> ::= boy | girl | cat | dog
(5) <verb-phrase> ::= <verb> <noun-phrase>
(6) <verb> ::= sees | pets | bites
Símbolos Terminais:
'a' 'the' 'boy' 'girl' 'sees' 'pets' 'bites'
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �10
Gramática Livre de Contexto
21
a girl sees a boy
a girl sees a girl
a girl sees the dog
the dog pets the girl
a boy bites the dog
a dog pets the boy
...
Uma sentença que “bate” com as produções (1) - (6) é válida.
Para eliminar sentenças indesejáveis sem impor restrições de contexto (gramática sensível ao contexto), deve-se especificar regras semânticas:
"a boy may not bite a dog"
Rog
ério
Edu
ardo
Gar
cia
BNF
� BNF é formal e precisa
� BNF é essential para construção decompiladores
� Há muitos dialetos de BNF em uso, mas asdiferenças são insignificantes
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �11
BNF
� < > indica um nãoterminal – termo que precisaser expandido, por exemplo <variable>
� Símbolos não cercados por < > são terminais;
– Eles são representativos por si� Exemplo: if, while, (, =
� Os símbolos ::= siginificam é definido como
� O símbolo | significa or
– Usado para separar alternativas,� Exemplo: <sinal> ::= + | -
Rog
ério
Edu
ardo
Gar
cia
BNF usa recursão
<integer> ::= <digit> | <integer> <digit>
Ou
<integer> ::= <digit> | <digit> <integer>
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �12
BNF – Exemplos I
<digit>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<if statement> ::=if( <condition> ) <statement> |
if (<condition>) <statement> else <statement>
Rog
ério
Edu
ardo
Gar
cia
BNF Exemplos II
<unsigned integer> ::= <digit> |
<unsigned integer> <digit>
<integer>::= <unsigned integer> |
+ <unsigned integer> |
- <unsigned integer>
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �13
BNF Exemplos III
<identifier> ::= <letter> |
<identifier> <letter> |
<identifier> <digit>
<block> ::= { <statement list> }
<statement list> ::= <statement> |
<statement list> <statement>
Rog
ério
Edu
ardo
Gar
cia
BNF Exemplos IV
<statement> ::=<block>
| <assignment statement>| <break statement>| <continue statement>| <do statement>| <for loop>| <goto statement>| <if statement>| . . .
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �14
Extended BNF – EBNF
� Estendem o padrão:– [ ] indicam uma parte opcional da regra
� Exemplo:
<if statement> ::= if ( <condition> ) <statement> [ else <statement> ]
– { } indica que pode ser repetido zero ou mais vezes� Exemplo
<parameterl ist> ::= ( ) | ( { <parameter> , } <parameter> )Rog
ério
Edu
ardo
Gar
cia
Variations
� A notação anterior é a notação original e maiscomum– BNF foi projetado antes de termos negrito, cor, mais
de uma fonte, etc.
– Uma variação moderna típica pode:� Usar negrito para indicar terminais de vários caracteres
� Citar terminais de um único caractere (porque negrito não étão óbvio neste caso)
� Exemplo:
– if_statement ::=
– if "(" condition ")" statement [ else statement ]
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �15
Limitações da BNF
� Não é fácil impor limite de tamanho – porexemplo tamanho máximo para nome devariável
� Não há como impor restrição de distribuição nocódigo fonte – por exemplo, uma variável deveser declarada antes de ser usada
� Descreve apenas a sintaxe, não descre asemântica
� Nada melhor foi proposto
Rog
ério
Edu
ardo
Gar
cia
32
Exemplo
� Uma gramática simplificada para uma atribuição com operaçõesaritméticas – ex: y = (2*x + 5)*x - 7;
<assignment> ::= ID = <expression> ;
<expression> ::= <expression> + <term>
| <expression> – <term>
| <term>
<term> ::= <term> * <factor>
| <term> / <factor>
| <factor>
<factor> ::= ( <expression> )
| ID
| NUMBER
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �16
33
O deve ser produzido?
� O analisador sintático (parser) deve identificaruma entrada válida.
� Isso é feito com a definição de mais alto nível(top level production), chamada de símboloinicial.
– Geralmente o símbolo inicial é a primeira produção.
� O parser tenta "reduzir" a entrada ao símboloinicial.
Rog
ério
Edu
ardo
Gar
cia
Aplicando as regras da gramática (1)
Entrada: z = (2*x + 5)*y - 7;
34
z = (2*x + 5)*y - 7;
tokens: ID ASSIGNOP GROUP NUMBER OP ID OP NUMBER GROUP OP ID OP NUMBER DELIM
valores: z = ( 2 * x + 5 ) * y - 7 ;
Scanner
Fonte:
Parser
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �17
35Aplicando as regras da gramática (2)
tokens: ID = ( NUMBER * ID + NUMBER ) * ID - NUMBER ;
parser: ID ... read (shift) first token
factor ... reduce
factor = ... shift
FAIL: Can't match any rules (reduce)
Backtrack and try again
ID = ( NUMBER ... shift
ID = ( factor ... reduce
ID = ( term * ... sh/reduce
ID = ( term * ID ... shift
ID = ( term * factor ... reduce
ID = ( term ... reduce
ID = ( term + ... shift
ID = ( expression + NUMBER ... reduce/sh
ID = ( expression + factor ... reduce
ID = ( expression + term ... reduce
Ação
Rog
ério
Edu
ardo
Gar
cia
36
Aplicando as regras da gramática (3)
tokens: ID = ( NUMBER * ID + NUMBER ) * ID -NUMBER;
input: ID = ( expression ... reduce
ID = ( expression ) ... shift
ID = factor ... reduce
ID = factor * ... shift
ID = term * ID ... reduce/sh
ID = term * factor ... reduce
ID = term ... reduce
ID = term - ... shift
ID = expression - ... reduce
ID = expression - NUMBER ... shift
ID = expression - factor ... reduce
ID = expression - term ... reduce
ID = expression ; shift
assignment reduce
SUCCESS!!Símbolo Inicial
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �18
37Aplicando as regras da gramática (4)
O parser cria umaárvore a partir daentrada:
assignment
NUMBER
-
y
* NUMBER
7
ID
+
ID expression=z
*
5x
IDNUMBER
2
expression term
factorterm
factor
expression
term factor
Algumas produções foram omitidas para reduzir o espaço
factor
( )
Rog
ério
Edu
ardo
Gar
cia
38
Árvore de Análise (Parse Tree)� O parser cria uma
estrutura de dadosrepresentando comouma entrada “encaixa”nas regras da gramática.
� Geralmente como umaárvore.
Exemplo:
x = y * 12 - z
assignment
=
*
-
z
12
y
x
IDexpr
term
factor
ID
expr
term
factor
NUMBER
term
factor
ID
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �19
Estrutura da Parse Tree
� O símbolo inicial é o nó raiz da árvore.
– Isso representa a entrada sendo analisada.
� Cada troca é uma derivação (parse) usando uma regracorrespondente a um nó e seus filhos.
� Exemplo: <term> ::= <term> + <factor>
39
term
factor+term
Rog
ério
Edu
ardo
Gar
cia
Exemplo: Parse Tree para (2+3)*4
Rog
ério
Edu
ardo
Gar
cia
40
expr
*term
number
4
expr
expr term+
number
2
3
expr
( ) factor
factorterm
number
factor
termfactor
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �20
41
Árvore de Sintaxe (Syntax Trees)
� Árvores de Análise são detalhadas: cada passo em um derivação é um nó.
� Após a análise, os detalhes de derivação não são necessáriospara fases subsequentes.
� O Analisador Semântico remove as produções intermediáriaspara criar uma árvore sintática abstrata – (abstract) syntax tree.
expr
term
factor
ID: x
expr
ID: x
Parse Tree: árvore sintática abstrata :
Rog
ério
Edu
ardo
Gar
cia
Exemplo: árvore sintática abstrata para (2+3)*4
42
*
4 +
2 3
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �21
Semântica dirigida pela sintaxe
� A árvore sintática abstrata corresponde àcomputação realizada.
� Para executar a computação, basta percorrer aárvore in order (in order traversal).
Q: o que signifia "in order traversal"?
43
+
*-
5 3 2 4
Rog
ério
Edu
ardo
Gar
cia
BNF e Precedência de Operadores
� A ordem de produção afeta a ordem de computação.
� Considere a BNF:
<assignment> => id = <expression> ;
<expression> => id + <expression>
| id - <expression>
| id * <expression>
| id / <expression>
| id
| number
� Essa BNF descreve a aritmética padrão?
44R
ogér
io E
duar
do G
arci
a
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �22
Ordem de Operações
� Exemplo: sum = x + y + z;
45
sum = expression
+
id
x
+
id
y id
z
Não exatamente correto (right associative)
Resultado:
sum = x + (y + z)
Aplicação da regra:
assignment
id = expression
id = id + expression
id = id + id + expression
id = id + id + id
sum = x + y + z
expression
expressionRog
ério
Edu
ardo
Gar
cia
Ordem de Operações
� Exemplo: sum = x - y - z;
46
Errado! Subtração não é associativo a direita
Result:
sum = x - (y - z)
Aplicação da regra :
assignment
id = expression
id = id - expression
id = id - id - expression id
= id - id - id
sum = x - y - z
sum = expression
-
id
x
-
id
y id
z
expression
expression
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �23
O Problema da associatividade a direita
� O Problema é que as regras apresentadas sãorecursivas à direita. Isso produz parse tree que éassociativa a diretia.
<expression> ::= id + <expression>
| id - <expression>
| id * <expression>
� Solução: definir a regra de derivação recursiva à esquerda.
Isso Produz uma parse associativa a esquerda.
expression => expression + id
| expression - id
| ...47R
ogér
io E
duar
do G
arci
a
Gramática Revisada (1)
� A regra da gramática deveria usar recursão à
esquerda para gerar associação a esquerda deoperadores
assignment => id = expression ;
expression => expression + id
| expression - id
| expression * id
| expression / id
| id
| number
� Isso funciona?
48R
ogér
io E
duar
do G
arci
a
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �24
Ordem de Operações
� Exemplo: sum = x - y - z;
49
sum = expression
-
id
z
-
id
x
id
y
Aplicando a Regra:
sum = expression
sum = expression - id
sum = expression - z
sum = expression - id - z
sum = expression - y - z
sum = id - y - z
sum = x - y - z
Resultado:
sum = (x - y) - z
expression
Rog
ério
Edu
ardo
Gar
cia
Ordem de Operações
� Exemplo: sum = x + y * z;
50
sum = expression
+ id
z
*
id
x
id
y
Aplicando a Regra:
sum = expression
sum = expression * id
sum = expression * z
sum = expression + id * z
sum = expression + y * z
sum = id + y * z
sum = x - y - z
Result:
sum = (x + y) * z
expression
Errado!
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �25
Gramática Revisada (2)
� Para obter a precedência de operadores, é precisodefinir outras regras
assignment => id = expression ;
expression => expression + term
| expression - term
| term
term => term * factor
| term / factor
| factor
factor => ( expression )
| id
| number51R
ogér
io E
duar
do G
arci
a
Ordem de Operações
� Exemplo: sum = x + y * z;
52
sum = expression
term *
x
+
term
y
factor
Aplicando a regra:
sum = expression
sum = expression + term
sum = term + term
sum = factor + term
sum = id + term
sum = x + term
sum = x + term * factor
...
Resultado:
sum = x + (y * z)
expression term
factor
id
z
id
.
.
.
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �26
Outro Caso
� Exemplo: sum = x / y - z;
53
sum = expression
term
/
x
-
term
y
factor
Resultado:
sum = (x/y) - z
expression term
factor
z
id
.
.
.
.
.
.
Rog
ério
Edu
ardo
Gar
cia
Precedência – “mais abaixo é mais alto”
� Regras que estão mais abaixo na sequência deproduções são aplicadas primeiro por estarem maispróximas de símbolos terminais.
� Regras mais abaixo na definição têm maiorprecedência.
<expression> :: ==== <expression> + <term>
| <expression> - <term >
| <term>
<term > ::==== <term> * <factor>
| <term >/ <factor >
| <factor>
<factor> ::::::::==== ( <expression> ) | id | number54R
ogér
io E
duar
do G
arci
a
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �27
58
Ambiguidade
� Uma gramática é dita ambígua se houvermais de uma árvore gramatical para umsentença válida.
� Exemplo:
<expr> ::= <expr> + <expr>
|<expr> * <expr>
| id
| number
Como é árvore para 2 + 3 * 4 nessa regra?
Rog
ério
Edu
ardo
Gar
cia
Parei aqui!
Exemplo de Ambiguidade
� Duas árvores possíveis:
59
expr
expr expr
expr
+
* expr
expr
expr
+
* expr
expr expr NUMBER
(2)
NUMBER
(3)
NUMBER
(4)
NUMBER
(2)
NUMBER
(3)
NUMBER
(4)
Rog
ério
Edu
ardo
Gar
cia
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �28
Ambiguidade (2)
Para resolver a ambiguidade:
– Reescreva as regras removendo a ambiguidade
– Utilize padrões para o parser, como “sempre use a
o match mais a esquerda primeiro"
– EBNF (mais adiante) ajuda a remover ambiguidade
60R
ogér
io E
duar
do G
arci
a04
/05/
2017
Rog
ério
Edu
ardo
Gar
cia
71
Árvore de Derivação
� Árvore de Derivação e Ambigüidade– Uma gramática é ambígua quando existem duas ou mais
árvores de derivação diferentes.
� Associatividade de Operadores– A associatividade a esquerda é garantida por uma regra de
produção recursiva a esquerda. (Soma e multiplicação)
– A associatividade a direita é garantida por uma regra deprodução recursiva a direita. (Exponenciação)
� Grafos de Sintaxe– São grafos dirigidos que representam as informações nas
regras BNF.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �29
04/0
5/20
17R
ogér
io E
duar
do G
arci
a72
Exemplo de BNF
AMBIGUIDADE...
C::= I� E | C;
E::= I | E O E | (E)
O::= + | *
I::= a | b
04/0
5/20
17R
ogér
io E
duar
do G
arci
a73
Árvore de Derivação
(a+b)*a
GramáticaE::= a | b| E*E | E+E | (E)
E
EE *
b
)( E a
EE +
a
E � E*E � (E)*E � (E+E)*E �
(a+E)*E � (a+b)*E � (a+b)*a
E � E*E � E*a � (E)*a �
(E+E)*a � (E+b)*a � (a+b)*a
E � E*E � (E)*E � (E+E)*E �
(E+E)*a � (a+E)*a � (a+b)*a
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �30
Árvore de Derivação
04/0
5/20
17R
ogér
io E
duar
do G
arci
a74
Problema: AMBIGÜIDADEa+b*a E
E*
b
E
aEE +
a
E � E*E � E+E*E � a+E*E
� a+b*E � a+b*a
E � E+E � E+E*E � a+E*E
� a+b*E � a+b*a
E
E+
b
E
*EEa
a
Uma gramática é dita ambígua se L(G) contém uma
sentença para a qual existe mais de uma árvore de
derivação
04/0
5/20
17R
ogér
io E
duar
do G
arci
a75
Exemplo
Exemplo: ELSE pendente
C::= a | if b then C else C | if b then C
if a=b then if x=y then x=0
ELSE x=1
A qual if pertence o ELSE?
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �31
04/0
5/20
17R
ogér
io E
duar
do G
arci
a76
Exemplo
Exemplo: ELSE pendente
C::= a | if b then C else C | if b then C
C
then
a
if Cb
a
else C
thenif Cb
C
a
thenif b C
thenif Cb else C
a
04/0
5/20
17R
ogér
io E
duar
do G
arci
a78
Eliminação da Ambigüidade
� Como a regra geral é “associar o else ao ifmais próximo” é possível incorporar tal regra agramática como abaixo:
cmd → cmdIsol | cmdAssoc
cmdAssoc → if (expr) cmdAssoc else cmdAssoc| outro
cmdIsol → if (expr) cmd | if (expr) cmdAssoc else cmdIsol
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �32
04/0
5/20
17R
ogér
io E
duar
do G
arci
a79
Eliminação da Ambigüidade
� Esta gramática resolve o problema do “else-vazio” pois:– Todo comando deve ser inicialmente tratado como
um comando isolado– Um comando figurando entre um if e um else deve
ser tratado como comando associado– Comandos associados ou são if-else ou são outros
comandos
� Devemos notar que neste caso existem“regras” de uso associada a gramática
04/0
5/20
17R
ogér
io E
duar
do G
arci
a80
Eliminação da Ambigüidade
cmdIsol
if ( expr )
cmdAssoc
elseif ( expr ) cmdAssoc cmdAssoc
cmd
cmd1 cmd2
cmd
E2
E1
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �33
04/0
5/20
17R
ogér
io E
duar
do G
arci
a81
Grafos de Sintaxe
� Terminais em círculos ou elipses
� Não Terminais em retângulos
� Conectores
� Ex: declarações em Pascal
type_identifier
( identifier )
,
constant .. constant
04/0
5/20
17R
ogér
io E
duar
do G
arci
a82
Exemplo
(
,
)
Operando
(ExpressãoFunção
)
Operador
Número
Operadores: ‘+’, ‘-’, ‘/’, ‘*’, ‘^’
Funções: SEN(), COS(), ABS(), MIN(), MAX()
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �34
04/0
5/20
17R
ogér
io E
duar
do G
arci
a83
Gramática e Reconhecedores
� Um reconhecedor pode ser construídoalgoritmicamente para uma gramática livre decontexto;
� Analisadores sintáticos são chamados dePARSERS e constroem árvores para analisardeterminados programas.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a84
Analise sintática descendente recursiva
� Análise Sintática– Processo de rastrear ou de construir uma árvore
sintática para determinada string de entrada.
� Analisa o código fonte
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �35
04/0
5/20
17R
ogér
io E
duar
do G
arci
a85
Analise sintática descendente recursiva
� Passos da análise sintática descendenterecursiva:
1. Ler string de entrada / procura 1°não-terminal
2. Subprograma define qual das opções do RHSda string coincide com o token de entrada (1°terminal gerado pelo não-terminal);
3. Subprograma daquele não-terminal analisa aárvore de derivação;
4. Analisador Léxico -> achar próximo não-terminal .
04/0
5/20
17R
ogér
io E
duar
do G
arci
a86
Analise sintática descendente recursiva
� Identificação de problemas de sintaxe:– Todas os subprogramas deixam o Token de
entrada como o próximo token para q este fiquesempre o mais a esquerda possível na entrada.
– Símbolos terminais comparados com o próximotoken:� Iguais: Correto
� Diferentes: Problema de sintaxe
– Compilador deve prosseguir a analise até o fim.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �36
04/0
5/20
17R
ogér
io E
duar
do G
arci
a87
Gramática de Atributos
� Descreve mais detalhes da LP que umalinguagem livre de contexto
� Trata a sintaxe e a semântica estática
� Semântica estática: Se relaciona com asformas legais do programa, difíceis ou atéimpossíveis de descrever por BNF– Exemplo: regras de compatibilidade de tipo
� Ex.: na linguagem Java, um valor tipo real nãopode ser atribuído a uma variável do tipointeiro
04/0
5/20
17R
ogér
io E
duar
do G
arci
a88
Gramática de Atributos
� Gramática com a adição de:– Atributos: Símbolos gramaticais que podem ter
valores atribuídos a si;
– Funções de computação de atributos: Regrasgramaticais para especificar como os valores sãoatribuídos;
– Funções Predicadas: Declaram as regras desintaxe e semântica estática.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �37
04/0
5/20
17R
ogér
io E
duar
do G
arci
a89
Gramática de Atributos
� Conjunto de atributos:– Atributos Sintetizados: Passam informações
semânticas para níveis acima na arvore dederivação;
– Atributos Herdados: Passam informaçõessemânticas para níveis abaixo na arvore dederivação.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a90
Gramática de Atributos
� Derivações permitidas– Todo predicado de um não-terminal é verdadeiro;
� Derivações violadas– Se houver violação das regras de sintaxe e/ou
semântica estática.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �38
04/0
5/20
17R
ogér
io E
duar
do G
arci
a91
Gramática de Atributos
� Exemplo:– Tipo_efetivo:Atributo sintetizado associado aos não-
terminais <var> e <expr>;
– Tipo_esperado: Atributo herdado associado ao nãoterminal <expr>.
– Sintaxe:� <atribuição> -> <var> := <expr>
� <expr> -> <var> + <var> | <var>
� <var> -> A | B | C
04/0
5/20
17R
ogér
io E
duar
do G
arci
a92
Gramática de Atributos
� Exemplo (continuação) :– Variáveis: A, B ou C;
– Variáveis do tipo inteiro ou real;
– Lado direito pode ser uma variável ou umaexpressão na forma de adição entre variáveis;
– Quando estão do lado direito não precisam ser domesmo tipo;
– Operandos diferentes: expressão do tipo real;
– Tipo do lado esquerdo = tipo do lado direito.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �39
04/0
5/20
17R
ogér
io E
duar
do G
arci
a93
Gramática de Atributos
� Exemplo (Regras) :1. Sint.: <atribuição> → <var> := <expr>
Sem.: <expr>.tipo_esperado ← <var>.tipo_efetivo
2. Sint.: <expr> → <var>[2] + <var>[3]Sem.: <expr>.tipo_efetivo ←
if (<var>[2].tipo_efetivo = int) and(<var>[2].tipo_efetivo = int)
then intelse realend_if
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
tipo herdadotipo herdado
04/0
5/20
17R
ogér
io E
duar
do G
arci
a94
Gramática de Atributos
� Exemplo (Regras) :
3. Sint.: <expr> → <var>
Sem.: <expr>.tipo_efetivo ← <var>.tipo_efetivo
Predicado: <expr>.tipo_efetivo = <expr>.tipo_esperado
4. Sint.: <var> → A | B | C
Sem.: <var>.tipo_efetivo ← look-up(<var>.string)
look-up pesquisa na tabela de símbolos o tipo da var.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �40
04/0
5/20
17R
ogér
io E
duar
do G
arci
a95
Gramática de Atributos
� Exemplo (continuação) :
<Atribuição>
<Var> <Var>[2] <Var>[3]
<Exp>
A := A + B
Tipo Efet.
Tipo Efet. Tipo Efet.
Tipo Esp.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a96
Gramática de Atributos
� Avaliação:– Usada para descrições completas de sintaxe e
semântica estática de LP´s; (+)
– Geração de compiladores; (+)
– Complexo e de grande tamanho; (-)
– Muitos atributos e regras semânticas; (-)
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �41
04/0
5/20
17R
ogér
io E
duar
do G
arci
a97
Descrevendo o significado dos programas: semântica dinâmica
� Descrever o significado das expressões, dasinstruções e das unidades de programa
� Sintaxe (notação disponível) x Semântica (semnotação)– Não há uma notação amplamente aceitável ou
formalismo para descrever a semântica
� Necessidade de descrever semanticamente osprogramas e elaborar provas de exatidão.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a98
Métodos para o formalismo semântico
� Semântica Operacional;
� Semântica Axiomática;
� Semântica Denotacional.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �42
04/0
5/20
17R
ogér
io E
duar
do G
arci
a99
Semântica Operacional
� Não é formal quanto aos outros métodos
� Idéia:– descrever o significado do programa, observando a
mudança no estado do computador (registradores,memória, informação de status), causado pelaexecução da instrução
� Processo básico– o uso do método requer a construção de 2 (dois)
componentes básicos: um tradutor e uma máquinavirtual;
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
0
Semântica Operacional
� Tradutor converte as instruções existentes nalinguagem de alto nível para linguagem debaixo nível
� As mudanças de estado (registradores,memória, status) na máquina virtual, levadas aefeito pela execução de código de cadainstrução, definem o seu significado
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �43
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
1
Semântica Operacional
� Instrução C
for (expr1; expr2; expr3) {
. . .
}
� Semântica Operacionalexpr1;
loop: if expr2 = 0 goto out
. . .
expr3;
goto loop;
out: . . .
� A MV é capaz de “executar” (interpretar)corretamente as instruções e de reconheceros efeitos da “execução”.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
2
Semântica Operacional
� Constitui um meio efetivo de descrever asemântica de um programa, para usuários eescritores de compiladores
� Freqüentemente encontrado nos livros deprogramação e manuais de consulta dalinguagem
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �44
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
3
Semântica Operacional
� Depende de algoritmos, não de conceitosmatemáticos
� Não baseia-se na lógica e na matemática, masem máquinas.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
4
Semântica Axiomática
� Definida para provar a exatidão dosprogramas, baseia-se na lógica matemática
� Em uma prova, cada instrução tanto éprecedida como seguida de uma expressãológica que especifica restrições às variáveis
� As expressões lógicas são chamadas depredicados ou asserções
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �45
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
5
Semântica Axiomática
� Toda instrução deve ter pré-condição e pós-condição
� Pré-condição: asserções que precedem umainstrução, impondo restrições às variáveisnaquele ponto do programa
� Pós-condição: asserções que segueimediatamente uma instrução
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
6
Semântica Axiomática
� Ex.: sum = 2 * X + 1; { sum > 1}
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �46
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
7
Semântica Axiomática
Pós-condição
Pré-condições válidas: { X > 10 }, { X > 50 }, { X > 1000 }
� Ex.: sum = 2 * X + 1; { sum > 1}
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
8
Semântica Axiomática
Qual é a melhor?
Pós-condição
Pré-condições válidas: { X > 10 }, { X > 50 }, { X > 1000 }
� Ex.: sum = 2 * X + 1; { sum > 1}
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �47
04/0
5/20
17R
ogér
io E
duar
do G
arci
a10
9
Semântica Axiomática
� Pré-condição mais fraca– é a menos restritiva que garantirá a validade da pós-condição;
– { X > 0 } é a pré-condição mais fraca;
– A pré-condição mais fraca pode ser computada por meio deuma Regra de Inferência (RI) da pós-condição dada;
� RI– é um método de suposição da verdade de uma asserção,
baseando-se nos valores de outras;
� Axioma– é uma afirmação lógica que se presume verdadeira.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
0
Semântica Axiomática
� Instruções de atribuição (axioma);
� Seqüências de instruções (regra deinferência);
� Seleção;
� Laços de Pré-Teste Lógico.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �48
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
1Semântica Axiomática - Instruções de atribuição
� x = E, instrução de atribuição, e Q sua pós-condição. Então sua pré-condição, P, édefinida pelo seguinte axioma:
� P = Q x -> E (P é computado como Q com todasas instâncias de x substituídas por E)
� Ex.:
a = b / 2 – 1 { a < 10 } b / 2 – 1< 10 b < 22
{ b < 22 } a = b / 2 -1 { a < 10 }
�
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
2
Semântica Axiomática - Seqüências de instruções
� Sejam S1 e S2 instruções adjacentes de umprograma;
� S1 e S2 possuem as seguintes pré e pós-condições:{P1} S1 {P2}
{P2} S2 {P3}
� A regra de inferência para esta seqüência será:{P1} S1 {P2}, {P2} S2 {P3}
{P1} S1; S2 {P3}
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �49
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
3Semântica Axiomática - Seqüências de instruções
� Se S1 e S2 forem instruções de atribuição:
� X1 = E1; (S1)
� X2 = E2; (S2)
� {P3}, teremos:
{P3X2->E2} X2 = E2 {P3}
{(P3X2->E2)X1->E1} X1 = E1 {P3X2->E2}
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
4
Semântica Axiomática - Seqüências de instruções
� Ex.:Y = 3 * X + 1; (S1)
X = Y + 3; (S2)
{ X < 10 }
X = Y + 3 {X<10} Y + 3 < 10 {Y < 7}
Y = 3 * X + 1 {Y<7} 3 * X + 1 < 7 {X < 2}
{X < 2} S1; S2 {Y < 7}
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �50
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
5
Semântica Axiomática
� É necessário um axioma ou uma regra deinferência para cada instrução;
� Para algumas instruções a definição de umaxioma ou RI é uma tarefa difícil;
� É uma ferramenta poderosa para provas deexatidão, mas sua utilidade para descrever osignificado de programas para os usuários ouescritores de compiladores, é bastantelimitada.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
6
Semântica Denotacional
� É o método mais rigoroso, bastante conhecidopara descrever o significado de programas;
� Baseia-se na teoria das funções recursivas;
� O conceito fundamental da semânticadenotacional é definir para cada instrução umobjeto matemático e uma função que relacioneas instâncias da instrução com o objeto bemdefinido.
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �51
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
7
Semântica Denotacional
� Ex.: “Seja uma construção de linguagem muitosimples, números binários na ordem n = 2 bits, paraapresentar o método denotacional”.
– Regras gramaticais da sintaxe dos números binários:� <num_bin> -> 0 | 1 | <num_bin> 0 | <num_bin> 1
– Objetos são simples números decimais (0,1,2,3), querepresentam o significado real associado a cada regra;
– A função semântica Mbin, relaciona os objetos sintáticos comas regras gramaticais acima.
04/0
5/20
17R
ogér
io E
duar
do G
arci
a11
8
Semântica Denotacional
Mbin(‘0’) = 0
Mbin(‘1’) = 1
Mbin(<num_bin> ‘0’) = 2 * Mbin(<num_bin>)
Mbin(<num_bin> ‘1’) = 2 * Mbin(<num_bin>) + 1
Ex.:
Mbin(‘11’) = 2 * Mbin(‘1’) + 1 = 2 * 1 + 1 = 3
�FCT-UNESP �04/05/2017
�Prof. Dr. Rogério Eduardo Garcia �52
04/0
5/20
17R
ogér
io E
duar
do G
arci
a12
4
Semântica Denotacional
� A semântica denotacional pode ser usada comoauxílio para o projeto de linguagens;
� Devido à complexidade das descrições denotacionais,elas têm pouca utilidade para usuários da linguagem.
Ler capítulo do livro!!!
Recommended