Professora Isabel Harb Manssour Paradigmas de Linguagens I 1

1.5.4.2. Estruturas de Controle: Nvel de Unidades de Programao

As estruturas de controle no nvel de unidades de programao so mecanismos de linguagens utilizadospara especificar o fluxo de controle entre unidades de um programa. O mecanismo mais simples o bloco, que criaum novo escopo de definio de objetos, sendo ativado e executado quando encontrado durante o processo deexecuo seqencial do programa. Mecanismos mais poderosos permitem ao programador transferir o controle deuma unidade para outra, atravs de uma chamada explcita a nova unidade.

Na maioria dos casos, a unidade chamada est subordinada que a chamou, ou seja, aps sua execuo aunidade chamada retorna o controle a unidade que a chamou. Este o caso de subprogramas, onde o retorno feitoatravs de uma operao do tipo return. No caso de linguagens que possuam facilidades de tratamento de excees,a transferncia de controle implcita. A execuo de uma unidade pode provocar uma exceo no processamentoe implicitamente o controle passado a um tratador de exceo associado quele tipo de exceo (seo 1.6).

As unidades de um programa podem ser organizadas em um esquema simtrico, atravs de um conjunto deco-rotinas, onde as unidades passam explicitamente o controle de uma para outra. Finalmente, as unidades tambmpodem ser organizadas como um conjunto de unidades concorrentes, ou processos. Neste caso, no existe a noode passagem de controle de uma unidade para outra, ou seja, as unidades so consideradas autnomas, sendoexecutadas assincronamente (seo 4.2) [SIL 88]. Como tratamento de excees e programao concorrente sodiscutidos em outras sees, agora sero descritos os mecanismos de subprogramas e blocos, e co-rotinas.

1) Subprogramas e Blocos

As linguagens de programao fornecem meios para agrupar instrues implementando uma abstrao deao em uma unidade de programa apropriada. O exemplo mais comum e til o subprograma, presente desde aformulao das primeiras linguagens de montagem. A abstrao representada pelos subprogramas corresponde aomapeamento de um conjunto de entradas num conjunto de sadas que pode ser descrito por uma especificao. Talespecificao define como as sadas se relacionam com as entradas, porm, no necessrio revelar a maneiracomo as sadas so processadas. Um subprograma uma abstrao porque permite a seus usurios concentrarem-seno que feito e no no como implementado. Essa classe cobre desde as sub-rotinas e funes do Fortran, at osprocedimentos de Ada [GHE 87, SIL 88].

Ento, um subprograma consiste num mecanismo de decomposio de programa que permite que osprogramas sejam divididos em vrias unidades. Chamadas de subprogramas so estruturas de controle quegovernam o fluxo de controle entre estas unidades. As relaes entre subprogramas definidas atravs de chamadasso assimtricas: a unidade que invoca outra unidade transfere o controle para a unidade chamada, a qual, apscompletar sua tarefa, devolve o controle ao ponto de chamada [GHE 97, SIL 88].

A maioria das LP fazem distino entre dois tipos de rotinas (ou subprogramas): procedimentos e funes.Um procedimento no retorna um valor; ele um comando abstrato que chamado para fazer alguma troca deestado desejada. O estado pode mudar porque os valores de alguns parmetros transmitidos ao procedimentosofrem modificaes, pois algumas variveis no locais so atualizadas pelo procedimento e algumas aes sodesempenhadas no ambiente externo (exemplo: leitura ou escrita). Numa funo, em contraposio, supe-se queum valor, que depende do valor dos parmetros, deve ser retornado. Pascal, assim como Ada, fornece tantoprocedimentos como funes. J em C todos os subprogramas so funes, isto , retornam algum valor, a menosque o tipo retornado seja void, que identifica explicitamente que nenhum valor retornado [GHE 97].

Um subprograma caracterizado por quatro elementos: seu nome, uma lista de parmetros, um corpo e umambiente. Um subprograma normalmente definido por uma palavra chave que informa ao compilador tratar-se deum subprograma, seguido do seu nome, da definio de uma lista de identificadores (parmetros formais) e doseu corpo. Os identificadores contidos na lista no so variveis, mas meramente nomes, que definem o papel queser exercido pelos parmetros reais passados quando o subprograma for chamado. Normalmente, existe umacorrespondncia posicional (baseada na ordem em que aparecem na lista) entre os parmetros reais e formais.Entretanto, algumas linguagens permitem, alm do esquema posicional, associar os parmetros reais aos formaisatravs dos seus nomes.

