Semântica Computacional com Lean

10.5. Consulta ao Léxico e Análise Léxica🔗

namespace Parsing

O léxico associa cada palavra às categorias sintáticas que ela pode ter. Uma palavra pode admitir mais de uma categoria. Por exemplo, that pode ser um determinante ou um pronome relativo. Por isso, a consulta ao léxico devolve uma lista de categorias.

Guardaremos as entradas em listas de Cat, agrupadas por classe de palavras. Cada entrada contém a forma da palavra, seu rótulo, seus traços e sua lista de subcategorização. Como são categorias lexicais, todas têm uma forma no campo Cat.phon, exibida no atributo PHON da AVM. Para consultar uma palavra, selecionaremos as entradas cujo campo contém essa forma.

Começamos pelos pronomes pessoais, reflexivos, interrogativos e relativos. Suas entradas especificam os traços que a forma permite determinar. Por exemplo, she tem terceira pessoa, número singular, gênero feminino e caso nominativo. Já you deixa o número e o caso em aberto. As formas que podem funcionar como interrogativos ou relativos recebem entradas distintas, com rótulos NP ou REL. A lista também inclui os usos de that e which como determinantes, com rótulo DET.

def pronouns : List Cat := [ -- personal pronouns ⟨"i", "NP", [.pers, .fst, .sg, .nom], []⟩, ⟨"me", "NP", [.pers, .fst, .sg, .accOrDat], []⟩, ⟨"we", "NP", [.pers, .fst, .pl, .nom], []⟩, ⟨"us", "NP", [.pers, .fst, .pl, .accOrDat], []⟩, ⟨"you", "NP", [.pers, .snd], []⟩, ⟨"he", "NP", [.pers, .thrd, .sg, .nom, .masc], []⟩, ⟨"him", "NP", [.pers, .thrd, .sg, .accOrDat, .masc], []⟩, ⟨"she", "NP", [.pers, .thrd, .sg, .nom, .fem], []⟩, ⟨"her", "NP", [.pers, .thrd, .sg, .accOrDat, .fem], []⟩, ⟨"it", "NP", [.pers, .thrd, .sg, .neutr], []⟩, ⟨"they", "NP", [.pers, .thrd, .pl, .nom], []⟩, ⟨"them", "NP", [.pers, .thrd, .pl, .accOrDat], []⟩, -- reflexive pronouns ⟨"myself", "NP", [.refl, .sg, .fst, .accOrDat], []⟩, ⟨"ourselves", "NP", [.refl, .pl, .fst, .accOrDat], []⟩, ⟨"yourself", "NP", [.refl, .sg, .snd, .accOrDat], []⟩, ⟨"yourselves", "NP", [.refl, .pl, .snd, .accOrDat], []⟩, ⟨"himself", "NP", [.refl, .sg, .thrd, .accOrDat, .masc], []⟩, ⟨"herself", "NP", [.refl, .sg, .thrd, .accOrDat, .fem], []⟩, ⟨"itself", "NP", [.refl, .sg, .thrd, .accOrDat, .neutr], []⟩, ⟨"themselves", "NP", [.refl, .pl, .thrd, .accOrDat], []⟩, -- wh-pronouns and relatives ⟨"who", "NP", [.wh, .thrd, .mascOrFem], []⟩, ⟨"who", "REL", [.mascOrFem], []⟩, ⟨"whom", "NP", [.sg, .wh, .thrd, .accOrDat, .mascOrFem], []⟩, ⟨"whom", "REL", [.sg, .mascOrFem, .accOrDat], []⟩, ⟨"what", "NP", [.wh, .thrd, .accOrDat, .neutr], []⟩, ⟨"that", "REL", [], []⟩, ⟨"that", "DET", [.sg], []⟩, ⟨"which", "REL", [.neutr], []⟩, ⟨"which", "DET", [.wh], []⟩ ]

Os nomes próprios recebem o rótulo NP e traços de pessoa, gênero e número. O caso fica em aberto, para que a mesma entrada possa ser usada como sujeito ou como objeto. As formas são guardadas em minúsculas, como alice e snowwhite.

Os determinantes, com rótulo DET, podem especificar o número. Assim, every exige singular e all exige plural. Outros, como some e the, deixam esse traço em aberto.

Para expressões como less than e more than, usamos o rótulo DF, de função de determinante. A análise léxica representará cada uma dessas expressões por uma única forma, less_than ou more_than, que pode ser consultada no léxico.

