Paradigmas de Linguagem de Programação - arieldias.comarieldias.com/material/2019-1/PLP/Aula2.pdf · Expressões regulares e as gramáticas regulares Descrevem a sintaxe das linguagens

9/8/2018

1

Paradigmas de Linguagem de ProgramaçãoSintaxe

Introdução

▪ Sintaxe: conjunto de regras que definem a forma da linguagem;

▪ Como as sentenças podem ser formadas como sequências de componentes básicos –palavras;

▪ A sintaxe não revela nada sobre o significado da sentença;

▪ Exemplo:▪ Em C, palavras chaves como while, do, for, if, são palavras da linguagem;

▪ Palavras não são elementares, elas são construídas com caracteres que pertencem a umalfabeto;

▪ Assim, a sintaxe de uma linguagem é definida por dois conjuntos de regras: regras léxicase regras sintáticas.

Professor Ariel da Silva Dias - www.arieldias.com - Obra Gratuita, proibida reprodução e venda

9/8/2018

2

Introdução

▪ Será apresentado nos próximos slides a definição de compilador e suas fases deanálise léxica, sintática e semântica

▪ Compreender a sintaxe e o comportamento de um compilador é essencial para obom programador


Contexto de um compilador

▪ Aquilo que é usualmente designado por um compilador é de fato um conjunto de programas que no seu conjunto formam o compilador;


9/8/2018

3



▪ Componentes▪ Pré-Processador: processa diretivas; retira os comentários; entre outras tarefas.

▪ Compilador: faz a análise do texto escrito na linguagem fonte e faz a sua transcriçãopara a linguagem destino;

▪ Assembler: faz a transcrição da linguagem intermediária para a linguagem final(máquina);

▪ Loder/Linker: no caso de que se querer um programa executável os “loader/linker”fazem a junção do código máquina produzido pelas anteriores fases a um conjuntode serviços (“run-time routines”) que permitem a criação de um programaindependente



Código Fonte

Tokens e Lexemas

Árvore Sintática Abstrata

AST Decorada

Código de Máquina

Ab

stra

ção

Imp

lem

enta

ção

9/8/2018

4

Processo de compilação

▪ 1) Análise ▪ 1.1) Análise léxica

▪ Organiza caracteres de entrada em grupos, chamados tokens

▪ Erros: tamanho máximo da variável excedido, caracteres inválidos.



▪ 1) Análise ▪ 1.2) Análise sintática

▪ Organiza tokens em uma estrutura hierárquica

▪ Erros: falta de (, ), =, identificador inválido...


9/8/2018

5


▪ 1) Análise ▪ 1.3) Análise semântica

▪ Checa se o programa respeita regras básicas de consistência

▪ Erro: tipos inconsistentes ➔ atribuir uma string em uma variável inteira



▪ Vejamos um exemplo, seja a seguinte instrução de atribuição:▪ posicao = inicial + incremento * 60

▪ Na análise léxica é separada em uma lista de palavras:

▪ (posicao,=,inicial,+,incremento,*,60)


9/8/2018

6



▪ Na análise sintática tenta-se construir uma frase correta com a lista de palavrasproduzidas pela fase anterior. É usual construir uma estrutura em árvore pararepresentar a frase obtida.




▪ Na análise semântica verifica a validade da frase no que diz respeito aos tipos dasentidades utilizadas. Por exemplo, se um dos identificadores presentes na expressãoé do tipo real, então é necessário converter 60 para a sua representação real:


9/8/2018

7

Tabela de símbolos

▪ A informação acerca das palavras que o programa contém tem de fluir entre asvárias fases do compilador;

▪ A tabela de símbolos vai conter uma entrada para cada uma das palavras queforam identificadas pelo analisador léxico;


Gestão de erros

▪ Trata-se de detectar os erros enviando uma mensagem apropriada para outilizador: local do erro; tipo do erro; causa provável;

▪ É importante tentar recuperar do erro automaticamente de forma a podercontinuar a tarefa de compilação até ao máximo possível;


9/8/2018

8

Descrição gráfica das fases


Definição de linguagem

▪ Linguagens Formais▪ Alfabeto: Um conjunto finito e não vazio de símbolos arbitrários é designado por um

alfabeto, e é denotado por Σ;

▪ Um símbolo de um alfabeto é uma entidade abstrata básica, podendo representarnúmeros, letras, desenhos, etc, por exemplo: 1,2,a,b,c.

▪ Um alfabeto é representado por: Σ (sigma)

Σ = {0,1}

Σ = {a,b}


9/8/2018

9


▪ Linguagens Formais▪ Palavra (ou cadeia de caracteres): As sequências finitas de símbolos (do alfabeto)

justapostos;

▪ O conjunto de todas as palavras sobre Σ é denotado por Σ ∗;

▪ A palavra vazia, não contém nenhuma letra, e é denotada por ɛ;

▪ Seja Σ = {a,b}