Professora Isabel Harb Manssour Paradigmas de Linguagens I 2

A especificao dos parmetros de um subprograma contm, normalmente, alm do nome dos parmetrosformais, seu tipo e a maneira como eles sero utilizados em tempo de execuo, que corresponde a passagem deparmetros. Passagem de parmetros utilizada para comunicao de objetos entre unidades de programas.Distintamente de comunicao entre unidades via ambiente global, parmetros permitem a transferncia de objetosdiferentes a cada chamada e constituem um meio mais adequado, considerando os aspectos de legibilidade dosprogramas e de manuteno. Duas classes de objetos podem ser repassados como parmetros: dados esubprogramas [SIL 88].

Existem trs convenes distintas para passagem de dados como parmetros a um subprograma:

Por referncia: a unidade que chamou passa unidade chamada o endereo do parmetro real. Uma refernciaao parmetro, na unidade chamada, tratada como uma referncia posio cujo endereo passado. Portanto,uma varivel passada por referncia pode ser modificada diretamente pelo subprograma chamado.

Por cpia: feita uma cpia do valor do parmetro real para o parmetro formal. Assim, os parmetros formaisno compartilham memria com os parmetros reais; em vez disso, eles agem como uma varivel local. Apassagem por cpia tem a vantagem de proteger os parmetros reais de modificaes inadvertidas (efeitoscolaterais). Existem trs maneiras de passar parmetros por cpia: por valor, por resultado e por valor-resultado. (1) Na passagem por valor, os valores dos parmetros reais so utilizados para inicializar osparmetros formais correspondentes, que agem como variveis locais na unidade chamada. No permitidoretorno de informaes unidade que chamou atravs dos parmetros. (2) Na passagem por resultado, osvalores dos parmetros formais so copiados para os parmetros reais no trmino de execuo da unidadechamada. No permite o fluxo de informaes da unidade que chamou para a chamada. (3) A passagem porvalor-resultado compreende a fuso das duas anteriores, ou seja, os parmetros formais so variveis locais queso inicializadas com os valores dos parmetros reais no momento da chamada (como na passagem por valor)e, no trmino da unidade chamada, os valores finais dos parmetros formais so copiados para os parmetrosreais (como passagem de resultado).

Por nome: como na passagem de referncia, um parmetro denota uma posio no ambiente da unidade quechamou, no sendo uma varivel local; entretanto a amarrao entre os parmetros formais e reais no feitana inicializao da unidade que chamou, mas toda vez que o parmetro formal usado. Como conseqncia,cada utilizao de um parmetro formal pode referenciar uma localizao diferente. Com essas caractersticaspode-se observar que se os parmetros reais forem variveis escalares, a chamada por nome ser equivalente chamada por referncia. Se o parmetro real for uma expresso, a expresso ser avaliada cada vez que oparmetro formal for utilizado, podendo produzir valores diferentes a cada vez (basta que existam variveis naexpresso, cujos valores tenham sido modificados entre as duas avaliaes).

A passagem de subprogramas como parmetros til em muitas situaes prticas. Por exemplo, se alinguagem no proporciona mecanismos explcitos para o tratamento de excees, um subprograma tratador deexcees pode ser transmitido como parmetro unidade que pode acusar a exceo. Entretanto, embora til,subprogramas como parmetros podem facilmente levar criao de programas obscuros, com pouca legibilidade.

Transmitir um subprograma como um parmetro requer no mnimo a passagem de uma referncia aosegmento de cdigo do argumento. Entretanto, o subprograma passado como parmetro pode, por sua vez, acessarvariveis no locais, sendo portanto necessrio passar informaes sobre o ambiente no local do argumento.

Em linguagens do gnero Algol, onde os registros de ativao so organizados em pilha, um parmetro dotipo subprograma representado pelo par (pc, pa), onde pc um ponteiro para o segmento de cdigo e pa um ponteiro para o registro de ativao da unidade onde esse subprograma foi definido. Quando for feita umachamada para o subprograma parmetro, o seu registro de ativao instalado no topo da pilha, o link estticoassume o valor de pa e o controle de execuo passado ao cdigo especificado por pc. O prximo exemploem Pascal ilustra a passagem de um subprograma como parmetro [GHE 87, SIL 88]:

Professora Isabel Harb Manssour Paradigmas de Linguagens I 3

procedure principal ... procedure a ... ... end a; procedure b (procedure x); var y: integer;