def properNames : List Cat := [ ⟨"snowwhite", "NP", [.thrd, .fem, .sg], []⟩, ⟨"alice", "NP", [.thrd, .fem, .sg], []⟩, ⟨"dorothy", "NP", [.thrd, .fem, .sg], []⟩, ⟨"goldilocks", "NP", [.thrd, .fem, .sg], []⟩, ⟨"littlemook", "NP", [.thrd, .masc, .sg], []⟩, ⟨"atreyu", "NP", [.thrd, .masc, .sg], []⟩ ] def determiners : List Cat := [ ⟨"every", "DET", [.sg], []⟩, ⟨"all", "DET", [.pl], []⟩, ⟨"some", "DET", [], []⟩, ⟨"several", "DET", [.pl], []⟩, ⟨"a", "DET", [.sg], []⟩, ⟨"no", "DET", [], []⟩, ⟨"the", "DET", [], []⟩, ⟨"most", "DET", [.pl], []⟩, ⟨"many", "DET", [.pl], []⟩, ⟨"few", "DET", [.pl], []⟩, ⟨"this", "DET", [.sg], []⟩, ⟨"these", "DET", [.pl], []⟩, ⟨"those", "DET", [.pl], []⟩, -- determiner functions ⟨"less_than", "DF", [.pl], []⟩, ⟨"more_than", "DF", [.pl], []⟩ ]

Os substantivos comuns recebem o rótulo CN. Para cada um, registramos uma forma singular e uma forma plural, com o mesmo gênero e a terceira pessoa. A função noun recebe as duas formas e o gênero e produz as duas entradas.

As formas são fornecidas explicitamente, de modo que podemos usar a mesma função para pares como boy e boys ou man e men. Quando há mais de uma forma para o plural, regular e irregular, acrescentamos uma entrada à lista. É o caso de dwarves, que aparece junto com o plural dwarfs.

def noun (sg pl : String) (g : Feat) : List Cat := [⟨sg, "CN", [.sg, g, .thrd], []⟩, ⟨pl, "CN", [.pl, g, .thrd], []⟩] def commonNouns : List Cat := noun "thing" "things" .neutr ++ noun "person" "persons" .masc ++ noun "boy" "boys" .masc ++ noun "man" "men" .masc ++ noun "girl" "girls" .fem ++ noun "woman" "women" .fem ++ noun "princess" "princesses" .fem ++ noun "dwarf" "dwarfs" .masc ++ [⟨"dwarves", "CN", [.pl, .masc, .thrd], []⟩] ++ noun "giant" "giants" .masc ++ noun "wizard" "wizards" .masc ++ noun "sword" "swords" .neutr ++ noun "dagger" "daggers" .neutr [[CAT CN, PHON boy, GEN masc, NUM sg, PER thrd], [CAT CN, PHON boys, GEN masc, NUM pl, PER thrd]]#eval noun "boy" "boys" .masc

Os auxiliares do nosso fragmento são did e didn't, ambos com rótulo AUX. Para os demais verbos, registramos a forma do passado, com Feat.tense, e a forma infinitiva, com Feat.infl. O infinitivo é a forma sem marca de tempo ou pessoa que encontramos em smile e love. É também a forma usada depois do auxiliar, como em didn't smile. A função verb produz as duas entradas com a mesma lista de subcategorização.

Um verbo intransitivo, como smiled, tem essa lista vazia. Um transitivo, como loved, pede um objeto NP com caso Feat.accOrDat. A categoria objNP representa essa exigência. Para complementos preposicionais, objPP f representa um PP com o traço de preposição f.

Um mesmo verbo pode admitir diferentes listas de complementos. A forma gave tem uma entrada que pede um NP seguido de um PP com Feat.to e outra que pede dois NP. As entradas de sold seguem os mesmos padrões.

Também representamos complementos opcionais com entradas distintas. Uma entrada de kicked pede um NP e um PP com Feat.with, enquanto a outra pede apenas o NP. Para took, o complemento opcional é um PP com Feat.from. Cada um desses padrões vale tanto para a forma do passado quanto para a infinitiva.

def auxiliaries : List Cat := [ ⟨"did", "AUX", [], []⟩, ⟨"didn't", "AUX", [], []⟩ ] def verb (past inf : String) (subcat : List Cat) : List Cat := [⟨past, "VP", [.tense], subcat⟩, ⟨inf, "VP", [.infl], subcat⟩] def objNP : Cat := ⟨"_", "NP", [.accOrDat], []⟩ def objPP (f : Feat) : Cat := ⟨"_", "PP", [f], []⟩ def verbs : List Cat := -- intransitive verb "smiled" "smile" [] ++ verb "laughed" "laugh" [] ++ verb "cheered" "cheer" [] ++ verb "shuddered" "shudder" [] ++ -- transitive verb "loved" "love" [objNP] ++ verb "admired" "admire" [objNP] ++ verb "helped" "help" [objNP] ++ verb "defeated" "defeat" [objNP] ++ -- ditransitive verb "gave" "give" [objNP, objPP .to] ++ verb "gave" "give" [objNP, objNP] ++ verb "sold" "sell" [objNP, objPP .to] ++ verb "sold" "sell" [objNP, objNP] ++ -- an NP and an optional with-PP verb "kicked" "kick" [objNP, objPP .with] ++ verb "kicked" "kick" [objNP] ++ -- an NP and an optional from-PP verb "took" "take" [objNP, objPP .from] ++ verb "took" "take" [objNP] [[CAT VP, PHON loved, VFORM tense, SUBCAT ⟨[CAT NP, CASE accOrDat]⟩], [CAT VP, PHON love, VFORM infl, SUBCAT ⟨[CAT NP, CASE accOrDat]⟩]]#eval verb "loved" "love" [objNP]