▪ Então as cadeias possíveis são:▪ w = ɛ▪ w = a▪ w = b▪ w = ab



▪ Linguagens Formais▪ Linguagem: Um conjunto arbitrário de palavras de Σ∗ é designado por uma

linguagem e é usualmente denotado por L;

▪ Se Σ representa um alfabeto,

▪ Então Σ* representa o conjunto de todas as palavras possíveis sobre Σ;

▪ Σ+ representa o conjunto de todas as palavras excetuando a palavra vazia.


9/8/2018

10


▪ Linguagens Formais▪ Linguagem

▪ Assim podemos dizer que:

▪ Σ* = {ɛ, a, b, ab, ba, aab, abb, aaaa, ...}

▪ Σ+ = Σ* - ɛ = {a, b, ab, ba, aab, abb, aaaa, ...}

▪ Uma linguagem L é geralmente definida como um subconjunto de Σ*;

▪ Uma sentença é geralmente definida como uma cadeia pertencente à linguagem L.



▪ Linguagens Formais▪ Tamanho ou Comprimento

▪ O tamanho ou comprimento de uma cadeia w, representado por |w|, é o número de símbolos que compõem a cadeia;

▪ w = ɛ |w| = 0

▪ w = a |w| = 1

▪ w = ab |w| = 2

▪ w = abb |w| = 3


9/8/2018

11


▪ Linguagens Formais▪ Concatenação de Palavras: a concatenação de w e v é a cadeia obtida pela adição

dos símbolos de v no final de w. Nenhum símbolo pode ser mudado de lugar;

▪ Se w = a1, a2,...,an e v = b1, b2, ... ,bn

Então a concatenação, w o v = a1a2...anb1b2...bn

Por exemplo: seja w = ababa e v = cdcdcd

Então w o v = ababacdcdcd



▪ Linguagens Formais▪ Concatenação de Palavras

▪ A operação de concatenação satisfaz as seguintes propriedades:▪ a) associatividade ▪ b) elemento neutro a direita e a esquerda


9/8/2018

12


▪ Linguagens Formais▪ Concatenação de Palavras

▪ A operação de concatenação também vale para as linguagens▪ L1 o L2 = {x o y | x Є L1 e y Є L2}