procedure c ... ... y := ...; ... end c; x; b(c); ... end b; ... b(a); ...end principal;

2) Co-Rotinas

Subprogramas no podem descrever unidades de programas que executam de maneira intercalada. Porexemplo, a simulao de um jogo de cartas com quatro jogadores no pode ser feita utilizando-se quatro sub-rotinas, uma para cada jogador, porque as sub-rotinas normalmente no guardam a histria de sua execuo eexecutam do seu incio at o fim, antes de retornar unidade que as chamou.

Assim, vrias LP implementam o conceito de co-rotinas para atender tais necessidades. Distintamente desubprogramas, co-rotinas so unidades simtricas que explicitamente ativam outra unidade; elas no retornam, mas,em vez disso, passam o controle para outra unidade atravs de um comando do tipo resume. Quando uma co-rotinarecebe o controle de outra unidade, ela normalmente s executa parcialmente. A sua execuo suspensa quandoela passa o controle para outra unidade e em um instante mais tarde sua execuo pode ser reassumida, continuandonormalmente a partir do ponto em que foi suspensa.

O modelo de execuo utilizando uma pilha para armazenar os registros de ativao das unidades inadequado para suportar o conceito de co-rotinas. Quando uma co-rotina A envia o comando resume para umaco-rotina B, o seu registro de ativao no pode ser desativado e, alm disso, deve ser salvo o ponteiro para ainstruo, aps o comando resume, de onde essa co-rotina prosseguir, quando o controle lhe for devolvido.

Cada co-rotina pode, por sua vez, chamar subprogramas; consequentemente, cada co-rotina precisa de umapilha de registros de ativao, capaz de crescer e diminuir durante a sua execuo, independentemente das pilhasdas outras co-rotinas. Dessa forma, a criao de uma nova co-rotina corresponde criao de uma nova pilha deexecuo. O modelo de execuo pode ser visto como uma rvore de pilhas, onde a pilha do programa principal araiz da rvore e as pilhas das co-rotinas so seus filhos.

1.5.5. Gramticas Livres de Contexto

Como j comentado anteriormente, a sintaxe de uma linguagem descrita atravs de uma gramtica, queconsiste num conjunto de regras que definem todas as construes bsicas que podem ser aceitas numa linguagem.Os elementos bsicos de uma gramtica so;

Professora Isabel Harb Manssour Paradigmas de Linguagens I 4

1. Conjunto de smbolos terminais: so os smbolos atmicos (no divisveis) que podem ser combinados paraformar construes vlidas na linguagem. Smbolos terminais so geralmente um conjunto de caracteresatravs dos quais algumas linguagens podem considerar strings como smbolos.

2. Conjunto de smbolos no terminais: estes smbolos no esto includos na linguagem propriamente dita, masso smbolos usados para representar definies intermedirias dentro da linguagem, definidas comoprodues. Os smbolos no terminais representam classes ou categorias sintticas.

3. Conjunto de produes: consistem na definio de um smbolo no terminal. Possuem a forma x ::= y, ondex um smbolo no terminal e y uma seqncia de smbolos que podem ser terminais ou no terminais.

4. Smbolo inicial: corresponde a um dos smbolos no terminais.

Duas regras devem ser obedecidas para estes elementos bsicos formarem uma gramtica: (1) cada smbolono terminal deve aparecer no lado esquerdo de ::= em pelo menos uma produo; (2) o smbolo inicial no deveaparecer no lado direito de ::= em nenhuma produo [DER 90].

Para ilustrar o conceito de gramtica, a seguir apresentada a construo de uma gramtica simples paradescrever a linguagem de uma calculadora (j descrita em BNF na seo 1.5.1).

Smbolos Terminais: 0 1 2 3 4 5 6 7 8 9 + - * / = .Smbolos No Terminais: Smbolo Inicial: Produes:1. ::= =2. ::= 3. ::= 4. ::= 5. ::= 6. ::= 7. ::= . 8. ::= 9. ::= 10. ::= 011. ::= 112. ::= 213. ::= 314. ::= 415. ::= 516. ::= 617. ::= 718. ::= 819. ::= 920. ::= +21. ::= -22. ::= +23. ::= -24. ::= *25. ::= /

Pode-se observar que esta gramtica tem 16 smbolos terminais e 8 no terminais. Tambm observa-se quecada no terminal, com exceo do smbolo inicial, definido por mltiplas produes. Apesar de que mltiplasprodues no so requeridas, elas so comuns e representam definies alternadas. Produes recursivas, isto ,produes onde o no terminal que est sendo definido encontrado na sua prpria definio no lado direito daproduo, so permitidas. Existem duas maneiras de se usar uma gramtica como a apresentada. A primeira

