unisul-apostila-formais-compiladores.pdf

7/15/2019 unisul-apostila-formais-compiladores.pdf

1/74

UNISUL - UNIVERSIDADE DO SUL DE SANTA CATARINA

DEPARTAMENTO DE CINCIAS TECNOLGICAS

CURSO DE CINCIA DA COMPUTAO

Prof. Roberto M. Scheffel

Apostila

Compiladores I


2/74

i

Sumrio

SUMRIO ......................................................................................................................................................................... I

INTRODUO ............................................................. .................................................................. .................................. 1

I - TEORIA DA COMPUTAO ........................................................................ ........................................................... 2

1.INTRODUO............................................................................................................................................................... 22.ALGORITMOS E DECIDIBILIDADE................................................................................................................................. 23.INTRODUO A COMPILADORES ................................................................................................................................. 3

3.1 Processadores de Linguagem .................................................................. ............................................................ 3

3.2. Modelo Simples de Compilador ............................................................................ .............................................. 4

II - TEORIA DE LINGUAGENS ............................................................................................................ ........................ 6

1.LINGUAGENS FORMAIS................................................................................................................................................ 61.1. Smbolo ........................................................... ................................................................ ................................... 6

1.2. Cadeia ................................................................................................................................................................ 6

1.3. Linguagens ......................................................................................................................................................... 72.GRAMTICAS .............................................................................................................................................................. 7

2.1. Definio Formal de Gramtica ........ ............................................................................ .................................... 8

2.2. Derivao ........................................................................................................ ................................................... 8

2.3. Notao .............................................................................................................................................................. 9

3.LINGUAGENS DEFINIDAS PORGRAMTICAS ............................................................................................................. 104.TIPOS DE GRAMTICAS ............................................................................................................................................. 105.TIPOS DE LINGUAGENS.............................................................................................................................................. 11EXERCCIOS .................................................................................................................... .......................................... 11

III - LINGUAGENS REGULARES E AUTMATOS FINITOS .............................................................................. 13

1.LINGUAGENS REGULARES ......................................................................................................................................... 131.1. Operaes de Concatenao e Fechamento ......................................................................... ............................ 13

1.2. Definio de Expresses Regulares ................................................................... ............................................... 132.AUTMATOS FINITOS ................................................................................................................................................ 14

2.1 Autmatos Finitos Determinsticos ....................................................................... ............................................. 15

2.2. Autmatos Finitos No-Determinsticos .................................................................... ....................................... 17

2.3. Comparao entre AFD e AFND .......................................................................................................... ........... 18

2.4. Transformao de AFND para AFD ................................................................................................................ 18

2.5. Autmato Finito com -Transies ................................................................... ................................................ 19

3.RELAO ENTRE GRE AF ............................................................ ............................................................... ............. 204.MINIMIZAO DE AUTMATOS FINITOS ................................................................................................................... 22

4.1. Algoritmo para Construo das Classes de Equivalncia................................................................................ 22

4.2. Algoritmo para Construo do Autmato Finito Mnimo .............................. .................................................. 23

5.CONSTRUO DO ANALISADORLXICO ................................................................................................................... 25EXERCCIOS: ............................................................................................................................ ................................. 28

IV - LINGUAGENS LIVRES DE CONTEXTO .......................................................................................................... 30

1.LINGUAGENS AUTO-EMBEBIDAS............................................................................................................................... 302.GRAMTICAS LIVRES DE CONTEXTO ........................................................................................................................ 303.RVORE DE DERIVAO ........................................................................................................................................... 304.DERIVAO MAIS ESQUERDA E MAIS DIREITA .................................................................................................... 315.AMBIGIDADE........................................................................................................................................................... 326.SIMPLIFICAES DE GRAMTICAS LIVRES DE CONTEXTO ...................................................... .................................. 32

6.1. Smbolos Inteis ............................................................. ......................................................................... .......... 32

6.2. Eliminao de -Produes ................................................................... ........................................................... 34

6.3. Produes Unitrias .............................................................. ........................................................................... 36

7.FATORAO .............................................................................................................................................................. 378.ELIMINAO DE RECURSO ESQUERDA................................................................................................................. 389.TIPOS ESPECIAIS DE GLC ............................................................... ............................................................... ............ 3910PRINCIPAISNOTAES DE GLC .................................................................................................................. ............. 40


3/74

ii

11.CONJUNTOS FIRST E FOLLOW.................................................................................................................................. 4111.1 Conjunto First ................................................................................................................................................. 41

11.2. Conjunto Follow ............................................................ ...................................................................... ........... 42

EXERCCIOS .................................................................................................................... .......................................... 44

V - AUTMATOS DE PILHA .................................................................. .................................................................... 46

1.INTRODUO............................................................................................................................................................. 46

2.AUTMATOS DE PILHA.............................................................................................................................................. 462.1. Definio Formal ............................................................................................................................................. 473.AUTMATOS DE PILHA DETERMINSTICOS ................................................................................................................ 49EXERCCIOS .................................................................................................................................................................. 50

VI - ANLISE SINTTICA ........................................................... .................................................................... ........... 51

1.INTRODUO............................................................................................................................................................. 512.CLASSES DE ANALISADORES SINTTICOS ................................................................................................................. 513.ANALISADORES ASCENDENTES (FAMLIA LR) .......................................................................................................... 51

3.1. Estrutura dos Analisadores LR .......................................................... ............................................................... 51

3.2. Algoritmo de Anlise Sinttica LR ................................................................................................................... 52

3.3. A Tabela de Parsing LR.................................................................................................................................... 52

3.4. A Configurao de um Analisador LR .................................................................... .......................................... 53

3.5. Gramticas LR(0) ........................................................................................................... .................................. 533.6. Itens LR .......................................................... .................................................................. ................................. 53

3.7. Clculo dos Conjuntos de Itens Vlidos .................................................................... ....................................... 54

3.8. Definio de uma Gramtica LR(0) .............................................................................. ................................... 56

3.9. Construo do Conjunto LR ..................................................................................... ........................................ 56

3.10. Construo da Tabela de Parsing SLR(1) ........................................................................... ........................... 57

4.ANALISADORES DESCENDENTES ............................................................................................................................... 584.1. Analisadores Descendentes sem Back-Tracking .................. ................................................................ ............ 58

EXERCCIOS .................................................................................................................................................................. 61

RESPOSTAS AOS EXERCCIOS PROPOSTOS .............................................................. ......................................... 62

REFERNCIAS BIBLIOGRFICAS .............................................................................................................. ............ 71


4/74

1

Introduo

Este texto prov os elementos essenciais da disciplina de Compiladores I. O captulo Isitua a rea de linguagens formais no contexto da teoria da computao. Em seguida trata de algunsaspectos relacionados construo de compiladores.

O captulo II apresenta algumas definies bsicas de linguagens formais e uma breveintroduo s gramticas gerativas, que sero base para o restante da apostila.

O captulo III apresenta a teoria de linguagens regulares e das mquinas de estados finitos,ou autmatos finitos, que sero utilizados como base para a construo de analisadores lxicos.

O captulo IV apresenta a teoria especifica de gramticas livres de contexto, que soimportantes ferramentas para a construo de analisadores sintticos de compiladores.

O captulo V apresenta alguns conceitos relativos a autmatos de pilha, que so utilizadospara analisar sentenas geradas pelas gramticas livres de contexto.

Finalmente, o captulo VI apresenta o processo de anlise sinttica propriamente dito.A partir do captulo II, ao final de cada captulo so propostos alguns exerccios de fixao.

O exerccio cujo enunciado estiver marcado com um asterisco (*) tem sua resoluo no final daapostila.O material apresentado nesta apostila cobre o contedo bsico da disciplina. Maiores

subsdios podem ser encontrados na bibliografia indicada no final da apostila.


5/74

I - Teoria da Computao

2


1. IntroduoTeoria de Linguagens Formais e Teoria de Mquina so tpicos abrangentes que se inserem

no estudo da Teoria da Computao em geral. A Teoria da Computao uma cincia que procuraorganizar o conhecimento formal relativo aos processo de computao, como complexidade dealgoritmos, linguagens formais, problemas intratveis, etc.

Atualmente, o termo computar est associado ao conceito de fazer clculos ou aritmtica,usando para isso mquinas computadoras. Entretanto, a noo de computabilidade pode serdissociada da implementao fsica da mquina. Originalmente, a palavra latinaputare significapensar, mas no caso da teoria da computao o sentido mais adequado seria algo comomanipulao de smbolos, o que no , necessariamente, pensamento. Essa manipulao desmbolos envolvendo, principalmente, letras, nmeros e proposies algbricas permitiria smquinas computadoras, segundo Alan Turing (1939) realizar qualquer operao formal de que o

ser humano seria capaz.Mesmo assim, alguns filsofos sustentam que os computadores no podem computar (fazeraritmtica), porque no compreendem a noo de nmero (apenas manipulam sinais eltricos).Todavia, pode-se falar, sem entrar no mrito da questo, que os computadores realizam umacomputao perceptvel, j que transformam uma entrada em sada como se estivessem realmentecomputando. Neste caso, o que importa o efeito final do processo e no a maneira como ele feito.

2. Algoritmos e DecidibilidadeOs algoritmos surgiram na histria da humanidade possivelmente com as tbuas de

logaritmos e de nmeros primos, na antigidade. Certos algoritmos tambm eram usados para

calcular a posio dos planetas e outros auxiliavam a navegao. Pode-se dizer que oscomputadores surgiram graas aos algoritmos. Por exemplo: Charles Babbage (1820), consideradoo pai da Computao, irritou-se com a maneira mecnica e repetitiva com que os clculos da

posio de estrelas e planetas eram feitos na Royal Astronomical Society, onde trabalhava, eescreveu o artigo Observations on the Application of Machinery to the Computatiuon ofMathematical Tables, onde propunha que estes algoritmos fossem realizados por mquinas.

Mas foi apenas em 1900 que o matemtico Frege chegou concluso de que se precisava deuma noo precisa e concisa do conceito de algoritmo. Frege procurou usar a lgica comoferramenta para estabelecer os principais algoritmos de matemtica. A notao utilizada realmenteera precisa mas verificou-se pouco depois que o trabalho continha uma contradio, que ficouconhecida como paradoxo de Russel.

O Paradoxo de RusselMuitos problemas at hoje no possuem soluo algortmica, isto , no podem ser

