Correlation of acoustic data and sediment cores

Este cap´ıtulo apresentou um conjunto de ferramentas dividido segundo dois enfoques n˜ao exclusivos entre si: um que prioriza o aspecto educativo e outro com maior ˆenfase na diminui¸c˜ao do tempo gasto na constru¸c˜ao de analisadores sint´aticos LALR pela utiliza¸c˜ao de ambientes integrados de desenvolvimento.

Do estudo realizado, conclui-se que embora o n´umero de ferramentas visuais re- lacionadas ao desenvolvimento e entendimento de analisadores LR/SLR/LALR seja consider´avel, existe pouca preocupa¸c˜ao por parte dessas ferramentas em prover meca- nismos para remo¸c˜ao de conflitos. Esta desconsidera¸c˜ao, no entanto, n˜ao ´e justificada, pois conforme argumentado, a ocorrˆencia de conflitos ´e extremamente recorrente e sua remo¸c˜ao ´e respons´avel por grande parte do tempo gasto na produ¸c˜ao de tais analisa- dores.

Para suprir esta necessidade, a ferramenta SAIDE enfoca a resolu¸c˜ao de conflitos, via suporte a uma metodologia que sistematiza o processo de remo¸c˜ao em um ambiente independente de linguagens de especifica¸c˜ao. As funcionalidades disponibilizadas por SAIDE incluem a exibi¸c˜ao modularizada e propriamente ligada dos elementos relaci- onados `a an´alise LALR (autˆomato caracter´ıstico, a gram´atica e os conflitos obtidos), visualiza¸c˜ao dos conflitos na forma de ´arvores de deriva¸c˜ao, apresenta¸c˜ao de exemplos cl´assicos de ambig¨uidade e suas poss´ıveis solu¸c˜oes de forma a permitir que o projetista adapte-as a seu contexto, resolu¸c˜ao autom´atica de uma subclasse de conflitos e lista- gem dos conflitos segundo uma ordena¸c˜ao de prioridade. A ferramenta disp˜oe ainda de gera¸c˜ao de analisadores sint´aticos LALR(k) cujas tabelas sint´aticas s˜ao compactadas de acordo com o perfil da aplica¸c˜ao alvo. Estas funcionalidades s˜ao explicadas em de- talhes no Cap´ıtulo 5 e comparadas `as oferecidas por Visual Parse++, ferramenta que mais se assemelha a SAIDE.

An´alise Sint´atica LALR(k)