▪ Exemplo:▪ L1 = {a, bc} e L2 = {aa, cb, bb}▪ L1 o L2 = {x o y | x Є L1 e y Є L2} = {▪ L1 o L2 = {



▪ Linguagens Formais▪ Sufixo, prefixo e subcadeia


9/8/2018

13


▪ Linguagens Formais▪ União, Intersecção e Diferença

▪ União: L1 U L2 = {w: w Є L1 ou w Є L2}

▪ Intersecção: L1 ∩ L2 = {w: w Є L1 e w Є L2}

▪ Diferença: L1 - L2 = {w: w Є L1 e w Ɇ L2}

▪ Exemplo:

▪ L1={a, b, aa, ab, abb, aab, aaa} e L2={a, aa, aaa, aaaa}

▪ União: L1 U L2 =

▪ Intersecção: L1 ∩ L2 =

▪ Diferença: L1 - L2 =



▪ Linguagens Formais▪ A imagem inversa de P, denotada por P−1 é a palavra que se obtém de P por inversão

da ordem das letras. Por exemplo: se P = abcd, então

▪ P −1 = dcba;


9/8/2018

14

Análise léxica

▪ Regras Léxicas▪ Especificam o conjunto de caracteres que constituem o alfabeto da linguagem, bem

como a maneira que eles podem ser combinados;

▪ Exemplo

▪ Pascal: letras maiúsculas e minúsculas são idênticas;

▪ C e ADA: letras maiúsculas e minúsculas são diferenciadas;

▪ Pascal: sinal de diferente → <>

▪ C: sinal de diferente → !=

▪ ADA: sinal de diferente → /=:


Análise léxica

▪ Seu objetivo é analisar a entrada dada (programa fonte) e dividi-la em sequênciasconsiderando os tokens da linguagem, definidos por expressões regulares;

▪ Cada token é normalmente formado por seu tipo (se é um operador lógico, umidentificador, um número inteiro, etc.) e pelo seu valor e outros atributos.


9/8/2018

15

Análise léxica

▪ Este valor vai depender do tipo do token e normalmente corresponde àsequência de caracteres realmente lida da entrada.


Análise léxica

▪ Tarefa principal▪ Ler o arquivo onde se encontra o programa-fonte

▪ Produzir como saída uma sequência de tokens com seus respectivos códigos que oAnalisador Sintático usará para validar regras da gramática;


9/8/2018

16

Análise léxica

▪ Primeira fase do compilador;

▪ Lê a sequência de caracteres do canal de entrada e produz uma sequência de palavras (lexemas);

▪ Expressões regulares e as gramáticas regulares

▪ Descrevem a sintaxe das linguagens de programação

▪ Dado uma palavra

▪ Trata-se agora de, dado uma linguagem, ser capaz de reconhecer de forma automática se uma dada frase pertence a essa linguagem.


Análise léxica

▪ Lê os caracteres de entrada (scanner) e os agrupa em sequências chamadas lexemas (tokens);

▪ Os tokens são consumidos na fase seguinte (análise sintática);


Analisador Léxico (scanner)

token

GetToken()

Programa

Fonte Para Análisesemântica

Analisador sintático (parser)

Tabela de Símbolos (identificadores e

constantes)

9/8/2018

17

Análise léxica

▪ A tabela de símbolos é utilizada para diferenciar palavras e símbolos reservados da linguagem (while, for, =, >, <) de identificadores definidos pelo usuário


Lexema (lido) Token (Tipo)

; <PONTO_VIRGULA>

aux <IDENTIFICADOR>

while <PALAVRA_RESERVADA>

Análise léxica

▪ A tabela de símbolos também é utilizada para armazenar o tipo e o valor das variáveis e o seu escopo


Lexema (lido) Token (Tipo) Valor

; <PONTO_VIRGULA> -

aux <IDENTIFICADOR> 10

while <PALAVRA_RESERVADA> -

9/8/2018

18

Análise léxica

▪ Classes de tokens 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.


Análise léxica

▪ Exemplos de tokens que podem ser reconhecidos em uma linguagem deprogramação como C:


9/8/2018

19

Análise léxica

▪ O analisador léxico desconsidera o trecho do código fonte que encontra-se entredelimitadores de comentários.

▪ Além disso, ele desconsidera espaços em branco colocados pelos programadoresa fim de melhorar a legibilidade do código fonte (endentação).


Análise léxica

EXEMPLO: seja a cadeia 3.2 + (2 * 12.01), o analisador léxico teria:


9/8/2018

20

Análise léxica


Expressão Regular

a

corresponde a

a

abc abc

[abc] a, b ou c

[a-f] a,b,c,d,e ou f

[0-9] qualquer digito de 0 a 9

X+ um ou mais elemento de X

X* zero ou mais elemento de X

[0-9]+ qualquer inteiro

(...) agrupamento de expressão

| alternância OU

(a|b|c)* equivale a [a-c]*

Análise léxica

▪ Exemplo: Expressão para reconhecer números reais (0, 27, .12, 2.19)▪ [0-9]+|[0-9]+\.[0-9]+|\.[0-9]+ [0-9]+(\.[0-9]+)?|\.[0-9]+ [0-9]*(\.)?[0-9]+


9/8/2018

21

Análise sintática

▪ Regras Sintáticas▪ Especificam as sequências de símbolos que constituem estruturas sintáticas válidas;

▪ Estas regras permitem o reconhecimento de expressões e comandos;

▪ Exemplo:

▪ Pascal: atribuição → a:=b;

▪ C: atribuição → a=b;


Análise sintática

As linguagens de programação possuem regras precisas para descrever a estruturasintática de programas bem formados;

Exemplo: Linguagem C

Funções➔ declaração e comando

Comando➔ expressões

A estrutura sintática das construções de uma linguagem de programação éespecificada pelas regras gramaticais de uma gramática livre de contexto


9/8/2018

22

Análise sintática

Benefícios para projetistas de linguagens:

▪ Uma gramática provê uma especificação sintática precisa e fácil de entenderpara as linguagens de programação;

▪ A partir de determinadas classes gramaticais, podemos construirautomaticamente um analisador sintático eficiente;

▪ Durante o processo de construção do analisador, podem ser detectadasambiguidades sintáticas;

▪ Uma gramática permite o desenvolvimento de uma linguagem iterativamente,possibilitando lhe acrescentar novas construções para realizar novas tarefas;


Análise sintática

▪ Utiliza os tokens produzidos pela análise léxica e verifica a formação do programa com o uso de GLC (Gramáticas Livres de Contexto)▪ A partir dos tokens é criada uma representação intermediária da árvore sintática ➔

mostra a estrutura gramatical da sequência de tokens;


9/8/2018

23

Análise sintática

expr = a + b * 60

<identificador, 1>,

< = >,

<identificador, 2>,

<+>,

<identificador, 3>,

< * >,

<numero, 60>


Percorrendo a árvore e consultando a GLC é possível verificar se a expressão pertence à

linguagem.=

<id,1> +

<id,2> *

<id,3> 60

Análise sintática

▪ O analisador sintático recebe do analisador léxico uma cadeia de tokensrepresentando o programa fonte e verifica se essa cadeia de tokenspertence à linguagem gerada pela gramática.


9/8/2018

24

Análise sintática

O analisador sintático constrói uma árvore de derivação e a passa aorestante do front-end do compilador para processamento.

Obs: na prática não é necessário construir a árvore de derivaçãoexplicitamente, pois a ações de verificação e tradução podem serimplementados em um único módulo.


Análise sintática

Existem 3 estratégias gerais de análise sintática para o processamento degramáticas: Universal, Descendente (Top –Down) e Ascendente (Bottom –Up).

Em ambas as estratégias a entrada do analisador sintático é consumida daesquerda para a direita, um símbolo de cada vez

Os analisadores criados à mão normalmente utilizam gramáticas LL

Os analisadores sintáticos para a maioria de gramáticas LR geralmente sãoconstruídos utilizando ferramentas automatizadas


9/8/2018

25

Análise sintática

▪ Para descrever uma linguagem é necessário uma série de regras gramaticais;

▪ As regras são formadas por uma única estrutura do lado esquerdo seguida dometasímbolo “::=“ e por uma sequência de itens do lado direito (símbolos ouestruturas);

▪ Estruturas entre <> são chamadas de não terminais;

▪ Símbolos como garota e cachorro são chamadas de terminais;

▪ As regras gramaticais são as produções.


Análise sintática

▪ Exemplo de uma gramática para expressões aritméticas de adição emultiplicação:▪ <exp>::= <exp>+<exp> | <exp>*<exp> | (exp) | <num>

▪ <num> ::= <num><digito> | <digito>

▪ <digito> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9


9/8/2018

26

Análise sintática

▪ BNF▪ Sentenças simples consistem de uma frase nominal e de uma frase verbal seguida de

um ponto, da seguinte maneira:

▪ <sentence> ::= <frase_nominal><frase_verbal>.

▪ Deve-se saber descrever a estrutura de uma frase nominal e de uma frase verbal:

▪ <frase_nominal> ::= <artigo><substantivo>

▪ <artigo> ::= um | a

▪ <substantivo> ::= garota | cachorro

▪ <frase_verbal> ::= <verbo> <frase_nominal>

▪ <verbo> ::= viu | abraça


Análise sintática

▪ Cada regra gramatical apresentada consiste de uma string colocada entre “<“ e“>”, esta string é o nome da estrutura que está sendo descrita;

▪ O símbolo ::= pode ser lido como “consiste de” ou “é o mesmo que”;

▪ Após o símbolo ::=, temos uma sequência de outros nomes e símbolos;


9/8/2018

27

Análise sintática

▪ Construção de uma sentença legal:▪ Inicia-se com o símbolo <sentença> e prossegue-se trocando o lado esquerdo por

alternativas do lado direito nas regras;

▪ Este processo criará uma derivação na linguagem;

▪ Desta forma, podemos construir a sentença: “A garota viu um cachorro”;


Análise sintática


▪ Montando a derivação da sentença: “a garota viu um cachorro”▪ <sentença> → <frase_nominal><frase_verbal>.▪ → <artigo><substantivo><frase_verbal>.▪ → a <substantivo><frase_verbal>.▪ → a garota <frase_verbal>.▪ → a garota <verbo><frase_nominal>.▪ → a garota viu <frase_nominal>.▪ → a garota viu <artigo><substantivo>.▪ → a garota viu um <substantivo>.▪ → a garota viu um cachorro.

▪ Pode-se começar com a sentença “a garota viu um cachorro”, e voltar até <sentença> para provar que é uma sentença válida da linguagem.

9/8/2018

28

Análise sintática - Extensão da BNF ➔ EBNF (Extend BNF)


Definição EBNF para uma linguagem de programação simples

Definição EBNF para uma calculadora Definição de sintaxe para uma linguagem

Análise sintática – Recursão a Esquerda

Na gramática a seguir, o não-terminal E representa expressões consistindo emtermos separados pelo operador +; T representa termos consistindo em fatoresseparados pelo operador *; e F representa fatores que podem ser expressos entreparênteses ou identificadores.

Essa gramática não pode ser usada com o método de análise descendente pois érecursiva a esquerda.


9/8/2018

29


Gramáticas são recursivas à esquerda se possui um não-terminal A para o qualexistam derivações do tipo A➔Aα para uma cadeia α.

Para o par de produções recursivas à esquerda

A➔ Aα|β

A substituição abaixo elimina a recursão

imediata à esquerda:

A➔ βA’

A’➔ αA’ | ε

Nenhuma outra modificação é requerida a partir de A.



Gramática para expressões simples:

E → E + T | T

T → T * F | F

F → ( E ) | id

Aplicando transformação na Primeira Regra

E → E + T | T é do tipo

A ➔ Aα | β

Obtemos:

A ➔ βA’

E ➔TE’

A’ ➔ αA’ | ε

E’ ➔ +TE’ | ε


9/8/2018

30


Gramática para expressões simples:

E → E + T | T

T → T * F | F

F → ( E ) | id

Aplicando transformação na Segunda Regra

E → T * F | F é do tipo

A ➔ Aα | β

Obtemos:

A ➔ βA’

T ➔FT’

A’ ➔ αA’ | ε

E’ ➔ *FT’ | ε



Assim, obtemos a partir de:

E → E + T | T

T → T * F | F

F → ( E ) | id

A gramática equivalente sem recursão à esquerda:

E → TE’

E’ → +TE’

T → FT’T’ → *FT’ | ε

F → (E) | id


9/8/2018

31


Exemplo 2:

A→ Aa | b

Exemplo 3:

S → SS+ | SS* | a

Exemplo 4:

S → Sa | B

B → Bb | c

Para o par de produções recursivas à esquerda

A ➔ Aα|β

Considere para eliminar a recursão

A ➔ βA’

A’ ➔ αA’ | ε


Análise sintática – Recuperação de erro

O recuperador de erros em um analisador sintático possui objetivos simples, masdesafiadores:

▪ Informar a presença de erros de forma clara e precisa;

▪ Recuperar-se de cada erro com rapidez suficiente para detectar errossubsequentes;

▪ Acrescentar um custo mínimo no processamento de programas corretos.

Como um recuperador de erro deve informar a presença de um erro?

No mínimo ele precisa informar o local no programa fonte onde o erro foidetectado, pois existe uma boa chance de que o local exato do erro seja em umdos tokens anteriores.


9/8/2018

32


Recuperação em nível de frase

Ao detectar um erro, o analisador sintático pode realizar a correção localsobre o restante da entrada.

Uma correção local típica compreende a substituição de uma vírgula por umponto-e-vírgula, exclusão de um ponto-e-vírgula desnecessário.

A escolha da correção local fica a critério do projetista do compilador.



Produções de Erro

Nesta estratégia de recuperação de erro podemos estender a gramática dalinguagem em mãos com produções que geram construções erradas,antecipando assim os erros mais comuns.


9/8/2018

33

Análise sintática

▪ Não é possível enumerar a sintaxe de todos os programas das mais diferenteslinguagens;

▪ É necessário uma maneira de definir um conjunto infinito usando uma descriçãofinita:

▪ A sintaxe de uma linguagem é definida através de uma gramática;

▪ Gramática: conjunto de regras que definem todos os construtores que podem seraceitos na linguagem.


Análise sintática

▪ Fortran foi definido através da especificação de algumas regras em inglês;

▪ Algol 60 foi definido através de uma gramática livre de contexto desenvolvida porJonh Backus;▪ Essa gramática ficou conhecida como BNF (Backus-Naur Form);

▪ BNF foi utilizada posteriormente na definição de várias linguagens como C, Pascale Ada;

▪ BNF é uma metalinguagem pois consiste numa linguagem para descrição deoutras linguagens.


9/8/2018

34

Análise sintática

▪ Observe os dois trechos de código a seguir, sendo o código a. em C e o código b. em Pascal

a. b.

while(x!=y) while x<>y do

{ begin

... ...

} end

▪ Ambas possuem a mesma estrutura conceitual, porém, diferem na aparência léxica;

▪ Quando duas construções diferem apenas no nível léxico, se diz que elas seguem a mesmasintaxe abstrata e diferem na sintaxe contreta.


Análise sintática

▪ Com tudo isso, é possível concluir que a descrição sintática de uma linguagem:▪ Ajuda o programador a saber como escrever um programa sintaticamente correto;

▪ Pode ser usada para determinar se um programa está sintaticamente correto ➔ este é exatamente o trabalho do compilador!


9/8/2018

35

Análise sintática - Análise Top-Down

▪ Como reconhecer se uma sentença está de acordo com uma gramática?▪ Pode-se implementar reconhecedores de sentença

▪ Recursivamente, com retrocesso

▪ Com mecanismo preditivo▪ First e Follow

▪ Para usar os reconhecedores, primeiramente deve-se transformar a Gramática Livre de Contexto

▪ Eliminação de produções vazias

▪ Eliminação de recursividade a esquerda

▪ Fatoração de uma gramática


Análise sintática – Conjuntos First

▪ First(α)▪ Definição informal: conjunto de todos os terminais que começam com qualquer

sequência derivável de α▪ Definição formal

▪ Se existe um t ∈ T e um β ∈ V* tal que α ⇒* t β então t ∈ First(α)

▪ Se α ⇒* ε então ε ∈ First(α)

A → B | C | D first(A) = {b, c, d}

B→ b first(B)= {b}

C → c first(C)= {c}

D → d first(D)= {d}


9/8/2018

36


▪ Para determinar o FIRST(A):▪ Se a é terminal, então o first(a) = a;

▪ Se A é não terminal e A→aα é uma produção, então se acrescenta a ao conjunto defirst de A, logo: first(A)=a;

▪ Se A→ε é uma produção ε, logo first(A)=ε;

▪ Se A→Y1Y2...Yk é uma produção, então todo i tal que todos Y1...Yi-1 são nãoterminais e FIRST(Yj) contém ε, onde j=1,2...i-1. acrescente todo símbolo diferentede ε de FIRST(Yj) a FIRST(A). Se ε ∈ FIRST(A), para todo i=1,2..k. então acrescente ε aFIRST(A).



E → TE’

E’ → +TE’ | ε

T→ FT’

T’→ *FT’ | ε

F → (E) | id

First(E) = { ? }

First(E’) = { ? }

First(T) = { ? }

First(T’) = { ? }

First(F) = { ? }


9/8/2018

37


E → TE’

E’ → +TE’ | ε

T→ FT’

T’→ *FT’ | ε

F → (E) | id

First(E) = First(T) = First(F) ={ (,id }

First(E’) = { +, ε}

First(T) = First(F) = { (, id }

First(T’) = { *, ε }

First(F) = { (, id }



E → TE’

E’ → +TE’ | ε

T→ FT’

T’→ *FT’ | ε

F → (E) | id


First(E’) = { +, ε}


First(T’) = { *, ε }



Se F derivasse em ε seria preciso incluir o first(T’)

em first(T)

9/8/2018

38


E → TE’

E’ → +TE’ | ε

T→ FT’

H → E’T

T’→ *FT’ | ε

F → (E) | id


First(E’) = { +, ε}


First(H) = { ? }

First(T’) = { *, ε }




E → TE’

E’ → +TE’ | ε

T→ FT’

H → E’T

T’→ *FT’ | ε

F → (E) | id


First(E’) = { +, ε}


First(H) = { First(E’) U First(T) }

First(T’) = { *, ε }



9/8/2018

39


E → TE’

E’ → +TE’ | ε

T→ FT’

H → E’T

T’→ *FT’ | ε

F → (E) | id


First(E’) = { +, ε}


First(H) = { +, (, id }

First(T’) = { *, ε }



Análise sintática – Conjuntos Follow

▪ Se A é um não-terminal, o follow(A) é o conjunto de terminais imediatamenteseguintes (à direita) de A


9/8/2018

40


▪ Para determinar follow(A)1. Colocar $ em follow(S) se S é o símbolo de partida. $ é o marcador de fim de

entrada durante análise

2. Se existe uma produção A→αBβ e β ∉ ε então tudo que estiver em first(β), excetoε, deve ser adicionado em follow(B)

3. Se existe uma produção A→ αB ou A→ αBβ onde first(β) contem ε (β → ε), entãotudo que está em follow(A) está em follow(B)



E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | id



First(E’) = { +, ε}


First(T’) = { *, ε }


Follow(E) = { ), $ }

Follow(E’) = Follow(E) = { ), $ }

Follow(T) = First(E’) U Follow(E) U Follow(E’) = { +, ), $}

Follow(T’) = Follow(T) = {+, ), $}

Follow(F) = First(T’) U Follow(T) U Follow(T’) = { *, +, ), $}

9/8/2018

41


E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | id



First(E’) = { +, ε}


First(T’) = { *, ε }


Follow(E) = { ), $ }