resolvidos por mquinas. Destes problemas, alguns no tm soluo conhecida, mas existe umgrupo de problemas dos quais sabe-se que no existem algoritmos formais que possam resolv-los.Em muitos casos, o problema apresentado como uma simples questo, que deve ser respondidacom sim ou no. Posto o problema desta forma, se existe um algoritmo que sempre responda sim ouno para qualquer entrada, ento o problema decidvel. Em alguns casos, porm, provou-se queno existem nem podero existir estes algoritmos. Tais problemas so chamados, ento, deindecidveis, ou parcialmente decidveis, se pelo menos uma das respostas sim ou no puder serencontrada.

Gdel, em 1931, provou que a aritmtica elementar indecidvel, ou seja, no existe umalgoritmo para provar a verdade ou falsidade de qualquer proposio da aritmtica. Hilbert, em1925, props vrios problemas que se supunha fossem indecidveis, dentre eles, por exemplo, o de


6/74


3

dizer se o polinmio P(x1,x2,...,xn)=0 tem soluo inteira. Apenas em 1970 Matijacevic provou queno existe nenhum procedimento efetivo para decidir esta questo.

Em termos de linguagem, pode-se dizer que uma linguagem decidvel se dada umalinguagemL e uma sentena w for possvel decidir algoritmicamente se w uma sentena de L.Para as linguagens no-decidveis, pode-se esperar que para algum w, a pergunta w L? no serrespondida, porque o algoritmo que procura pela resposta no parar.

Um algoritmo uma descrio finita de um processo de computao; um texto finito,escrito em um linguagem algortmica na qual cada sentena tem um significado no-ambguo.A palavra algoritmo uma corruptela daAl-Khuwarizmi, sobrenome de um matemtico

persa do sculo IX. O algoritmo deve poder ser resolvido em tempo finito (deve ter paradagarantida). Umprocedimento no termina necessariamente. Assim, existem problemas que possuem

procedimentos para serem resolvidos, mas no possuem algoritmos. Em outras palavras, existemum procedimento de procura de soluo, que pode chegar a uma resposta em um tempo finito, ouento pode no chegar a uma resposta em momento algum, ao contrrio do algoritmo, que semprechega uma resposta (afirmativa ou negativa) num tempo finito.

Decidir se um problema possui um algoritmo ou simplesmente um procedimento oprincipal problema indecidvel da teoria da computao, conhecido como Problema da Parada.

Outra forma de enunciar o problema da parada a seguinte: Dado um programa P e um conjuntode dados d, responda sim se P(d) pra e no caso contrrio.

A Tese de ChurchAlguns dos mais importantes modelos formais de computabilidade existentes so a Mquina

de Turing, as gramticas do Tipo 0 e as Funes Recursivas Parciais. A Tese de Church (1936)estabelece que: Embora todas estas caracterizaes sejam diferentes na forma, elas caracterizam omesmo conjunto de funes. No caso, Church provou que era possvel definir funes de traduode representaes de um formalismo para qualquer um dos outros, donde se concluiu que tudo oque expressvel em um deles pode ser expresso em qualquer um dos outros. Isto garante que todosos modelos formais de computao tm o mesmo poder expressivo.

Como as Funes Recursivas Parciais so suficientemente inclusivas em relao computao aparente, e a caracterizao da Mquina de Turing demonstra o aspecto mecnico do

processamento algortmico, estes formalismos so aceitos como capazes de expressar qualquerfuno ou algoritmo que possa ser formalmente expresso de alguma maneira.

3. Introduo a Compiladores

3.1 Processadores de Linguagem

Um processador de linguagem um programa que permite ao computador entender oscomandos de alto nvel fornecidos pelos usurios.

Existem duas espcies principais de processadores de linguagem: os interpretadores e ostradutores

.Um interpretador um programa que aceita como entrada um programa escrito em umalinguagem chamada linguagem fonte e executa diretamente as instrues dadas nesta linguagem.

Um tradutor um programa que aceita como entrada um programa escrito em umalinguagem fonte e produz como sada uma outra verso do programa escrito em uma linguagemobjeto. Muitas vezes a linguagem objeto a prpria linguagem de mquina do computador. Nestecaso o programa objeto pode ser diretamente executado pela mquina.

Tradutores so arbitrariamente divididos em montadores e compiladores, os quais traduzemlinguagens de baixo nvel e de alto nvel, respectivamente. Alm disso, h ospr-processadores quetraduzem uma linguagem de alto nvel em outra linguagem de alto nvel.

O fundamento matemtico da teoria de processamento de linguagens a teoria de autmatos

e linguagens formais.


7/74


4

3.2. Modelo Simples de Compilador

O objetivo de um compilador traduzir as seqncias de caracteres que representam oprograma fonte em instrues de mquina que incorporam a inteno do programador. Esta tarefa complexa o suficiente para poder ser vista como uma estrutura formada por processos menoresinterconectados.

Em um modelo simples de compilador o trabalho pode ser feito por uma interconexo serialentre trs blocos, chamados: bloco lxico, bloco sinttico e gerador de cdigo.

Os trs blocos tm acesso a tabelas de informaes globais sobre o programa fonte. Umadestas tabelas , por exemplo, a tabela de smbolos, na qual a informao sobre cada varivel ouidentificador utilizado no programa fonte armazenada. A conexo entre estes blocos e tabelas mostrada na figura seguinte:

Gerador deCdigo

BlocoSinttico

BlocoLxico

Tabelas

3.2.1. Bloco LxicoA entrada para um compilador a cadeia de caracteres quer representa o programa fonte. O

objetivo do bloco lxico quebrar esta cadeia de caracteres separando as palavras que nela estorepresentadas. Por exemplo, a cadeia de entrada poderia ser:

RESULTADO: =RESULTADO+15Neste caso, o bloco lxico deve ser capaz de discernir que esta cadeia contm o nome de

uma varivel RESULTADO, seguido de um comando de atribuio : =, seguido novamente deRESULTADO, seguido de uma operao aritmtica +e finalizado por uma constante numrica 15.Assim, os 23 caracteres da cadeia de entrada so transformados em 5 novas entidades. Estasentidades so freqentemente denominadas de tokens.

Um token consiste de uma par ordenado Classe x Valor. A classe indica que o tokenpertence a uma classe de um conjunto finito de classes possveis e indica a natureza da informaocontida em valor.

Voltando ao exemplo, a varivel RESULTADOpoderia pertencer classe varivel e seuvalor seria um ponteiro para a entrada RESULTADOna tabela de smbolos. O token 15 poderia

pertencer classe constante e ter valor correspondente ao nmero inteiro 15. J os tokens : =e +poderiam pertencer classes smbolos especiais.

Se a tabela de smbolos for vista como um dicionrio, ento o processo lxico pode ser vistocomo o ato de agrupar letras em palavras e determinar suas localizaes no dicionrio.

Outras funes normalmente atribudas ao bloco lxico so as de ignorar espaos em brancoe comentrios, alm de detectar os erros lxicos.

3.2.2. Bloco SintticoO bloco sinttico agrupa os tokens fornecidos pelo bloco lxico em estruturas sintticas,

verificando se a sintaxe da linguagem foi obedecida. Tomando novamente o exemplo anterior, os 5tokens gerados pelo bloco lxico poderiam ser agrupados na estrutura sinttica atribuio,representada por uma rvore sinttica, da seguinte forma:


8/74


5

atribuio

expresso

var atrib var op num

RESULTADO : = RESULTADO + 15 Note que a rvore exige que para a atribuio aparea uma varivel, seguida de uma

atribuio e de uma expresso. Desta forma, uma entrada do tipo15: =RESULTADO+10

passaria no bloco lxico, pois as tokens esto escritos da maneira correta, porm no passaria nobloco sinttico, pois no esto escritos na ordem correta.

3.2.3. Gerador de CdigoA funo do gerador de cdigo expandir os tomos gerados pelo bloco sinttico em uma

seqncia de instrues do computador que executam a inteno do programa fonte. Consistebasicamente noprocessamento semntico e na otimizao de cdigo.

Processamento SemnticoCertas atividades relacionados ao significado dos smbolos so freqentemente classificadas

como processamento semntico. Por exemplo, a semntica de um identificador pode incluir o seutipo, e, se for um array, por exemplo, seu tamanho. O processamento tambm pode incluir o

preenchimento da tabela de smbolos com as propriedades dos identificadores quando estas setornam conhecidas (quando so declaradas ou implcitas).

Na maioria dos compiladores, as atividades semnticas so realizadas por um blocoseparado, denominado bloco semntico, que fica entre o bloco sinttico e o gerador de cdigo.Algumas operaes semnticas usuais so: verificao de compatibilidade de tipo, anlise deescopo, verificao de compatibilidade entre declarao e uso de entidades, verificao decorrespondncia entre parmetros atuais e formais e verificao de referncia no resolvidas.

Otimizao de CdigoCertas atividades de um compilador que no so estritamente necessrias, mas que permitem

obter melhores programas objeto, so freqentemente referidas como otimizao. Para algunscompiladores, a otimizao inserida como um bloco entre o bloco sinttico e o semntico (sehouver). Este bloco pode resolver problemas como, por exemplo, instrues invariantes em laos,rearranjando os smbolos sintticos antes de pass-los para a anlise semntica.


9/74

II - Teoria de Linguagens

6


1. Linguagens Formais

O estudo dos diversos tipos de linguagens aplicam-se a diversas reas da informtica,sempre que for necessrio analisar o formato e o significado de uma seqncia de entrada. Dentre asaplicaes possveis, temos: editor de estruturas, que analisa as estruturas de um programa fontesendo editado, tentando minimizar erros; pretty printers, que tenta tornar os programas maislegveis; verificadores ortogrficos, verificadores gramaticais, verificadores estticos,interpretadores, compiladores, etc.

Sero apresentados nesta seo conceitos gerais sobre linguagens que serviro parafundamentar o estudo de todos os tipos de linguagens que viro a seguir.

1.1. Smbolo

Um smbolo uma entidade abstrata que no precisa ser definida formalmente, assim como

ponto e linha no so definidos na geometria. Letras e dgitos so exemplos de smbolosfreqentemente usados.Smbolos so ordenveis lexicograficamente e, portanto, podem ser comparados quanto

igualdade ou precedncia. Por exemplo, tomando as letras do alfabetos, podemos ter a ordenao a< b < c < ... < z. A principal utilidade dos smbolos est na possibilidade de us-los comoelementos atmicos em definies de linguagens.

1.2. Cadeia

Uma cadeia (ou string, ou palavra) uma seqncia finita de smbolos justapostos (isto ,sem vrgulas separando os caracteres). Por exemplo, se a, b e c so smbolos, ento abcb umexemplo de cadeia usando utilizando estes smbolos.

