Anais do 5º Encontro do Celsul, Curitiba-PR, 2003 (840-849)
ANALISADOR GRAMATICAL EM PROLOG PARA GRAMÁTICAS CATEGORIAIS
Luiz Arthur PAGANI (Universidade Federal do Paraná)
[email protected]
ABSTRACT: A categorial-grammar parser for AB-model will be presented here. Since the parsing result
is formatted in the so called Prawitz style, the algorithm for dealing it will also be explained.
KEYWORDS: categorial grammar; shift-reduce parser; Prolog
Introdução
Apesar de não desfrutar da grande difusão da gramática gerativa, principalmente entre os
pesquisadores brasileiros, nem mesmo do prestígio secundário de alguns métodos alternativos para a
análise gramatical, como a LFG (Lexical Functional Grammar; Bresnan (ed.) 1982), a GPSG
(Generalized Phrase Structure Grammar; Gazdar, Klein, Pullum & Sag 1985), a HPSG (Head-Driven
Phrase Structure Grammar; Pollard & Sag 1994) e até a também pouco conhecida gramática de
dependência (Tesnière 1959), a gramática categorial talvez seja uma das melhores opções para a
formalização de gramáticas. Ela pode ser encontrada, por exemplo, na base do componente sintático da
gramática de Montague, e ainda influenciou consideravelmente a GPSG1 e a HPSG, ainda que nem
sempre isso seja explicitamente reconhecido.
Um dos principais interesses da gramática categorial para a Lingüística é o da avaliação do que se
poderia chamar de ontologia categorial: quais são as categorias elementares necessárias para a descrição
lingüística e quais categorias podem ser definidas a partir da relação que elas estabelecem com aquelas?
Outro aspecto interessante da gramática categorial é o de permitir um relacionamento direto entre a
estrutura sintática e sua interpretação semântica (nos casos mais extremos, poderíamos achar que há um
isomorfismo entre os dois níveis; no entanto, a postura mais comum, adotada pelo próprio Montague, é o
de reconhecer uma relação homomórfica entre a estrutura sintática e sua interpretação semântica).2
Devido a estas características formais, que geralmente também interessam à lingüística
computacional, vamos apresentar aqui uma proposta para a implementação em Prolog de um analisador
gramatical empregando as regras da gramática categorial pura, também chamada de modelo AB, em
homenagem a Ajduciewicz e a Bar-Hillel. Para nos concentrarmos mais na implementação, apesar de sua
pequena difusão, não será possível oferecer uma apresentação mais detalhada da gramática categorial;
para isso, o leitor interessado é indicado a consultar o livro de Wood (1993) e a introdução (infelizmente
ainda inédita) de Borges Neto (1999). (Há uma proposta de implementação em Prolog da gramática
categorial em Moortgat (1988). Concebido na linha da análise gramatical como dedução, Moortgat
desenvolveu um provador de teoremas para a gramática categorial; ao invés de focar aspectos lógicos, a
implementação proposta3 aqui envolverá, ao contrário, a elaboração de uma apresentação ao estilo de
Prawitz (1965) que não aparece na implementação de Moortgat.) Apesar de ainda inédito, como a
1
O tratamento das elipses (gaps) na GPSG emprega inclusive a notação de barras da gramática
categorial, ainda que suas funções sejam um pouco diferentes.
2
O isomorfismo pode ser entendido de duas maneiras: ou que as duas estruturas são construídas
seguindo exatamente os mesmos princípios (como, por exemplo, quando se exige que para cada regra
sintática deve haver uma única regra semântica correspondente e vice-versa), ou que as duas estruturas
são exatamente iguais (ou seja, que elas não são duas estruturas diferentes, e sim uma única). O
homomorfismo está relacionado ao reconhecimento de que algumas estruturas sintáticas podem ser
interpretadas de mais de uma maneira, e que uma mesma informação semântica pode ser expressa por
mais de uma estrutura sintática.
3
Para o desenvolvimento desse analisador gramatical, foi empregado o interpretador SWIProlog, em sua versão 4.0.11 (esse interpretador é gratuito e pode ser obtido em
http://www.swi.psy.uva.nl/projects/SWI-Prolog/). Além disso, o analisador foi testado no interpretador
Arity/Prolog32 , em sua versão 1.1.101 (também gratuito em http://www.arity.com/Prolog/); como os
funtores nesse interpretador são sempre separados de seus argumentos por espaços, as cláusulas da
definição de ‘tamanho/2’ precisam ter a soma aumentada em mais duas unidades em todos os casos nos
quais estiver envolvido uma categoria complexa (ou seja, em todas menos na primeira cláusula).
Luiz Arthur PAGANI
841
introdução de Borges Neto já teve alguma divulgação no Brasil, as regras serão empregadas aqui da
forma como ele as apresentou.
Analisador gramatical por deslocamento e redução
O analisador gramatical para a gramática categorial a ser proposto aqui foi adaptado da
implementação em Prolog do analisador gramatical por deslocamento e redução (shift-reduce parser),
desenvolvido por Covington (1994: 159), a partir da idéia original de Pereira (1985).
Para começarmos a comentar como a análise será feita, é preciso lembrar que uma das principais
estruturas de dados operadas em Prolog é a lista; assim, as expressões serão consideradas como se fossem
listas de expressões elementares. Uma lista é apenas uma pilha (stack): uma estrutura de armazenamento
na qual as operações de retirada ou colocação de elementos só podem ocorrer pela mesma posição; 4 em
termos mais formais, uma lista vazia é uma lista, e qualquer coisa da qual retiremos o seu primeiro
elemento e ainda continuarmos com uma lista também é uma lista. Em Prolog, as listas são representadas
por elementos separados por vírgulas, dentro de colchetes; a lista vazia é representada apenas pelos
colchetes “[]”; um exemplo de uma lista não-vazia é “[a, b, c]” pois, se retirarmos o seu primeiro
elemento “a”, ainda continuaremos com uma lista “[b, c]” (para constarmos indutivamente que “[a, b, c]”
é mesmo uma lista, ainda precisamos retirar o primeiro elemento “b” dessa nova lista “[b, c]”, restando
apenas uma lista com um único elemento “[c]”, que ainda precisa ser retirado para restar somente a lista
vazia “[]” que, segundo a cláusula de base da definição, é uma lista). Essa definição indutiva de lista é
replicada em Prolog pelo Programa 1, abaixo.
lista([]).
lista([_ | Lista]) :- lista(Lista).
Programa 1 – Definição de lista
Nesse programa, ainda foi empregado um outro recurso notacional das listas: o seu primeiro
elemento é separado do resto da lista através da barra vertical “|”; além disso, o traço horizontal inferior
“_” (slash) é a chamada variável anônima, usada quando entre as variáveis não há ligações a serem
representadas. Esse programa executa exatamente o procedimento descrito acima, removendo o primeiro
elemento da lista, até chegar à lista vazia.
Através das listas, uma sentença com “Pedro ama Maria” será representada no analisador como
“[pedro, ama, maria]” (como as letras maiúsculas em Prolog servem para nomear as variáveis, é costume
ainda representar as expressões básicas sempre em minúsculas). Como existem diversas versões de
programas que convertem as expressões em seu formato regular para esse formato de lista (conhecidos
como tokenizers), que podem ser encontrados facilmente em qualquer manual de introdução ao Prolog,
nenhum deles será apresentado aqui.5 Agora podemos passar para a apresentação do analisador proposto.6
A análise é conduzida pelo predicado de três lugares ‘conexo’ (abreviadamente representado como
‘conexo/3’). Na implementação, dispomos também do predicado ‘conexo/1’ que permite que se inicie a
análise digitando-se menos coisa do que sua versão de três lugares; o que essa versão de apenas um
argumento faz é tomar esse único argumento e invocar a versão de três argumentos colocando-o na
primeira posição argumental, garantindo que a pilha esteja vazia. Na primeira cláusula de sua definição,
depois de construída a análise gramatical através do predicado ‘conexo/3’, o predicado ‘conexo/1’ invoca
o predicado ‘prawitz/3’, que faz a apresentação ao estilo de Prawitz (esse estilo será explicado na seção
Derivação ao estilo de Prawitz, a partir da página 843; sua implementação em Prolog será explicada na
seção
Desenhando a derivação ao estilo de Prawitz, na página 844; o predicado pré-defindo ‘write/1’,
invocado pela segunda cláusula da definição de ‘conexo/1’, é pré-definido e apenas apresenta na saída
designada o conteúdo do seu argumento.) A função desse predicado em relação à gramática categorial é a
de replicar a noção de conexidade sintática, tal como ela foi proposta por Ajdukiewicz (Borges Neto
1999: 19). Nas palavras de Wood (1993: 23), “dentro de uma cadeia bem-formada, uma sub-cadeia é
‘conexa’, ou seja, é um constituinte, em relação a uma derivação em particular, se em algum ponto dessa
derivação ela puder ser rotulada por uma única categoria”. Recorrendo a diagramas em árvores, aos quais
os lingüistas estão mais acostumados, uma expressão seria conexa se ela pudesse ser analisada por uma
4 Nesse sentido, a pilha se opõe à fila (queue), na qual a retirada e a colocação só podem ocorrer em posições opostas.
5
No apêndice do livro do Covington (1994: 318-320), há um desses tokenizers (que parece ter sido inspirado no de
Clocksin & Mellish 1981, ainda que isso não seja admitido explicitamente). Outro tokenizer bem mais simples pode ser encontrado
em Pereira & Shieber (1987:155-156).
6
Daqui por diante, as definições dos predicados mencionados nas explicações podem ser encontradas no A.
842
ANALISADOR GRAMATICAL EM PROLOG PARA GRAMÁTICAS CATEGORIAIS
árvore com uma única raiz;7 ou ainda, que a análise da expressão resultasse numa árvore em que todos os
ramos estivessem ligados.
A primeira cláusula da definição do predicado ‘conexo/3’ corresponde ao caso elementar, no qual
toda a expressão já foi processada (representado pela lista vazia no primeiro argumento) e na pilha há
uma lista com um único elemento (“[Resultado]” no segundo argumento); esse elemento é apresentado
como o resultado da operação de conexidade (no terceiro argumento).
A segunda cláusula, responsável pela parte indutiva da definição, transfere o primeiro elemento
ainda não processado da expressão para uma pilha na qual serão executadas as derivações (invocadas
através do predicado ‘conectado/2’), para que a operação de conexidade seja invocada novamente, até que
não haja mais nenhum elemento a ser processado na expressão (o que vai ser garantido pela primeira
cláusula da definição).
É preciso agora passar à explicação do predicado ‘conectado/2’, que vai executar efetivamente as
derivações e onde estarão representadas as regras da gramática categorial. Na verdade, da forma como a
implementação foi feita, o predicado ‘conectado/2’ ainda será responsável por lidar com os itens lexicais;
apesar de arbitrária em relação à gramática categorial, essa opção pode ser justificada por motivos de
economia ou, em termos mais técnicos da programação em Prolog, por execução parcial (Pereira &
Shieber 1987: 98). Ao invés da operação de deslocamento estar parcialmente executada na definição do
predicado ‘conexo/3’ e do processamento dos itens lexicais ser executado por uma das cláusulas da
definição do predicado ‘conectado/2’, poderíamos definir um outro predicado que fosse responsável por
essas duas funções. 8
Para que a representação das categorias complexas possa ser introduzida no programa sem
nenhuma alteração, é preciso definir seus conectivos como operadores. Isso é feito através das seguintes
cláusulas: ‘:- op(100, xfx, /).’ e ‘:- op(100, xfx, \).’; como essa é mais uma exigência técnica da
programação em Prolog do que propriamente uma solução lingüisticamente motivada, não a explicaremos
aqui. Além disso, a indicação das regras empregadas será feita pelo operador ‘@’, definido na cláusula ‘:op(150, yfx, @).’
A primeira cláusula da definição do predicado ‘conectado/2’, responsável pela inclusão dos itens
lexicais (que aqui serão chamados apenas de “palavra”), busca num léxico pela primeira palavra (ainda
não processada) da expressão (a ser estabelecido pelo predicado ‘palavra/2’, conforme explicaremos a
seguir), acrescentando-a à antiga pilha, junto com sua categoria, ligada por dois-pontos, e com a
informação de que ele é um item lexical (‘lex’), indicado por ‘@’ (‘Palavra: Categoria @ lex’).
Assim, caso tenhamos no léxico a informação de que a palavra ‘pedro’ é um nome
(‘palavra(pedro, n).’), e invocarmos o predicado ‘conectado/2’ aplicado a um primeiro argumento do tipo
‘[pedro, ...]’, com uma pilha vazia (“[]”) como segundo argumento, isso faz com que a pilha vazia se
transforme em ‘[pedro: n @ lex]’.
Agora sim, podemos começar apresentando as regras de derivação da gramática categorial.
Comecemos pela regra de aplicação para a direita (forward application). Segundo essa regra, uma
expressão “A”, da categoria complexa “X/Y”, quando se junta à sua direita (se pensarmos no
encadeamento da direita para a esquerda como ocorre no nosso sistema ortográfico; depois dela, se
pensarmos num encadeamento seqüencial como ocorre na produção lingüística oral) com uma expressão
“B”, de categoria “Y”, resulta na concatenação das expressões em “A” e “B”, cuja categoria é “X”.9 Em
termos esquemáticos, poderíamos representar essa operação categorial como uma regra de estrutura
sintagmática do tipo “X/Y Y X”.
No programa, essa regra aparece logo abaixo do comentário “% Aplicação funcional para a
esquerda”. Como, devido ao empilhamento, a ordem acaba sendo invertida, para que a regra de aplicação
para a direita possa ser aplicada, é preciso que, na pilha, haja uma expressão da categorial “Y” na
primeira posição e uma expressão da categoria “X/Y” na segunda posição.
Nesse momento, já podemos solicitar para nosso programa analisar uma expressão como “ama
Maria”, através da invocação ‘conexo([ama, maria], [], Resultado).’, de forma que o interpretador Prolog
nos apresenta como resposta: ‘[ama: (n\s)/n @ lex, maria: n @ lex]: n\s @ ad’.10
7
Esse conceito de conexidade é um pouco mais amplo do que o de símbolo inicial, vindo da gramática de estrutura
sintagmática, na qual algum nó (ou pelo menos um) precisa ser explicitamente determinado como possível raiz das árvores. Com a
noção de conexidade, qualquer nó pode ser raiz, contanto que a derivação da expressão termine exclusivamente nele.
8
Esse predicado poderia ser algo do tipo ‘transfere([Palavra | Resto], Pilha, Resto, [Palavra: Categoria @ lex | Pilha]) :palavra(Palavra, Categoria).’, e a segunda cláusula da definição do predicado ‘conexo/2’ precisaria ser modificada para
‘conexo(Expressão, Pilha, Resultado) :- transfere(Expressão, Pilha, Resto, NovaPilha), conectado(NovaPilha, PilhaConexa),
conexo(Resto, PilhaConexa, Resultado).’; a definição do predicado ‘palavra/2’, que será explicada a seguir, continuaria inalterada.
9
Seguindo Borges Neto (1999), vamos adotar a notação de Lambek no texto. Uma outra variante notacional muito
empregada é a de Steedman, na qual o resultado é sistematicamente apresentado à esquerda. Para esse caso, especificamente, não há
diferença entre as notações; quando elas divergirem, apresentarei a variação de Steedman em nota.
10
Na verdade, para operar efetivamente ainda estaria faltando uma cláusula que define o que deve ser feito quando a
pilha já estiver completamente conexa, mas isso será explicado mais adiante.
Luiz Arthur PAGANI
843
Além da aplicação para a direita, a gramática categorial pura ainda dispõe de outra versão da regra
de aplicação (backward application) que busca o complemento da expressão complexa antes dela. Ou
seja, se temos uma expressão “A”, de categoria “Y”, seguida de outra expressão “B”, de categoria
“Y\X”,11 o resultado é a concatenação das expressões em “A” e “B”, cuja categoria é “X”.
Esquematicamente, a regra de reescrita seria “Y Y\X X”.12
No programa, a cláusula relativa à aplicação para a esquerda na definição do predicado
‘conectado/2’ aparece logo abaixo do seu respectivo comentário. Se a regra de aplicação para a direita era
responsável pela combinação do verbo com seu objeto, a regra de aplicação para a esquerda reúne o
sujeito ao predicado. Novamente devido ao empilhamento, para que essa regra se aplique é preciso que os
dois primeiros elementos da pilha sejam, respectivamente, uma expressão de categoria “Y\X” e outra de
categoria “Y”, cuja combinação resulta numa expressão de categoria “X”, conforme fica registrado no
primeiro elemento da nova pilha.
Através da regra de aplicação para a esquerda, é possível analisar uma sentença como “Pedro
corre”, invocada por ‘conexa([pedro, corre], [], Resultado).’, cujo resultado será a análise ‘[pedro: n @
lex, corre: n\s @ lex]: s @ ae’. E através das duas regras de aplicação, a análise da sentença “Pedro ama
Maria”, invocada por ‘conexo([pedro, ama, maria]).’, resultaria em ‘[pedro: n @ lex, [ama: (n\s)/n @ lex,
maria: n @ lex]: n\s @ ad]: s @ ae’, composta primeiro pela derivação da expressão “ama Maria”
(conforme explicado logo acima) e depois pela concatenação desta com “Pedro”.
Como todas as cláusulas do predicado ‘conectado/2’ apresentadas sempre invocam recursivamente
o próprio predicado ‘conectado/2’ é preciso incluir ainda uma última cláusula que forneça a condição de
término quando não reste mais nenhuma conexão que possa ser feita na pilha. Essa cláusula precisa
informar simplesmente que a pilha já é a pilha conectada.
Derivação ao estilo de Prawitz
Como acabamos de ver, para as sentenças “Pedro corre” e “Pedro ama Maria”, os resultados das
análises gramaticais obtidas são, respectivamente, ‘[pedro: n @ lex, corre: n\s @ lex]: s @ ae’ e ‘[pedro:
n @ lex, [ama: (n\s)/n @ lex, maria: n @ lex]: n\s @ ad]: s @ ae’. Além de dificultar a visualização das
operações sintáticas envolvidas, a representação obtida ainda não se parece em absoluto com o tipo de
apresentação normalmente empregado na gramática categorial, na qual geralmente se representa a
estrutura sintática como se fosse uma derivação de uma prova de teorema, apresentada ao estilo de
Prawitz (1965).
Apresentada nesse estilo, a derivação de “Pedro corre” pode ser vista no Diagrama 1.13
n
Pedro
lex
n\s
corre
lex
s
ae
Diagrama 1 – Derivação de “Pedro corre ao estilo de Prawitz
No Diagrama 1, podemos ver que “Pedro” pertence à categoria ‘n’ e “corre” à categoria ‘n\s’,
ambas por informação lexical. Podemos ver ainda que o resultado da regra de aplicação para a esquerda
11
Na notação de Steedman, a categoria seria “X\Y”.
Ainda na notação de Steedman, a regra seria “Y X\Y
X”.
Na verdade, o diagrama aqui sofreu algumas adaptações. Nas versões em que se apresenta apenas o cálculo categorial,
como em Wood (1993: 40), a sentença “he likes him” fica:
12
13
he
s/(n\s)
likes
n\s/n
Him
(s/n)\s
n\s
<C
>A
s
A versão apresentada no presente texto é uma abreviação de uma apresentação que eu tenho empregado, que é um pouco
mais exaustiva ainda, principalmente do ponto de vista lingüístico. Nessa versão mais informativa, a expressão lingüística aparece
sobre o traço, a categoria ao lado esquerdo do traço, a regra ao lado direito do traço e a representação semântica abaixo do traço;
assim, a mesma sentença “Pedro corre” ficaria:
n
s
Pedro
p
lex
Pedro corre
Cp
n\s
corre
C
lex
ae
(Na representação semântica, o indivíduo denotado pelo nome “Pedro” é representado por ‘j’, a função de indivíduos a
valores de verdade denotada pelo verbo “corre” é representada por ‘C’ e ‘Cp’ é representa a aplicação da função ao indivíduo.)
844
ANALISADOR GRAMATICAL EM PROLOG PARA GRAMÁTICAS CATEGORIAIS
concatena “Pedro” e “corre” , que pertence à categoria ‘s’ (formando “Pedro corre”, ainda que isso não
apareça explicitamente no diagrama; mas, como dissemos na nota 13, estamos empregando uma
representação mais reduzida; dois motivos justificam essa redução: 1) o estágio ainda inicial do
analisador gramatical em relação à representação gramatical e 2) a apresentação de uma analisador
gramatical mais simples).
A sentença “Pedro ama Maria” seria analisada como no Diagrama 2.
n
Pedro
lex
(n\s)/n
ama
lex
n
Maria
n\s
s
lex
ad
ae
Diagrama 2 – Derivação de “Pedro ama Maria” ao estilo de Prawitz
No Diagrama 2, pode-se observar que “ama” pertence à categoria ‘(n\s)/n’ e “Maria” à categoria
‘n’, ambas por informação lexical. O resultado da concatenação dessas duas expressões, devido à regra de
aplicação para a direita, pertence à categoria ‘n\s’. Ainda por informação lexical, observa-se que “Pedro”
pertence à categoria ‘n’ e, quando concatenada à expressão resultante da concatenação anterior, resulta
em uma expressão da categoria ‘s’, devido à regra de aplicação para a esquerda.
Desenhando a derivação ao estilo de Prawitz
O desenho da derivação ao estilo de Prazwitz é executado pelo predicado ‘prawitz/3’.
A primeira cláusula de ‘prawitz/3’ é responsável por lidar com a parte externa da representação de
expressões complexas. Por parte externa de expressões complexas, entendemos a categoria e a regra
envolvidas na formação dessas expressões. Assim, para a análise de “Pedro corre” (‘[pedro: n @ lex,
corre: n\s @ lex]: s @ ae’), a parte interna é a lista ‘[pedro: n @ lex, corre: n\s @ lex]’, enquanto a parte
externa inclui as informações sobre a categoria (‘s’) e a regra empregada na construção (‘ae’). Isso é feito
logo após o comentário “% Exp -> lista não vazia”.
Nessa cláusula, o predicado ‘lista_n_v/1’ apenas testa se o conteúdo da variável ‘Exp’ é uma lista
não vazia (definida na cláusula “lista_n_v([_|_]).”) e, em caso afirmativo, transfere recursivamente o
conteúdo dessa variável para o próprio predicado ‘prawitz/3’. Depois disso, ele troca de linha (‘nl’),
escreve o valor da variável ‘Cat’ (‘write(Cat)’), calcula o tamanho da categoria instanciada em ‘Cat’,
traça uma linha cujo tamanho é o total vindo do desenho do conteúdo da variável ‘Exp’ subtraído do
tamanho da categoria em ‘Cat’ e do valor da tabulação em ‘Tab’ e finalmente escreve a regra em ‘Reg’.
A segunda cláusula da definição de ‘prawitz/3’ desenha a combinação de duas expressões básicas
(no nosso caso, simplesmente as palavras), como pode ser visto logo após o comentário “% Exp1 e Exp2
-> palavra”.
O teste para constatar que ‘Exp1’ e ‘Exp2’ contêm mesmo uma expressão básica, ou atômica, é
executado pelo predicado pré-definido ‘atom/1’; o ‘!’ garante que, atingida essa condição, o interpretador
não precisa testar outras opções. Depois, é calculado o tamanho da categoria da primeira expressão
(‘tamanho(Cat1, TamanhoCat1)’) e a tabulação para essa expressão (‘Tab1 is Tab + TamanhoCat1 + 1’),
que é a soma da tabulação inicial (‘Tab’) do tamanho da categoria da primeira expressão acrescida ainda
de um (porque o traço sob a expressão será dois caracteres maior do que a expressão, e essa unidade
corresponde ao primeiro traço antes da expressão); a primeira expressão será escrita com essa tabulação
(‘tab(Tab1)’ e ‘write(Exp1)’). Para o cálculo da tabulação para a segunda expressão (‘Tab2’), é preciso
calcular os tamanhos da regra da primeira expressão (‘tamanho(Reg1, TamanhoReg1)’) e da categoria da
segunda expressão (‘tamanho(Cat2, TamanhoCat2)’); essa tabulação é a soma de um (do traço depois da
primeira expressão, do tamanho da regra da primeira expressão, de dois (o espaçamento entre os dois
blocos formados pelas expressões e suas anotações) e do tamanho da categoria da segunda expressão
(‘Tab2 is 1 + TamanhoReg1 + 2 + TamanhoCat2 + 1’); a segunda expressão será escrita com essa
tabulação (‘tab(Tab2)’ e ‘write(Exp2)’).
Para continuar, é preciso passar para a próxima linha (‘nl’). Depois, respeitando a tabulação inicial
(‘tab(Tab)’), escreve-se a categoria da primeira expressão (‘write(Cat1)’); e para traçar a linha sob a
primeira expressão (‘Linha1 is TamanhoExp1 + 2’ e ‘linha(Linha1)’) é preciso calcular o tamanho desta
expressão (‘tamanho(Exp1, TamanhoExp1)’). Logo em seguida, escreve-se a regra da primeira expressão
(‘write(Reg1)’), salta-se dois espaços (‘tab(2)’, relativo ao espaçamento ente os dois blocos, mencionado
no parágrafo anterior) e escreve-se a categoria da segunda expressão (‘write(Cat2)’). Para traçar a linha
sob a segunda expressão (‘Linha2 is TamanhoExp2 + 2’ e ‘linha(Linha2)’), é preciso calcular o seu
tamanho (‘tamanho(Exp2, TamanhoExp2)’); finalmente, escreve-se a regra da segunda expressão
Luiz Arthur PAGANI
845
(‘write(Cat2)’), passa-se para a próxima linha e o valor total ocupado pelo desenho é calculado (‘Total is
Tab1 + TamanhoExp1 + Tab2 + TamanhoExp2 + 1’).
Nesse ponto, já podemos apresentar a derivação de “Pedro corre”. Invocada através da diretiva
‘conexo([pedro,corre]).’, o resultado será a apresentação do Diagrama 3 que, como se pode constatar, é
completamente semelhante ao Diagrama 1.
pedro
n-------lex
corre
n\s-------lex
s----------------------ae
Diagrama 3 - Derivação de "Pedro corre" ao estilo de Prawitz em Prolog
Para desenhar a derivação da sentença “Pedro ama Maria”, ainda é necessária uma terceira
cláusula na definição do predicado ‘prawitz/3’, que se encontra bem abaixo do comentário “% Exp1 ->
palavra e Exp2 -> expressão complexa”.
No caso da análise de “Pedro ama Maria”, a combinação pertinente para a terceira cláusula conterá
uma expressão básica (“Pedro”) e uma expressão complexa (“ama Maria). Isso é testado nessa terceira
cláusula por ‘atom(Exp1)’ e ‘lista_n_v(Exp2)’, e o ‘!’ garante que nenhuma outra opção precisaria ser
mais explorada. E dessa vez, ao contrário do que aconteceu na cláusula anterior, será preciso desenhar
primeiro o bloco formado pela segunda expressão e por suas respectivas anotações. Assim, calcula-se a
tabulação para a primeira expressão (‘Tab1 is Tab + TamanhoCat1 + 1’) a partir do tamanho da categoria
da primeira expressão (‘tamanho(Cat1, TamanhoCat1)’), depois a tabulação para a segunda expressão
(‘Tab2 is Tab1 + TamanhoReg1 + 2 + TamanhoCat2 + 1’) a partir do tamanho da regra da primeira
expressão (‘tamanho(Reg1, TamanhoReg1)’) e da categoria da segunda (‘tamanho(Cat2,
TamanhoCat2)’); o segundo bloco será desenhado a partir dessa segunda tabulação (‘prawitz(Exp2, Tab2,
Total)’). Depois, a partir da primeira tabulação (‘tab(Tab1)’), escreve-se a primeira expressão
(‘write(Exp1)’), passa-se para uma nova linha escreve-se a categoria da primeira expressão
(‘write(Cat1)’, respeitando a tabulação inicial ‘tab(Tab)’), traça-se a linha sob a primeira expressão
(‘Linha1 is TamanhoExp1 + 2’ e ‘linha(Linha1)’, a partir do tamanho da expressão (‘tamanho(Exp1,
TamanhoExp1)’)) e escreve-se sua respectiva regra (‘write(Reg1)’). Após respeitar o espaçamento de dois
caracteres entre os blocos (‘tab(2)’), escreve-se a categoria da segunda expressão (‘write(Cat2)’), traça-se
a linha sob ela ( ‘linha2 is Total - Tab2 - TamanhoCat2’ e ‘linha(Linha2)’), escreve-se sua respectiva
regra (‘write(Reg2)’) e troca-se de linha (‘nl’).
Agora, então, é possível apresentar a derivação de “Pedro ama Maria”, que é feita através da
diretiva ‘conexo([Pedro,ama,Maria]).’, e aparecerá como no Diagrama 4,14 que é completamente
semelhante ao Diagrama 2.
ama
(n\s)/n-----lex
pedro
n-------lex
maria
n-------lex
n\s----------------------ad
s-------------------------------------ae
Diagrama 4 - Derivação de "Pedro ama Maria" ao estilo de Prawitz em Prolog
Para encerrar a explicação do funcionamento do predicado ‘prawitz/3’ ainda é preciso comentar os
predicados ‘tamanho/2’ e ‘linha/1’. Comecemos pelo segundo, que é mais simples.
A definição do predicado ‘linha/1’ aparece sob o comentário “% Desenha uma linha de tamanho
especificado”. A condição de término da definição é encontrada quando o predicado é invocado com zero
como seu argumento (‘linha(0) :- !.’). Quando o predicado é invocado com algum outro número inteiro
positivo, ele escreve um hífen (‘write(‘-’)’), subtrai o valor inicial de um e invoca novamente o predicado
‘linha/1’ com esse novo valor.
A definição do predicado ‘tamanho/3’ é um pouco mais complexa, principalmente porque o
recurso utilizado para decompor as categorias (o predicado pré-definido ‘=..’) desconsidera os pares de
parêntesis que aparecem nas combinações feitas a partir de categorias complexas. Ou seja, uma categoria
como ‘(n\s)/n’ seria decomposta em ‘n\s’ e ‘n’, para as quais o resultado seria um tamanho igual a quatro,
quando, na verdade o tamanho real é igual a seis.
Assim, a primeira condição a ser considerada nessa definição é quando a categoria é atômica. Isso
é feito logo depois do comentário “% Categoria atômica”.
14
Na verdade, o diagrama produzido começa a primeira linha dois espaços antes e termina a última linha também dois
espaços antes.
846
ANALISADOR GRAMATICAL EM PROLOG PARA GRAMÁTICAS CATEGORIAIS
A condição de atomicidade é testada pelo predicado pré-definido ‘atom/1’ (‘atom(Atomo)’) e
interrompe-se a busca por outras alternativas (‘!’). Depois, a categoria é transformada numa lista pelo
predicado pré-definido ‘name/2’ (‘name(Atomo, Lista)’) e seu tamanho é medido pelo predicado prédefinido ‘length/2’ (‘length(Lista, Atomo)’), que conta a quantidade de elementos numa lista. Assim, para
a diretiva ‘tamanho(s, Tamanho).’, o resultado será ‘Tamanho = 1’; para a diretiva ‘tamanho(sn,
Tamanho).’, o resultado será ‘Tamanho = 2’.
Se a categoria for complexa, três casos precisam ser considerados: 1) quando ela formada por duas
categorias atômicas, 2) quando ela é formada por uma categoria atômica e outra complexa, e 3) quando
ela é formada por duas categorias complexas. No segundo caso, como a categoria atômica pode vir antes
ou depois da categoria complexa, ele se desdobra em dois subcasos, somando mais quatro condições a
serem definidas.
A segunda cláusula do predicado ‘tamanho/2’ define a condição da categoria complexa formada
por duas categorias atômicas. Nesse caso, o tamanho da categoria complexa é igual à soma dos tamanhos
das categorias atômicas acrescida de um (relativo a um dos dois conectivos: ‘/’ ou ‘\’).
Depois de desmembrar a categoria complexa em uma lista (Complexo =.. [_, X, Y]’), composta
pelo conectivo (que é simplesmente ignorado através da variável anônima ‘_’) e pelas categorias
respectivamente à esquerda (‘X’) e à direita do conectivo (‘Y’), a atomicidade das categorias é testada
(‘atom(X)’ e ‘atom(Y)’) e a possibilidade de busca de alternativas é interrompida (‘!’). Calcula-se o
tamanho de cada uma das categorias atômicas (‘tamanho(X, TamanhX)’ e ‘tamanho(Y, TamanhoY)’) e o
resultado é a soma mencionada acima (‘Tamanho is TamanhoX + TamanhoY +1’).
Nas outras três cláusulas a seguir, a estratégia da definição continua basicamente a mesma,
mudando apenas os testes para se determinar a condição pertinente. Além disso, a soma precisa ser um
pouco diferente, de acordo com o caso.
A definição para as categorias complexas formadas por uma categoria atômica seguida de outra
complexa pode ser vista depois do comentário “% Categoria complexa formada por categoria atômica e
complexa”.
Como o teste de atomicidade para ambas as categorias decompostas foi feito na cláusula anterior,
garantindo-se que as opções se interrompiam quando aquela condição fosse satisfeita, se exigirmos que
apenas a primeira categoria seja atômica (‘atom(X)’), não é preciso testar a atomicidade da segunda. Os
tamanhos são calculados (‘tamanho(X, TamanhoX)’ e ‘tamanho(Y, TamanhoY)’) e a soma dos dois ainda
é acrescida de três (um para o conectivo e dois para o par de parêntesis da categoria complexa).
O caso da categoria complexa formada por uma categoria complexa seguida de outra atômica é
definido logo após o comentário “% Categoria complexa formada por categoria atômica e complexa”. Ele
é uma espécie de imagem espelhada da cláusula anterior, porque agora é a segunda categoria que precisa
ser atômica e não a primeira (‘atom(Y)’). No resto, os procedimentos são todos exatamente os mesmos.
Finalmente, a cláusula para a condição de uma categoria complexa formada por duas outras
categorias complexas é determinada depois do comentário “% Categoria complexa formada por duas
categorias complexas”.
Como todas as opções de combinação de atomicidade já foram testadas pelas cláusulas anteriores,
está cláusula só se aplica quando ambas as categorias forem complexas. Os tamanhos de cada uma delas é
calculado (‘tamanho(X, TamanhoX)’ e ‘tamanho(Y, TamanhoY)’) e a soma deles é acrescida de cinco
(um para o conectivo e dois para cada par de parêntesis de cada uma das duas categorias complexas).
Com isso, encerram-se as explicações de todas as definições necessárias para se construir em
Prolog primeiro uma derivação usando uma gramática categorial e um analisador gramatical por
deslocamento e redução, e depois apresentar o resultado dessa derivação ao estilo de Prawitz.
Conclusão
Na verdade, esse foi o relato não apenas de uma pesquisa em andamento, mas de um trabalho
ainda bem em seu início.
Apesar de toda a complexidade técnica, em relação à gramática categorial, apenas as regras de
aplicação foram introduzidas; apesar de serem em um número bastante restrito, para uma abordagem
empiricamente interessante para servirem de gramática para uma língua natural, ainda seria preciso
introduzir algumas outras regras, como a permutação (ou associatividade), a composição, a promoção (ou
alçamento) e a divisão. No entanto, a inclusão dessas outras regras, principalmente as regras unárias
(permutação, promoção e divisão) suscitam problemas de computabilidade, o que exigiria do analisador
gramatical alguns recursos de decisão para não entrar em recursão infinita.
Além disso, a inclusão dessas regras ainda afetaria a implementação do apresentador da derivação
ao estilo de Prawitz, ao criar configurações da análise que não existiam na versão apresentada aqui.
Luiz Arthur PAGANI
847
De qualquer forma, mesmo sem a inclusão dessas regras, o apresentador da derivação ao estilo de
Prawitz ainda teria problemas para lidar com a inclusão de outras categorias, além dos nomes e dos
predicados de um (‘n\s’) ou dois (‘(n\s)/n’) lugares. Se, por exemplo, incluíssemos no léxico um nome
comum como “menino” (cuja categoria poderia ser representada por ‘nc’) e um determinante como “o”
(cuja categoria complexa poderia ser ‘n/nc’), apesar do analisador ser capaz de construir análises para “o
menino corre” (‘[[o: n/nc @ lex, menino: nc @ lex]: n @ ad, corre: n\s @ lex]: s @ ae’) e “o menino ama
Maria” (‘[[o: n/nc @ lex, menino: nc @ lex]: n @ ad, [ama: (n\s)/n @ lex, maria: n @ lex]: n\s @ ad]: s
@ ae’), ele só consegue desenhar a apresentação para “Maria ama o menino”, como se vê no Diagrama
5.15
o
menino
n/nc---lex n--------lex
ama
(n\s)/n-----lex
Maria
n-------lex
n--------------------ad
n\s-----------------------------------ad
s--------------------------------------------------ae
Diagrama 5 - Derivação de "Maria ama o menino"
Dessa forma, como se pode ver, tanto o analisador quanto o apresentador da derivação ainda
precisam ser muito melhorados.16
RESUMO: Será apresentado aqui um analisador gramatical por deslocamento e redução para o modelo
AB da gramática categorial. Como o resultado da análise é apresentado no estilo de Prawitz, , o
algoritmo para isso também será explicado.
PALAVRAS-CHAVE: gramática categorial; analisador gramatical por deslocamento e redução; Prolog
Anexo
Listagem completa dos programas
% gramcat.pl
% Gramática categorial em Prolog
% para gramáticas categoriais
% Definição dos operadores %
% Conectivos para as categorias complexas
:- op(100, xfx, /).
:- op(100, xfx, \).
% Conectivo para indicação de regra sintática
:- op(150, yfx, @).
% Iniciador de análises
conexo(Expressão) :conexo(Expressão, [], Resultado),
write(Resultado).
% Conexidade sintática
conexo([], [Resultado], Resultado).
conexo([Palavra | Resto], Pilha, Resultado) :conectado([Palavra | Pilha], PilhaConexa),
conexo(Resto, PilhaConexa, Resultado).
% Regras de conexão para:
% Expressões básicas
15
Como no Diagrama 4, esse também apresenta os mesmos problemas de tabulação, que ficam ainda mais graves por
serem introduzidos duas vezes.
16
Como sempre foi mencionado em notas anteriores, convém também apontar em nota que uma das primeiras coisas que
precisam ser melhoradas é o problema da tabulação que aparece quando se desenha o diagrama para a combinação entre uma
palavra e uma expressão complexa.
848
ANALISADOR GRAMATICAL EM PROLOG PARA GRAMÁTICAS CATEGORIAIS
conectado([Palavra | Pilha], PilhaConexa) :palavra(Palavra, Categoria),
conectado([Palavra: Categoria @ lex | Pilha], PilhaConexa).
% Aplicação funcional para a direita
conectado([B: Y @ Regra2, A: X/Y @ Regra1 | Resto], PilhaConexa) :conectado([[A: X/Y @ Regra1, B: Y @ Regra2]: X @ ad | Resto],
PilhaConexa).
% Aplicação funcional para a esquerda
conectado([B: Y\X @ Regra2, A: Y @ Regra1 | Resto], PilhaConexa) :conectado([[A: Y @ Regra1, B: Y\X @ Regra2]: X @ ae | Resto],
PilhaConexa).
% Pilha totalmente conexa
conectado(PilhaConexa, PilhaConexa).
% Léxico
palavra(pedro, n).
palavra(maria, n).
palavra(ama, (n\s)/n).
palavra(corre, n\s).
palavra(o, n/nc).
palavra(menino, nc).
% Apresentação ao estilo de Prawitz:
% Exp -> lista não vazia
prawitz(Exp: Cat @ Reg, Tab, Total) :lista_n_v(Exp), prawitz(Exp, Tab, Total), nl, tab(Tab),
write(Cat),
tamanho(Cat, TamanhoCat), Linha is Total - TamanhoCat - Tab,
linha(Linha), write(Reg).
% Exp1 e Exp2 -> palavra
prawitz([Exp1: Cat1 @ Reg1, Exp2: Cat2 @ Reg2], Tab, Total) :atom(Exp1), atom(Exp2), !, tamanho(Cat1, TamanhoCat1),
Tab1 is Tab + TamanhoCat1 + 1, tab(Tab1), write(Exp1),
tamanho(Reg1, TamanhoReg1), tamanho(Cat2, TamanhoCat2),
Tab2 is 1 + TamanhoReg1 + 2 + TamanhoCat2 + 1, tab(Tab2),
write(Exp2),
nl, tab(Tab), write(Cat1), tamanho(Exp1, TamanhoExp1),
Linha1 is TamanhoExp1 + 2, linha(Linha1), write(Reg1), tab(2),
write(Cat2), tamanho(Exp2,TamanhoExp2), Linha2 is TamanhoExp2 + 2,
linha(Linha2), write(Reg2), nl,
Total is Tab1 + TamanhoExp1 + Tab2 + TamanhoExp2 + 1.
% Exp1 -> palavra e Exp2 -> expressão complexa
prawitz([Exp1: Cat1 @ Reg1, Exp2: Cat2 @ Reg2], Tab,Total) :atom(Exp1), lista_n_v(Exp2), !, tamanho(Cat1, TamanhoCat1),
Tab1 is Tab + TamanhoCat1 + 1, tamanho(Reg1, TamanhoReg1),
tamanho(Cat2, TamanhoCat2),
Tab2 is Tab1 + TamanhoReg1 + 2 + TamanhoCat2 + 1,
prawitz(Exp2, Tab2, Total), tab(Tab1), write(Exp1), nl, tab(Tab),
write(Cat1), tamanho(Exp1, TamanhoExp1), Linha1 is TamanhoExp1 +
2,
linha(Linha1), write(Reg1), tab(2), write(Cat2),
Linha2 is Total - Tab2 - TamanhoCat2, linha(Linha2), write(Reg2),
nl.
% Quantidade de caracteres numa categoria para:
% Categoria atômica
tamanho(Atomo, Tamanho) :atom(Atomo), !, name(Atomo, Lista), length(Lista, Tamanho).
% Categoria complexa formada por duas categorias atômicas
tamanho(Complexo, Tamanho) :Complexo =.. [_, X, Y], atom(X), atom(Y), !, tamanho(X, TamanhoX),
tamanho(Y, TamanhoY), Tamanho is TamanhoX + TamanhoY + 1.
% Categoria complexa formada por categoria atômica e complexa
tamanho(Complexo, Tamanho) :Complexo =.. [_, X, Y], atom(X), !, tamanho(X, TamanhoX),
tamanho(Y, TamanhoY), Tamanho is TamanhoX + TamanhoY + 3.
% Categoria complexa formada por categoria complexa e atômica
Luiz Arthur PAGANI
849
tamanho(Complexo, Tamanho) :Complexo =.. [_, X, Y], atom(Y), !, tamanho(X, TamanhoX),
tamanho(Y, TamanhoY), Tamanho is TamanhoX + TamanhoY + 3.
% Categoria complexa formada por duas categorias complexas
tamanho(Complexo, Tamanho) :Complexo =.. [_, X, Y], tamanho(X, TamanhoX),
tamanho(Y, TamanhoY), Tamanho is TamanhoX + TamanhoY + 5.
% Definição de lista não vazia
lista_n_v([_ | _]).
% Desenha uma linha de tamanho especificado
linha(0) :!.
linha(X) :write('-'), Y is X - 1, linha(Y).
REFERÊNCIAS BIBLIOGRÁFICAS
BORGES Neto, José. 1999. Introdução às Gramáticas Categoriais. Inédito.
BRESNAN, Joan (ed.). 1982. The Mental Representation of Grammatical Relations. Cambridge,
Massachusetts: The MIT Press.
CLOCKSIN, William F. & Mellish, Christopher S. 1981. Programming in Prolog. Berlin: Springer.
COVINGTON, Michael A. 1994. Natural Language Processing for Prolog Programmers. Englewood
Clifts, New Jersey: Prentice Hall.
GAZDAR, Gerald; Klein, Ewan; Pullum, Geoffrey K. & Sag, Ivan. 1985. Generalized Phrase Structure
Grammar. Oxford: Basil Blackwell.
MOORTGAT, M. 1988. Categorial Investigations: Logical and Linguistic Aspects of the Lambek
Calculus. Dordrecht: Foris.
PEREIRA, Fernando. 1985. A new characteriozation of attachment preferences. In Dowty, Karttunen &
Ziwick (eds.), Natural Language Parsing, Cambridge: Cambridge Univeristy Press, pp. 307-319.
PEREIRA, Fernando & Shieber, Stuart. 1987. Prolog and Natural-Language Analysis. Stanford: Center
for the Study of Language and Information.
POLLARD, Carl & Sag, Ivan. 1994. Head-Driven Phrase Structure Grammar. Chicago: University of
Chicago Press.
PRAWITZ, D. 1965. Natural Deduction - A Proof-Theoretical Study. Stockholm: Almqvist & Wiksell.
TESNIÈRE, Lucien. 1959. Elements de Syntaxe Structurale. Paris: Klincksiek.
WOOD, Mary McGee. 1993. Categorial Grammars. London: Routledge.