Regra 2 e regra 1


E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | id



First(E’) = { +, ε}


First(T’) = { *, ε }


Follow(E) = { ), $ }





Regra 3

9/8/2018

42


E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | id



First(E’) = { +, ε}


First(T’) = { *, ε }


Follow(E) = { ), $ }





Regra 2 e Regra 3


E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | id



First(E’) = { +, ε}


First(T’) = { *, ε }


Follow(E) = { ), $ }





Regra 3

9/8/2018

43


E → TE’

E’ → +TE’ | ε

T → FT’

T’ → *FT’ | ε

F → (E) | id



First(E’) = { +, ε}


First(T’) = { *, ε }


Follow(E) = { ), $ }





Regra 2 e Regra 3

Análise sintática – First Follow

S→AB first(S)={c} follow(S)={ $ }

A→c | ε first(A)={c, ε} follow(A)={ c }

B→ cbB | ca first(B)={c} follow(B)={ $ }


9/8/2018

44

Análise sintática – Analisador Top-Down

▪ A análise top-down é realizada da raiz para as folhas

▪ Parte-se de um não-terminal que é o símbolo inicial da gramática em direção aos terminais


Análise sintática preditiva não-recursiva

▪ O símbolo da cadeia de entrada, em análise, é suficiente para determinar qual regra de produção deve ser escolhida