Este cap´ıtulo apresenta o formalismo da an´alise sint´atica LALR(k) necess´ario `a poste- rior compreens˜ao dos algoritmos utilizados na ferramenta SAIDE. A partir da defini¸c˜ao dos conceitos iniciais e da terminologia adotada, apresenta-se as situa¸c˜oes que resul- tam em conflitos, o que permite classific´a-los. Em seguida discute-se a fronteira entre os conflitos que aparecem na obten¸c˜ao de analisadores LR(k) em rela¸c˜ao aos obtidos na constru¸c˜ao de analisadores LALR(k). No restante do cap´ıtulo, descreve-se o al- goritmo de DeRemer e Penello [DeRemer e Pennello, 1982] e o proposto por Charles [Charles, 1991] para cˆomputo de lookaheads de tamanho igual ou maior ou igual a 1 respectivamente, utilizados na gera¸c˜ao do autˆomato LALR.

As formula¸c˜oes e defini¸c˜oes apresentadas s˜ao baseadas naquelas utilizadas nos es- tudos feitos por [Aho et al., 1986], [Aho e Ullman, 1972], [Kristensen e Madsen, 1981], [DeRemer e Pennello, 1982] e [Charles, 1991].

3.1

Conceitos e Terminologia Adotada

Uma gram´atica livre de contexto ´e uma qu´adrupla G = (N, Σ, P, S), onde N ´e o conjunto finito de n˜ao terminais, Σ o conjunto finito de s´ımbolos terminais, P o conjunto finito de produ¸c˜oes e S o s´ımbolo de partida. O vocabul´ario V de G ´e V = N ∪ Σ. Presume-se que toda gram´atica esteja em sua forma estendida (N′_{, Σ}′_{, P}′_{, S}′_{), onde}

N′ _{= N ∪ {S}′_{}, Σ}′ _{= Σ ∪ {$}, P}′ _{= P ∪ {S}′ _{→ S$}, desde que S’ /∈ N e $ /∈ V .}

Letras gregas min´usculas, como α, β, γ, ..., denotam strings em V∗_{; letras romˆanicas}

do in´ıcio do alfabeto (a, b, c), d´ıgitos, s´ımbolos de opera¸c˜ao (+, -, *, /, etc.), strings em negrito (id, if, etc.) ou contidos entre aspas duplas indicam s´ımbolos em Σ; letras min´usculas do final do alfabeto (x, y, z) representam s´ımbolos em Σ∗_{; letras mai´usculas}

do in´ıcio do alfabeto (A, B, C) e strings escritos em caixa baixa em it´alico, como expr e stmt, representam s´ımbolos em N ; letras mai´usculas do final do alfabeto (X, Y, Z)

denotam elementos em V . O string vazio ´e dado por λ, o comprimento de um string γ por |γ| e Ω representa a constante de indefini¸c˜ao.

Defini¸c˜ao 1. F IRSTk(α) = {x | (α ∗ ⇒ lm xβ e |x| = k) ou (α ∗ ⇒ x e |x| < k)}

Dada uma gram´atica livre de contexto, F IRSTk(α) consiste em todos os prefixos

de terminais de tamanho menor ou igual a k deriv´aveis a partir de α.

Defini¸c˜ao 2. Seja G uma gram´atica livre de contexto. O autˆomato LR(k) referente a G ´e uma sˆextupla LRAk = (Mk, V, P, IS, GOT Ok, REDk), onde Mk ´e um conjunto finito

de estados, V e P s˜ao como em G, IS ´e o estado inicial, GOT Ok : Mk× V∗ → Mk

´e a fun¸c˜ao de transi¸c˜ao e REDk : Mk × Σ∗k → P(P ) ´e a fun¸c˜ao de redu¸c˜ao, com

Σ∗k = {w | w ∈ Σ∗ ∧ 0 ≤ |w| ≤ k}.

Defini¸c˜ao 3. Um estado em Mk´e composto por itens LR(k). Esses itens s˜ao elementos

em N × V∗_{× V}∗_{× P(Σ}∗

k) e s˜ao escritos de duas formas:

a) (A → α • β, {w1, w2, ..., wn}), onde w1, w2, ..., wn s˜ao strings de lookaheads. Esta

forma ´e usada no caso de k ≥ 1; b) A → α • β, caso contr´ario.

O primeiro componente de um item LR(k) ´e denominado n´ucleo.

Defini¸c˜ao 4. Seja K um conjunto de itens LR(k). O fechamento de K, definido pela fun¸c˜ao CLOSURE, ´e dado por:

CLOSU RE(K) = K ∪ {(A → •ω, {x1, x2, ..., xn}) | (B → α • Aβ, {w1, w2, ..., wn}) ∈ K

∧ A → ω ∈ P

∧ x1 = F IRSTk(βw1),

∧ x2 = F IRSTk(βw2),

...

∧ xn= F IRSTk(βwn)}

Defini¸c˜ao 5. A fun¸c˜ao GOT Ok ´e definida pelas equa¸c˜oes:

GOT Ok(p, λ) = p

GOT Ok(p, X) = F−1(CLOSURE(ADVANCE(p, X))

onde ADVANCE(p, X) ´e dado por ADVANCE(p, X) = {(A → αX • Y β, {x1, x2, ..., xn}) | (A → α • XY β, {w1, w2, ..., wn}) ∈ p ∧ w1 = FIRSTk(βx1), ∧ w2 = FIRSTk(βx2), ... ∧ wn = FIRSTk(βxn)} ∪

{(A → αX•, lookaheads) | (A → α • X, lookaheads) ∈ p} e F ´e uma fun¸c˜ao bijetora que mapeia um estado no respectivo conjunto de itens, exclu´ıdo o conjunto vazio.

Defini¸c˜ao 6.

P RED(q, α) = {p | GOT Ok(p, α) = q}

Considerando α = X1X2...Xn, P RED retorna os estados predecessores de q con-

tanto que GOT Ok(...(GOT Ok(p, X1), X2), ...), Xn) seja definido. No caso de n = 0,

P RED(q, λ) = {q}.

Defini¸c˜ao 7. O autˆomato LRA0 ´e composto pelos seguintes componentes:

M0 = {F−1(CLOSURE({S′ → •S$}))}∪

{F−1_{(CLOSURE(F (q))) | q ∈ SU CC(p) ∧ p ∈ M} 0}

A fun¸c˜ao SUCC ´e definida por

SU CC(p) = {F−1(ADV AN CE(p, X)) | X ∈ V }

O estado inicial IS ´e dado por IS = F−1_{(CLOSU RE({S}′ _{→ •S$})) e ∀w ∈ Σ}∗ _e

X ∈ V , tem-se:

REDk(q, w) = {A → γ | A → γ• ∈ F (q)}

Observe que a fun¸c˜ao de redu¸c˜ao ´e definida independentemente de w, o que est´a em concordˆancia com o valor de k = 0. A fun¸c˜ao F garante uma correspondˆencia um para um entre estados e conjunto de itens. Para facilitar a leitura, todas as ocorrˆencias de F e F−1 _{ser˜ao omitidas e a distin¸c˜ao entre um estado e seu conjunto de itens dar-se-´a}

pelo contexto em que s˜ao utilizadas.

Defini¸c˜ao 8. O autˆomato de um analisador LALR(k) ´e uma sˆextupla: LALRAk= (M0, V, P, IS, GOT O0, REDk)

onde M0, IS, GOT O0 s˜ao como em LRA0 e V e P como em G. A fun¸c˜ao de redu¸c˜ao

´e dada por

REDk(q, w) = {A → γ | w ∈ LAk(q, A → γ•)}

onde LAk ´e definida pelo seguinte teorema:

Teorema 1.

LAk(q, A → γ) = {w ∈ F IRSTk(z) | S ∗

⇒

rm αAz ∧ αγ access q}

Diz-se que uma forma sentencial ξ access q quando P RED(q, ξ) 6= ∅. A prova deste teorema ´e fornecida por DeRemer e Pennello em [DeRemer e Pennello, 1982].