Aula_3_Ana_Sintatica_GLC_Comp_2S_2023_Parte_01_Final

Prévia do material em texto

<p>Universidade de Brasília</p><p>Compiladores</p><p>2o semestre - 2023</p><p>Prof. Luís Filomeno</p><p>3.6 – Propriedade de fechamento das GLC</p><p>Linguagens livres de contexto são fechadas em:</p><p>-União</p><p>- Concatenação</p><p>- Operação estrela de Kleene</p><p>a)União</p><p>Sejam L1 e L2 são duas linguagens livres de contexto. Então L1 U L2 também é livre</p><p>de contexto.</p><p>Exemplo 3.7:</p><p>A gramática correspondente G terá as propriedades adicionais de S → S1|S2</p><p>Compiladores Aula 3</p><p>3.6 – Propriedade de fechamento das GLC</p><p>b) Concatenação</p><p>Sejam L1 e L2 são duas linguagens livres de contexto. Então L1L2 também é livre de</p><p>contexto.</p><p>Exemplo 3.8:</p><p>A gramática correspondente G terá as propriedades adicionais de S → S1S2</p><p>c) Estrela de Kleene (Kleene Star)</p><p>Se L é uma linguagem livre de contexto, então L* também é livre de contexto.</p><p>Exemplo 3.9:</p><p>Compiladores Aula 3</p><p>3.6 – Propriedade de fechamento das GLC</p><p>Linguagens livres de contexto não estão fechadas em:</p><p>- Intersecção: Se L1 e L2 são linguagens livres de contexto, então L1 L2 não é</p><p>necessariamente livre de contexto.</p><p>- Interseção com linguagem regular: se L1 é uma linguagem regular e L2 é uma</p><p>linguagem livre de contexto, então L1 L2 é uma linguagem livre de contexto.</p><p>- Complemento: Se L1 é uma linguagem livre de contexto, então L1’ pode não ser</p><p>livre de contexto.</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>Introdução</p><p>Teorema 3.1</p><p>Seja G = (V, T, S, P) uma gramática livre de contexto. Então para cada w ∈ L(G),</p><p>existe uma árvore de derivação de G cujo resultado é w. Por outro lado, a realização</p><p>de qualquer árvore de derivação está em L(G). Além disso, se é qualquer árvore de</p><p>derivação parcial para G cuja raiz é rotulada como S, então o resultado de tG é uma</p><p>forma sentencial de G.</p><p>Teorema 3.2</p><p>Suponha que G = (V, T, S, P) seja uma gramática livre de contexto que não possui</p><p>nenhuma regra da forma</p><p>A→λ,</p><p>ou</p><p>A→B,</p><p>onde A, B ∈ V . Então o método de análise de busca exaustiva pode ser transformado</p><p>em um algoritmo que, para qualquer w ∈ Σ^∗, produz uma análise de w ou nos diz</p><p>que nenhuma análise é possível.</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>Introdução</p><p>Também discutimos formas normais, isto é, formas gramaticais que são muito</p><p>restritas, mas são, no entanto, gerais no sentido de que qualquer gramática livre de</p><p>contexto tem um equivalente na forma normal. Embora existam vários tipos de</p><p>formas normais; aqui apresentam-se apenas duas das mais úteis: Forma normal de</p><p>Chomsky e forma normal de Greibach.</p><p>Antes de podermos estudar linguagens livres de contexto com maior profundidade,</p><p>devemos atender a alguns assuntos técnicos. A definição de um ambiente de gramática</p><p>livre de contexto não impõe nenhuma restrição no lado direito de uma produção.</p><p>Contudo, a liberdade total não é necessária e, na verdade, é um prejuízo em alguns</p><p>argumentos. No Teorema 3.2, vemos a conveniência de certas restrições nas formas</p><p>gramaticais; eliminar regras da forma A → λ e A → B torna os argumentos mais fáceis.</p><p>Em muitos casos, é desejável impor restrições ainda mais rigorosas à gramática. Por</p><p>causa disso, precisamos examinar métodos para transformar uma GLC arbitrária em uma</p><p>equivalente que satisfaça certas restrições em sua forma.</p><p>Também investigamos formas normais para gramáticas livres de contexto. Uma forma</p><p>normal é aquela que, embora restrita, é ampla o suficiente para que qualquer gramática</p><p>tenha uma versão equivalente da forma normal.</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>Numa GLC, pode acontecer que todas as regras e símbolos de produção não sejam</p><p>necessários para a derivação de strings (linguagem ou token). Além disso, pode haver</p><p>algumas produções nulas e produções unitárias. A eliminação destas produções e</p><p>símbolos é chamada de simplificação dos GLCs.</p><p>A simplificação compreende essencialmente as seguintes etapas:</p><p>- Redução do GLC</p><p>- Remoção de Produções Unitárias</p><p>- Remoção de Produções Nulas</p><p>1- Redução de CFG</p><p>As GLCs são reduzidos em duas fases:</p><p>Fase 1: Derivação de uma gramática equivalente, G’, do GLC, G, de modo que cada</p><p>variável derive alguma string terminal.</p><p>Procedimento de Derivação:</p><p>Passo1: inclua todos os símbolos, W1, que derivam de algum terminal e inicialize</p><p>i=1.</p><p>Passo 2: Incluir todos os símbolos, Wi+1, que derivam Wi.</p><p>Passo 3: Incremente i e repita o Passo 2, até Wi+1 = Wi.</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>Passo 4: inclua todas as regras de produção que contenham Wi.</p><p>Fase 2: Derivação de uma gramática equivalente, G”, da GLC, G’, tal que cada</p><p>símbolo apareça em forma sentencial.</p><p>Procedimento de Derivação:</p><p>Passo 1: inclua o símbolo inicial em Y1 e inicialize i = 1.</p><p>Passo 2: Incluir todos os símbolos, Yi+1, que podem ser derivados de Yi e incluir</p><p>todas as regras de produção que foram aplicadas.</p><p>Passo 3: Incremente i e repita o Passo 2, até Yi+1 = Yi.</p><p>Exemplo 3.10</p><p>Encontre uma gramática reduzida equivalente à gramática G, tendo regras de</p><p>produção, P: S → AC | B, A →a, C → c | BC, E → aA | e</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>Exemplo 3.10 - Solução</p><p>Fase 1</p><p>Fase 2</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>Exemplo 3.10 - Solução</p><p>Fase 2 –continuação</p><p>2 – Remoção das Produções Unitárias</p><p>Qualquer regra de produção na forma A → B onde A, B ∈ Não terminal é chamada</p><p>de produção unitária.</p><p>Procedimento de remoção:</p><p>Passo 1: Para remover A→B, adicione a produção A→x à regra gramatical sempre</p><p>que B→x ocorrer na gramática. [x ∈ Terminal, x pode ser nulo]</p><p>Passo 2: Exclua A→B da gramática.</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>2 – Remoção das Produções Unitária</p><p>Passo 3: Repita a partir do passo 1 até que todas as produções unitárias sejam</p><p>removidas.</p><p>Exemplo 3.11</p><p>Remova a produção unitária do seguinte:</p><p>Exemplo 3.11 – Solução:</p><p>Existem 3 produções unitárias na gramática</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>2 – Remoção das Produções Unitárias</p><p>Exemplo 3.11 – Solução:</p><p>Agora Z, M e N estão inacessíveis, portanto pode-se removê-los. A GLC final é livre</p><p>de produção unitária é dada abaixo:</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>3 – Remoção de Produções Nulas</p><p>Em uma GLC, um símbolo não terminal ‘A’ é uma variável anulável se houver uma</p><p>produção A → ϵ ou se houver uma derivação que começa em A e finalmente termina</p><p>com</p><p>Procedimento de remoção:</p><p>Passo 1 – Determine (encontre) variáveis (não terminais) anuláveis ​​que derivam ϵ.</p><p>Passo 2 - Para cada produção A → a, construa todas as produções A → x onde x é</p><p>obtido de ‘a’ removendo um ou vários não-terminais do passo 1.</p><p>Passo 3 - Combine as produções originais com o resultado do passo 2 e remova as</p><p>produções ϵ.</p><p>Compiladores Aula 3</p><p>3.7 – Simplificação das GLC</p><p>3 – Remoção de Produções Nulas</p><p>Exemplo 3.12</p><p>Remova a produção nula do seguinte:</p><p>Solução 12 :</p><p>Existem duas variáveis anuláveis: A e B</p><p>Compiladores Aula 3</p><p>3.8 – Forma normal de Chomsky (FNC)</p><p>Ao trabalhar com GLC, é conveniente tê-las de forma simplificada. Uma das formas</p><p>mais simples e úteis é chamada de forma normal de Chomsky. A forma normal de</p><p>Chomsky é útil para fornecer algoritmos para trabalhar com GLC.</p><p>Definição 3.1 - Uma gramática livre de contexto está na forma normal de Chomsky</p><p>se todas as regras tiverem a forma</p><p>onde a é qualquer terminal e A, B e C são quaisquer variáveis (não-terminal) - exceto</p><p>que B e C podem não ser variáveis iniciais. Além disso, permitimos a regra S → ϵ,</p><p>onde S é a variável (símbolo) inicial.</p><p>Uma GLC está na forma normal de Chomsky se as produções estiverem nas seguintes</p><p>formas:</p><p>onde A, B e C são não terminais e a é terminal.</p><p>Compiladores Aula 3</p><p>3.8 – Forma normal de Chomsky</p><p>Algoritmo para converter uma GLC para a forma normal de Chomsky:</p><p>Passo 1 - Se o símbolo inicial S ocorrer em algum lado direito, crie um novo símbolo</p><p>inicial S’ e uma nova produção S’ → S.</p><p>Passo 2 - Remova as produções nulas. (Usando o algoritmo de remoção de produção</p><p>nula discutido anteriormente).</p><p>Passo 3 - Remova as produções unitárias. (Usando o algoritmo de remoção de</p><p>produção unitária discutido anteriormente).</p><p>Passo 4 - Substitua cada produção A → B1…Bn onde n>2 por A→B1C onde C →</p><p>B2…Bn. Repita este passo para todas as produções que tenham dois ou mais</p><p>símbolos no lado direito.</p><p>Passo 5 - Se o lado direito de qualquer produção estiver na forma A→aB, onde a é</p><p>um terminal e A, B são não-terminais, então a produção é substituída por A→XB e</p><p>X→a. Repita esta etapa para cada produção que esteja na forma A→aB.</p><p>Compiladores Aula 3</p><p>3.8 – Forma normal de Chomsky</p><p>Algoritmo para converter uma GLC para a forma normal de Chomsky:</p><p>Exemplo 3.13 -</p><p>Converta a seguinte GLC para a forma normal de Chomsky (FNC).</p><p>Solução 3.13 –</p><p>Compiladores Aula 3</p><p>3.8 – Forma normal de Chomsky</p><p>Algoritmo para converter uma GLC para a forma normal de Chomsky:</p><p>Solução 3.13</p><p>Compiladores Aula 3</p><p>3.8 – Forma normal de Chomsky</p><p>Algoritmo para converter uma GLC para a forma normal de Chomsky:</p><p>Solução 3.13</p><p>Compiladores Aula 3</p><p>3.9 – Forma normal de Greibach (FNG)</p><p>Uma GLC está na forma normal de Greibach se as produções estiverem nas seguintes</p><p>formas:</p><p>A → b</p><p>A → bD1…Dn</p><p>S → ϵ</p><p>onde A, D1, ...,Dn são não-terminais e b é um terminal.</p><p>Algoritmo para converter uma GLC para a forma normal de Greibach:</p><p>Etapa 1 - Se o símbolo inicial S ocorrer em algum lado direito, crie um novo símbolo</p><p>inicial S’ e uma nova produção S’ → S.</p><p>Etapa 2 - Remova as produções nulas. (Usando o algoritmo de remoção de produção</p><p>nula discutido anteriormente).</p><p>Etapa 3 - Remova as produções unitárias. (Usando o algoritmo de remoção de</p><p>produção unitária discutido anteriormente).</p><p>Etapa 4 - Remova toda recursão à esquerda direta e indireta.</p><p>Etapa 5 - Faça substituições adequadas de produções para convertê-las na forma</p><p>adequada de FNG.</p><p>Compiladores Aula 3</p><p>3.9 – Forma normal de Greibach (FNG)</p><p>Exemplo 3.14 -</p><p>Converta a seguinte GLC para a forma normal de Greibach (FNG).</p><p>Solução 3.14</p><p>Aqui, S não aparece no lado direito de nenhuma produção, e não há produções</p><p>unitárias ou nulas no conjunto de regras de produção. Portanto, pode-se pular da</p><p>Etapa 1 para a Etapa 3.</p><p>Etapa 4 - Remova toda recursão à esquerda direta e indireta.</p><p>Etapa 5</p><p>Compiladores Aula 3</p><p>3.9 – Forma normal de Greibach (FNG)</p><p>Etapa 4 - Remova toda recursão à esquerda direta e indireta.</p><p>Compiladores Aula 3</p><p>Slide 1: Universidade de Brasília</p><p>Slide 2: 3.6 – Propriedade de fechamento das GLC Linguagens livres de contexto são fechadas em: -União - Concatenação - Operação estrela de Kleene a)União Sejam L1 e L2 são duas linguagens livres de contexto. Então L1 U L2 também é livre de context</p><p>Slide 3: 3.6 – Propriedade de fechamento das GLC b) Concatenação Sejam L1 e L2 são duas linguagens livres de contexto. Então L1L2 também é livre de contexto. Exemplo 3.8: A gramática correspondente G terá as propriedades adicionais de S → S1S2 c</p><p>Slide 4: 3.6 – Propriedade de fechamento das GLC Linguagens livres de contexto não estão fechadas em: - Intersecção: Se L1 e L2 são linguagens livres de contexto, então L1 L2 não é necessariamente livre de contexto. - Interseção com linguagem regu</p><p>Slide 5: 3.7 – Simplificação das GLC Introdução Teorema 3.1 Seja G = (V, T, S, P) uma gramática livre de contexto. Então para cada w ∈ L(G), existe uma árvore de derivação de G cujo resultado é w. Por outro lado, a realização de qualquer árvore de der</p><p>Slide 6: 3.7 – Simplificação das GLC Introdução Também discutimos formas normais, isto é, formas gramaticais que são muito restritas, mas são, no entanto, gerais no sentido de que qualquer gramática livre de contexto tem um equivalente na forma normal.</p><p>Slide 7: 3.7 – Simplificação das GLC Numa GLC, pode acontecer que todas as regras e símbolos de produção não sejam necessários para a derivação de strings (linguagem ou token). Além disso, pode haver algumas produções nulas e produções unitárias. A elim</p><p>Slide 8: 3.7 – Simplificação das GLC Passo 4: inclua todas as regras de produção que contenham Wi. Fase 2: Derivação de uma gramática equivalente, G”, da GLC, G’, tal que cada símbolo apareça em forma sentencial. Procedimento de Derivação:</p><p>Slide 9: 3.7 – Simplificação das GLC Exemplo 3.10 - Solução Fase 1 Fase 2</p><p>Slide 10: 3.7 – Simplificação das GLC Exemplo 3.10 - Solução Fase 2 –continuação 2 – Remoção das Produções Unitárias Qualquer regra de produção na forma A → B onde A, B ∈ Não terminal é chamada de produção unitária. Procedimento de remoção: Pa</p><p>Slide 11: 3.7 – Simplificação das GLC 2 – Remoção das Produções Unitária Passo 3: Repita a partir do passo 1 até que todas as produções unitárias sejam removidas. Exemplo 3.11 Remova a produção unitária do seguinte: Exemplo 3.11 – Solução: Existem</p><p>Slide 12: 3.7 – Simplificação das GLC 2 – Remoção das Produções Unitárias Exemplo 3.11 – Solução: Agora Z, M e N estão inacessíveis, portanto pode-se removê-los. A GLC final é livre de produção unitária é dada abaixo:</p><p>Slide 13: 3.7 – Simplificação das GLC 3 – Remoção de Produções Nulas Em uma GLC, um símbolo não terminal ‘A’ é uma variável anulável se houver uma produção A → ϵ ou se houver uma derivação que começa em A e finalmente termina com Procedimento d</p><p>Slide 14: 3.7 – Simplificação das GLC 3 – Remoção de Produções Nulas Exemplo 3.12 Remova a produção nula do seguinte: Solução 12 : Existem duas variáveis anuláveis: A e B</p><p>Slide 15: 3.8 – Forma normal de Chomsky (FNC) Ao trabalhar com GLC, é conveniente tê-las de forma simplificada. Uma das formas mais simples e úteis é chamada de forma normal de Chomsky. A forma normal de Chomsky é útil para fornecer algoritmos para traba</p><p>Slide 16: 3.8 – Forma normal de Chomsky Algoritmo para converter uma GLC para a forma normal de Chomsky: Passo 1 - Se o símbolo inicial S ocorrer em algum lado direito, crie um novo símbolo inicial S’ e uma nova produção S’ → S. Passo 2 - Remova as p</p><p>Slide 17: 3.8 – Forma normal de Chomsky Algoritmo para converter uma GLC para a forma normal de Chomsky: Exemplo 3.13 - Converta a seguinte GLC para a forma normal de Chomsky (FNC). Solução 3.13 –</p><p>Slide 18: 3.8 – Forma normal de Chomsky Algoritmo para converter uma GLC para a forma normal de Chomsky: Solução 3.13</p><p>Slide 19: 3.8 – Forma normal de Chomsky Algoritmo para converter uma GLC para a forma normal de Chomsky: Solução 3.13</p><p>Slide 20: 3.9 – Forma normal de Greibach (FNG) Uma GLC está na forma normal de Greibach se as produções estiverem nas seguintes formas: A → b A → bD1…Dn S → ϵ onde A, D1, ...,Dn são não-terminais e b é um ter</p><p>Slide 21: 3.9 – Forma normal de Greibach (FNG) Exemplo 3.14 - Converta a seguinte GLC para a forma normal de Greibach (FNG). Solução 3.14 Aqui, S não aparece no lado direito de nenhuma produção, e não há produções unitárias ou nulas no conjunto</p><p>Slide 22: 3.9 – Forma normal de Greibach (FNG) Etapa 4 - Remova toda recursão à esquerda direta e indireta.</p><p>Slide 23</p>