▪ São construídos utilizando gramáticas LL ( 1 ) ▪ Cadeia de entrada é analisada da esquerda para a direita ( Left-toright)

▪ A derivação das produções é feita mais a esquerda ( Leftmost)

▪ A cada passo é observado um ( 1) símbolo a frente para determinar que ação deve ser tomada


9/8/2018

45


▪ Condições▪ Eliminar a recursividade a esquerda

▪ Fatorar a gramática

▪ Construir o conjunto first e follow



▪ Construção da tabela preditiva▪ Dimensão1: não terminal X

▪ Dimensão2: símbolo de entrada (terminal) t

▪ A entrada (X, t) contém a regra da produção a aplicar → obtida a partir dosconjuntos first e follow


Não Terminal Símbolo de Entrada

a b c

S erro erro S→ cAa

A A→B A→B A→cB

B B→ε B→bcB erro

S→cAa first(S)={c} follow(S)={ $ }

A→cB | B first(A)={b, c, ε} follow(A)={ a }

B→ bcB | ε first(B)={b, ε} follow(B)={ a }

9/8/2018

46

Análise Sintática – Tabela Preditiva

Pilha Entrada Ação

S$ cbca$



a b c




Entrada: cbca

Topo da pilha SS deriva em c?Sim: S→ cAa



