Para descrever a estrutura das expressões, usaremos os termos
sentença, oração, sintagma e constituinte, seguindo a
terminologia do capítulo sobre a ordem e a função das palavras de
Caseli and (org.) (2024)Marginal noteH. M. Caseli and M. G. V. Nunes (org.) (2024). “Processamento de Linguagem Natural: Conceitos, Técnicas e Aplicações em Português”. 3ª edição, BPLN. .. Na escrita, uma sentença se estende da letra
maiúscula até a pontuação final. Ela é a maior unidade que tomamos
como entrada para a análise sintática.
Uma oração se organiza em torno de um verbo e expressa uma predicação.
Em Alice smiled and Dorothy laughed., há uma única sentença e duas
orações. A primeira atribui a Alice o evento de sorrir, e a segunda
atribui a Dorothy o evento de rir. Uma sentença pode, portanto,
reunir mais de uma oração.
Um sintagma é uma unidade organizada em torno de um núcleo. A classe
desse núcleo determina o tipo do sintagma. Usaremos NP para
sintagmas nominais, VP para sintagmas verbais e PP para sintagmas
preposicionais. Em Alice loved the dwarfs., por exemplo,
the dwarfs é um sintagma nominal cujo núcleo é dwarfs, e
loved the dwarfs é um sintagma verbal cujo núcleo é loved.
Chamamos de constituintes as partes que funcionam como unidades
dentro de uma estrutura maior. Assim, the dwarfs é um constituinte
do sintagma verbal, e esse sintagma é um constituinte da oração.
Uma palavra também pode formar um constituinte, como Alice nesse
exemplo.
O símbolo inicial das gramáticas que usaremos é S, de sentença.
Esse rótulo também representa orações. Em uma regra como
S → S and S, os dois símbolos S à direita representam as
orações coordenadas, enquanto o símbolo S à esquerda representa
a sentença que elas formam. Para uma sentença com uma única oração,
o mesmo nó representa ambas as unidades.
Uma árvore sintática representa a estrutura de uma expressão. As folhas
guardam informação lexical, e os nós internos guardam informação
sintática. O tipo ParseTree α β deixa em aberto que informação
guardamos em cada caso. Uma folha, construída com .leaf, contém um
valor de tipo α. Um nó, construído com .branch, contém um rótulo de
tipo β e uma lista de subárvores. O número de filhas do nó é o
comprimento dessa lista.
Para exibir uma árvore, precisamos saber como exibir os valores de
tipos α e β. A função ParseTree.toText usa ToString
para ambos. Ela escreve uma folha como o texto do seu conteúdo. Para
um nó, escreve [., o rótulo e as subárvores, separadas por espaços,
e fecha com ].
Na árvore snowWhite, tanto os rótulos quanto o conteúdo das folhas
são textos de tipo String. A raiz, rotulada S, tem duas
filhas. A primeira é um NP com a folha Snow White. A segunda é um
VP, que contém o verbo sob o rótulo TV e o objeto sob outro
NP.
Uma mesma subárvore pode ocorrer em mais de um lugar. Se, na árvore
snowWhite, trocássemos a folha the dwarfs por Snow White,
a subárvore [.NP Snow White] teria duas ocorrências. Para distinguir
uma da outra, usamos o caminho da raiz até cada ocorrência. O primeiro
NP fica em [0], a primeira filha da raiz. O segundo fica em
[1, 1], a segunda filha da segunda filha da raiz.
Uma posição é uma lista de índices naturais. Em cada passo, o índice
indica qual filha visitar, contando a partir de zero. O caminho vazio
[] aponta para a própria raiz. Para listar as posições de uma
árvore, pos inclui [] e, para cada filha, acrescenta seu índice ao
início de cada caminho que parte dela. A função auxiliar local
posFrom i ts, definida com let rec, percorre as filhas em ts a
partir do índice i.
A função subtree t p percorre a árvore t seguindo os índices de
p. O acesso ts[i]? devolve a filha de índice i quando ela existe.
Se um índice estiver fora da lista ou se ainda houver passos a dar
ao chegar a uma folha, o resultado é Option.none. Quando o
caminho termina, a função devolve a subárvore encontrada com
Option.some. Por fim, subtrees usa List.filterMap
para aplicar subtree t às posições de pos t e recolher as
subárvores. Esses caminhos vêm da própria árvore e, portanto, todos
são válidos.
abbrevPos:=ListNatdefpos{αβ:Type}(p:ParseTreeαβ):ListPos:=letrecposFrom{αβ:Type}:Nat→List(ParseTreeαβ)→ListPos|_,[]=>[]|i,t::ts=>(post).map(i::·)++posFrom(i+1)tsmatchpwith|.leaf_=>[[]]|.branch_ts=>[]::posFrom0ts[[],[0],[0,0],[1],[1,0],[1,0,0],[1,1],[1,1,0]]#evalpossnowWhitedefsubtree{αβ:Type}:ParseTreeαβ→Pos→Option(ParseTreeαβ)|t,[]=>somet|.branch_ts,i::is=>matchts[i]?with|somet=>subtreetis|none=>none|.leafVariable name `t` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_tNote: This linter can be disabled with `set_option linter.unusedVariables false`t,Variable name `a` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_aNote: This linter can be disabled with `set_option linter.unusedVariables false`a::Variable name `as` is not explicitly referenced.Hint: The binding can be removed (if unused) or named `_` (if used implicitly). Alternatively, prefix the name with `_` to silence this warning:[apply]_asNote: This linter can be disabled with `set_option linter.unusedVariables false`as=>nonedefsubtrees{αβ:Type}(t:ParseTreeαβ):List(ParseTreeαβ):=(post).filterMap(subtreet)(some [.VP [.TV loved] [.NP the dwarfs]])
#evalIO.println(subtreesnowWhite[1])
Uma posição p domina uma posição q se o caminho até q começa
pelo caminho até p. Nesse caso, a subárvore em q está contida na
subárvore em p. Em snowWhite, por exemplo, [1] domina
[1, 0] e também domina a si mesma. A dominância própria exige
ainda que as duas posições sejam distintas.
Para representar essas relações, posPairs t forma todos os pares
de posições da árvore t. A notação p <+: q exprime a proposição
de que p é prefixo de q, definida por List.IsPrefix.
Como essa proposição é decidível para listas de naturais, o Lean
pode convertê-la em um Bool para
List.filter. Assim, dominance conserva os pares em que
p <+: q, e properDominance exige também que p ≠ q.
A posição pdomina imediatamenteq quando p domina propriamente
q e não há posição r, diferente das duas, tal que p domina r e
r domina q. Defina immDominance e confira o resultado na árvore
snowWhite.
Duas posições são irmãs quando são filhas diferentes do
mesmo nó. Os caminhos até elas coincidem até a mãe e diferem no
último índice. A função sisters testa essa condição, e
sisterhood reúne os pares de posições que a satisfazem.
Uma posição pc-comanda uma posição q quando alguma irmã de
p domina q. Para expressar isso, cCommand usa a composição
das relações de irmandade e dominância. Em relComp r s, cada
(x, y) de r é combinado com os pares de s que começam em
y. Cada combinação com um par (y, z) produz (x, z).
List.eraseDups elimina os pares repetidos.
Em snowWhite, a posição do sujeito, [0], tem como irmã a
posição do VP, [1]. Por isso, o sujeito c-comanda o VP e
todas as posições que ele domina. Já o objeto, em [1, 1], tem como
irmã a posição do verbo, [1, 0]. O objeto c-comanda essa posição
e a folha do verbo. A posição do sujeito está fora desse ramo.
Uma posição ramifica quando domina imediatamente pelo menos duas
posições distintas. Como as filhas são numeradas a partir de zero,
basta verificar se os caminhos p ++ [0] e p ++ [1] existem.
Em snowWhite, apenas a raiz, [], e o VP, [1],
satisfazem essa condição.
Para estudar a relação entre c-comando e dominância, basta considerar
os caminhos envolvidos. Se p c-comanda q, existe uma irmã r
de p que é prefixo de q. Os três lemas abaixo descrevem o que
sabemos sobre p e r a partir de sisters: os caminhos
têm o mesmo comprimento, p não é prefixo de r, e, sem o último
índice, os dois caminhos coincidem, isto é, p e r têm a mesma
mãe. O exercício
usa esses fatos para investigar a dominância entre p e q.
Suponha que p c-comanda q, isto é, uma irmã r de p domina q. Prove que
p não domina q e que q não domina p. Prove também que a mãe
de p domina q. A mãe ramifica, porque tem as filhas
p e r, e é a posição ramificada mais baixa acima de p.
Dicas, uma para cada teorema:
Se p dominasse q, p e r seriam prefixos de q com o mesmo
comprimento. Então p seria prefixo de r
(List.prefix_of_prefix_length_le), o que sisters_not_prefix
proíbe.
Se q dominasse p, teríamos r prefixo de q e q prefixo de p,
com p e r do mesmo comprimento. Os três teriam o mesmo comprimento e
seriam iguais (List.IsPrefix.eq_of_length), e p seria irmã de
si mesma.
As irmãs p e r têm a mesma mãe (sisters_dropLast), e uma lista
sem o último elemento é prefixo dela (List.dropLast_prefix).
O c-comando não é simétrico, mas o c-comando mútuo é: p e q se
c-comandam mutuamente quando p c-comanda q e q c-comanda p.
Defina mutualCCommand e confira, na árvore snowWhite, que ele coincide
com a relação de irmãs.
A definição de c-comando deste capítulo não é a única em
uso. Outras duas partem do primeiro nó ramificado acima de p:
p c-comanda q quando o primeiro nó ramificado acima de p domina
q, com a dominância reflexiva. É uma definição usada para descrever a
ligação de variáveis.
p c-comanda q quando nenhuma das duas posições domina a outra e o
primeiro nó ramificado acima de p domina q. É a definição que o
verbete C-command (Wikipedia, 2026)Marginal noteColaboradores da Wikipedia (2026). “C-command”. Wikipedia, the free encyclopedia; acesso em 15 nov. 2026. . apresenta como padrão.
A função lowestBranchingAbove dá o primeiro nó ramificado acima de uma
posição, se houver um. A função labelPairs troca cada par de posições
pelo par dos rótulos dos nós nessas posições; na árvore cTree, cada
rótulo aparece uma só vez, e o rótulo identifica o nó. Defina
cCommandBranching e cCommandStandard, uma para cada definição. Os teoremas
abaixo comparam as três definições na árvore cTree, em que A está em [0],
B em [1], C em [1, 0], E em [1, 0, 0], D em [1, 1], F em
[1, 1, 0] e G em [1, 1, 1]:
O nó C tem uma só filha, E. Pela definição deste capítulo, E não
c-comanda nada, porque não tem irmãs. Por cCommandStandard, E c-comanda
D, F e G. O exemplo do próprio verbete diz que E não c-comanda
nada: ele segue a definição pelas irmãs, a da primeira sentença do verbete, e
não a que o verbete chama de padrão. Então cCommandBranching
acrescenta os pares em que uma posição domina a outra: E, por
exemplo, passa a c-comandar também a si mesmo, a sua mãe, C, e a sua
avó, B.
Para saber se uma posição p precede outra posição q,
comparamos os caminhos até elas a partir da raiz. Enquanto os índices
coincidem, avançamos nas duas listas. Na primeira diferença, p
precede q se o seu índice é menor. Se um dos caminhos termina antes
de encontrarmos uma diferença, a precedência não vale. Em particular,
uma posição não precede nenhuma das posições que domina.
Por exemplo, em snowWhite, a posição do sujeito, [0],
precede a do objeto, [1, 1], pois já diferem no primeiro índice.
A função precedence aplica o teste precede aos pares de
posições da árvore.
Defina a precedência imediata, a partir da precedência, do mesmo modo
que a dominância imediata foi definida a partir da dominância. Confira o
resultado na árvore snowWhite.
Antes da noção de c-comando, foi proposta a relação de comando.
Uma posição p comanda q quando nenhuma das duas domina a outra
e o nó com rótulo S mais próximo que domina p também domina
q.
Exercício★★(command)
Defina command supondo que o S mais próximo é sempre a raiz da árvore.
Confira o resultado na árvore snowWhite.