O tamanho de uma cadeia o comprimento da seqncia de smbolos que a forma. Otamanho de uma cadeia w ser denotado por |w|. Por exemplo, |abcb| = 4. A cadeia vazia denotadapor, e tem tamanho igual a 0; assim, || = 0.

Umprefixo de uma cadeia um nmero qualquer de smbolos tomados de seu incio, e umsufixo um nmero qualquer de smbolos tomados de seu fim. Por exemplo, a cadeia abc tem

prefixos , a, ab, e abc. Seus sufixos so , c, bc, abc. Um prefixo ou sufixo que no so a prpriacadeia so chamados deprefixo prprio e sufixo prprio, respectivamente. No exemplo anterior, os

prefixos prprios so , a e ab; e os sufixos prprios so , c e bc.A concatenao de duas cadeias a cadeia formada pela escrita da primeira cadeia seguida

da segunda, sem nenhum espao no meio. Por exemplo, a concatenao de compila e dores compiladores. O operador de concatenao a justaposio. Isto , se w e x so variveis quedenotam cadeias, ento wx a cadeia formada pela concatenao de w e x. No exemplo acima, setomarmos w = compila e x = dores, ento temos wx = compiladores.

A n-sima potncia de uma cadeia x, denotada por xn, a concatenao de x com ela mesman-1 vezes, ou a repetio da cadeia n vezes. Por exemplo, abc3 = abcabcabc.

Um alfabeto definido simplesmente como um conjunto finito de smbolos. Por exemplo, oalfabeto da lngua portuguesa V = {a, b, c, ..., z}. O alfabeto utilizado para expressar os nmerosnaturais V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}.

Ofechamento de um alfabeto V, representado por V*, o conjunto de todas as cadeias quepodem ser formadas com os smbolos de V, inclusive a cadeia vazia. Ofechamento positivo de V,denotado por V+ definido como V* - {}. Ou seja, todas as cadeias formadas com os smbolos de

V, exceto a cadeia vazia. Por exemplo, dado o alfabeto V = {0, 1}, ento o fechamento de V dado


10/74


7

por V* = {, 0, 1, 00, 01, 10, 11, 000, 001, ... } e o fechamento positivo de V dado por V+ = V* -{} = {0, 1, 00, 01, 10, 11, 000, 001, ... }

1.3. Linguagens

Uma linguagem (formal) um conjunto de cadeias de smbolos tomados de algum alfabeto.Isto , uma linguagem sobre o alfabeto V um subconjunto de V*. Note-se que esta definio

meramente extensional, isto , no considera os mecanismos formadores da linguagem, mas apenasa sua extenso. Assim, por exemplo, o conjunto de sentenas vlidas da lngua portuguesa poderiaser definido extensionalmente como um subconjunto de {a, b, c,..., z}+.

Uma linguagem finita se suas sentenas formam um conjunto finito. Caso contrrio, alinguagem infinita. Uma linguagem infinita precisa ser definida atravs de uma representaofinita. Por exemplo, a linguagem dos nmeros naturais menores que 10 finita, e pode serrepresentada, literalmente, como L = {1, 2, 3, 4, 5, 6, 7, 8, 9}. J a linguagem dos nmeros naturaiscomo um todo no uma linguagem finita, j que existem infinitos nmeros naturais. Porm, comoveremos adiante, existem mecanismos que permitem expressar esta e outras linguagens infinitasatravs de representaes finitas. o caso das gramticas e das expresses regulares.

Umreconhecedor

para uma linguagem um dispositivo formal usado para verificar se umadeterminada sentena pertence ou no a uma determinada linguagem. So exemplos dereconhecedores de linguagens as Mquinas de Turing, o Autmato de Pilha e o Autmato Finito.Cada um destes mecanismos reconhece um conjunto bastante particular de linguagens. Entretanto,os modelos so inclusivos: todas as linguagens reconhecveis por um Autmato Finito podem serreconhecidas por uma Autmato de Pilha e todas as linguagens reconhecveis por um Autmato dePilha so reconhecveis por Mquinas de Turing. As recprocas, entretanto, no so verdadeiras.

Um sistema gerador um dispositivo formal atravs do qual as sentenas de uma linguagempodem ser sistematicamente geradas. Exemplos de sistemas geradores so as gramticas gerativas,definidas pela primeira vez por Noam Chomsky, em seus estudos para sistematizar a gramtica dalngua inglesa.

Todo reconhecedor e todo sistema gerador pode ser representado por algoritmos e/ouprocedimentos. Como ser visto mais adiante, pode-se garantir que linguagens reconhecidas porautmatos so reconhecidas algoritmicamente. J o conjunto das linguagens reconhecidas porMquinas de Turing, que mais abrangente, inclui linguagens reconhecveis algoritmicamente elinguagens indecidveis, que no possuem algoritmos para reconhecimento.

2. GramticasUma gramtica gerativa um instrumento formal capaz de construir (gerar) conjuntos de

cadeias de uma determinada linguagem. As gramticas so instrumentos que facilitam muito adefinio das caractersticas sintticas das linguagens. So instrumentos que permitem definir, deforma formal e sistemtica, uma representao finita para linguagens infinitas.

Usar um mtodo de definio de conjuntos particular para definir uma linguagem pode serum passo importante no projeto de um reconhecedor para a linguagem, principalmente se existiremmtodos sistemticos para converter a descrio do conjunto em um programa que processa oconjunto. Como veremos adiante neste curso, certos tipos de gramticas, que possuem algoritmos

para definir se uma sentena pertence ou no linguagem que geram, so utilizadas paraimplementar compiladores. J gramticas que no permitem a definio de algoritmos no podemser utilizadas para tal.

Mais adiante sero vistos mtodos para transformar gramticas em mquinas abstratascapazes de reconhecer e traduzir os conjuntos definidos pelas gramticas. Antes, porm, necessrio entender como conjuntos de sentenas so definidos por gramticas.


11/74


8

2.1. Definio Formal de Gramtica

Uma gramtica possui um conjunto finito de variveis (tambm chamadas de no-terminais). A linguagem gerada por uma gramtica definida recursivamente em termos dasvariveis e de smbolos primitivos chamados terminais, que pertencem ao alfabeto da linguagem.

As regras que relacionam variveis e terminais so chamadas deprodues, que sempreiniciam num ponto, o smbolo inicial, pertencente ao conjunto de variveis (no-terminais). Umaregra de produo tpica estabelece como uma determinada configurao de variveis e terminais

pode ser reescrita, gerando uma nova configurao.Formalmente, uma gramtica especificada por uma qudrupla (N,T,P,S), onde: N o conjunto de no-terminais, ou variveis. T o conjunto de terminais, ou alfabeto, sendo que N e T so conjuntos disjuntos. P um conjunto finito de produes, ou regras, sendo que

P (N T)+ (N T)*. S um smbolo no-terminal inicial, sendo S N. A partir dele so geradas todas as

sentenas da linguagem.Uma produo (n,p) pode ser escrita n ::= p, para facilitar a leitura. No caso de existir mais

de uma alternativa para uma mesma configurao e smbolos do lado esquerdo da regra, como porexemplo: ::= coisa ::= co ::= pedra

pode-se escrever as opes em uma nica produo, separada por |. O exemplo acima ficaria: ::= coisa | co | pedra.O smbolo ::= pode ser lido como definido por e o smbolo | pode ser lido como ou.

2.2. Derivao

Uma gramtica pode ser usada para gerar uma linguagem atravs de reescrita ou derivao.

A derivao pode ser definida da seguinte maneira: dada uma sentena a1ba2, com a1 e a2 sendocadeias de terminais e no-terminais, se existir uma regra da forma b ::= c, ento a sentena inicial

pode ser reescrita como a1ca2. A derivao, ou reescrita, denotada da seguinte forma:a1ba2 a1ca2Por exemplo, digamos que exista a seguinte seqncia de terminias (letras minsculas) e

no-terminais (letras maisculas): aaaDbbb, e que exista a produo D ::= ab na gramtica.Assim, a derivao aaaDbbb aaaabbbb uma derivao vlida na gramtica dada.

Se a b, ento se diz que a produz diretamente b. O fecho transitivo e reflexivo da relao *. Portanto, se a b ... z, ento se diz que a produz z, simplesmente, anotando a

produo por a* z. O fecho transitivo pode ser definido da seguinte forma:a)a 0 a

b)a 1b se abc)a n+1 z se a n y e y 1 zd)a * z se a n z, para algum n 0.Seja, por exemplo, a seguinte gramtica, onde as regras so numeradas para acompanhar o

desenvolvimento da derivao:1: ::= +=2,3: ::= 1 | 14: +1 ::= 1+5: 1 ::= 1

6: += ::= 7: 1 ::= 1


12/74


9

A derivao de uma sentena a partir desta gramtica consiste em uma seqncia deaplicaes das produes a partir do smbolo inicial. Por exemplo:

+= [1]1+= [2 no primeiro ]1+1= [3 no segundo ]11+= [4]11+= [5]11 [6]111 [3]

O fato das regras terem sido aplicadas praticamente em seqncia foi mera coincidncia. Aprincpio, qualquer regra de derivao pode ser aplicada a qualquer ponto de sentena desde que aconfigurao de smbolos do lado esquerdo da regra aparea na sentena sendo derivada.

Outro exemplo a seguinte gramtica: ::= 1 | 0 | 1 ::= 0 | 1A sentena 100101 gerada pela seguinte seqncia de derivaes:

1

10

100

1001

10010

100101Originalmente, a motivao do uso de gramticas foi o de descrever estruturas sintticas dalngua natural. Poderia-se escrever regras (produes) como:

::= . | .

::= dorme | escuta | ama::= gato | rdio | rato ::= oDesta gramtica simples pode-se obter derivaes como: o .

o gato . o gato ama .o gato ama o . o gato ama o rato.

Entretanto a mesma gramtica tambm permite derivar o gato dorme o rato, frase que nofaz sentido. Para evitar a gerao de tais frases, pode-se usar uma gramtica sensvel ao contexto,estabelecendo que s pode ser reescrito para dorme se for sucedido pelo ponto final dafrase:

::= . | .

. ::= dorme. ::= escuta | ama ::= gato | rdio | rato ::= oPara esta gramtica, impossvel derivar as sentenas o gato dorme o rato, o gato ama e