S$ cbca$ S→cAa

cAa$ cbca$



a b c




Entrada: cbca

S→ cAasubstitui na pilha o S por

cAa

9/8/2018

47



S$ cbca$ S→cAa

cAa$ cbca$ casar(c)



a b c




Entrada: cbca

O topo da pilha é igual ao valor do topo de entrada



S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$



a b c




Entrada: cbca

A deriva em b?Sim: A→B

9/8/2018

48



S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$



a b c




Entrada: cbca

Substitui o A na pilha por B



S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$



a b c




Entrada: cbca

B deriva em b?Sim: B→bcB

9/8/2018

49



S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$ B→bcB



a b c




Entrada: cbca

B deriva em b?Sim: B→bcB


S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$ B→bcB

bcBa$ bca$ casar(b)



a b c




Entrada: cbca


9/8/2018

50



S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$ B→bcB

bcBa$ bca$ casar(b)

cBa$ ca$ casar(c)



a b c




Entrada: cbca




S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$ B→bcB

bcBa$ bca$ casar(b)

cBa$ ca$ casar(c)

Ba$ a$ B→ε



a b c




Entrada: cbca

B deriva em a?SIM: quando B→ε

9/8/2018

51



S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$ B→bcB

bcBa$ bca$ casar(b)

cBa$ ca$ casar(c)

