Teoria da Computação e Compiladores: Linguagens Formais e Autômatos

TEORIA DA COMPUTAÇÃO E COMPILADORES Engenharia da Computação Prof Renato Matroniani Linguagens regulares livresdecontexto e sensíveisaocontexto obje7vos Conceituar linguagens formais Relacionar o conceito de linguagens regulares com autômatos Bibliografia Sugerida MENEZES P B Linguagens Formais e Autômatos Porto Alegre Sagra LuzzaCo 3ª Ed 2000 178p EMENTA Gramácas Linguagens regulares livresde contexto e sensíveisaocontexto Tipos de reconhecedores Operações com linguagens Propriedades das linguagens Autômatos de estados finitos Autômatos de pilha Máquina de Turing Análise léxica e sintáca Tabelas de símbolos Esquemas de tradução Ambientes de tempo de execução Linguagens intermediárias Geração e omização de código Montadores Ligadores Projeto e implementação de um compilador Revisando A GRAMÁTICA E AS LINGUAGENS DE PROGRAMAÇÃO Conjunto finito de símbolos de um alfabeto Palavra Conjunto de todas as palavras de uma gramáOca Linguagem Linguagens livresdecontexto Segundo Menezes 2011 p 151 O estudo das linguagens livres do contexto é de fundamental importância pois compreende a sintaxe da maioria das linguagens de programação de propósitos gerais como Pascal C e Java Dois formalismos livres do contexto são apresentados gramáBca livre do contexto e autômato com pilha Alguns estudos e resultados são desenvolvidos objeBvando reconhecimento de linguagens e prova de propriedades como árvores de derivação simplificação de gramáBcas e formas normais de gramáBcas Linguagens livres do contexto Compreende um universo mais amplo de linguagens em relação a das regulares Trata de questões como parênteses balanceados construções bloco estruturadas entre outras Tpicas de linguagens de programação como Pascal C Java etc Os algoritmos são relavamente simples e possuem uma eficiência razoável Linguagens livres do contexto Exemplos Tpicos de aplicações linguagens arOficiais e em especial nas linguagens de programação Em parOcular destacamse analisadores sintáOcos tradutores de linguagens e processadores de texto em geral Linguagens livres do contexto formalismos GramáOca livre de contexto é uma gramáOca com regras de produção porém mais livres que na gramáOca regular Autômato com pilha é um formalismo que adiciona ao autômato finito uma memória auxiliar do po pilha Essa memória auxiliar pode ser lida ou gravada Linguagens livres do contexto outros teoremas Menezes 2011 GramáOca ambígua Se existe pelo menos uma palavra que possua duas ou mais árvores de derivação nesta gramáOca Simplificação de gramáOca Simplifica as produções sem reduzir o poder de geração da gramáca Forma normal Estabelece restrições rígidas na forma das produções sem reduzir o poder de geração da gramáca Linguagens livres do contexto Definição de Gramática Livre do Contexto Menezes 2011 Uma gramáOca livre do contexto 𝐺 é uma gramáOca 𝐺 𝑉 𝑇 𝑃 𝑆 com a restrição de que qualquer regra de produção de P é da forma 𝐴 𝛼 onde 𝐴 é uma variável de 𝑉 e 𝛼 uma palavra de 𝑉 𝑇 Portanto uma gramáca livre do contexto é uma gramáca na qual o lado esquerdo das produções contém exatamente uma variável Na práOca Linguagens livresdecontexto Tipo 2 As linguagens livres de contexto são definidas a parr das gramá3cas livres de contexto Seja G uma gramáca livre do contexto A linguagem gerada pela gramáca G 𝐺𝐸𝑅𝐴𝐺 𝑤 𝑇 𝑆 𝑤 Na práca Considere a gramáca 𝐿1 𝑎𝑛𝑏𝑛 𝑛 0 A seguinte gramáca livre do contexto 𝐺1 𝑆 𝑎 𝑏 𝑃1 𝑆 em que 𝑃1 𝑆 𝑎𝑆𝑏 𝑆 𝜀 é tal que 𝐺𝐸𝑅𝐴𝐺1 𝐿1 Por exemplo a palavra aabb pode ser gerada pela seguinte sequência de derivação 𝑆 𝑎𝑆𝑏 𝑎𝑎𝑆𝑏𝑏 𝑎𝑎𝜀𝑏𝑏 𝑎𝑎𝑏𝑏 Linguagens livresdecontexto Tipo 2 Esse é um caso clássico e de fundamental importância no estudo da computação e informáOca Permite estabelecer analogia com estruturas de duplo balanceamento em linguagens de programação como Pascal C Java etc Por exemplo Linguagens blocoestruturadas como beginn endn e similares Linguagens com parênteses balanceados em expressões na forma n n Linguagens livresdecontexto Tipo 2 BNF BNF Backus Naur Form Em computação e informáOca uma maneira comum para representar uma gramáca livre do contexto é o uso da forma BNF Backus Naur form Em uma BNF vale que as variáveis são palavras delimitadas pelos símbolos 𝑒 as palavras não delimitadas são terminais uma regra de produção 𝐴 𝛼 é representada por 𝐴 𝛼 Linguagens livresdecontexto Tipo 2 BNF BNF como idenOficador em Pascal Por exemplo definir uma BNF capaz de gerar qualquer idenOficador válido na linguagem de programação Pascal toda letra é um idenOficador se S é um idenOficador então a concatenação à direita de S com qualquer letra ou dígito também é um idenOficador Uma BNF para essa linguagem fica identificador letra identificador letra identificadordígito letra a b z dígito 0 1 9 Gramáticas livres do contexto Árvore de derivação em compiladores e processadores de texto a derivação é representada da seguinte forma GramáBcas livres do contexto EXEMPLO Como é representada a árvore de derivação da operação 𝒙 𝒙 𝒙 GramáBcas livres do contexto EXEMPLO Como é representada a árvore de derivação da operação 𝒙 𝒙 𝒙 Linguagens livresdecontexto Outras formas de representação de 𝑥 𝑥 𝑥 𝐸 𝐸 𝐸 𝑥 𝐸 𝑥 𝐸 𝐸 𝑥 𝑥 𝐸 𝑥 𝑥 𝑥 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝑥 𝐸 𝑥 𝑥 𝑥 𝑥 𝑥 𝐸 𝐸 𝐸 𝐸 𝐸 𝐸 𝑥 𝐸 𝐸 𝑥 𝑥 𝐸 𝑥 𝑥 𝑥 𝑒𝑡𝑐 Observação no item a em cada passo de derivação sempre é derivada a variável mais à esquerda Analogamente para a variável mais a direita no item b Gramá7ca livre do contexto ambígua Segundo Menezes 2011 p 160 Eventualmente uma mesma palavra pode ser associada a duas ou mais árvores de derivação caracterizando uma gramáca ambígua Em muitas aplicações como por exemplo no desenvolvimento e omização de alguns pos de algoritmos de reconhecimento é conveniente que a gramáca usada seja não ambígua Entretanto nem sempre é possível eliminar ambiguidades Simplificação de gramá7ca livre do contexto A exclusão de símbolos inúteis símbolos não usados na geração de palavras de terminais é realizada excluindose as produções que fazem referência a esses símbolos bem como os próprios símbolos inúteis Não é necessária qualquer modificação adicional nas produções da gramáOca O algoritmo apresentado é dividido em duas etapas como segue Simplificação de gramá7ca livre do contexto Etapa 1 Qualquer variável gera terminais O algoritmo restringe o conjunto de variáveis analisando as produções da gramáca a parr de terminais gerados Inicialmente considera todas as variáveis que geram terminais diretamente exemplo A a A seguir são adicionadas sucessivamente as variáveis que geram terminais indiretamente exemplo B Ab Etapa 2 Qualquer símbolo é angível a parr do símbolo inicial Após esta execução o algoritmo analisa as produções da gramáca a parr do símbolo inicial Começa considerando exclusivamente o símbolo inicial Sucessivamente as produções da gramáca são aplicadas e os símbolos referenciados são adicionados aos novos conjuntos Simplificação de gramá7ca livre do contexto Na práOca Algoritmo de exclusão de símbolos inúteis Considere a GramáOca G1 V1 T P1 S A parOr da G1 é obOda G2 V2 T2 P2 S Onde V2 V1 e T2 T são construídos conforme o algoritmo apresentado O conjunto P2 possui os mesmos elementos que P1 exceto pelas produções cujos símbolos não pertencem a V2 ou T2 Obs é subconjunto está con8do Simplificação de gramá7ca livre do contexto Na práOcaExecução de dois algoritmos Outras formas de simplificação Exclusão das produções vazias Exclusão das produções que substuem variáveis Linguagens livresdecontexto Exemplos Suponha uma linguagem livre de contexto L1 anb2n n1 que é gerada pela gramáOca livre de contexto E1 à aE1bb abb Pela lógica qual a GramáOca E2 gerada pela linguagem L2 a2nbn n1 Autômatos a pilha Assim como as linguagens livres Tipo 1 as linguagens livres do contexto Tipo 2 podem ser associadas a um formalismo do Opo autômato denominado autômato com pilha De acordo com Menezes 2011 O autômato com pilha é análogo ao autômato finito incluindo uma pilha como memória auxiliar e a facilidade de não determinismo A pilha é independente da fita de entrada e não possui limite máximo de tamanho o que implica uma noção de tão grande quanto se queira Portanto é baseada na noção de conjunto infinitamente contável Estruturalmente sua principal caracterísca é que o úlmo símbolo gravado é o primeiro a ser lido A base de uma pilha é fixa e define o seu início O topo é variável e define a posição do úlmo símbolo gravado Autômatos a pilha Fonte MENEZES P B Linguagens Formais e Autômatos 2011 p 175 Autômatos a pilha Definições de automatos a pilha 1 O valor inicial da pilha é vazio e o autômato para aceitando ao angir um estado final 2 a pilha contém inicialmente um símbolo especial denominado símbolo inicial da pilha Não existem estados finais e o autômato para aceitando quando a pilha esver vazia Essas duas definições possuem o mesmo senOdo computacional Partes de um automato a pilha nãodeteminís7co qFita Análoga à do autômato finito qPilha Memória auxiliar do Opo pilha que pode ser usada para leitura e gravação qUnidade de controle Reflete o estado corrente da máquina Possui uma cabeça de fita e uma cabeça de pilha qPrograma função programa ou função de transição Comanda a leitura da fita leitura e gravação da pilha e define o estado da máquina Outra definição para um automato a pilha Um autômato com pilha não determinísBco ou simplesmente autômato com pilha frequentemente abreviado por AP M é uma 6upla 𝑀 Σ 𝑄 𝛿 𝑞0 𝐹 𝑉 onde Σ é um alfabeto de símbolos de entrada ou simplesmente alfabeto de entrada Q é um conjunto de estados possíveis do autômato o qual é finito δ é uma função programa ou simplesmente programa ou ainda função de transição suponha que ε e não são símbolos do alfabeto de entrada δ Q Σ ε V ε 2QV a qual é uma função total Outra definição para um automato a pilha Assim para p Q x Σ ε e y V ε 𝛿𝑝 𝑥 𝑦 𝑞1 𝑣1 𝑞𝑛 𝑣𝑛 é uma transição do autômato q0 é um elemento disnguido de Q denominado estado inicial F é um subconjunto de Q denominado conjunto de estados finais V é um alfabeto auxiliar ou alfabeto da pilha Autômato a pilha Representando graficamente Exemplos de operações com Autômato a pilha Linguagem aceita linguagem rejeitada linguagem loop Seja M Σ Q δ q0 F V um autômato com pilha Então A linguagem aceita ou linguagem reconhecida por M denotada por ACEITAM ou LM é o conjunto de todas as palavras pertencentes a Σ aceitas por M a parJr do estado inicial q0 A linguagem rejeitada por M denotada por REJEITAM é o conjunto de todas as palavras pertencentes a Σ rejeitadas por M a parJr do estado inicial q0 A linguagem loop de M denotada por LOOPM é o conjunto de todas as palavras pertencentes a Σ para as quais M fica processando indefinidamente a parJr do estado inicial q0 Exemplo Autômato a pilha Considere o seguinte autômato com pilha M1 a b q0 q1 qf δ1 q0 qf B no qual δ1 é como a seguir é tal que ACEITAM1 L1 δ1 q0aεq0B δ1 q0bBq1ε δ1 q0qfε δ1 q1bBq1ε δ1 q1qfε Construa o diagrama do autômato com base nas informações Exemplo 1 Autômato a pilha No estado q0 para cada símbolo a lido da fita é armazenado um símbolo B na pilha No estado q1 é realizado um baOmento verificando se para cada símbolo b da fita existe um correspondente B na pilha O algoritmo somente aceita se ao terminar de ler toda a palavra de entrada a pilha esver vazia δ1 q0aεq0B δ1 q0bBq1ε δ1 q0qfε δ1 q1bBq1ε δ1 q1qfε Exemplo 2 Autômato a pilha Autômato com pilha anbmanm Considere a seguinte linguagem sobre o alfabeto a b L4 anbmanm n 0 m 0 O autômato não determinísOco M4 é tal que ACEITAM4 L4 M4 empilha um símbolo auxiliar X para cada a ou b em q0 ou q1 respecvamente Após em q2 verifica se o número de a no sufixo é igual ao de X empilhado Construa o diagrama do autômato que segue este programa Exercícios 1 Considere G a gramáOca Determine a derivação mais a esquerda de aabbaa Determine a derivação mais a esquerda de abaabbbaabbaa Construa as árvores de derivação para as duas situações Exercícios 2 Construir o diagrama de M q0 q1 a b A δ q0 q0 q1 com δq0aλq0A δq0bAq1λ δq1bAq1λ q0 q1 Exercícios para nota 1º Bimestre 1 Considere a seguinte gramáJca G S a b P S na qual PSSSaSa bSbε a Qual a linguagem gerada b A gramáJca é ambígua c Para a palavra aabbaaaa construa uma árvore de derivação 2 Sobre simplificação de gramáJcas a Quais algoritmos de simplificação apenas restringem excluem elementos de conjuntos a gramáJca original se necessário b Quais algoritmos de simplificação modificam modificam elementos de conjuntos a gramáJca original se necessário 3 Sobre as linguagens livres do contexto a Qual a importância do seu estudo b Exemplifique suas aplicações c Faça um quadro comparaJvo com as linguagens regulares destacando as principais caracterísJcas semelhanças e diferenças 4 Considere o exemplo dado neste material sobre GramáJca livre do contexto expressões aritméJcas a É possível gerar a mesma expressão xxx com uma sequência de derivação diferente da apresentada no exemplo bNeste caso quantas sequências disJntas são possíveis Exercícios para nota 1º Bimestre 5 Marque os conjuntos que são alfabetos e jusJfique 6 Explique dentro da teoria da computação o que são prefixos e sufixos Apresente os possíveis prefixos e sufixos de cada uma das seguintes palavras Exercícios para nota 1º Bimestre 7 Quais das seguintes palavras são aceitas pelos autômatos finitos não determinísJcos sobre o alfabeto Σ a b ilustrado na figura a seguir bb bab bbbaaa bbbbbbababababa Exercícios para nota 1º Bimestre 8 Quais das seguintes palavras são aceitas pelos autômatos finitos não determinísJcos sobre o alfabeto Σ a b ilustrado na figura a seguir bb bab bbbaaa bbbbbbababababa