Compilador+simples+de+uma+passagem

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