Professora Isabel Harb Manssour Paradigmas de Linguagens I 5

consiste em gerar programas vlidos na linguagem. Neste caso, comea-se pelo smbolo inicial e em cada passosubstitui-se alguma definio por um no terminal, prosseguindo-se at que todos os smbolos restantes sejamsmbolos terminais e gerando-se, assim, um programa vlido. A seqncia abaixo ilustra estes procedimentos.

String Corrente Produo Aplicada

= = = = =2 =2 =25 =25* =25* =25* =25* . =25* . =25*1. =25*1. =25*1.5=

134691281524247811815

A segunda maneira na qual uma gramtica pode ser usada na reduo de um programa vlido para osmbolo inicial atravs da aplicao reversa de produes. Isto permite verificar que um string de smbolosterminais de fato um programa na linguagem definida pela gramtica. Esta derivao somente possvel se feita uma escolha prudente da seqncia de produes a serem aplicadas, como mostra o exemplo da figura 1.7.

Como j comentado na seo 1.5.1, as gramticas que podem ser descritas atravs de BNF ou EBNF soconhecidas como gramticas livres de contexto. Isto significa que as definies vlidas dos smbolos no terminaisso independentes do contexto onde o smbolo encontrado. A maioria das LP no podem ser completamenteespecificadas por uma gramtica livre de contexto porque elas contm algumas regras que so sensveis aocontexto, o que significa que suas definies no terminais dependem do contexto. Por exemplo, a requisiocomum de que uma varivel deve ser declarada antes do seu uso no pode ser expressa em uma gramtica livre decontexto, desde que a validade de uma varivel depende se sua declarao est no contexto do seu uso ou no.Apesar de existirem ferramentas formais para expressar gramticas sensveis ao contexto, estas so muito maiscomplexas do que as livres de contexto e geralmente no so usadas para na especificao de linguagens. Aabordagem comum consiste em especificar formalmente a parte livre de contexto da sintaxe de uma linguagemusando BNF ou uma ferramenta similar, e especificar informalmente a parte sensvel ao contexto.

Figura 1.7 Verificao que a expresso 6+3/12 um calculo [DER 90]

calculatio

6|

digit|

unsigned|

+|

operato

3|

digit|

unsigned|

/|

operato

1|

digit

2|

digit|

=

unsigned|

number|

value|

expressio

expressio

Professora Isabel Harb Manssour Paradigmas de Linguagens I 6

Outro problema na especificao formal a ambigidade. A ambigidade ocorre quando h mais de rvorede derivao associada com um string vlido da linguagem. Para ilustrar, considera-se a gramtica anteriormodificada para trocar a produo expression por: ::= | O resultado uma gramtica ambgua, como demonstrado na figura 1.8, onde h duas rvores de derivao vlidaspara o string 4+2*3.

Figura 1.8 Duas derivaes para o string 4+2*3 [DER 90]

Se a gramtica est sendo usada somente para determinar quando o string vlido ou no, estaambigidade no causa problemas, desde que qualquer derivao suficiente para este objetivo. Freqentemente,entretanto, uma gramtica usada para interpretar o significado de um string. Neste caso, as duas derivaesdiferentes possveis tm significados diferentes no sentido que elas significam que os dois operadores so aplicadosem direes opostas quando o comando executado. Assim, a aplicao da rvore da direita representa um clculocujo resultado 18, enquanto a rvore da esquerda representa um clculo cujo resultado 10.

Sendo assim, sempre que possvel deve-se eliminar a ambigidade. Como no h uma tcnica genrica paraeliminar a ambigidade, cada situao deve ser cuidadosamente analisada. Algumas linguagens, entretanto, nopodem ser representadas atravs de uma gramtica no ambgua, e tentativas de encontrar tais representao soimprodutivas. Tais linguagens so chamadas de linguagens ambguas.

calculation

4|

digit|

unsigned|

value|

expression

+|

operator

2|

digit|

unsigned|

value|

expression

*|

operator

3|

digit|

unsigned|

value|

expression

=

expression

expression

calculation

4|

digit|

unsigned|

value|

expression

+|

operator

2|

digit|

unsigned|

value|

expression

*|

operator

3|

digit|

unsigned|

value|

expression

=

expression

expression