Cada preposição tem o rótulo PREP e um traço que identifica qual preposição ela é. Esse traço será transmitido ao PP. Assim, uma exigência de complemento como a de gave pode selecionar um PP com Feat.to. Um complemento com Feat.with entra em conflito com essa exigência.

Registramos também as palavras que conectam orações. A palavra and recebe o rótulo CONJ, e as palavras if e then recebem os rótulos COND e THEN. Essas palavras ligam orações dentro de uma mesma sentença: Alice smiled and Dorothy laughed é uma única sentença, com duas orações. O parser da seção Análise Sintática com Categorias, porém, só tem a regra S → NP VP e não aceita orações coordenadas nem condicionais. As entradas com os rótulos CONJ, COND, THEN e REL serão usadas por regras que acrescentaremos depois.

A função lexicon reúne as listas de entradas e filtra aquelas cuja forma coincide com a palavra consultada. A consulta de that devolve suas duas categorias, e a de gave devolve seus dois padrões de subcategorização. Se a palavra não estiver nas listas, como unicorn, o resultado será a lista vazia.

def prepositions : List Cat := [ ⟨"on", "PREP", [.on], []⟩, ⟨"with", "PREP", [.with], []⟩, ⟨"by", "PREP", [.by], []⟩, ⟨"to", "PREP", [.to], []⟩, ⟨"from", "PREP", [.from], []⟩ ] def connectives : List Cat := [ ⟨"and", "CONJ", [], []⟩, ⟨"if", "COND", [], []⟩, ⟨"then", "THEN", [], []⟩ ] def lexicon (w : String) : List Cat := (pronouns ++ properNames ++ determiners ++ commonNouns ++ auxiliaries ++ verbs ++ prepositions ++ connectives).filter (·.phon == w) [[CAT REL, PHON that], [CAT DET, PHON that, NUM sg]]#eval lexicon "that" [[CAT VP, PHON gave, VFORM tense, SUBCAT ⟨[CAT NP, CASE accOrDat], [CAT PP, PFORM to]⟩], [CAT VP, PHON gave, VFORM tense, SUBCAT ⟨[CAT NP, CASE accOrDat], [CAT NP, CASE accOrDat]⟩]]#eval lexicon "gave" []#eval lexicon "unicorn"

Antes de consultar o léxico, precisamos transformar o texto de entrada em uma lista de palavras. A função scan percorre os caracteres com scanChars e insere um espaço apenas antes de cada ponto, vírgula ou interrogação. Assim, em smiled,, a vírgula pode ser separada da palavra que a precede quando o texto é dividido nos espaços.

O tipo Words abrevia uma lista de textos. A função lexer aplica scan, converte o resultado para minúsculas e o divide nos espaços. Em seguida, remove os textos vazios que essa divisão pode produzir e aplica preproc à lista obtida.

Esperamos que a entrada de lexer seja uma única sentença, já que a nossa gramática analisa uma sentença de cada vez, e não um texto. A divisão de um texto em sentenças caberia a uma função de segmentação, aplicada antes, que não definimos aqui. Uma entrada com mais de uma sentença, como Alice smiled. Dorothy laughed., está fora do que as funções desta seção esperam.

O pré-processamento elimina as vírgulas e remove o ponto ou a interrogação que estiver no fim da lista. Numa só sentença, esse é o único ponto, e por isso o ponto final não tem entrada no léxico.

A função preproc também ajusta a divisão de certas expressões às entradas do léxico. A sequência did not vira didn't, e nobody vira duas palavras, no e person. De modo semelhante, everybody vira every person. No sentido inverso, less than e more than são reunidas nas formas less_than e more_than. As expressões at least e at most também são reunidas, embora as formas at_least e at_most ainda não tenham entradas em lexicon.

Por exemplo, o processamento de Did not everybody smile? produz a lista ["didn't", "every", "person", "smile"].