Ba$ a$ B→ε

a$ a$ casar(a)



a b c




Entrada: cbca




S$ cbca$ S→cAa

cAa$ cbca$ casar(c)

Aa$ bca$ A→B

Ba$ bca$ B→bcB

bcBa$ bca$ casar(b)

cBa$ ca$ casar(c)

Ba$ a$ B→ε

a$ a$ casar(a)

$ $ aceita



a b c




Entrada: cbca


9/8/2018

52

Análise sintática – Analisador Bottom-up

▪ A análise top-down é realizada das folhas para a raiz

▪ Parte-se dos símbolos terminais em direção ao símbolo inicial da gramática



id * id


F * id

id

T * id

F

id

T * F

F id

id

T

T * F

F id

id

E

T

T * F

F id

id

E → E + T | T T → T * F | F F → (E) | id

Entrada: id*id

9/8/2018

53


▪ O processo de análise sintática ascendente pode ser encarado como um processode “reduzir” uma cadeia w para o símbolo inicial da gramática

▪ Redução : operação de substituição do lado direito de uma produção pelo não-terminal correspondente do lado esquerdo

▪ Para a regra A→ α , α pode ser reduzido em A



▪ Analisadores sintáticos Bottom-up▪ Analisadores conhecidos como empilha-reduz (shift-reduce)

▪ Etapas do reconhecimento: determinar quando reduzir e determinar a produção aser utilizada para que a análise prossiga


9/8/2018

54


▪ Componentes do analisador bottom-up▪ Pilha, onde os símbolos a serem reduzidos são empilhados▪ Tabela sintática, que guia o processo de shift e reduce

▪ Processo de reconhecimento de uma sentença1. Empilhar símbolos da cadeia de entrada2. Quando um lado direito apropriado de uma produção aparece, ele é reduzido

(substituído) pelo lado esquerdo da produção3. Se a análise tiver sucesso, esse processo ocorre até que os símbolos da cadeia de

entrada sejam todos consumidos e a pilha fique apenas com o símbolo inicial dagramática



Gramática:

S→(L) | a

L→ L+S | S

Entrada: a+a

Pilha Cadeia Regra

$ (a+a)$

$ (a+a)$ shift (

$( a+a)$ shift a

$(a +a)$ reduce S→a

$(S +a)$ reduce L→S

$(L +a)$ shift +

$(L+ a)$ shift a

$(L+a )$ reduce S→a

$(L+S )$ reduce L→L+S

$(L )$ shift )

$(L) $ reduce S→(L)

$S $ aceita

9/8/2018

55


▪ Operações durante a análise:▪ Shift: coloca-se no topo da pilha o primeiro símbolo da cadeia de entrada

▪ Reduce: substitui-se o lado direito do handle pelo seu lado esquerdo

▪ Aceita: a cadeia de entrada é reconhecida

▪ Erro: a cadeia de entrada não é reconhecida


Análise semântica

▪ A semântica define o significado dos programas sintaticamente corretos;

▪ Por exemplo, em C, a instrução

if(a>b)

max = a;

else

max = b;

▪ Diz que a expressão a>b deve ser avaliada e, dependendo do retorno (true ou false), um dos dois comandos de atribuição será executado.


9/8/2018

56

Análise semântica

▪ Regras sintáticas: mostram como formar o comando;

