22
Compiladores BNF e Grafo Sintático Baseado no livro do Prof. Delamaro Como Construir um Compilador

Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

  • Upload
    others

  • View
    10

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Compiladores

BNF e Grafo Sintático

Baseado no livro do Prof. Delamaro – Como Construir um Compilador

Page 2: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Linguagem Livre de Contexto

• Em geral, uma linguagem de programação pertence a uma classe de linguagens chamadas de linguagens livres de contexto.

• Uma das maneiras de se definirem tais linguagens é por meio das gramáticas livres de contexto.

Page 3: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Gramática

Page 4: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Gramática Livre de Contexto

• GLC é É uma quádrupla G = (Ω,Σ,P,S), na qual:

– Σ – é o alfabeto sobre a linguagem definida;

– Ω – é um conjunto não vazio de símbolos não terminais;

– P – é um conjunto de produções da forma A → α, onde A ε Ω e α ε (Σ U Ω)*;

– S – é o símbolo inicial da gramática, S ε Ω

Page 5: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Exemplo de GLC

Page 6: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Exemplo de GLC

Page 7: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Forma de Backus-Naur (BNF)

• A Forma de Backus-Naur (BNF) é uma outra maneira de se definir linguagens livres de contexto.

• Ela é semelhante a uma gramática livre de contexto, mas permite que o lado direito das produções possua alguns operadores.

– seleção

– opcional

– repetição 0 ou mais vezes

– repetição 1 ou mais vezes

Page 8: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

BNF - Seleção

Page 9: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

BNF – Seleção - Exemplo

Page 10: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

BNF – Opcional

Page 11: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

BNF – Opcional - Exemplo

Page 12: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

BNF – Opcional - Exemplo

Page 13: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Repetição – 0 ou mais vezes

Page 14: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Repetição – 0 ou mais vezes - Exemplo

Page 15: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Repetição – 1 ou mais vezes

Page 16: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Repetição – 1 ou mais vezes - Exemplo

Page 17: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

BNF novamente

Page 18: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Grafo Sintático

Page 19: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Grafo Sintático

Page 20: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Grafo Sintático

Page 21: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Grafo Sintático

Page 22: Compiladores - UNIMEP - Universidade Metodista de ...unimep.br/~anbelgamo/compiladores/BNF_Grafo.pdfForma de Backus-Naur (BNF) •A Forma de Backus-Naur (BNF) é uma outra maneira

Exercício

• Escrever na forma de grafo sintático