9 - Gramáticas livres de contexto

Prévia do material em texto

<p>Gramáticas livres do contexto</p><p>Apresentação</p><p>Ao se falar em gramática, remete-se vertiginosamente à ideia de alguma linguagem, em que</p><p>há especificações das sentenças, frases e componentes gramaticais. Pode-se compreender</p><p>gramática como um conjunto de regras e prescrições que objetivam o uso correto e apropriado das</p><p>sentenças utilizadas na linguagem. Dessa forma, uma gramática busca delinear a respeito da correta</p><p>utilização de determinada linguagem.</p><p>Em teoria da computação, há algumas linguagens formais necessárias e que foram categorizadas de</p><p>acordo com a hierarquia de Chomsky. Essas linguagens têm gramáticas que as geram, sendo uma</p><p>delas a gramática livre de contexto. A gramática livre de contexto é um mecanismo restrito, porém</p><p>com forte poder de representação e que tem grande aceitação em definições de compiladores e</p><p>estruturas sintáticas das linguagens de programação. Em termos gerais, entende-se por</p><p>gramática livre de contexto um conjunto de regras de produção, em que as produções são definidas</p><p>de forma mais livre do que nas gramáticas regulares e o resultado dessas produções deve gerar</p><p>linguagens livres de contexto.</p><p>Nesta Unidade de Aprendizagem, você vai conhecer o conceito, as características, a formalização</p><p>das gramáticas livres do contexto, assim como aprender o processo de derivação de cadeias nesse</p><p>tipo de gramática e estudar o problema da ambiguidade. Por fim, será exemplificada a construção</p><p>de gramáticas livres de contexto, em que, a partir do conjunto de regras, pode-se chegar</p><p>à linguagem, ou vice-versa.</p><p>Bons estudos.</p><p>Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:</p><p>Definir o formalismo de gramática livre de contexto.•</p><p>Apresentar o processo de passos de derivação em gramáticas livres de contexto e o problema</p><p>da ambiguidade.</p><p>•</p><p>Exemplificar a construção de gramáticas livres de contexto.•</p><p>Desafio</p><p>UML é uma linguagem de modelagem para elaboração da estrutura de projetos que deixa o escopo</p><p>muito mais claro por centralizar tudo em uma única visão, utilizando uma linguagem fácil de ser</p><p>entendida.</p><p>Acompanhe a seguinte situação:</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/f49a2936-a432-49e7-b623-b67acbf96f9d/d4abe81a-542f-4d4a-b527-adb903c84b17.png</p><p>De acordo com as árvores sintáticas desenhadas, determine uma gramática livre de contexto que</p><p>reconheça essas árvores e justifique sua resposta.</p><p>Infográfico</p><p>As gramáticas livres de contexto surgiram com a finalidade de descrever um conjunto de regras e</p><p>especificações formais de linguagens, tendo uma grande aceitação e utilização nas linguagens de</p><p>programação. Com o passar do tempo, houve algumas propostas de representações para as</p><p>gramáticas livres de contexto, dentre propostas textuais e visuais.</p><p>No Infográfico a seguir, você conhecerá algumas estratégias para denotar as gramáticas livres de</p><p>contexto, incluindo o conceito, as características e as formas de representação usadas em cada</p><p>modelo de gramática, sendo aquelas mais voltadas para os formatos visuais, enquanto outra é mais</p><p>voltada para o textual.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/568391b9-3a81-4909-b7f0-75715bf8c7eb/fc9ea6cd-906f-4f74-9ae3-fd4dd3bae436.png</p><p>Conteúdo do livro</p><p>Gramática livre de contexto é um dos formalismos implementados pelas linguagens livres</p><p>de contexto. Nesse formalismo, há símbolos terminais e símbolos não terminais, utilizados nas</p><p>produções das cadeias geradas a partir das regras definidas no conjunto R da formalização da</p><p>gramática em questão, sendo um mecanismo com grande poder representacional quando</p><p>comparado aos autômatos finitos e às expressões regulares.</p><p>No capítulo Gramáticas livres do contexto, base teórica desta Unidade de Aprendizagem, você</p><p>estudará sobre as gramáticas livres de contexto, compreendendo o conceito e a formalização desse</p><p>tipo de gramática, assim como os passos do processo de derivação das cadeias e a ideia de</p><p>ambiguidade em expressões aritméticas a partir da utilização das árvores sintáticas e da formação</p><p>da mesma cadeia por meio de várias derivações permitidas pelas regras definidas no conjunto das</p><p>regras. Por fim, é exemplificada a construção de gramáticas livres de contexto. Dentre os exemplos</p><p>apresentados, há uma gramática que define o escopo básico de uma linguagem de programação.</p><p>Boa leitura.</p><p>LINGUAGENS</p><p>FORMAIS E</p><p>AUTÔMATOS</p><p>OBJETIVOS DE APRENDIZAGEM</p><p>> Definir o formalismo de gramática livre de contexto.</p><p>> Apresentar o processo de passos de derivação em gramáticas livres de</p><p>contexto e o problema da ambiguidade.</p><p>> Exemplificar a construção de gramáticas livres de contexto.</p><p>Introdução</p><p>As gramáticas livres de contexto são um tipo de formalismo das linguagens</p><p>livres de contexto, funcionando como um excelente gerador dessas linguagens.</p><p>De fato, trata-se da segunda gramática definida nas linguagens formais de</p><p>acordo com a hierarquia de Chomsky, sendo considerada, inicialmente, como</p><p>uma gramática de estrutura frasal, ou seja, uma estrutura para gerar frases,</p><p>o que, traduzido para linguagens formais, seriam cadeias e linguagens. Atua,</p><p>portanto, como um mecanismo axiomático ou gerador, mas com limitações no</p><p>formato de suas regras de derivação. Essas limitações são definidas de maneira</p><p>mais livre que na gramática normativa tradicional regular (MENEZES, 2011).</p><p>A gramática livre de contexto vem sendo bem aceita e utilizada em compi-</p><p>ladores de linguagem de programação, nos quais geralmente é utilizada para</p><p>definir escopo de blocos e as questões sintáticas da linguagem. Esse tipo de</p><p>gramática viabiliza uma abordagem concisa e matematicamente simples para</p><p>delinear sobre mecanismos nos quais as frases em linguagem natural e de</p><p>programação são construídas a partir de blocos menores, como a utilização</p><p>da cláusula if-then-else (HOPCROFT; ULLMAN; MOTWANI, 2003).</p><p>Gramáticas livres</p><p>do contexto</p><p>Leonardo Brendo Gomes Nascimento</p><p>Neste capítulo, vamos apresentar o conceito, as características e a formali-</p><p>zação das gramáticas livres do contexto, explicando como aprender o processo</p><p>de derivação de cadeias nesse tipo de gramática e como estudar o problema da</p><p>ambiguidade por meio da análise de árvore sintática. Por fim, são apresentados</p><p>exemplos de construção de gramáticas livres de contexto, em que, a partir do</p><p>conjunto de regras (gramática), pode-se chegar à linguagem ou vice-versa.</p><p>Conceitos fundamentais</p><p>Conforme Menezes (2011), as linguagens livres de contexto ou tipo 2, de acordo</p><p>com a hierarquia de formalização de Chomsky, são geradas a partir das gra-</p><p>máticas livres do contexto. As gramáticas livres de contexto também geram</p><p>as linguagens regulares e, por consequência, suas cadeias, pois as linguagens</p><p>regulares são um subconjunto do conjunto das linguagens do tipo 2 (DIVERIO;</p><p>MENEZES, 2011).</p><p>O formalismo que reconhece a linguagem livre de contexto deve, de igual</p><p>modo, reconhecer suas linguagens que atuam como subconjuntos, por isso a</p><p>classe das linguagens regulares pode ser gerada pelas gramáticas livres de</p><p>contexto, embora o contrário não seja verdadeiro (DIVERIO; MENEZES, 2011).</p><p>A Figura 1 apresenta a classificação das linguagens formais usadas na</p><p>hierarquia de Chomsky. O formalismo gramáticas livres de contexto é um</p><p>mecanismo utilizado nas linguagens livres de contexto, mas que também</p><p>pode ser utilizado para gerar linguagens pertencentes às linguagens regulares.</p><p>Figura 1. Linguagens do tipo 2, 3 e o universo de todas as linguagens.</p><p>Fonte: Menezes (2011, p. 238).</p><p>Gramáticas livres do contexto2</p><p>As linguagens livres do contexto possuem dois tipos de formalismos:</p><p>autômatos de pilha e gramáticas livres de contexto (MENEZES, 2011). Neste</p><p>capítulo, vamos tratar do último formalismo, as gramáticas livres de contexto.</p><p>Vamos considerar GLCa uma gramática livre de contexto</p><p>que produz uma</p><p>clássica linguagem, que trouxe destaque à linguagem do tipo 2 da hierarquia</p><p>de Chomsky na computação, pois foi e é amplamente utilizada em compila-</p><p>dores (VIEIRA, 2006), sobretudo em linguagens de programação, para analisar</p><p>e verificar as questões sintáticas. Veja, a seguir, as regras de produção no</p><p>exemplo dos parênteses aninhados e colchetes bem formados.</p><p>S → SS | [S] | (S) | () | []</p><p>Observe que, até determinado ponto, as atribuições dos símbolos ao S</p><p>(s maiúsculo) são intuitivamente entendíveis, mas há alguns conceitos idios-</p><p>sincráticos de gramáticas livres de contextos que precisam ser explicados.</p><p>Dessa forma, entende-se que uma gramática é um conjunto de regras de</p><p>produções ou substituições, em que cada regra aparece como uma atribuição</p><p>na gramática e consiste em sua estrutura de um símbolo e em uma cadeia,</p><p>separados pelo recurso visual de uma seta (LEWIS; PAPADIMITRIOU, 2000).</p><p>A cadeia gerada é alcançada por meio das variáveis e de outros símbolos,</p><p>chamados de terminais. Os símbolos variáveis são representados por letras</p><p>maiúsculas do alfabeto, enquanto os terminais são representados por le-</p><p>tras minúsculas do alfabeto ou símbolos especiais. Portanto, a GLCa tem as</p><p>seguintes especificações:</p><p>1. S é única variável, sendo ela inicial;</p><p>2. [] e () são os símbolos terminais.</p><p>Por fim, pode-se usar essa gramática para descrever uma linguagem</p><p>criando cadeia a cadeia, conforme os passos a seguir (SIPSER, 2005).</p><p>1. Declare a variável inicial. Essa é variável responsável por iniciar a</p><p>primeira atribuição disposta na gramática em questão.</p><p>2. Escolha uma variável que esteja declarada e uma regra que começa</p><p>com aquela variável. Faça a substituição da variável declarada pelo</p><p>lado direito daquela regra.</p><p>3. Enquanto houver variáveis, repita o passo 2.</p><p>Gramáticas livres do contexto 3</p><p>Como exemplificação, a GLCa gera a cadeia [()()]. Ao conjunto de substi-</p><p>tuições implementado pela gramática para gerar uma cadeia, chama-se de</p><p>derivação. Pode-se ver a derivação da cadeia [()()] a partir de GLCa em:</p><p>S ⇒ [S] ⇒ [SS] ⇒ [()S] ⇒ [()()]</p><p>Há outra representação que pode denotar a derivação dessa gramática:</p><p>a árvore sintática. Na Figura 2, é esboçada a árvore sintática da gramática GLCa.</p><p>Figura 2. Árvore sintática da gramática GLCa.</p><p>Por meio de GLCa, todas as possíveis cadeias podem ser geradas a partir</p><p>de cada substituição das variáveis, até que só haja símbolos terminais.</p><p>Até agora, vimos exemplos de aplicação e a explicação de alguns compo-</p><p>nentes da gramática de forma superficial, mas como podemos saber o que</p><p>pode ser utilizado em cada componente ou como funciona formalmente essa</p><p>gramática? Para essas perguntas, a resposta é a formalização da gramática,</p><p>que será vista a seguir.</p><p>Formalização da gramática livre de contexto</p><p>A formalização da gramática é importante, pois a torna precisa em suas</p><p>afirmações, viabilizando notações e terminologias que são de extrema impor-</p><p>tância para fazer as representações formais dos componentes, dirimindo toda</p><p>ambiguidade no tocante ao que pode se declarar sobre determinada ideia e</p><p>Gramáticas livres do contexto4</p><p>denotando conceitos e abstrações por meio de recursos visuais ou símbolos.</p><p>Portanto, a formalização das gramáticas livres de contextos pode ser vista</p><p>por meio de uma 4-upla (V, Σ, R, S), onde (HOPCROFT; ULLMAN; MOTWANI, 2003;</p><p>SIPSER, 2005; MENEZES, 2011):</p><p>� V é uma coleção finita denominada as variáveis;</p><p>� Σ é uma coleção finita chamada de terminais, não tendo interseção</p><p>de símbolos de V;</p><p>� R é uma coleção finita de regras, sendo que cada regra é uma variável</p><p>e uma cadeia de variáveis e terminais, como (V U Σ)*;</p><p>� S ∈ V, onde S é o símbolo ou variável inicial.</p><p>A seguir, vamos ver exemplos de aplicação da formalização das gramáticas</p><p>livres de contexto.</p><p>Exemplo 1</p><p>Determine a formalização da gramática que gera a linguagem-problema dos</p><p>parênteses aninhados e colchetes bem formados.</p><p>Resposta. V = {S}, Σ = {(,), [,]}, S = S e R são as regras usadas na gramática do</p><p>clássico problema dos parênteses aninhados e colchetes bem formados,</p><p>a saber: S → SS, S → [S], S → (S), S → (), S → [].</p><p>Exemplo 2</p><p>Considere a gramática Ga = {{S}, {a, b}, R, S}, sendo o conjunto das regras R o</p><p>seguinte: S → aSb | SS | ε. Determine a linguagem gerada por Ga.</p><p>Resposta. Observe alguns exemplos de cadeias geradas por essa gramática:</p><p>abab, aaabbb, aababb. Aparentemente, é uma linguagem sem padrão, mas,</p><p>ao considerar que a é o parêntese que abre a expressão e que b é o parêntese</p><p>que fecha a expressão, teremos a linguagem de todas as cadeias de parênteses</p><p>adequadamente aninhadas.</p><p>Exemplo 3</p><p>Considere a gramática Gb = {V, Σ, R, {EXPR}}, sendo V = {{EXPR}, {TERMO}, {FATOR}},</p><p>Σ = {a, +, ×, ( , )} e R = {EXPR} → {EXPR} + {TERMO} | {TERMO}, {TERMO} → {TERMO} ×</p><p>{FATOR} | {FATOR}, {FATOR} → ({EXPR}) | a}. Determine, então, a linguagem de Gb.</p><p>Gramáticas livres do contexto 5</p><p>Resposta. As linguagens geradas por Gb são expressões aritméticas que podem</p><p>gerar cadeias para representar a operação de adição e multiplicação a partir</p><p>do símbolo a, com ou sem parênteses. Exemplos de cadeias geradas incluem:</p><p>a + a, a × a, (a + a), (a × a) e assim por diante.</p><p>A seguir, veremos como acontecem as derivações nas gramáticas livres</p><p>de contexto e como várias derivações podem chegar na mesma cadeia da</p><p>linguagem.</p><p>Derivações em gramáticas livres de</p><p>contexto e geração de ambiguidade</p><p>As gramáticas livres de contexto, em suas produções de cadeias, possuem</p><p>três estruturas básicas:</p><p>1. símbolo que vai receber o valor (lado esquerdo da regra);</p><p>2. operador de atribuição (encontra-se no centro da regra);</p><p>3. valor atribuído (lado direito da regra).</p><p>O lado esquerdo da regra, em gramáticas livres de contexto, trabalha</p><p>apenas com uma variável por vez e não pode ser ε, sendo a primeira regra</p><p>atribuída à variável inicial por meio dos argumentos dispostos em seu lado</p><p>direito. A partir da variável inicial, pode-se atribuir outras variáveis, bem</p><p>como símbolos terminais, incluindo o ε. Em cada regra, é possível fazer novas</p><p>produções de cadeias, o que gera novas derivações nas gramáticas.</p><p>Processo de derivações nas gramáticas livres</p><p>de contexto</p><p>As derivações de novas cadeias surgem a partir do funcionamento do com-</p><p>ponente R da 4-upla descrita na formalização das gramáticas livres de con-</p><p>texto (SIPSER, 2005). Para fins didáticos, suponha que u, v e w são cadeias de</p><p>variáveis e terminais, e que A → w é uma regra pertencente à gramática em</p><p>questão, de modo que se pode dizer que uAv gera a partir de substituições</p><p>uwv, então se escreve A ⇒ uwv. Denota-se u derivando v, caso u = v ou se uma</p><p>série u1, u2,…, uk; logo, existe k ≥ 0 e u ⇒ u1 ⇒ u2 ⇒ … ⇒ uk ⇒ v. Veja, a seguir,</p><p>dois exemplos de derivações.</p><p>Gramáticas livres do contexto6</p><p>Exemplo 1</p><p>Dada a gramática Gk = (V, {0, 1}, R, A), onde R é dado por:</p><p>A → 0A1</p><p>A → B</p><p>B → #</p><p>A partir de Gk, por exemplo, temos que essa gramática produz a cadeia w</p><p>= 0000#1111. A série de substituições para alcançar uma cadeia é chamada de</p><p>derivação. Dessa forma, uma derivação da cadeia w = 0000#1111, na gramática</p><p>em questão, será:</p><p>A ⇒ 0A1 ⇒ 00A11 ⇒ 000A111 ⇒ 0000B1111 ⇒ 0000#1111</p><p>Observe que a derivação que gera a cadeia desejada w vai fazer chamadas</p><p>recursivas de 0A1 em si mesma e, ao final, ao alcançar os números iguais de</p><p>0s e 1s conforme a cadeia, a variável B é substituída pelo símbolo terminal #.</p><p>Observe que a Gk reconhece a linguagem livre de contexto Lk = {0n#1n | n > 0}.</p><p>Exemplo 2</p><p>Seja a gramática Gt ({S, B}, {a, b}, R, S), onde R é dado por:</p><p>S → aSa | aBa</p><p>B → bB | b</p><p>A partir de Gt, por exemplo, temos que essa gramática produz a cadeia</p><p>w = aaabbbaaa. A derivação da cadeia w = aaabbaaa na gramática em questão</p><p>será:</p><p>S ⇒ aSa ⇒ aaSaa ⇒ aaaBaaa ⇒ aaabBaaa ⇒ aaabbaaa</p><p>Observe que a derivação que gera a cadeia desejada w vai fazer chamadas</p><p>recursivas de aSa, utilizando aBa e bB para alcançar os números iguais de</p><p>a antes e após as aparições de quaisquer números de b, conforme a cadeia,</p><p>e a variável B é substituída pelo símbolo terminal b. Observe que a Gt gera a</p><p>linguagem Lt = {anbman | n > 0, m > 0}.</p><p>Gramáticas livres do contexto 7</p><p>Geração de ambiguidade nas gramáticas</p><p>livres de contexto</p><p>A essa altura, você pode estar se perguntando se é possível que uma cadeia</p><p>possa ser construída de várias formas diferentes, ainda que, ao final das</p><p>substituições, o resultado seja o mesmo, só alterando o ponto de partida da</p><p>construção. Pois a resposta é “sim”: uma mesma cadeia pode ser estruturada</p><p>de perspectivas gramaticais distintas. Dessa forma, a partir de uma gramá-</p><p>tica, é possível que determinada cadeia seja gerada de diversas abordagens</p><p>distintas; por consequência, essa cadeia vai ter mais de um tipo de árvore</p><p>sintática (SIPSER, 2005).</p><p>A aparição de muitas árvores sintáticas para a mesma cadeia pode ser um</p><p>problema, visto que, para determinadas aplicações, como as linguagens de</p><p>programação, um tipo de dado deve, necessariamente, ter uma única inter-</p><p>pretação (HOPCROFT; ULLMAN; MOTWANI, 2003). Dessa forma, a ambiguidade</p><p>nas derivações de cadeias surge quando há múltiplas árvores sintáticas para</p><p>a produção da mesma cadeia (SIPSER, 2005). Se alguma cadeia é gerada ambi-</p><p>guamente por uma gramática, pode-se dizer que essa gramática é ambígua.</p><p>A seguir, vamos considerar a gramática Gp, que gera uma cadeia</p><p>ambiguamente:</p><p><EXPR> → <EXPR> + <EXPR> | <EXPR> × <EXPR> | (<EXPR>) | a</p><p>Observe que há mais de um tipo de derivação e de árvore sintática para</p><p>representar a cadeia w = a + a × a. Pode-se ver as derivações a seguir.</p><p>� Derivação 1 a partir de w: <EXPR> → <EXPR> + <EXPR> ⇒ <EXPR> +</p><p><EXPR> × <EXPR> ⇒ a + <EXPR> × <EXPR> ⇒ a + a × <EXPR> ⇒ a + a × a.</p><p>� Derivação 2 a partir de w: <EXPR> ⇒ <EXPR> × <EXPR> ⇒ <EXPR> +</p><p><EXPR> × <EXPR> ⇒ a + <EXPR> × <EXPR> ⇒ a + a × <EXPR> ⇒ a + a × a.</p><p>As árvores sintáticas das derivações 1 e 2 podem ser visualizadas a seguir,</p><p>na Figura 3. A Figura 3a representa derivação 1, e a Figura 3b representa a</p><p>derivação 2.</p><p>Gramáticas livres do contexto8</p><p>Figura 3. (a) Árvore sintática da derivação 2 e (b) árvore sintática da derivação 3.</p><p>Fonte: Sipser (2005, p. 106).</p><p><EXPR> <EXPR></p><p><EXPR> <EXPR> <EXPR> <EXPR></p><p><EXPR> <EXPR> <EXPR> <EXPR></p><p>a a a+ × a a a+ ×</p><p>a b</p><p>Diante da situação envolvendo a ambiguidade na produção das cadeias</p><p>geradas pela gramática em questão, algumas estratégias estão disponíveis</p><p>para resolver esse problema: a exclusão de símbolos inúteis, exclusões de</p><p>produções vazias e da forma Variável → Variável 2. A partir da implementação</p><p>dessas iniciativas, pode-se simplificar a gramática em questão. Observe que</p><p>a gramática Gp foi simplificada para Gp = {E, T, F}, {a, + , ×, ( , ) }, R, S), com R</p><p>tendo as regras a seguir:</p><p>E → E + T | T</p><p>T → T × F | F</p><p>F → (E) | a</p><p>Cadeias que, em sua derivação, possuem mais de uma árvore sintática,</p><p>são cadeias ambiguamente produzidas. Entretanto, há linguagens que pro-</p><p>duzem somente cadeias ambiguamente, e essas linguagens são chamadas</p><p>de linguagens inerentemente ambíguas.</p><p>A gramática livre de contexto inicialmente foi chamada de gramática</p><p>de estrutura frasal ou gramática constituinte, sendo desenvolvida</p><p>e inserida na hierarquia das linguagens formais por Avram Noam Chomsky</p><p>na década de 1950 (CHOMSKY; SCHÜTZENBERGER, 1959). Esse formalismo foi</p><p>importante para o avanço na utilização de estruturas de blocos usados na</p><p>linguagem de programação Algol.</p><p>Gramáticas livres do contexto 9</p><p>A partir da implementação de estruturas de blocos na linguagem Algol,</p><p>surgiu a necessidade de uma gramática livre de contexto que descrevesse sua</p><p>sintaxe. Dessa forma, foi formalizada uma gramática livre de contexto para</p><p>essa linguagem de programação. Desde então, as linguagens de programação</p><p>passaram a utilizar esse formalismo como uma espécie de manual para descrever</p><p>suas sintaxes.</p><p>Exemplos da criação de gramáticas livres</p><p>de contexto</p><p>A seguir, serão realizados exercícios envolvendo gramáticas livres de contexto</p><p>para a fixação do conteúdo. Esta seção visa ajudar o aluno a aprofundar os</p><p>conhecimentos por meio de outros exemplos e a vislumbrar como esse assunto</p><p>por ser abordado por meio de questões. Cada exercício será composto por</p><p>duas partes: problema e resposta.</p><p>Problema 1</p><p>Dada a linguagem L1 = {anbn | n ≥ 0}, determine a gramática G1 que a gera.</p><p>Resposta. Observe que, nessa linguagem, haverá números iguais de a e b,</p><p>incluindo quando n = 0, pois haverá 0 a e 0 b. A gramática tem a seguinte</p><p>estrutura G1 = ({S}, {a, b}, R, S), onde R determina as regras a seguir:</p><p>S → aSb</p><p>S → ε</p><p>Exemplos de cadeias geradas a partir dessa linguagem e gramática incluem</p><p>{ε, ab, aabb, aaabbb, aaaabbbb}.</p><p>Problema 2</p><p>Dada uma linguagem de programação procedural contendo composição se-</p><p>quencial de comandos, como atribuição de variáveis, condicional if-then-else</p><p>e repetição while, determine uma gramática livre de contexto que descreve</p><p>essa linguagem de programação.</p><p>Resposta. Para descrever uma linguagem de programação, é necessário,</p><p>primeiramente, saber os recursos que ela vai suportar; porém, considerando</p><p>o escopo simples de uma linguagem procedural, a seguir, pode-se ver um</p><p>Gramáticas livres do contexto10</p><p>fragmento de uma linguagem de programação gerada a partir da gramática</p><p>livre de contexto G2:</p><p><PROGRAM> → BEGIN PROGRAM <COMAND-LIST> END PROGRAM</p><p><COMAND-LIST> → <COMAND> <COMAND-LIST> | <COMAND></p><p><COMAND> → <ASSING-COMAND> | <IF-THEN-</p><p>ELSE-COMAND> | <WHILE-COMAND>…</p><p><ASSING-COMAND> → <VARIABLE><EXPRESSION></p><p><IF-THEN-ELSE-COMAND> → IF<BOOLEAN-EXPRESSION></p><p>THEN <COMAND-LIST> ELSE <COMAND-LIST> END IF</p><p><WHILE-COMAND> → WHILE <BOOLEAN-EXPRESSION></p><p>DO <COMAND-LIST> END WHILE</p><p>… → ...</p><p><VARIABLE> → <LETTER> <VARIABLE-TALL> | <LETTER></p><p><VARIABLE-TALL> → <LETTER> <VARIABLE-TALL> |</p><p><DIGIT> <VARIABLE-TALL> | <LETTER> | <DIGIT></p><p><LETTER > → A| B| … |Z| a| b| … |z</p><p><DIGIT> → 0| 1 | … |9</p><p>Problema 3</p><p>Dada a gramática livre de contexto G3, que gera cadeias no formato de ex-</p><p>pressões algébricas sem usar colchetes e chaves, apenas parênteses e três</p><p>símbolos e as quatro operações básicas da matemática, determine essa</p><p>gramática e mostre exemplos de derivação de cadeias a partir de G3.</p><p>Resposta. A gramática que reconhece as expressões algébricas tem as se-</p><p>guintes especificações: G3 = ({S}, {x, y, z, +, –, /, ×, (, )}, R, S), onde R é o conjunto</p><p>de regras de produções a seguir:</p><p>S → S + S</p><p>S → S – S</p><p>S → S * S</p><p>S → S / S</p><p>S → ( S )</p><p>S → x</p><p>S → y</p><p>S → z</p><p>Gramáticas livres do contexto 11</p><p>Exemplos de cadeias geradas a partir dessa gramática incluem x + x, x +</p><p>y, x + z, (x + x), (x + z), (z – z) e (z × 2).</p><p>Problema 4</p><p>Dadas as especificações da gramática G4 = ({S, A, B}, {a, b}, R, S), onde R é a</p><p>coleção de regras seguintes:</p><p>S → abA</p><p>A → aA | bA| B</p><p>B → ba,</p><p>determine cinco cadeias que são geradas por essa gramática.</p><p>Resposta. Exemplos de cadeias geradas por essa gramática incluem abbbaba,</p><p>abba, ababba, abbabba e abaaaba.</p><p>Problema 5</p><p>Dada a linguagem livre de contexto L5 = {anbm | n ≠ m}, determine uma gramática</p><p>livre de contexto G5 que gera L5.</p><p>Resposta. A gramática G5 que gera L5 tem as especificações G5 = ({S, A, T, B},</p><p>{a, b}, R, S), onde R é o conjunto de regras a seguir:</p><p>S → AT |TB</p><p>T → aTb | ε</p><p>A → aA | a</p><p>B → bB | b</p><p>Neste capítulo, explicamos a importância e a formalização das gramáticas</p><p>livres de contexto. Também definimos como uma gramática faz a derivação</p><p>de uma cadeia e, por consequência, sua árvore sintática. Vimos que, se uma</p><p>derivação de cadeia chegar em mais de uma árvore sintática, tem-se o pro-</p><p>blema de ambiguidade na produção das cadeias. Por fim, foram elaborados</p><p>alguns exercícios, como aquele que pede para caracterizar uma estrutura</p><p>de uma linguagem de programação procedural. É recomendado, ao aluno,</p><p>buscar novas leituras sobre o assunto, a fim de que o conhecimento sobre a</p><p>temática seja aprofundado.</p><p>Gramáticas livres do contexto12</p><p>Referências</p><p>CHOMSKY, N.; SCHÜTZENBERGER, M. P. The algebraic theory of context-free languages.</p><p>Studies in Logic and the Foundations of Mathematics,</p><p>v. 26, p. 118–161, 1959.</p><p>DIVERIO, T. A.; MENEZES, P. B. Teoria da computação: máquinas universais e computabi-</p><p>lidade. 3. ed. Porto Alegre: Bookman, 2011. (Série Livros Didáticos Informática UFRGS, 5).</p><p>HOPCROFT, J. E.; ULLMAN, J. D.; MOTWANI, R. Introdução à teoria de autômatos, linguagens</p><p>e computação. Rio de Janeiro: Campus, 2003.</p><p>LEWIS, H. R.; PAPADIMITRIOU, C. H. Elementos de teoria da computação. 2. ed. Porto</p><p>Alegre: Bookman, 2000.</p><p>MENEZES, P. B. Linguagens formais e autômatos. 6. ed. Porto Alegre: Bookman, 2011.</p><p>(E-book). (Série Livros Didáticos Informática UFRGS, 3).</p><p>SIPSER, M. Introdução a teoria da computação. São Paulo: Cengage Learning, 2005.</p><p>VIEIRA, N. J. Introdução aos fundamentos da computação: linguagens e máquinas. São</p><p>Paulo: Cengage Learning, 2006.</p><p>Gramáticas livres do contexto 13</p><p>Dica do professor</p><p>A partir da gramática livre de contexto GLC = (V = {T, A}, Σ = {a, b}, R = {T → AA, A → AAA |bA |Ab</p><p>|a }, S = T), pode-se ver como são formadas as derivações das cadeias e as implementações de suas</p><p>árvores sintáticas. Quando uma cadeia não é gerada pela gramática GLC, não será possível realizar</p><p>sua derivação, nem a construção de sua árvore, pois essa cadeia não obedece aos critérios de</p><p>geração da gramática. Logo, as chamadas recursivas e atribuições da GLC também não serão</p><p>contempladas.</p><p>Na Dica do Professor, você acompanhará a utilização da ferramenta JFLAP em gramáticas livres de</p><p>contexto para a derivação de cadeia e criação de árvore sintática, os aspectos práticos no</p><p>software JFLAP a partir da inserção de cadeias, em que se pode ver se determinada cadeia é</p><p>derivável ou se é possível implementar uma árvore sintática, dada uma gramática.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/b1b11036a0bddbcd685dcb6a7d79e276</p><p>Exercícios</p><p>1) O formalismo gramática livre de contexto foi desenvolvido e sistematizado inicialmente por</p><p>Avram Noam Chomsky, sendo esse mecanismo um exímio gerador das linguagens livres de</p><p>contexto ou linguagem do tipo 2, conforme a hierarquia de Chomsky. Dessa forma,</p><p>considere a gramática G1 = ({L, K}, {0, 1}, R, K), em que R tem as seguintes regras:</p><p>K → 1K11 | L</p><p>L → 0 L | ε</p><p>Assinale a alternativa que traduz a gramática G1 em uma linguagem livre de contexto L1.</p><p>A) A linguagem tem a seguinte estrutura: L1 = {12n0m1n | n > 0, m ≥ 0}.</p><p>B) A linguagem tem a seguinte estrutura: L1 = {1n02m1n | n ≥ 0, m ≥ 0}.</p><p>C) A linguagem tem a seguinte estrutura: L1 = {1n0m12n | n > 0, m ≥ 0}.</p><p>D) A linguagem tem a seguinte estrutura: L1 = {1n0m12n | n ≥ 0, m ≥ 0}.</p><p>E) A linguagem tem a seguinte estrutura: L1 = {1n0m1n | n ≥ 0, m ≥ 0}.</p><p>2) As gramáticas livres de contexto foram desenvolvidas a partir de uma estratégia que utiliza</p><p>substituições recursivas dentro de seus símbolos denominados variáveis ou não terminais.</p><p>Em um símbolo não terminal, pode-se atribuir outro símbolo não terminal ou um terminal.</p><p>Dessa forma, considere a linguagem L2 = { 0n1m2m33n | n ≥ 0, m > 0} e determine as regras</p><p>usadas por essa gramática, em que será possível ver a utilização das chamadas recursivas</p><p>dentro das variáveis.</p><p>A) A gramática tem as seguintes regras: K → 0K33 | L, L → 1L22 | 12.</p><p>B) A gramática tem as seguintes regras: K → 0K3333 | L, L → 1L22 | 12.</p><p>C) A gramática tem as seguintes regras: K → 0K333 | L, L → 1L22 | 21.</p><p>D) A gramática tem as seguintes regras: K → 0K333 | L, L → 1L22 | 11.</p><p>E) A gramática tem as seguintes regras: K → 0K333 | L, L → 1L22 | 12.</p><p>3) A formalização de uma ideia fornece argumentos sólidos ao se questionar sobre</p><p>determinado escopo de atuação dela, tendo, assim, a seu favor, a precisão e</p><p>notações/terminologias para se expressar melhor no tocante ao assunto. Aproveitando a</p><p>ideia de formalização, as gramáticas livres de contextos também têm a sua.</p><p>Dada a linguagem:</p><p>L3 = { 1an#bn1 | n > 0}</p><p>Determine a valoração de sua formalização.</p><p>A) A 4-upla é: ({A, B}, {1, a, b}, {A → 1aAb, A → B, B → # }, Z).</p><p>B) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1Ab1 , A → B, B → # }, A).</p><p>C) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aBb1 , B → aBb, B → # }, A).</p><p>D) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aAb1 , A → Bb, B → # }, A).</p><p>E) A 4-upla é: ({A, B}, {1, a, b, c}, {A → 1aAb1 , A → B, B → # }, A).</p><p>A árvore sintática é um recurso visual e uma abordagem para fazer a representação das</p><p>gramáticas livres de contexto. Com ela, pode-se ver o funcionamento das substituições das</p><p>variáveis por outras variáveis ou símbolos terminais utilizados na gramática em questão.</p><p>Dadas as árvores sintáticas representadas nas figuras 1, 2, 3, 4 e 5, determine a gramática</p><p>que a desenha.</p><p>4)</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/f579e709-d2d4-4b56-8bef-bdedeefe378e/44b25551-74bf-4ad4-b0f7-cdbcd4ed18a1.png</p><p>A) A gramática é: ({S}, {1, 0, ε }, {S → 0S0| 1S11| L, L → 0 | 1 | ε }, S).</p><p>B) A gramática é: ({S, L}, {1, 0}, {S → 0S0| 1S1| L, L → 10 | 1 | ε }, S).</p><p>C) A gramática é: ({S, L}, {1, 0}, {S → 0S0| 1S1| L, L → 0 | 1 | ε }, S).</p><p>D) A gramática é: ({S}, {1, 0, ε }, {S → 0S0| 1S1| L, L → 0 | 1 | ε }, S).</p><p>E) A gramática é: ({S, L}, {1, 0, ε, # }, {S → 0S1| 1S1| L, L → 0 | 1 | ε }, S).</p><p>5) O problema da ambiguidade é algo indesejado em linguagens de programação, visto que as</p><p>linguagens de programação precisam trabalhar sobre um dado exato, sem dualidade de</p><p>significado, ou seja, sem ambiguidade. Por exemplo, na linguagem C, a cláusula de condição</p><p>if-then-else é bem definida e sem ambiguidade. Caso contrário, haveria problema para o</p><p>compilador entender a sintaxe da estrutura em questão.</p><p>De acordo com o conceito de ambiguidade em gramáticas livres de contexto, analise as</p><p>afirmações a seguir e assinale a alternativa que contém apenas as corretas:</p><p>I. Diz-se que uma cadeia é ambígua se tem mais de uma derivação implementável pela</p><p>gramática.</p><p>II. Diz-se que uma cadeia é ambígua se tem mais de uma árvore sintática para a derivação de</p><p>uma mesma cadeia.</p><p>III. Diz-se que uma gramática é ambígua se tem mais de uma derivação para a mesma cadeia.</p><p>IV. Diz-se que uma árvore sintática produz cadeia ambiguamente somente se faz derivações</p><p>à esquerda.</p><p>V. O fato de uma linguagem não conseguir deixar de ser ambígua indica que se trata de uma</p><p>linguagem inerentemente mbígua.</p><p>A) II e III.</p><p>B) II e IV.</p><p>C) II e V.</p><p>D) III e IV.</p><p>E) III e V.</p><p>Na prática</p><p>As gramáticas livres de contexto sempre foram excelentes formalismos para tratar do</p><p>reconhecimento de cadeias das linguagens, tendo, ultimamente, muito destaque e aceitação nas</p><p>linguagens de programação, pois estabelecem um conjunto de regras bem definidas, buscando</p><p>alcançar um fluxo sem ambiguidade e que possa processar as informações de forma concisa.</p><p>Neste Na Prática, será apresentada uma situação verídica, vivenciada pela equipe responsável por</p><p>desenvolver a linguagem de programação C, sendo proposta uma gramática livre de contexto para</p><p>essa linguagem, em que é elaborado um documento formal e com todas as especificações técnicas</p><p>do C.</p><p>Aponte a câmera para o</p><p>código e acesse o link do</p><p>conteúdo ou clique no</p><p>código para acessar.</p><p>https://statics-marketplace.plataforma.grupoa.education/sagah/33a5f0db-68bb-41fc-b113-06ad5a0b48bf/0740ebd9-1d83-4857-b952-b3c4a232722d.png</p><p>Saiba +</p><p>Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:</p><p>Analisador sintático de Earley para gramáticas livres de</p><p>contexto adaptativas e sua aplicação na caracterização de</p><p>famílias de RNAs com pseudonós</p><p>No link a seguir, você verá uma dissertação de mestrado que propõe a utilização de gramáticas</p><p>livres de contexto para auxiliar algoritmos genéticos na caracterização de famílias de RNAs com</p><p>pseudonós.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Método de pontos interiores</p><p>para estimar os parâmetros de uma</p><p>gramática probabilística livre de contexto</p><p>No link a seguir, você verá uma tese de doutorado. Nos capítulos 1 e 5, é abordada a utilização de</p><p>pesos com teores probabilísticos em cada regra da gramática livre de contexto para estimar</p><p>parâmetros de métodos de pontos interiores primal-dual.</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>Gramáticas livres de contexto (GLCs) – Introdução</p><p>Neste vídeo, você verá o conceito de gramáticas livres de contexto, assim como um pouco da sua</p><p>história, sua formalização, além das produções de cadeias e a resolução de exercícios envolvendo</p><p>essas gramáticas.</p><p>https://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/publico/mestradogilmardissertacaocorrigida.pdf</p><p>http://repositorio.unicamp.br/bitstream/REPOSIP/331498/1/Lopez_EstherSofiaMamian_D.pdf</p><p>Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.</p><p>https://www.youtube.com/embed/YUrt9q2U-bg</p>