o rato escuta. O verbo dorme s pode ser derivado se for sucedido por um ponto final e os verbosescuta e ama s podem ser derivados se forem sucedidos por um artigo. Porm ainda possvelderivar uma sentena do tipo o rdio ama o rato. O leitor convidado a modificar a gramticaacima para no aceitar sentenas desse tipo (dica: permitir que o substantivo rdio apareasomente no final da sentena).

2.3. Notao

Como conveno notacional, pode-se admitir que smbolos no terminais sero semprerepresentados por letras maisculas, e terminais por minsculas. Assim, uma regra como


13/74


10

::= b | b poderia ser escrita como A ::= Ab | b. Alm disso, os conjuntos T e N podem ficarsubentendidos e no precisam ser expressos sempre.

Pode-se ainda arbitrar que o smbolo inicial S ser sempre o no-terminal que aparecerprimeiro do lado esquerdo da primeira produo da gramtica. Assim, bastaria listar as regras deproduo para se ter a definio completa da gramtica. Por exemplo, a gramtica

S ::= ABSc |

BA ::= ABBc ::= bcAb ::= abBb := bbAa ::= aaTem como smbolo inicial S, o conjunto de terminais {a, b, c} e o conjunto de no-

terminais (variveis) {A, B, S}. As produes esto detalhadas. Tem-se assim a definiocompleta da gramtica.

3. Linguagens Definidas por GramticasA linguagem definida por uma gramtica consiste no conjunto de cadeias de terminais que

esta gramtica pode potencialmente gerar. Este conjunto ser denotado por L(G). A linguagemdefinida por uma gramtica G=(N,T,P,S) dada por:

L(G) = { | T* S * }Em outras palavras, uma cadeia pertence a L(G) se e somente se ela consiste somente de

terminais (pode ser a cadeia vazia ), e pode ser produzida a partir de S em 0 ou mais derivaes.Uma cadeia em (T N)* chamada deforma sentencial se ela pode ser produzida a partir

de S (mas ainda contm no-terminais). Assim, pode-se caracterizar L(G) como o conjunto de todasas formas sentenciais que contm apenas terminais, e foram geradas a partir do smbolo inicial deG. Desta forma, aaaBbbC uma forma sentencial, pois contm variveis (B e C). J aabb uma sentena, pois contm apenas terminais.

4. Tipos de GramticasImpondo restries na forma das produes, pode-se identificar quatro tipos diferentes de

gramticas. Esta classificao foi feita por Chomsky e conhecida como hierarquia de Chomsky.Os tipo de gramtica definidos nesta hierarquia so:

a)Tipo 0: No h restrio na forma das produes. Este o tipo mais geral. Exemplo:S ::= ABS | ab Ba ::= aB | a Aa ::= aa | a |

b)Tipo 1: Seja G=(N,T,P,S). Se: O smbolo inicial S no aparece no lado direito de nenhuma produo, e para cada produo 1 ::= 2, verdade que | 1 | | 2 | (com exceo da regra S

::= ),ento se diz que G uma gramtica do tipo 1, ou Gramtica Sensvel ao Contexto. Exemplo:

S ::= aBC | aABC A ::= aABC | aBC CB ::= BC aB ::= abbB ::= bb bC ::= bc cC ::= cc

c)Tipo 2: Uma gramtica G=(N,T,P,S) do tipo 2, ou uma Gramtica Livre de Contexto,se cada produo livre de contexto, ou seja, cada produo da formaA ::= , com A N e (T N)*.Exemplo:S ::= aSb | A A ::= cAd | e

O tipo 2 no definido como restrio do tipo 1, porque se permite produes da forma A::= , com A S. Tambm se permite que o smbolo inicial S aparea no lado direito das produes.


14/74


11

Entretanto, existe um teorema que prova que a partir de uma gramtica de tipo 2 se pode construiroutra gramtica equivalente, de tipo 2, que satisfaz as restries do tipo 1.

d)Tipo 3. Uma gramtica G de tipo 3, ou regular, se cada produo da formaA ::= aB, A ::= a ou A ::= , onde A e B so no-terminais e a um terminal.Exemplo:S ::= aS | bB B ::= bB | bC C ::= cC |

5. Tipos de LinguagensUma linguagem L de tipo i se existe uma gramtica G de tipo i tal que L = L(G), para i

igual a 0, 1, 2 ou 3. Pode-se ver que cada linguagem de tipo 3 tambm de tipo 2, cada linguagemde tipo 2 tambm de tipo 1, e cada linguagem de tipo 1 tambm de tipo 0. Estas incluses soestritas, isto , existem linguagens de tipo 0 que no so de tipo 1, existem linguagens de tipo 1 queno so do tipo 2 e existem linguagens do tipo 2 que no so do tipo 3. Graficamente esta incluso

pode ser representada por:

Linguagens do Tipo 0




Pode-se relacionar cada tipo de gramtica com uma mquina reconhecedora da seguinte

maneira: a gramtica de tipo 0 gera linguagens reconhecveis por mquinas de Turing; a gramticade tipo 2 gera linguagens reconhecidas por autmatos de pilha; a gramtica de tipo 3 geralinguagens reconhecidas por autmatos finitos.

No h uma classe de reconhecedores para apenas linguagens de tipo 1, porque qualquer

mquina capaz de reconhecer linguagens de tipo 1 poderosa o suficiente para reconhecerlinguagens do tipo 0. A principal razo para identificar as linguagens de tipo 1 como um tiposeparado porque toda a linguagem do tipo 1 decidvel, isto , se G=(N,T,P,S) do tipo 1, entoexiste um algoritmo tal que, para qualquer sentena w, responda sim se w L(G) e no casocontrrio.

Assim, pode-se dizer que as linguagens do tipo 1 so reconhecveis por Mquinas de Turing,sendo decidveis, ou seja, a mquina sempre vai parar num tempo finito com uma resposta,afirmativa ou negativa, sobre a sentena analisada. J as linguagens do tipo 0 tambm podem seranalisadas por Mquinas de Turing. O problema que podem existir linguagens, ou sentenasdentro de linguagens, para as quais a mquina no pare. Ou seja, a mquina ficar analisando asentena indefinidamente, sem chegar a nenhuma resposta.

EXERCCIOS1. Uma palndrome uma cadeia que pode ser lida da mesmo maneira da direita para a esquerda e

da esquerda para a direita. Exemplos: a, ama, osso, asddsa. Defina uma gramtica para alinguagem das palndromes (conjunto de todas as palndromes sobre o alfabeto {a, b, c, ... , z}.

* 2. Dada a gramtica (livre de contexto):S ::= aSba |

mostre trs cadeias de L(G) e a derivao de cada uma delas.

3. Dado o conjunto de terminais (alfabeto) T={a, b, c}, defina as gramticas para as seguinteslinguagens:* a) Sentenas que comeam e terminam com a.


15/74


12

* b) Sentenas que tenham tamanho mpar.c) Sentenas em que todos os as apaream consecutivos.* d) Sentenas na forma 1n0n2n, com n > 0.e) Sentenas na forma anbmcnan, n > 0 e m > 0.* f) Sentenas na forma anbmcn, com n > 0 e m 0.g) Sentenas na forma ambncn, com m 0 e n > 0.

h) Sentenas em que o nmero de as seja par.i) Sentenas na forma anb2ncm, n > 0 e m > 2.

4. Defina uma gramtica que gere as expresses numricas com o seguinte alfabeto: dgitos (0 a 9),sinais (+, -, *, /) e parnteses ( e ). Teste sua definio mostrando a derivao das seguintessentenas:

a) (5+5)/(4+1)b) 4*(7/9)c) ((5)/((4+5)*(1+3)))

5. Escreva uma gramtica para cada uma das linguagens abaixo:

* a) { a2i+1bi+3 | i 0 } {ai+4b3i } | i 0}* b) {aibk | k > 0, i > k }c) { aibj cj di e3 | i, j 0 }d) { aibj ckdl | i, j, k, l > 0, i l, j > k}

6. Indique o tipo de cada gramtica:( ) S ::= aS | b | ( ) S ::= AAA | aA AA ::= AbcAA | A ::= a | b( ) S ::= aB | b B ::= aB | b( ) S ::= (S) | S + S (S+S) ::= [id + id]

( ) S := ABc | abc A := ab | B ::= bc | b

7. Construa expresses regulares para as cadeias de 0s e 1s descritas abaixo:* a) com nmero par de 1s e 0s.

b) com nmero mpar de ocorrncias do padro 00.* c) com pelo menos duas ocorrncias do padro 101.d) com qualquer cadeia de entrada.e) com nenhuma cadeia de entrada.f) as cadeias 0110 e 1001.e) todas as cadeias que comeam com 01 e terminam com 10.g) todas as cadeias que contenham exatamente quatro 1s.

h) a cadeia nula e 001.


16/74

III - Linguagens Regulares e Autmatos Finitos

13


1. Linguagens Regulares

As linguagens regulares constituem um conjunto de linguagens decidveis bastante simples ecom propriedades bem definidas e compreendidas. Essas linguagens podem ser reconhecidas porautmatos finitos e so facilmente descritas por expresses simples, chamadas expresses regulares(E.R.) Antes de introduzir o mecanismo das E.R.s, ser feita uma reviso das operaes deconcatenao e fechamento de conjuntos, j que so estas as operaes bsicas para a definio delinguagens regulares.

1.1. Operaes de Concatenao e Fechamento

Seja C um conjunto finito de smbolos (alfabeto), e sejam L, L1 e L2 subconjuntos de C*

(linguagens sobre o alfabeto C). A concatenao de L1 e L2, denotada por L1L2 o conjunto {xy | x

L1 e y L2}. Em outras palavras, as cadeias da linguagem L1L2 so formadas por uma cadeia deL1 concatenada a uma cadeia em L2, nesta ordem, incluindo a todas as combinaes possveis.Define-se L0 = { } e Ln = LLn-1 para n 1. Ofecho de Kleene (ou simplesmentefecho) de

uma linguagem L, denotado por L*, o conjunto:

L L L L L Lii

* ...= = =

0

0 1 2 3U

e ofecho positivo da linguagem L, denotado por L+, o conjunto:

L L L L L Li

i

+

=

= =

1

1 2 3 4U ...

Em outras palavras, L* denota as cadeias construdas pela concatenao de qualquer nmerode cadeias tomadas de L. O conjunto L+ semelhante, mas neste caso, as cadeias de zero palavras,cuja concatenao definida como , so excludas. Note-se, porm, que L+ contm se e somentese L contm . Esta definio difere da definio do fechamento de alfabetos, onde A+ era definidocomo A* - { }. Note-se que no caso de linguagens, podem ocorre dois casos:

a) Se L, ento L+ = L*.b) Se L, ento L+ = L* - { }.

Exemplos:1. Seja L1 = {10, 1} e L2 = {0011, 11}. Ento L1L2 = {100011, 1011, 10011, 111}

2. {10, 11}* = {, 10, 11, 1010, 1011, 1110, 1111, ... }

1.2. Definio de Expresses Regulares

Seja A um alfabeto. As expresses regulares sobre o alfabeto A e os conjuntos (linguagens)que elas denotam so definidas indutivamente como segue:

a) uma expresso que denota o conjunto vazio.b) uma expresso regular que denota o conjunto {}.c) Para cada smbolo em a em A, a uma expresso regular que denota o conjunto {a}.d) Se r e s so expresses regulares que denotam os conjuntos R e S, respectivamente, ento

(r+s), (rs), e (r

*

) so expresses regulares que denotam os conjuntos RS, RS e R

*

,respectivamente.


17/74


14

Quando se escreve expresses regulares, pode-se omitir muitos parnteses se for assumidoque o smbolo * tem precedncia maior que a concatenao e +, e que a concatenao tem

precedncia maior que +. Por exemplo, ((0(1*))+0) pode ser escrita como 01*+0. Alm disso, pode-se aplicar simplificas abreviando expresses como rr* para r+.

As expresses regulares possuem as seguintes propriedades algbricas:

AXIOMA DESCRIOr + s = s + r + comutativo.

r + (s + t) = (r + s) + t + associativo.(rs)t = r(st) a concatenao associativa.r(s + t) = rs + rt(s + t)r = sr + tr

a concatenao distibutiva sobre +.

r = rr = r

o elemento neutro (identidade) daconcatenao.

r* = (r + )* relao entre e *.

r

**

= r

*

* idempotente.

Exemplos: 00 uma expresso regular que denota a linguagem { 00 }. A expresso (0+1)* denota todas as cadeias de 0s e 1s. (0+1)*00(0+1)* denota as cadeias de 0s e 1s com pelo menos dois 0s consecutivos. (1+10)* denota as cadeias de 0s e 1s que comeam com 1 e no tem 0s consecutivos. (0+1)*001 denota as cadeias de 0s e 1s que terminam por 001. a+b* denota as cadeias que tem qualquer quantidade de as (mnimo 1) seguidos de

qualquer quantidade de bs (possivelmente 0). Exemplo = {a, aaa, aab, aabbbbbb, ab,

abbbb, ...} importante notar que as linguagens regulares podem ser expressas tanto por expressesregulares como por gramticas regulares. Assim, qualquer linguagem descrita na forma de umaexpresso regular pode ser descrita por uma gramtica regular. A seguir apresentada uma tabelaque mostra linguagens regulares representadas por expresses regulares e por gramticas regulares.

Expresso Regular Gramtica Regular(0 + 1)* S ::= 0S | 1S | 001* S ::= 0A A ::= 0B B ::= 1B | (00)*(11)+ S ::= 0A | 1B A ::= 0S B ::= 1 | 1C C ::= 1Ba(aa)*(b+c)* S ::= aA A ::= | aB | bC | cC B ::= aA

C ::= bC | cC |

2. Autmatos FinitosO Autmato Finito (AF) o tipo mais simples de reconhecedor de linguagens. Ele usado

como reconhecedor de padres em processamento de textos e tambm como analisador lxico delinguagens.

Autmatos finitos so usados com vantagens na compilao porqu:a)Eles tm a capacidade de realizar vrias tarefas simples de compilao. Em particular, o

projeto do bloco lxico pode ser feito baseado em um autmato finito.b)Uma vez que a simulao de um AF por um computador requer apenas um pequeno

nmero de operaes para processar um smbolo de entrada individual, ela operarapidamente.


18/74


15

c)A simulao de um AF requer uma quantidade finita de memria.d)Existem vrios teoremas e algoritmos para construir e simplificar autmatos finitos para

vrios propsitos.O conceito fundamental do AF o conceito de estado. O estado representa uma condio

sobre o modelo representado. Por exemplo, um computador pode ser representado por um modelo

com dois estados: ligado e desligado. Pode-se ainda dizer que o ato de pressionar um botoocasiona uma mudana de estado, dependendo do estado atual. Esta mudana de estado denominada transio. O AF que representa este modelo pode ser:

ComputadorDesligado

ComputadorLigado

pressionar

pressionar

Um Autmato Finito um reconhecedor de Linguagens Regulares. Entende-se porreconhecedorde uma linguagem L um dispositivo que tomando uma seqncia w como entrada,responde sim se w L e no caso contrrio.

Os Autmatos Finitos classificam-se em:

Autmatos Finitos Determinsticos (AFD) Autmatos Finitos No-Determinsticos (AFND)2.1 Autmatos Finitos Determinsticos

Formalmente definimos um AFD como sendo um sistema formal M = (K, , , q0, F), onde: K um conjunto finitos no-vazio de ESTADOS; um ALFABETO, finito, de entrada; FUNO DE MAPEAMENTO (ou funo de transio), definida em

K x K; q0 K, o ESTADO INICIAL; F K, o conjunto de ESTADOS FINAIS.

2.1.1. Interpretao de A interpretao de (q, a) = p, onde {q, p} K e a , de que se o controle de M est

no estado q e o prximo smbolo de entrada a, ento a deve ser reconhecido e o controlepassa para o prximo estado (no caso, p). Note que a funo de mapeamento definida por K x K, ou seja, de um estado, atravs do reconhecimento de um smbolo, o controle passa para UMNICO outro estado. Por isso este tipo de autmato chamado de DETERMINSTICO.

2.1.2. Significado Lgico de um EstadoLogicamente um estado uma situao particular no processo de reconhecimento de uma

sentena. Mais genericamente, um estado representa uma condio sobre a parte da sentena que j

foi reconhecida.2.1.3. Sentenas Aceitas por M

Uma sentena x aceita (reconhecida) por um AF M = (K, , , q0, F) se, e somente se,(q0, x) = p p F. Em outras palavras, a sentena x reconhecida se, partindo do estado inicialq0, atravs das transies para cada smbolo de x, um estado final alcanado.

2.1.4. Linguagem Aceita por M um conjunto de todas as sentenas aceitas por M. Formalmente, definimos por:L(M) = {x | (q0, x) = p p F}.Ou seja, o conjunto de todas as sentenas que, partindo do estado inicial, fazem com que o

autmato alcance um estado final quando termina de reconhecer a sentena.

Obs.: Todo conjunto aceito por um Autmato Finito um Conjunto Regular.


19/74


16

2.1.5. Diagrama de TransioUm diagrama de transio para um AF M um grafo direcionado e rotulado. Os vrtices

representam os estados e fisicamente so representados por crculos, sendo que o estado inicial diferenciado por uma seta com rtulo incio e os estados finais so representados por crculosduplos. As arestas representam as transies, sendo que entre dois estados p e q existir uma

aresta direcionada de p para q com rtulo a (a ) (p, a) = q em M.2.1.6. Tabela de Transies

uma representao tabular de um AFNesta tabela as linhas representam os estados (o inicial indicado por uma seta e os finais

por asteriscos), as colunas representam os smbolos de entrada e o contedo da posio (q, a) serigual a p se existir(q, a) = p, seno ser indefinida.

ExemplosNesta seo daremos alguns exemplos de AFD nas formas grficas e tabulares.Exemplo 1: AFD que reconhea as sentenas da linguagem L = {(a,b)+, onde o nmero de

as mpar}.

Forma Grfica:

Forma Tabular: a b

q0 q1 q0* q1 q0 q1

possvel interpretar o estado q0 como a condio lgica h um nmero par de as nasentea e o estado q1 como a condio h um nmero mpar de as na sentena.

Para reconhecer a sentena abbaba o autmato realiza as seguintes transies, partindo doestado inicial:

q0 abbabaa q1 bbabaab q1 babaabb q1 abaabba q0 baabbab q0 aabbaba q1Como a sentena terminou com o autmato num estado final, a mesma reconhecida, ou

seja, faz parte da linguagem definida. J a sentena ababaab leva s seguintes transies do AFDacima:q0 ababaaba q1 babaabab q1 abaababa q0 baababab q0 aabababa q1 abababaa q0 bababaab q0Ao final da sentena o AFD est num estado no-final. Assim, a sentena no faz parte da

linguagem.

q0 q1a

aincio

b b


20/74


17

Exemplo 2: AFD que reconhea as sentenas da linguagem L = {(0,1)*, onde todos os 1sapaream consecutivos}.

Forma Grfica:

Forma Tabular: 0 1

* q0 q0 q1* q1 q2 q1* q2 q2 -

Note que neste caso, o no reconhecimento de sentenas com 1s no consecutivos

impossvel pois no h transio no estado q2 para o smbolo 1. A sentena 0101 leva sseguintes transies:q0 01010 q0 10101 q1 01010 q2 1 (?)Quando o AFD, no estado atual, no apresentar transio para um smbolo da entrada, a

sentena tambm rejeitada.

2.2. Autmatos Finitos No-Determinsticos

Um AFND um sistemas formal M = M = (K, , , q0, F) onde:K, , q0, F possuem a mesma definio de AFD uma funo de mapeamento, definida em K x = (K) (um conjunto de estados),

sendo que (K) um subconjunto de K. Isto equivale a dizer que (q, a) = p1, p2, ..., pn. Ainterpretao de que M no estado q, com o smbolo a na entrada pode ir tanto para o estado

p1, como para o estado p2, ..., como para o estado pn.Uma sentena x aceita por um AFND se (q0, x) = P, e {P F } . Em outras palavras,

uma sentena x aceita se, dentre os estados alcanados, pelo menos um final.Na anlise de uma sentena, quando um smbolo leva mais de um estado, pode-se dizer

que o AFND se divide em vrios, sendo que cada um deles continua o reconhecimento da sentenapor uma das possibilidades. Se pelo menos um deles chegar a um estado final no final da sentena,ento ela vlida. Se nenhum chegar a um estado final, ento a sentena invlida.

Exemplo: Seja a linguagem L = {(a,b)* abb}. O AFND seria:Forma Grfica:

FormaTabular:

a b

q0 q0, q1 q0

q0 q11incio

0 1

q20

0

q0 q1incio a

a, b

q3q2b b


21/74


18

q1 - q2q2 - q3

* q3 - -

Para reconhecer a sentena ababb, o autmato poderia seguir as seguintes alternativas:

q0 q0 q0 q0 q0 q0

q1 q2 q3

q1 q2

a b a b b

H trs possibilidades no reconhecimento da sentena: um caminho termina num estado no-final (q0); um caminho chega a um estado (q2) onde no h transio definida para o prximo

smbolo (a); um caminho chega a um estado final (q3) no final da sentena.Como h a possibilidade de chegar a um estado final com a sentena, ento a mesma

vlida, ou seja, deve ser reconhecida como parte da linguagem definida.

2.3. Comparao entre AFD e AFND

Os AFDs e os AFNDs representam a mesma classe de linguagens, ou seja, as linguagensregulares. A tabela abaixo mostra as principais diferenas entre AFD e AFND:

Vantagens DesvantagensAFD Implementao trivial No representa claramente algumas

L. R.AFND Representa mais claramente

algumas L. R.

Implementao complexa

2.4. Transformao de AFND para AFD

Como os autmatos finitos representam a mesma classe de linguagens, sejamdeterminsticos ou no-determinsticos, de se esperar que haja uma equivalncia entre eles.Realmente esta equivalncia existe. Assim, para cada AFND possvel construir um AFDequivalente. Nesta seo apresentado um algoritmo que converte um AFND num AFDequivalente. Assim, possvel utilizar a clareza da representao de um AFND, e para fins defacilidade de implementao, transform-lo num AFD.

Teorema 3.1: Seja L um conjunto aceito por um AFND., ento um AFD que aceita L.Prova: Seja M = (K, , , q0, F) um AFND Construa um A. F. D. M = (K, , , q0, F)

como segue:1 - K = {(K)} isto , cada estado de M formado por um conjunto de estados de M.2 - q0 = [q0] obs.: representaremos um estado q K por [q].3 - F = {(K) | (K) F }.4 - = .5 - Para cada (K) K, ((K), a) = (K), onde (K) = {p | para algum q(K),

(q, a) = p}, ou seja:Se (K) = [q1, q2, ..., qr] K ese (q1, a) = p1, p2, ..., pj

(q2, a) = pj+1, pj+2, ..., pk...


22/74


19

(qr, a) = pi, pi+1, ..., pn so as transies de M,ento (K) = [p1, p2, ..., pj, pj+1, ..., pk, ..., pi, pi+1, ..., pn] ser um estado de M e M conter

a transio: ((K), a) = (K).Para concluir a prova do teorema, basta provar que a linguagem de M igual linguagem

de M (L(M) = L(M)), prova esta que no apresentada neste texto.

Exemplo: Tomemos por exemplo o AFND da seo 3, representado na tabela abaixo: a b

q0 q0, q1 q0q1 - q2q2 - q3

* q3 - -

Para determinizar o AFND acima, basta definir o AFD M= (K, , , q0, F), onde a b

[q0] [q0, q1] [q0]

[q0, q1] [q0, q1] [q0, q2][q0, q2] [q0, q1] [q0, q3]

* [q0, q3] [q0, q1] [q0]

K = {[q0], [q0, q1], [q0, q2], [q0, q3] } = {a ,b} q0 = [q0] F = {[q0, q3]}

2.5. Autmato Finito com -TransiesPode-se estender o modelo de autmato finito no-determinstico para incluir transies com

entrada vazia: . O AFND da figura seguinte aceita uma linguagem constituda por qualquer

nmero de 0s, seguidos por qualquer nmero de 1s, seguido por qualquer nmero de 2s(incluindo a quantidade 0, para cada um dos casos).

0 1 2

q0 q1 q2

Definio:Um autmato finito no-determinstico com -transies uma quntupla (K, , , q0, F),

com todos os componentes de um AFND, mas com a relao de transio definida sobre K

{} K.Na representao da tabela de transies do AF, utilizada uma coluna para a -transio.No caso do exemplo, a tabela seria a seguinte:

0 1 2 q0 q0 q1

q1 q1 q2* q2 q2

2.5.1. Equivalncia Entre AFs Com e Sem -TransiesPara um autmato finito com -transies, define-se o -fechamento de um estado q como

sendo o conjunto de estados alcanveis a partir de q utilizando-se somente -transies.Para o AF do exemplo anterior, tm-se os seguintes -fechamento dos estados:


23/74


20

-fecho(q0) = {q0, q1, q2}-fecho(q1) = {q1, q2}-fecho(q2) = {q2}Seja M = (K, , , q0, F) um AF com -transies, pode-se construir M = (K, , , q0, F)

sem -transies, utilizando-se o seguinte algoritmo:

Algoritmo: Eliminao de -transiesEntrada: Um AFND com -transies M = (K, , , q0, F)Sada: Um AFND com -transies M = (K, , , q0, F)

F ser definido por F {q K e -fecho(q) contm um estado de F. deve conter todas as transies de t que no so -transies, mais aquelas que so obtidas pelacomposio de transies de com as -transies de , da seguinte maneira:

Se (q1, a) = q2 , e q3 -fecho(q2) entocoloque (q1, a) = q3 em

Fim Se;

Se (q1, a) = q2 , e q1 -fecho(q3) entocoloque (q3, a) = q2 em

Fim Se;Fim;

Para o autmato do exemplo anterior, tm-se o seguinte AFND sem -transies:

0, 1, 2

1, 2

0 1 2

0, 1q0 q1 q2

Claramente, para todo AFND com -transies, h um AFD equivalente, uma vez que bastaeliminar as -transies, e em seguida determinizar o AFND resultante, chegando-se ao AFDequivalente.

3. Relao Entre GR e AFAs gramticas regulares so sistemas geradores das linguagens regulares, enquanto os AFs

so sistemas reconhecedores do mesmo conjunto de linguagens. Assim, h uma correspondnciaentre as GR e os AF. Nesta seo so apresentados algoritmos para determinar o AF parareconhecer a linguagem de um GR, bem como para determinar a GR que gera a linguagem de umdado AF.

Teorema 3.2: Seja G = (N, T, P, S) uma Gramtica Regular, ento um AF M = (K, , ,q0, F) | L(M) = L(G).

Prova:a - Mostar que M existe;b- Mostrar que L(M) = L(G).

a) Defina M como segue:1 - K = N {A}, onde A um novo smbolo no-terminal;2 - = T;3 - q0 = S;4 - F = {B | B P} {A}, ou seja, todos os estados que produzem ,

juntamente com o novo estado.

5 - Construa de acordo com as regras a, b e c:a) Para cada produo da forma B a P, crie a transio (B,a) = A;


24/74


21

b) Para cada produo da forma B aC P, crie a transio (B,a) = C;c) Para produes da forma B , no criada nenhuma transio.d) Para todo a T, (A,a) = - (indefinida)

b) Para mostrar que L(M) = L(G), devemos mostrar que (1) L(G) L(M) e (2) L(M) L(G). Esta demonstrao fcil considerando-se as produes da GR e a definio das transies de

M, sendo omitida neste texto.Exemplo: Dada a GR abaixo, que gera as sentenas da linguagem {(anbm), com n par e m >

0}, iremos definir um AF que reconhea as sentenas desta linguagem.Gramtica: S ::= aA | bB | b

A ::= aSB ::= bB |

Autmato:Primeiramente devemos definir os estados do autmato, com um estado novo, denominado

aqui C. Assim, temos que K = {S, A, B, C). O alfabeto o mesmo, assim = (a, b), o estado inicial S, e F = {B, C}, pela definio acima. Na forma tabular o autmato fica o seguinte:

a b S A B, C

A S -* B - B* C - -

Na forma grfica o autmato fica o seguinte:

Teorema 3.3: Seja um AF M = (K, , , q0, F). Ento uma GR G = (N, T, P, S) | L(G) =L(M).

Prova:a - Mostra que G existe;b - Mostrar que L(G) = L(M).

a) Seja M = (K, , , q0, F) um AF. Construa uma G. R. G = (N, T, P, S) como segue:1 - N = K;2 - T = ;3 - S = q0;4 - Defina P como segue:4.a) Se (B,a) = C, ento adicione B ::= aC em P;4.b) Se (B,a) = C e C F, ento adicione B ::= a em P;4.c) Se q0 F, ento L(M). Assim a gramtica deve ser transformada encontrar

uma outra G.R. G1, tal que L(G1) = L(G) {}, e L(G1) = L(M). Seno L(M), e L(G) = L(M).

b) Para mostrar que L(G) = L(M), devemos mostrar que (1) L(M) L(G) e (2) L(G) L(M). Esta demonstrao anloga parte (b) da prova do teorema 5.1, sendo omitida neste texto.

Sincio

bb

ba

a

A

B

C


25/74


22

Exemplo: Tomemos o seguinte A. F.:

Na forma tabular:

a b

S A B* A S C

B C SC B A

A GR definida pelo algoritmo acima resulta em:S ::= aA | bB | aA ::= aS | bCB ::= aC | bSC ::= aB | bA | bPelo algoritmo acima, a GR gerada a partir de um AF nunca apresentar produes do tipo

A ::= .

4. Minimizao de Autmatos FinitosDefinio: Um A. F. D. M = (K, , , q0, F) MNIMO se:1 - No possui estados INACESSVEIS;2 - No possui estados MORTOS;3 - No possui estados EQUIVALENTES.

Estados Inacessveis:Um estado q K inacessvel quando no existe w tal que a partir de q0, q seja alcanado,

ou seja, ~ w | (q0, w) = q, onde w uma sentena ou parte dela.Estados Mortos:Um estado q K morto se ele F e ~ w | (q, w) = p, onde p F e w uma sentena ou

parte dela. Ou seja, q morto se ele no final e a partir dele nenhum estado final pode seralcanado.Estados Equivalentes:Um conjunto de estados q1, q2, ..., qj so equivalentes entre s, se eles pertencem a uma

mesma CLASSE DE EQUIVALNCIA.Classe de Equivalncia (CE):Um conjunto de estados q1, q2, ..., qj esto em uma mesma CE se (q1, a), (q2, a) ,...,

(qj, a), para cada a , resultam respectivamente nos estados qi, qi+1, ..., qn e estes pertencem auma mesma CE.

4.1. Algoritmo para Construo das Classes de Equivalncia

1.Se necessrio, crie um estado para representar as indefinies.2.Devida K em duas CE, uma contendo F e outra contendo K-F.

Sincio

A ba

ba

ab

ab B

C


26/74


23

3.Divida as CE existentes, formando novas CE (de acordo com a definio - lei deformao das CE), at que nenhuma nova CE seja formada.