▪ Regras semânticas: mostram qual é o efeito do comando;

▪ Erros semânticos ▪ tipos inválidos - o programa dá um resultado, mas não é correto!

▪ o computador não advinha o que eu quero

▪ logo: o programa que escrevi não resolve o problema pretendido

▪ os erros semânticos são os mais difíceis de corrigir


Análise semântica

▪ Conceitos semânticos básicos de uma LP▪ Variáveis: questões semânticas associadas a declaração (escopo, tipo e tempo de

vida);

▪ Valores e Referência: se o valor associado a variável denota localização na memória ou conteúdo localizado na memória;

▪ Expressões: possuem regras para serem escritas envolvendo os tipos de expressões permitidas;


9/8/2018

57

Análise semântica

▪ Abstração

▪ Processo de identificar apenas as qualidades ou propriedades relevantes dofenômeno que se quer modelar;

▪ As LP são as ferramentas com as quais os programadores podem implementar osmodelos abstratos;

▪ Por outro lado, as próprias LP são abstrações do processador subjacente;


Análise semântica

▪ Abstração

▪ Sugere a distinção que deve ser feita entre “o que” o programa faz e “como” ele éimplementado”;

▪ Quando um procedimento é chamado , pode-se concentrar apenas no que ele faz;

▪ Quando se está escrevendo o procedimento deve-se concentrar em como implementá-lo;

▪ As primeiras abstrações foram o uso de mnemônicos em assembly;


9/8/2018

58

Análise semântica

▪ Programas trabalham com entidades▪ Entidades: Variáveis, rotinas e comandos;

▪ As entidades dos programas possuem propriedades chamadas atributos;

▪ Os valores dos atributos devem ser definidos antes de sua utilização.


Análise semântica

▪ A definição do valor de um atributo é conhecida como amarração ou binding;


9/8/2018

59

Análise semântica

▪ Amarração estática: ▪ A amarração é estabelecida antes do tempo de execução e não pode ser alterada

depois;

▪ Exemplo: um conjunto de valores é amarrado ao tipo inteiro no tempo de implementação da linguagem, assim, a definição da linguagem específica que o tipo inteiro deve ser suportado e a implementação da linguagem amarra-o à representação da memória.


Análise semântica

▪ Amarração dinâmica: ▪ A amarração é estabelecida em tempo de execução.

▪ Exemplo: as variáveis são amarradas a um valor em tempo de execução;


9/8/2018

60

Exemplo

▪ Analise os códigos abaixo e identifique os erros em léxico, sintático e semântico:


int I2, A@;I2 = 0;while(I2 <= 0);

I = I+1;I2 = “a”;

int a, b c;a = 2;b := 3;c = 4;

media = (a+b+c)/3;

Fases da compilação


Analisador Léxico

total = num1 + num2 * 50

9/8/2018

61



Analisador Léxico


(id,1)(=>(id,2)(+>(id,3)(*>(50>



Analisador Léxico


Analisador Sintático

(id,1)(=>(id,2)(+>(id,3)(*>(50>

=(id,1) +

(id,2) *(id,3) 50

9/8/2018

62



Analisador Léxico



Analisador Semântico

(id,1)(=>(id,2)(+>(id,3)(*>(50>

=(id,1) +

(id,2) *(id,3) 50

=(id,1) +

(id,2) *(id,3) atof(50)



Analisador Léxico




Gerador de Código Intermediário

(id,1)(=>(id,2)(+>(id,3)(*>(50>

=(id,1) +

(id,2) *(id,3) 50

t1 = atof(50)t2 = id3 * t1t3 = id2 + t2id1 = t3

=(id,1) +

(id,2) *(id,3) atof(50)

9/8/2018

63



Analisador Léxico





(id,1)(=>(id,2)(+>(id,3)(*>(50>

=(id,1) +

(id,2) *(id,3) 50


Otimizador de Código

t1 = id3 * 50.0id1 = id2 + t1

=(id,1) +

(id,2) *(id,3) atof(50)



Analisador Léxico





(id,1)(=>(id,2)(+>(id,3)(*>(50>

=(id,1) +

(id,2) *(id,3) 50


Otimizador de Código

t1 = id3 * 50.0id1 = id2 + t1

=(id,1) +

(id,2) *(id,3) atof(50)

Gerador de Código

LDF R2,id3MULF R2, R2, #50.0LDF R1, id2ADDF R1, R1, R2STF id1, R1

9/8/2018

64

Referências

▪ SEBESTA, Robert W. Conceitos de linguagens de programação. 9ª ed. PortoAlegre: Bookman, 2011. 792 p. ISBN 978-85-7780-791-8.

▪ Notas de aula – Professora Isabel Harb Manssour


Documents

Paradigmas de Linguagem de Programação - arieldias.comarieldias.com/material/2019-1/PLP/Aula2.pdf · Expressões regulares e as gramáticas regulares Descrevem a sintaxe das linguagens