Baixe o app para aproveitar ainda mais
Prévia do material em texto
Profª. PhD. Larissa Luz Gomes lariluz@yahoo.com.br Aula 1 – Conceitos Básicos Aspectos Teóricos da Computação - ATC Visão Geral de Linguagens Formais Visão Geral de Linguagens Formais Teoria das Linguagens Formais Desenvolvida na década de 1950 Objetivo inicial: desenvolver teorias relacionadas com as linguagens naturais Hoje Importante para o estudo de linguagens artificiais (em especial, para as linguagens originárias na Ciência da Computação) Sintaxe e Semântica Linguagens Formais Preocupa-se com os problemas sintáticos das linguagens Historicamente O problema sintático foi reconhecido antes do problema semântico. Foi o primeiro a receber um tratamento adequado. São de tratamento mais simples que os semânticos. Visão Geral de Linguagens Formais Conseqüência Grande ênfase à sintaxe. Ao ponto de levar à ideia de que, questões das linguagens de programação resumiam-se às questões da sintaxe. A sintaxe basicamente manipula símbolos e não considera os correspondentes significados. Mas, para resolver qualquer problema real é necessário dar uma interpretação semântica aos símbolos. Exemplo: "estes símbolos representam os inteiros” Visão Geral de Linguagens Formais Atualmente Teoria da sintaxe possui construções matemáticas bem definidas e universalmente reconhecidas como exemplo: Gramáticas de Chomsky. Visão Geral de Linguagens Formais Sintaxe Trata das propriedades livres da linguagem “forma” Exemplo: verificação gramatical de programas Semântica Fornece uma interpretação para a linguagem Exemplo: Um significado ou valor para um determinado programa Visão Geral de Linguagens Formais Visão Geral de Linguagens Formais Sintaticamente “errado” Não existe uma noção de programa “errado”. Neste caso, simplesmente não é um programa. Sintaticamente “correto” Pode não ser o programa que o programador esperava escrever. Programa “correto” ou “errado” Deve considerar se modela adequadamente o comportamento desejado. Conceitos Básicos Conceitos Básicos Alfabeto ou Vocabulário É o conjunto finito de símbolos e não vazio. Exemplo: {A, B, C, ...Z} (Alfabeto de todas as letras maiúsculas) {a, b, c, ...z} (Alfabeto de todas as letras maiúsculas) {0, 1} (Alfabeto binário) OBS: Convencionou-se adotar o símbolo Σ para denotar um alfabeto, entretanto isto não é uma regra geral. Conceitos Básicos Sentença ou palavra ou cadeia ou string definida sobre um alfabeto. é uma seqüência de símbolos escolhidos de um alfabeto. Exemplo: Alfabeto V = {0,1} Sentenças válidas = {0,1,00,01,10,11, ..., 001} A sentença vazia é a sentença que não contém símbolos, possuindo tamanho 0. É representada por Ω ou ε. V* = conjunto de todas as sentenças compostas de símbolos de V incluindo a sentença vazia. V+ = V* - (ε) Conceitos Básicos Tamanho ou comprimento de uma sentença é dado pelo número de símbolos que compõem a sentença. Exemplo: Alfabeto V = {a,b,c} Sentenças w = ab Tamanho |w| = 2 Conceitos Básicos Potência de um alfabeto Se Σ é um alfabeto, definimos Σk, como o conjunto de todas as strings de comprimento k, onde o símbolo de cada uma das strings está em Σ. Exemplos: Se Σ = {0,1}, então Σ1 = {0,1}; Σ2 = {00, 01, 10, 11}; Σ3 = {000, 001, 010, 011, 100, 101, 110, 111} Conceitos Básicos Todas as strings de um alfabeto É o conjunto de todas as palavras compostas por símbolos de Σ, incluindo a sentença vazia. Σ* = Σ1 U Σ2 U Σ3 ... Notação: Usa-se a notação Σ+ para indicar o conjunto Σ* - {ε}. Conceitos Básicos Exemplos: Σ = {0,1} Σ* = {Ω, 0, 1, 00, 01, 10, 11, 000, 001, ...} Notação: Usa-se a notação + para indicar o conjunto Σ* - {Ω}. Σ+ = {0, 1, 00, 01, 10, 11, 000, 001, ...} Linguagens e Métodos de Representação de Linguagens Conceitos Básicos Linguagens e Métodos de Representação de Linguagens Definição Informal de Linguagem: Linguagem é o uso da palavra articulada ou escrita como forma de comunicação entre pessoas. Definição de Linguagem Formal: é qualquer conjunto de sentenças sobre um alfabeto, ou seja, uma linguagem L sobre um alfabeto V é um subconjunto de V* . Exemplos: L(Σ) = {01, 0011, 000111, ...} Conceitos Básicos As linguagens possuem sempre um método (ou regra) de formação. Conforme o número de sentenças que possuem, as linguagens se classificam em: Finitas Vazias Infinitas Conceitos Básicos Pode usar um formador de conjuntos, como {w/ algo sobre w}. Essa expressão é lida como o conjunto de palavras w tais que (seja o que for dito sobre w à direita da barra vertical). Alguns exemplos são: L = {w/ w consiste em número igual de 0’s e 1’s} L = {w/ w é um número inteiro binário primo} L = {w/ w é um programa sintaticamente correto} Conceitos Básicos Pode-se substituir w por alguma expressão com parâmetros e descrever as palavras na linguagem declarando condições sobre os parâmetros. O primeiro com o parâmetro n, o segundo com os parâmetros i e j. Esta forma de representar uma linguagem é conhecida como Método Algébrico ou Português Matemático, por alguns autores. Exemplo 1: L = {0 1n, n > = 1} Exemplo 2: L = {0i1j, 0 <= i <= j} Métodos de Representação de Linguagem Métodos de Representação de Linguagem Existem vários métodos para representação de linguagens, como por exemplo: 1. Enumeração das cadeias de símbolos que formam as suas sentenças (listando as palavras). Só para uma linguagem finita. 2. Através de um conjunto de leis de formação das cadeias (definindo um mecanismo que gera sistematicamente as sentenças da linguagem em alguma ordem – GERAÇÃO). Ao conjunto de leis de formação dá-se o nome de Gramática. • Exemplo: gramática 3. Através de regras de aceitação de cadeias. (definindo um algoritmo que determine se uma sentença pertence ou não à linguagem – RECONHECIMENTO). Às regras de aceitação dá-se o nome de Reconhecedor ou Autômatos). • Exemplo: autômato finito Conceitos Básicos O método mais comum de se especificar um procedimento para um computador é através de uma linguagem de programação. Conceitos Básicos Uma linguagem de programação é definida como um como um conjunto de símbolos chamado alfabeto e por um conjunto de regras que vai especificar como compor esses símbolos(sintaxe) e quais as ações associadas a eles. Uma seqüência de símbolos de uma linguagem é chamada programa. Conceitos Básicos Dois mecanismos ou modelos matemáticos muito importantes que estão por trás de uma linguagem são: Gramáticas Autômatos Conceitos Básicos Autômatos Reconhece uma linguagem pelo processo de “prova” de cada elemento possível, para verificar se ele pertence ou não a uma linguagem. Gramática Outro processo importante em uma linguagem é a geração dela. Gerar a linguagem é o processo feito por um procedimento que dá como saída os elementos da linguagem. É o mecanismo gerador de sentenças. Gramática Gramática Notação Formal de Gramática Uma gramática G é definida por uma quádrupla G = (N, T, P, S), onde: N – conjunto finito de símbolos variáveis ou não-terminais T – conjunto finito de terminais disjuntos de N P – conjunto finito de regras de produção S – é um elementodistinguido de N denominado símbolo inicial da gramática ou variável inicial da gramática OBS: N e T também podem ser representados por ΣN e ΣT ou ainda por V e T. Gramática Observações: N ∩ T = Ø e convencionamos adotar ∑= N U T S ε N P = {α → β | α ε V+ e β ε V*} O conjunto P das regras de produções consiste de expressões da forma α → β, onde α é uma palavra de Σ+ e β é uma palavra de Σ*(P define uma relação Σ*). Finalmente, S é um símbolo de N. Derivação Gramática - Derivação As regras de produção (P) definem as condições de geração das palavras da linguagem. A aplicação das regras de produção é denominada derivação de uma palavra. A aplicação sucessiva de regras de produção permite derivar as palavras da linguagem representadas pela gramática. A derivação é uma operação de substituição efetuada de acordo com as regras de produção da gramática. Representa-se esta operação pelo símbolo => Logo: x α y => x β y Se α → β Є P e x e y Є V* Para garantir que pelo menos uma derivação seja efetuada, a notação utilizada é +=>. Isto é: α1 +=> αm se α1 => α2, α2 *=> αm, α1, α2, ..., αm Є V* Gramática - Derivação Uma seqüência de derivações, de zero ou mais passos, é representada por * => Isto é: α1 *=> αm se α1 => α2, α2 => α3, ..., αm-1 => αm α1, α2, ..., αm Є V* Gramática - Derivação Exemplo de Derivação Exemplo 1: Dada a Gramática G1: G1 = ({S0, S1}, {0,1}, P, {S0}) P1: S0 → 0 S0 P2: S0 → 1 S1 P3: S1 → 0 S0 P4: S1 → 1 Encontre algumas cadeias geradas por G1 Exemplo 1: Dada a Gramática G1: G1 = ({S0, S1}, {0,1}, P, {S0}) P1: S0 → 0 S0 P2: S0 → 1 S1 P3: S1 → 0 S0 P4: S1 → 1 Algumas sentenças geradas por G1: P1 P1 P2 P4 1. S0 → 0 S0 → 00 S0 → 001 S1 → 0011 P2 P4 2. S0 → 1 S1 → 11 P2 P3 P1 P2 P4 3. S0 → 1 S1 → 10 S0 → 100 S0 → 1001 S1 → 10011 Exemplo de Derivação Exemplo 2: Dada a Gramática G2: G2 = ({S, M}, {a, b, c}, P, {S}), onde P: S → bS / aM / c M → bS Encontre algumas cadeias geradas por G2 Exemplo de Derivação Exemplo 2: Dada a Gramática G2: G2 = ({S, M}, {a, b, c}, P, {S}), onde P: S → bS / aM / c M → bS Algumas sentenças geradas por G2: P1 P2 P4 P3 1. S → bS → baM → babS → babc P2 P4 P1 P3 2. S → aM → abS → abbS → abbc P3 3. S → c P2 P4 P3 4. S → aM → abS → abc Exemplo de Derivação Exemplo 3: Dada a Gramática G3 = (ΣN, ΣT, P, S), onde: ΣN = {<sentença>, <SN>, <SV>} ΣT = {elefante, amendoim, comeu, o} P = {<sentença>→<SN> <SV>} <SN> → <artigo> <nome-comum> <SV> → <verbo> < SN> <artigo> → o <nome-comum> → elefante/ amendoim <verbo> → comeu S = {<sentença>} Encontre algumas cadeias geradas por G3 Exemplo de Derivação Exemplo 4: Dada a Gramática G4: G2 = ({expressão}, {+, *, (,), id}, P, {<expressão>}) Sendo P o conjunto das seguintes produções: P1: <expressão> → <expressão> + <expressão> P2: <expressão> → <expressão> * <expressão> P3: <expressão> → (<expressão>) P4: id Quais são alguma das cadeia gerada pela gramática G4? Exemplo de Derivação Exemplo de Derivação Exemplo 4: Dada a Gramática G4: G4 = ({expressão}, {+, *, (,), id}, P, {<expressão>}) Sendo P o conjunto das seguintes produções: P1: <expressão> → <expressão> + <expressão> P2: <expressão> → <expressão> * <expressão> P3: <expressão> → (<expressão>) P4: id Resposta: <expressão> P2 → <expressão> * <expressão> P3 → <expressão> * (<expressão>) P1 → <expressão> * (<expressão> + <expressão>) P4 → id * (<expressão> + <expressão>) P4 → id * (id + <expressão>) P4 → id * (id + id) Sentença e Forma Sentencial Sentença e Forma Sentencial Uma SENTENÇA de uma linguagem é uma seqüência formada de terminais, obtida a partir do símbolo inicial da gramática desta linguagem, através de derivações sucessivas. S +=> w {w = seqüência de terminais} Uma FORMA SENTENCIAL é uma seqüência qualquer, composta de símbolos terminais e de não-terminais, obtida a partir do símbolo inicial da gramática através de derivações sucessivas. S *=> α {α = seqüência de variáveis e terminais} Linguagem Gerada ou Linguagem Definida pela Gramática L(G) Linguagem Gerada ou Linguagem Definida pela Gramática L(G A linguagem gerada por uma gramática G = (N, T, P, S) é o conjunto de todas as palavras de símbolos terminais deriváveis, que podem ser geradas a partir do símbolo inicial (S) desta gramática, através de derivações sucessivas. L(G) = {w | w Є T* | S =>+ w} Linguagem Gerada – L(G) Exemplo 1: Qual é a linguagem gerada por esta gramática? G = ({S}, {0,1}, P, S) P = {S → 0S1 S → 01} Linguagem Gerada – L(G) Exemplo 1: Linguagem que gera números de 0’s e 1’s iguais G = (N, T, P, S) G = ({S}, {0,1}, P, S) P = {S → 0S1 S → 01} S => 0S1 => 00S11 => 03S13 => ...0n-1 S1n-1 => 0n1n L(G) = {0n1n | n >= 1} Linguagem Gerada – L(G) Exemplo 2: Qual é a linguagem gerada pela gramática abaixo: G = ({N,D}, {0,1,2,...,9}, P, S) P = {N → D, N → DN, D → 0| 1| ...|9 S => N | D} Mostre a derivação do número 17987? Linguagem Gerada – L(G) Exemplo 2: Qual é a linguagem gerada pela gramática abaixo: G = ({N,D}, {0,1,2,...,9}, P, S) P = {N → D, N → DN, D → 0| 1| ...|9 S => N | D} Linguagem que gera os números naturais Linguagem Gerada – L(G) Exemplo 3: G = (N, T, P, S) G = ({S,X,Y,A,B,F},{a,b}, P, S) P = {S XY, X XaA | XbB | F Aa aA, Ab bA, AY Ya, Ba Ab, Bb Bb, BY Yb Fa aF, Fb bF, FY ε} Qual é a linguagem gerada por esta gramática, mostre essa derivação. Hierarquia de Chomsky Hierarquia de Chomsky O estudo das linguagens formais teve um forte impulso no final da década de 50, quando o lingüista Noam Chomsky publicou dois artigos apresentando o resultado de suas pesquisas relativas à classificação hierárquica das linguagens. Até então a teoria dos autômatos se apresentava razoavelmente evoluída, porém a das linguagens formais ainda não havia de fato se estabelecido como disciplina. Hierarquia de Chomsky A partir dos artigos houve uma significativa concentração de pesquisas na área das linguagens formais. Esta por sua vez teve a oportunidade de se consolidar definitivamente, a partir do final da década de 60, como disciplina coesa e fundamental para as área de engenharia e ciência da computação. Hierarquia de Chomsky A classificação das linguagens por ele propostas ficou conhecida como Hierarquia de Chomsky. Tem como principal mérito agrupar as linguagens em classes, de tal forma que elas possam ser hierarquizadas de acordo com a sua complexidade. Hierarquia de Chomsky Como resultado, é possível antecipar as propriedades fundamentais exibidas por uma determinada linguagem, ou mesmo vislumbrar os modelos de implementação mais adequados para a sua realização de acordo com a classe a que pertençam.Hierarquia de Chomsky Deste modo o interesse prático na Hierarquia de Chomsky se deve ao fato de ela viabilizar a escolha de formas mais econômicas para a realização dos reconhecedores das linguagens, de acordo com a classe que pertencem. Evitando assim, o uso de formalismos mais complexos e o emprego de reconhecedores ineficientes para linguagens de menor complexidade. Hierarquia de Chomsky Do ponto de vista estritamente de engenharia, a Hierarquia de Chomsky permite determinar e selecionar o modelo de implementação (no que diz respeito apenas ao reconhecedor sintático) de menor custo para cada linguagem. Hierarquia de Chomsky Chomsky idealizou uma forma de classificar gramáticas segundo suas regras de produção, isto é, segundo o grau de liberdade apresentado por suas produções. Além de fazer esta classificação Chomsky notou que cada um dos níveis gramaticais propostos por ele poderia ser reconhecido por um autômato distinto Hierarquia de Chomsky Este fato vai permitir especificar o front-end de um compilador de forma mais ou menos automática a partir dos autômatos reconhecedores definidos por ele. O quadro a seguir apresenta os níveis hierárquicos propostos por Chomsky. Gramática de Chomsky Hierarquia de Chomsky Para Chomsky existem 4 (quatro) tipos de Gramática (gramáticas gerativas): Tipo 0 são chamadas GI (Gramáticas não restritivas ou Gramáticas Irrestritas ou Gramáticas com Estrutura de Frase) Tipo 1 são chamadas GSC (Gramáticas Sensíveis ao Contexto) Tipo 2 são chamadas GLC (Gramáticas Livres de Contexto) Tipo 3 são chamadas GR (Gramáticas Regulares). Hierarquia de Chomsky As gramáticas do tipo 0 contém as do tipo 1, que por sua vez, contém as do tipo 2, que contém as do tipo 3. Essa hierarquia é também válida para as linguagens. Hierarquia de Chomsky Tipos de Gramática Tipos de Gramáticas Tipo 0 – Gramáticas Irrestritas (GI) São definidas pelas seguintes regras de produção: • P = {α→β | α Є V+, β Є V*} Ou seja, do lado esquerdo da produção pode haver uma seqüência de quaisquer símbolos. Do lado direito da produção pode haver qualquer seqüência de símbolos, inclusive a sentença vazia. A gramática Irrestrita também é conhecida como a gramática onde nenhum limitação é imposta. São capazes de reconhecer linguagens Recursivamente Enumeráveis Tipos de Gramáticas Exemplo de Gramáticas Irrestritas (GI) Tipos de Gramáticas Exemplo de Gramáticas Irrestritas (GI) Tipos de Gramática • Tipo 1 – Gramáticas Sensíveis ao Contexto (GSC) Para toda produção α → β Є P |α| <= |β| Ou seja, o comprimento da sentença do lado esquerdo deve ser menor ou igual ao comprimento da sentença do lado direito da produção. Do lado direito não é aceita a sentença vazia. Tipos de Gramática • Tipo 1 – Gramáticas Sensíveis ao Contexto (GSC) Se às regras de substituição for imposta a restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe de gramáticas ditas sensíveis ao contexto. As gramáticas que obedecem a estas restrições pertencem ao conjunto das Gramáticas Sensíveis ao Contexto, ou do Tipo 1. Chamam-se linguagens do tipo 1 todas aquelas que podem ser geradas por alguma gramática do tipo 1. Note-se que todas as linguagens do tipo 1 podem ser geradas através de gramáticas com estrutura de frase ou do tipo 0, embora o inverso não seja verdade. Tipos de Gramática • Exemplo de Gramáticas Sensíveis ao Contexto (GSC) Tipos de Gramática • Exemplo de Gramáticas Sensíveis ao Contexto (GSC) Tipos de Gramática • Tipo 2 – Gramáticas Livres de Contexto (GLC) Quando as regras de produção são todas na seguinte forma: • P = {α → β | α Є N e β ≠ ε} Ou seja, do lado esquerdo da produção deve, sempre, ocorrer um e apenas um não-terminal. A sentença vazia também não é aceita do lado direito da produção. • Ex: X → abcX (não interessa o contexto em que X se encontra) Tipos de Gramática •Exemplo de Gramáticas Livres de Contexto (GLC) •Exemplo 1: •G = ({E, F, T}, {i}, P, {E}) •P: E → T / E + T / E – T •T → F / T * F / T / F •F → i / F * * i Tipos de Gramática Exemplo de Gramáticas Livres de Contexto (GLC) • G = ({S}, {a, +, *, (, )}, P, S) P = S Þ S * S S Þ S + S S Þ (S) S Þ a L(G) = conjunto das expressões aritméticas envolvendo *, +,( ) e a. Um exemplo de cadeia formada por esta gramática é a * (a + a). Verifique que essa gramática é ambígua! Tipos de Gramática • Tipo 3 – Gramáticas Regulares (GR) Toda produção é da forma: • A → aB ou • A → a Ou seja: • P= {A → aX | A Є N, a Є T, X Є N U {ε}} Do lado esquerdo da produção deve, sempre, ocorrer um e apenas um não-terminal e do lado direito podem ocorrer ou somente um terminal, ou um terminal mais um não-terminal. Exercício • Determine L(G), sendo: G = ({ S, B, C}, { a, b }, P, S) P: { S aB|bC B bS|aBB|b C aS|bCC|a } Dúvidas ou Perguntas Próxima Aula Exercício e Gramática Regular
Compartilhar