4.2. Algoritmo para Construo do Autmato Finito Mnimo

Entrada: Um AFD M = (K, , , q0, F);

Sada: Um AFD Mnimo M = (K, , , q0, F) | M M;Mtodo:1 - Elimine os estados inacessveis.2 - Elimine os estados mortos.3 - Construa todas as possveis classes de equivalncia.4 - Construa M como segue:

a) K o conjunto de CE obtidas.b) q0 ser a CE que contiver q0.c) F ser o conjunto das CE que contenham pelo menos um elemento F;

isto , {[q] | p [q] e p F, onde [q] um CE}.d ) ([p], a) = [q] (p, a) = q uma transio de M e p e q so

elementos de [p] e [q], respectivamente.


27/74


24

Exemplo: Minimize o AFD definido na seguinte tabela de transies: a b

* A G BB F EC C G

* D A HE E AF B C

* G G FH H D

Temos que os estados acessveis so: {A, G, B, F, E, C}. Portanto podemos eliminar osestados D e H. Assim o novo AFD :

a b

* A G B

B F EC C GE E AF B C

* G G F

Nenhum dos estados do AFD acima morto. Assim, podemos construir as classes deequivalncia. No primeiro passo, duas classes de equivalncia so construdas: F e K-F. Cada passodo algoritmo representado numa linha da tabela abaixo:

F K-F

1 {A, G} {B, C, E, F}2 {A, G} {B, F} {C, E}3 {A, G} {B, F} {C, E}

A primeira linha da tabela a diviso dos estados em F e K-F. Para i > 1, a linha i formadapela separao das CEs da linha i-1, at que uma linha seja repetida.

Algoritmicamente, a separao das CEs pode ser dada por:SE houver mais de um estado na CE ENTO

Crie uma nova CE aberta na linha i+1 para o primeiro estado da CE;PARA todos os outros estados da CE FAA

Procure encaixar o estado numa CE aberta

SE no for possvel ENTOcrie uma nova CE aberta na linha i+1 para o estado;

FIMSEFIMPARAFeche todas as CEs abertas

SENORepita a CE na linha i+1

Na tabela acima, na linha 2, foi aberta uma classe para B, e a seguir os outros estados foramtestados. C no pde ficar na mesma classe de B (pois (B, b) = E e (C, b) = G, e E e G pertencem

CEs separadas na primeira linha. Assim, uma nova CE foi aberta para C. O estado E no pdeficar na CE de B, mas pde ficar na CE de C, assim no foi aberta uma nova CE para E. J o estado


28/74


25

F pde ficar na CE de B. Como no havia mais estados na CE da primeira linha, as duas CEs dasegunda linha foram fechadas.

A repetio do algoritmo para a criao da linha 3 fez com que a linha 2 se repetisse. Assim,todas as CEs foram determinadas.

Denominando {A, G} = q0, {B, F} = q1 e {C, E} = q2, temos o seguinte AFD Mnimo:

a b* q0 q0 q1

q1 q1 q2q2 q2 q0

5. Construo do Analisador LxicoNo processo de compilao, o Analisador Lxico responsvel pela identificao dos

tokens, ou seja, das menores unidades de informao repassadas para o Analisar Sinttico.Assim, pode-se dizer que o analisador lxico responsvel pela leitura dos caracteres da

entrada, agrupando-os em palavras, que so classificadas em categorias. Estas categorias podem ser,

basicamente, as seguintes:Palavras reservadas: palavras que devem aparecer literalmente na linguagem, semvariaes. Por exemplo, na linguagem PASCAL, algumas palavras reservadas so: BEGIN, END,IF, ELSE.

Identificadores: palavras que seguem algumas regras de escrita, porm podem assumirdiversos valores. So definidos de forma genrica. Por exemplo, identificadores que devem iniciarcom uma letra, seguida de letras ou dgitos. Pode-se representar estes identificadores pela seguinteexpresso regular: (a + b + ... + c)(a + b + .. + z + 0 + 1 + ... + 9)*

Smbolos especiais: seqncias de um ou mais smbolos que no podem aparecer emidentificadores nem palavras reservadas. So utilizados para composio de expresses aritmticasou lgicas, por exemplo. Exemplos de smbolos especiais so: ; (ponto-e-vrgula), : (dois

pontos), := (atribuio).Constantes: tambm denominadas literais, so valores que so inseridos diretamente noprograma, ao invs de serem uma referncia para um endereo de memria. Por exemplo, nmeros(904, 8695, -9, 12E-9), strings (Hello world), booleanos (TRUE, FALSE), etc.

Para a construo de um analisador lxico, so necessrios 4 passos:1 - definir as gramticas e autmatos finitos determinsticos mnimos para cada token;2 - juntar os autmatos num nico autmato e determinizar (no minimizar);3 - acrescentar um estado de erro, para tratar tokens invlidos;4 - implementar o autmato numa linguagem de programao.

A construo de uma analisador lxico demonstrada a seguir, com um exemplo:

Sejam os tokens desejados os seguintes:

PALAVRAS RESERVADAS: goto, do.

IDENTIFICADORES: comeam com uma letra, seguidas de letras e _. ExpressoRegular: (a + .. + z)(a +...+ z + _ )*

1o passo: definir as gramticas e autmatos para cada token.

Token GOTO:

S ::= gA

A::= oBB ::= tC

C ::= o

g t o S A - -


29/74


26

A - - BB - C -

C - - X* X - - -

Token DO:

S ::= dD

D ::= o

d o S D -

D - Y

* Y - -

Token Identificador:

S ::= aE | bE | ... | zE

E ::= aE | bE | ... | zE | _E |

a b ... z _ S E E E E -*E E E E E E

Note que os autmatos acima j foram minimizados, sendo que o estado novo do autmatode identificadores foi eliminado por ser inalcanvel.

2o passo: juntar os autmatos num s e determinizar:

Os autmatos acima sero agora colocados juntos num s autmato. Note que j foi tomadoo cuidado de somente o nome do estado inicial coincidir. Todos os outros estados tm nomesdiferentes. O autmato no-determinstico geral fica:

g t o d a b ... z _ S A, E E E D, E E E E E -

A - - B - - - - - -

B - C - - - - - - -C - - X - - - - - -D - - Y - - - - - -

* X - - - - - - - - -* Y - - - - - - - - -* E E E E E E E E E E

O autmato acima, determinizado (e no minimizado) fica:


30/74


27

g t o d a b ... z _ S [S] A E E D E E E E -

* A [A,E] E E B E E E E E E

* B [B, E] E C E E E E E E E* C [C, E] E E X E E E E E E* D [D, E] E E Y E E E E E E* X [X, E] E E E E E E E E E* Y [Y,E] E E E E E E E E E

* E [E] E E E E E E E E E

O autmato acima poderia ser minimizado, mas isto faria com que todos os estados finais sejuntassem num s. Isto faz com que informaes importantes sejam perdidas. Note que o estadofinal do token GOTO est no estado que contm o estado final X, e o estado final do token DO estno estado final que contm o estado final Y. Os estados que contm o estado final E so os quereconhecem os identificadores. Onde h conflito entre identificadores e palavras reservadas a

prioridade das palavras reservadas.

Assim, se um token terminar no estado X do autmato acima ele ser um GOTO, no estadoY ser um DO, e nos demais estados finais ser um Identificador.

3o passo: acrescentar o estado de erro:

Note que no autmato acima so definidas as transies somente para letras e o caracter _.Para os demais caracteres (que so invlidos na nossa linguagem) acrescentado um estado de erro.Este estado ser alcanado quando houver um caracter invlido, bem como para as transiesindefinidas para os caracteres vlidos. Este estado de erro ser um estado final, que reportar erro.O autmato acima ficar:

g t o d a b ... z _ etc. S A E E D E E E E F F* A E E B E E E E E E F* B E C E E E E E E E F* C E E X E E E E E E F* D E E Y E E E E E E F* X E E E E E E E E E F* Y E E E E E E E E E F

* E E E E E E E E E E F* F F F F F F F F F F F

(etc. denota os caracteres no vlidos da linguagem).

4o passo: implementao:

O autmato acima facilmente implementado numa estrutura de dados do tipo tabela. Ouseja, no reconhecimento de um novo token, parte-se do estado inicial, determinando-se o novoestado pela coluna correspondente ao caracter lido do arquivo. Repete-se este procedimento atachar um separador de token (espao em branco, quebra de linha ou final de arquivo).


31/74


28

Quando um separador de token encontrado, verifica-se qual o estado atual do autmato. Sefor um estado no-final, houve um erro, que deve ser acusado. Se for um estado final, verifica-se oque o estado representa, e retorna-se o valor desejado.

No autmato acima, se um separador de tokens encontrado, verifica-se o estado corrente.Cada estado representa um token ou erro, da seguinte forma:

S erro;

X token GOTO

Y token DO

F erro - caracter invlido

outro estado Identificador.

EXERCCIOS:1) Construa um A. F. D. para cada linguagem abaixo.

a) {w | w (0, 1)

+

e |w| > 3}.* b) {w | w (0, 1)+ e w comece com 0 e termine com 1}* c) {w | w (0, 1, 2) + e a quantidade de 1s em w seja mpar}.d) {w | w (a, b, c)* e w no possua letras iguais consecutivas}.e) {w | w um comentrio PASCAL no aninhado, na forma (*x*), e x (a, b, ..., z)*.f) {begin, end}. Caso ocorra outra entrada o autmato deve ir para um estado de erro e

continuar l.

2) Construa as G. R. dos autmatos abaixo. A seguir determinize-os e minimize-os. Construaa G. R. dos autmatos resultantes.

* a) a b

A A, B AB C -C - D

* D D D

b) a b c d

A B, C D C C

B - D C C* C - - - DD - B, C - -


32/74


29

c) a b c

* S A B, F S, FA S, F C AB A - B, S, FC S, F - A, C

* F - - -d)

0 1

A A, B AB C AC D A

* D D D

3) Construa os A. F. que reconhecem as linguagens geradas pelas seguintes G. R. Caso o A. F.

seja no-determinstico, determinize-o. Minimize todos os A. F.* a) S ::= 0S | 1S | 0A | 0C | 1B

A ::= 0A | 0C | 0B ::= 1B | 1C ::= 0C | 0A | 0

b) S ::= aA | aC | bB | bCA ::= aF | aB ::= bF | bC ::= aA | aC | bB | bCF ::= aF | bF | a | b

c) S ::= aA | bBA ::= aS | aC | aB ::= bS | bD | bC ::= aBD ::= bA

