Compilador+simples+de+uma+passagem
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Compilador+simples+de+uma+passagem as PDF for free.
More details
- Words: 859
- Pages: 20
Compilador Simples de uma passagem Visão Geral:
Sintaxe
Definição de linguagem Semântica
Gramática Livre de contexto – Forma de Backus-Naur
Gramáticas
nenhuma limitação é imposta nenhuma substituição pode reduzir o comprimento da forma sentencial Gramática de Forma Simplificada provê uma forma concisa e flexível de identificar cadeias de caracteres
Forma de Backus Naur <símbolo> ::= <expressão com símbolos> Não Terminal <endereço-postal> ::= <parte-do-nome> <endereço-da-rua> <parte-do-CEP> <parte-do-nome> ::= <parte-pessoal> <último-nome> <parte-opc-jr> | <parte-pessoal> <parte-do-nome> <parte-pessoal> ::= "." | <primeiro-nome> <endereço-da-rua> ::= <nome-da-rua> < número-do-ímovel> <parte-do-CEP> ::= <nome-da-cidade> "-"
Definição de Sintaxe • Uma gramática descreve naturalmente a estrutura hierárquica de muitas construções de linguagens de programação Ex: if(expressão) comando else comando Substituindo por variáveis cmd
if (expr) cmd else cmd
Pode ter a forma if e parênteses são tokens cmd e expr são seqüências de tokens, não-terminais
Produção
Definição de Sintaxe Componentes de uma GLC • Conjunto de Tokens ou símbolos terminais • Conjunto de não-terminais • Conjunto de Produções • Designar um não terminal com ponto de partida
Definição de Sintaxe • Exemplo 1 (9-5+2) lista lista + dígito lista lista – dígito lista dígito dígito 0|1|2|3|4|5|6|7|8|9|0
Definição de Sintaxe Os lados direitos das 3 produções com o não terminal lista podem ser agrupados Lista
lista+dígito | lista-dígito | dígito
De acordo com a convenção: Tokens + - 1 2 3 4 5 6 7 8 9 0 Não-terminais lista e dígito lista é terminal de partida, pois suas produções são fornecidas primeiro Cadeia é uma sequncia de zero ou mais tokens
Definição de sintaxe Exemplo 2 : Aplicando o exemplo 1 em
9–2+5 • 9 é uma lista, pois 9 é um dígito; •9 – 5 é uma lista, pois 9 é uma lista e 5 é um dígito; •9 – 5 + 2 é uma lista, pois 9 – 5 é uma lista e 2 é um dígito
Definição de Sintaxe • Blocos e listas separadas por “;” Bloco Cmds_opcs lista_cmds
begin cmds_opcs end lista_cmds | Є lista_cmds; cmd | cmd
Exercício 1
Árvores gramaticais Demonstra como o símbolo de partida de uma gramática deriva uma cadeia Se uma produção A
XYZ então a árvore gramatical será: A X
Y
Z
Formalização da árvore gramatical •A raiz é rotlada pelo símbolo de partida •Cada folha é rotulada pelo token ou por Є •Cada nó interior é rotulado por um não-terminal
Árvores gramaticais • Árvore gramatical para 9 - 5 + 2 lista digito lista
lista
digito
digito
9
-
5
+
2
Ambiguidade • Quando uma gramática possui mais que uma árvore gramatical gerando uma cadeia de tokens cadeia
cadeia cadeia 9
-
+
cadeia 5
cadeia
cadeia 2
cadeia 9
cadeia
-
cadeia
5
+
cadeia 2
Eliminação da Ambiguidade Existem duas maneiras: – Estabelecer uma regra que especifique a cada caso ambíguo qual é o caminho correto. (Sem alterar a gramática) – Alterar a gramática para forçar a construção da árvore sintática correta, removendo a ambigüidade.
Para tratar o problema de ambigüidade em gramática são utilizados os conceitos de precedência e associatividade.
Exercício
Associatividade dos Operadores 9 + 5 + 2 é equivalente a (9 + 5) + 2
O número 5 possui operadores a esquerda e a direita O operador + associa a esquerda porque um operando com sinais de adição em ambos lados é absorvido pelo operador a sua esquerda cadeia
cadeia cadeia 9
+
+
cadeia 5
cadeia
cadeia 2
cadeia a
cadeia
=
cadeia
b
=
cadeia c
Tabela Associatividade em PHP Associação
Operador
esquerda
[
não associativo
++ --
não associativo
~ - (int) (float) (string) (array) (object) (bool) @
não associativo
instanceof
direita
!
esquerda
*/%
esquerda
+-.
esquerda
&&
esquerda
||
esquerda
?:
direita
= += -= *= /= .= %= &= |= ^= <<= >>=
Precedência de Operadores Considerando 9 + 5 * 2 Existem duas possíveis interpretações (9 + 5) * 2 e 9 + (5 * 2). A associatividade não resolve a ambiguidade. * Tem precedência mais alta do que +, se * capturar seus operandos antes de +
Precedência de Operadores • Exemplo •
expr e termo não-terminais para níveis de precedência fator gera as unidades básicas – dígitos é expressões parentetizadas fator Produções para termo termo Produções para expr expr
dígito | (expr)
termo * fator | termo / fator | fator
expr + termo | expr - termo | termo
Exercícios • Identifique os tokens terminais e não-terminais, e defina a gramática da expressão Y := A * X + B digito Y | A | X | B lista1 A*X lista2 lista1+B Tokens terminais = := * + Y A X B Não-terminais lista1 lista2
Exercícios if(3 % 2 == 0){ printf (“Número par”); 4++; } else{ } dígitos 3 | 2 | 0 | 4 expr 3%2==0 cmd printf(“numero par”);4++ cmd1 if(expr )cmd else Є Tokens terminais = % == ++ 3 2 0 4 if () printf Não-terminais expr cmd cmd1
voltar
Exercícios • Cria a árvore gramatical para a sentença • 4–3/5 lista lista
lista
dígito -
4
dígito 3
dígito / 5
voltar
Sintaxe
Definição de linguagem Semântica
Gramática Livre de contexto – Forma de Backus-Naur
Gramáticas
nenhuma limitação é imposta nenhuma substituição pode reduzir o comprimento da forma sentencial Gramática de Forma Simplificada provê uma forma concisa e flexível de identificar cadeias de caracteres
Forma de Backus Naur <símbolo> ::= <expressão com símbolos> Não Terminal <endereço-postal> ::= <parte-do-nome> <endereço-da-rua> <parte-do-CEP> <parte-do-nome> ::= <parte-pessoal> <último-nome> <parte-opc-jr>
Definição de Sintaxe • Uma gramática descreve naturalmente a estrutura hierárquica de muitas construções de linguagens de programação Ex: if(expressão) comando else comando Substituindo por variáveis cmd
if (expr) cmd else cmd
Pode ter a forma if e parênteses são tokens cmd e expr são seqüências de tokens, não-terminais
Produção
Definição de Sintaxe Componentes de uma GLC • Conjunto de Tokens ou símbolos terminais • Conjunto de não-terminais • Conjunto de Produções • Designar um não terminal com ponto de partida
Definição de Sintaxe • Exemplo 1 (9-5+2) lista lista + dígito lista lista – dígito lista dígito dígito 0|1|2|3|4|5|6|7|8|9|0
Definição de Sintaxe Os lados direitos das 3 produções com o não terminal lista podem ser agrupados Lista
lista+dígito | lista-dígito | dígito
De acordo com a convenção: Tokens + - 1 2 3 4 5 6 7 8 9 0 Não-terminais lista e dígito lista é terminal de partida, pois suas produções são fornecidas primeiro Cadeia é uma sequncia de zero ou mais tokens
Definição de sintaxe Exemplo 2 : Aplicando o exemplo 1 em
9–2+5 • 9 é uma lista, pois 9 é um dígito; •9 – 5 é uma lista, pois 9 é uma lista e 5 é um dígito; •9 – 5 + 2 é uma lista, pois 9 – 5 é uma lista e 2 é um dígito
Definição de Sintaxe • Blocos e listas separadas por “;” Bloco Cmds_opcs lista_cmds
begin cmds_opcs end lista_cmds | Є lista_cmds; cmd | cmd
Exercício 1
Árvores gramaticais Demonstra como o símbolo de partida de uma gramática deriva uma cadeia Se uma produção A
XYZ então a árvore gramatical será: A X
Y
Z
Formalização da árvore gramatical •A raiz é rotlada pelo símbolo de partida •Cada folha é rotulada pelo token ou por Є •Cada nó interior é rotulado por um não-terminal
Árvores gramaticais • Árvore gramatical para 9 - 5 + 2 lista digito lista
lista
digito
digito
9
-
5
+
2
Ambiguidade • Quando uma gramática possui mais que uma árvore gramatical gerando uma cadeia de tokens cadeia
cadeia cadeia 9
-
+
cadeia 5
cadeia
cadeia 2
cadeia 9
cadeia
-
cadeia
5
+
cadeia 2
Eliminação da Ambiguidade Existem duas maneiras: – Estabelecer uma regra que especifique a cada caso ambíguo qual é o caminho correto. (Sem alterar a gramática) – Alterar a gramática para forçar a construção da árvore sintática correta, removendo a ambigüidade.
Para tratar o problema de ambigüidade em gramática são utilizados os conceitos de precedência e associatividade.
Exercício
Associatividade dos Operadores 9 + 5 + 2 é equivalente a (9 + 5) + 2
O número 5 possui operadores a esquerda e a direita O operador + associa a esquerda porque um operando com sinais de adição em ambos lados é absorvido pelo operador a sua esquerda cadeia
cadeia cadeia 9
+
+
cadeia 5
cadeia
cadeia 2
cadeia a
cadeia
=
cadeia
b
=
cadeia c
Tabela Associatividade em PHP Associação
Operador
esquerda
[
não associativo
++ --
não associativo
~ - (int) (float) (string) (array) (object) (bool) @
não associativo
instanceof
direita
!
esquerda
*/%
esquerda
+-.
esquerda
&&
esquerda
||
esquerda
?:
direita
= += -= *= /= .= %= &= |= ^= <<= >>=
Precedência de Operadores Considerando 9 + 5 * 2 Existem duas possíveis interpretações (9 + 5) * 2 e 9 + (5 * 2). A associatividade não resolve a ambiguidade. * Tem precedência mais alta do que +, se * capturar seus operandos antes de +
Precedência de Operadores • Exemplo •
expr e termo não-terminais para níveis de precedência fator gera as unidades básicas – dígitos é expressões parentetizadas fator Produções para termo termo Produções para expr expr
dígito | (expr)
termo * fator | termo / fator | fator
expr + termo | expr - termo | termo
Exercícios • Identifique os tokens terminais e não-terminais, e defina a gramática da expressão Y := A * X + B digito Y | A | X | B lista1 A*X lista2 lista1+B Tokens terminais = := * + Y A X B Não-terminais lista1 lista2
Exercícios if(3 % 2 == 0){ printf (“Número par”); 4++; } else{ } dígitos 3 | 2 | 0 | 4 expr 3%2==0 cmd printf(“numero par”);4++ cmd1 if(expr )cmd else Є Tokens terminais = % == ++ 3 2 0 4 if () printf Não-terminais expr cmd cmd1
voltar
Exercícios • Cria a árvore gramatical para a sentença • 4–3/5 lista lista
lista
dígito -
4
dígito 3
dígito / 5
voltar
More Documents from "cristiane maria pinto"
Compilador+simples+de+uma+passagem
June 2020 5
Como_o_narrador_e_a_lingua_estruturam_o.pdf
April 2020 19
Ind Camed
October 2019 25
Ind Goldencros
October 2019 16