def scanChars : List Char → List Char | [] => [] | x :: xs => if x ∈ ['.', ',', '?'] then ' ' :: x :: scanChars xs else x :: scanChars xs def scan (s : String) : String := String.ofList (scanChars s.toList) abbrev Words := List String def preproc : Words → Words | [] => [] | ["."] => [] | ["?"] => [] | "," :: xs => preproc xs | "did" :: "not" :: xs => "didn't" :: preproc xs | "nothing" :: xs => "no" :: "thing" :: preproc xs | "nobody" :: xs => "no" :: "person" :: preproc xs | "something" :: xs => "some" :: "thing" :: preproc xs | "somebody" :: xs => "some" :: "person" :: preproc xs | "everything" :: xs => "every" :: "thing" :: preproc xs | "everybody" :: xs => "every" :: "person" :: preproc xs | "less" :: "than" :: xs => "less_than" :: preproc xs | "more" :: "than" :: xs => "more_than" :: preproc xs | "at" :: "least" :: xs => "at_least" :: preproc xs | "at" :: "most" :: xs => "at_most" :: preproc xs | x :: xs => x :: preproc xs def lexer (s : String) : Words := preproc (((scan s).toLower.splitOn " ").filter (· ≠ "")) "Alice smiled , and Dorothy laughed ."#eval scan "Alice smiled, and Dorothy laughed." ["alice", "smiled", "and", "dorothy", "laughed"]#eval lexer "Alice smiled, and Dorothy laughed." ["didn't", "every", "person", "smile"]#eval lexer "Did not everybody smile?"

Uma consulta ao léxico tem tipo String → List Cat. A função lookupWord db w consulta a palavra w no léxico db. Para preparar uma entrada inteira para o parser, precisamos consultar todas as palavras e reunir suas possíveis categorias.

A função collectCats associa cada palavra à lista de categorias devolvida pela consulta. Se alguma dessas listas for vazia, a palavra é desconhecida. Nesse caso, a função devolve um erro que contém as palavras desconhecidas da entrada.

Para representar os dois resultados possíveis, usamos o tipo Except. Em Except ε α, ε é o tipo do erro e α é o tipo do valor produzido em caso de sucesso. O construtor Except.ok guarda esse valor, e Except.error guarda o erro. Aqui, usamos String para o erro e List (List Cat) para o resultado.

Quando todas as palavras são conhecidas, initCats escolhe uma categoria de cada lista, conservando a ordem das palavras. Ela enumera todas as combinações possíveis. Para a lista vazia de palavras, há uma escolha, que também é vazia. Para uma lista não vazia, a função antepõe cada categoria da primeira palavra a cada escolha feita para as demais.

Na entrada Alice admired that girl., a palavra that dá origem a duas escolhas de categorias. O parser poderá testar cada uma para determinar se ela permite uma análise da sentença. Já a entrada com unicorn produz um erro durante a consulta.

def lookupWord (db : String → List Cat) (w : String) : List Cat := db w def initCats : List (List Cat) → List (List Cat) | [] => [[]] | cs :: rests => cs.flatMap fun c => (initCats rests).map (c :: ·) def collectCats (db : String → List Cat) (words : Words) : Except String (List (List Cat)) := let listing := words.map fun x => (x, lookupWord db x) let unknown := (listing.filter (·.2.isEmpty)).map (·.1) if unknown ≠ [] then .error s!"unknown words: {unknown}" else .ok (initCats (listing.map (·.2))) Except.ok [[[CAT NP, PHON alice, GEN fem, NUM sg, PER thrd], [CAT VP, PHON admired, VFORM tense, SUBCAT ⟨[CAT NP, CASE accOrDat]⟩], [CAT REL, PHON that], [CAT CN, PHON girl, GEN fem, NUM sg, PER thrd]], [[CAT NP, PHON alice, GEN fem, NUM sg, PER thrd], [CAT VP, PHON admired, VFORM tense, SUBCAT ⟨[CAT NP, CASE accOrDat]⟩], [CAT DET, PHON that, NUM sg], [CAT CN, PHON girl, GEN fem, NUM sg, PER thrd]]]#eval collectCats lexicon (lexer "Alice admired that girl.") Except.error "unknown words: [unicorn]"#eval collectCats lexicon (lexer "Alice admired the unicorn.")
Exercício★★(init-cats-length)

Prove que o número de escolhas devolvidas por initCats é o produto do número de categorias de cada palavra.

theorem declaration uses `sorry`length_initCats (css : List (List Cat)) : (initCats css).length = (css.map List.length).prod := css:List (List Cat)⊢ (initCats css).length = (List.map List.length css).prod All goals completed! 🐙
end Parsing