d) S ::= 0B | 1A | 1 | A ::= 0B | B ::= 0C | 0 | 1D

C ::= 0B | 1A | 1D ::= 1C | 1


33/74

IV - Linguagens Livres de Contexto

30


1. Linguagens Auto-EmbebidasA importncia das LLCs reside no fato de que praticamente todas as linguagens de

programao podem ser descritas por este formalismo, e que um conjunto bastante significativodestas linguagens pode ser analisado por algoritmos muito eficientes. A maioria das linguagens de

programao pertence a um subconjunto das LLCs que pode ser analisado por algoritmos queexecutam n.log(n) passos para cada smbolo da sentena de entrada. Outro subconjunto quecorresponde s linguagens no ambguas pode ser analisado em tempo n2. No pior caso, uma LLCambgua pode ser analisada em tempo n3. O que ainda bastante eficiente, se comparado slinguagens sensveis ao contexto, que podem requerer complexidade exponencial (2n), sendo,

portanto, computacionalmente intratveis, e s linguagens de tipo 0, que podem ser, inclusive,indecidveis, isto , o algoritmo de anlise pode no parar nunca.

2. Gramticas Livres de Contexto

Uma gramtica livre de contexto (GLC) denotada por G=(N,T,P,S), onde N e T soconjuntos disjuntos de variveis e terminais, respectivamente. P um conjunto finito de produes,cada uma da forma A ::= , onde A uma varivel do conjunto N e uma cadeia de smbolos(NT)*. Finalmente, S uma varivel especial denominada smbolo inicial.

3. rvore de DerivaoMuitas vezes til mostrar as derivaes de uma GLC atravs de rvores. Estas figuras,

chamadas rvores de derivao ou rvores sintticas, impe certas estruturas teis s sentenas daslinguagens geradas, principalmente as de programao.

Os vrtices de uma rvore de derivao so rotulados com terminais ou variveis, ou mesmo

com a cadeia vazia. Se um vrtice interior n rotulado com A, e os filhos de n so rotulados comX1, X2,...,Xk, da esquerda para a direita, ento A::= X1X2...Xkdeve ser uma produo da gramtica.Considere, como exemplo, a gramtica:

E ::= E + E| E * E| ( E )| id

Uma rvore de derivao para a sentena (id+id)*id gerada por esta gramtica poderia ser:

E

EE

E

E

E

idid

id

*

( )

+

Mais formalmente, seja G=(N,T,P,S) uma GLC. Ento uma rvore uma rvore de

derivao para G, se:a)cada vrtice tem um rtulo, que um smbolo de NT{};

b)o rtulo da raiz o smbolo S;c)os vrtices interiores so rotulados apenas com smbolos de N;


34/74


31

d)se o vrtice n tem rtulo A, e os vrtices n1, n2, ..., nkso flhos de n, da esquerda para adireita, com rtulos X1,X2,...,Xk, respectivamente, ento A ::= X1X2...Xkdeve ser uma

produo em P;e)se o vrtice n tem rtulo , ento n uma folha e o nico filho de seu pai.Exemplo:

Considere a gramtica G=({S,A},{a,b},P,S), onde P consiste de:

S ::= aAS | aA ::= SbA | SS | baA figura seguinte uma rvore de derivao para uma sentena desta gramtica, na

qual os nodos foram numerados para facilitar a explicao:

Os vrtices interiores so 1, 3, 4, 5 e7. O vrtice 1 tem o rtulo S, e seus filhos,da esquerda para a direita tm rtulos a, A e S.

Note que S ::= aAS uma produo. Da mesma forma, o vrtice 3 tem rtulo A, e os rtulos deseus filhos so S, b e A, da esquerda para a direita, sendo que A := SbA tambm uma produo.Os vrtices 4 e 5 tm ambos o rtulo S. O nico filho deles tem rtulo a, e S ::= a tambm uma

produo. Finalmente, o vrtice 7 tem rtulo A, e seus filhos, da esquerda para a direita, so b e a, eA ::= ba tambm produo. Assim, as condies para que esta rvore seja uma rvore dederivao para G foram cumpridas.

Pode-se estender a ordem da esquerda para a direita dos filhos para produzir uma ordemda esquerda para a direita de todas as folhas. No exemplo acima, o caminhamento da esquerda paraa direita nas folhas da rvore produziria a seguinte seqncia: 2, 9, 6, 10, 11 e 8.

Pode-se ver que a rvore de derivao uma descrio natural para a derivao de umaforma sentencial particular da gramtica G.

Uma sub-rvore de uma rvore de derivao composta por um vrtice particular da rvore,juntamente com seus descendentes.

4. Derivao mais Esquerda e mais Direita

Se cada passo na produo de uma derivao aplicado na varivel mais esquerda, ento aderivao chamada derivao mais esquerda, Similarmente, uma derivao onde a cada passo avarivel mais direita substituda, chamada de derivao mais direita.

Se w est em L(G), ento w tem ao menos uma rvore de derivao. Alm disso, em relaoa uma rvore de derivao particular, w tem uma nica derivao mais esquerda e uma nicaderivao mais direita.

Evidentemente, w pode ter vrias derivaes mais esquerda e vrias derivaes mais direita, j que pode haver mais de uma rvore de derivao para w. Entretanto, fcil mostrar que,

para cada rvore de derivao, apenas uma derivao mais esquerda e uma derivao mais direita podem ser obtidas.

Exemplo:

A derivao mais esquerda correspondente rvore do exemplo anterior :S aAS aSbAS aabAS aabbaS aabbaa

S1

A3a2 S4

b6 A7S5

a9 b10 a11

a8


35/74


32

A derivao mais direita correspondente :S aAS aAa aSbAa aSbbaa aabbaa

5. AmbigidadeSe uma gramtica G tem mais de uma rvore de derivao para uma mesma sentena, ento

G chamada de gramtica ambgua. Uma linguagem livre de contexto para a qual toda gramtica

livre de contexto ambgua denominada linguagem livre de contexto inerentemente ambgua.6. Simplificaes de Gramticas Livres de Contexto

Existem vrias maneiras de restringir as produes de uma gramtica livre de contexto semreduzir seu poder expressivo. Se L uma linguagem livre de contexto no-vazia, ento L pode sergerada por uma gramtica livre de contexto G com as seguintes propriedades:

a)Cada varivel e cada terminal de G aparecem na derivao de alguma palavra de L.b)No h produes da forma A ::= B, onde A e B so variveis.Alm disso, se L, ento no h necessidade de produes da forma A ::= .

6.1. Smbolos Inteis

Pode-se eliminar os smbolos inteis de uma gramtica sem prejudicar seu potencialexpressivo. Um smbolo X til se existe uma derivao S * X* w, para algum w, e ,onde w uma cadeia de T* e e so cadeias quaisquer de variveis e terminais. Caso contrrio, osmbolo X intil. Tanto terminais quanto no-terminais podem ser teis ou inteis. Se o smboloinicial for intil, ento a linguagem definida pela gramtica vazia.

H dois tipos de smbolos inteis: aqueles que no geram nenhuma cadeia de terminais eaqueles que jamais so gerados a partir de S. O primeiro caso corresponde aos smbolosimprodutivos (ou mortos), e o o segundo caso corresponde aos smbolos inalcanveis. Um terminalsempre produtivo, mas pode ser inalcanvel. J o no-terminal pode ser tanto improdutivo quantoinalcanvel, mas o smbolo inicial sempre alcanvel. A seguir sero vistos algoritmos para

eliminar tanto o primeiro quanto o segundo tipo de smbolos inteis.O algoritmo para eliminao dos smbolos improdutivos baseado na idia de que se umno-terminal A tem uma produo consistindo apenas de smbolos produtivos, ento o prprio A

produtivo.Algoritmo: Eliminao de Smbolos Improdutivos

Entrada: Uma GLC G=(N,T,P,S)Sada: Uma GLC G=(N,T,P,S), sem smbolos improdutivos.

SP := T {}Repita

Q := {X | X N e X SP e (existe pelo menos uma produo X ::= X1X2,...Xn tal que

X1SP, X2SP, ..., XnSP)};SP := SP Q;

At Q = ;N= SP N;Se S SP Ento

P:= {p | pP e todos os smbolos de p pertencem a SP}Seno L(G) = ;

P:= ;Fim SeFim.

No seguinte exemplo, para facilitar o acompanhamento do algoritmo, os smbolos doconjunto SP sero sublinhados a cada passo.


36/74


33

Seja G a seguinte gramtica:S ::= ASB | BSA | SS | aS | A ::= ABS | BB ::= BSSA | AInicialmente SP = {a}, e so marcadas as produes:S ::= aS

S ::= Uma vez que o lado direito da produo S ::= est completamente marcado, deve-se

marcar todas as ocorrncias de S. Como S o nico novo smbolo a ser marcado, entoQ := {S}. As marcaes resultam:

S ::= ASB | BSA | SS | aS | A ::= ABS | BB ::= BSSA | A

Neste momento SP = {a, S}. Agora Q := , e assim a repetio do algoritmo termina comSP = {a, S}, os nicos smbolos produtivos.

Para simplificar a gramtica, os smbolos improdutivos podem ser removidos, bem comotodas as produes de P que contenham estes smbolos. Assim, a gramtica simplificada para oexemplo seria:

S ::= SS | aS | O segundo tipo de smbolos inteis so aqueles que jamais so gerados a partir de S. Estes

smbolos, chamados de inalcanveis, so eliminados pelo seguinte algoritmo:


37/74


34

Algoritmo: Eliminao de Smbolos Inalcanveis

Entrada: Uma GLC G=(N,T,P,S)Sada: Uma GLC G=(N,T,P,S), sem smbolos inalcanveis.

SA := {S}

RepitaM := {X | X NT e X SA e existe uma produo Y ::= X e Y SA};SA := SA M;

At M = ;N= SA N;T= SA T;P:= {p | pP e todos os smbolos de p pertencem a SA};Fim.

Para exemplificar, seja G:

S ::= aS | SB | SS | A ::= ASB | cB ::= bInicialmente, SA = {S} e M = {S}. Assim, se obtm:S ::= aS | SB | SS | e a e B so os nicos smbolos recm marcados que no esto em SA. Assim, a M

atribudo o conjunto {a, B} e a SA atribudo {S, a, B}. Em seguida se obtm:B ::= b

e assim M passa a ser igual a {b} e SA igual a {S, a, B, b}. J que M no contm no-terminais, aex

Documents

unisul-apostila-formais-compiladores.pdf