10.1. Falando de árvores sintáticas
namespace Parsing
inductive ParseTree (α β : Type) where
| ep
| leaf (a : α)
| branch (b : β) (ts : List (ParseTree α β))
deriving Repr, BEq
def ParseTree.toText {α β : Type}
[ToString α] [ToString β] : ParseTree α β → String
| .ep => "[]"
| .leaf a => toString a
| .branch b ts =>
"[." ++ toString b ++ " " ++
" ".intercalate (ts.map toText) ++ "]"
instance {α β : Type} [ToString α] [ToString β] :
ToString (ParseTree α β) :=
⟨ParseTree.toText⟩
def snowWhite : ParseTree String String :=
.branch "S"
[.branch "NP" [.leaf "Snow White"],
.branch "VP" [.branch "TV" [.leaf "loved"],
.branch "NP" [.leaf "the dwarfs"]]]
#eval IO.println snowWhite
abbrev Pos := List Nat
def pos {α β : Type} (p : ParseTree α β) : List Pos :=
let rec posFrom {α β : Type} :
Nat → List (ParseTree α β) → List Pos
| _, [] => []
| i, t :: ts =>
(pos t).map (i :: ·) ++ posFrom (i + 1) ts
match p with
| .ep => [[]]
| .leaf _ => [[]]
| .branch _ ts => [] :: posFrom 0 ts
#eval pos snowWhite
def subtree {α β : Type} :
ParseTree α β → Pos → ParseTree α β
| t, [] => t
| .branch _ ts, i :: is =>
match ts[i]? with
| some t => subtree t is
| none => .ep
| _, _ :: _ => .ep
def subtrees {α β : Type} (t : ParseTree α β)
: List (ParseTree α β) :=
(pos t).map (subtree t)
#eval IO.println (subtree snowWhite [1])
def posPairs {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
(pos t).flatMap fun p => (pos t).map fun q => (p, q)
def properDominance {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
(posPairs t).filter fun (p, q) => p ≠ q && p <+: q
def dominance {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
(posPairs t).filter fun (p, q) => p <+: q
#eval properDominance snowWhite
A posição p domina imediatamente q 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.
def immDominance {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
sorry
theorem immDominance_snowWhite :
immDominance snowWhite =
[([], [0]), ([], [1]), ([0], [0, 0]), ([1], [1, 0]),
([1], [1, 1]), ([1, 0], [1, 0, 0]),
([1, 1], [1, 1, 0])] := ⊢ immDominance snowWhite =
[([], [0]), ([], [1]), ([0], [0, 0]), ([1], [1, 0]), ([1], [1, 1]), ([1, 0], [1, 0, 0]), ([1, 1], [1, 1, 0])]
All goals completed! 🐙
def sisters : Pos → Pos → Bool
| [i], [j] => i != j
| i :: is, j :: js => i == j && sisters is js
| _, _ => false
def sisterhood {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
(posPairs t).filter fun (p, q) => sisters p q
#eval sisterhood snowWhite
def relComp {γ : Type} [BEq γ] (r s : List (γ × γ)) :
List (γ × γ) :=
(r.flatMap fun (x, y) =>
(s.filter fun (w, _) => y == w).map fun (_, z) =>
(x, z)).eraseDups
def cCommand {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
relComp (sisterhood t) (dominance t)
#eval dominance snowWhite
#eval cCommand snowWhite
def branchingPos {α β : Type} (t : ParseTree α β) :
List Pos :=
let ps := pos t
ps.filter fun p =>
ps.contains (p ++ [0]) && ps.contains (p ++ [1])
#eval branchingPos snowWhite
Dois lemas sobre posições irmãs
theorem sisters_length (p r : Pos)
(h : sisters p r = true) : p.length = r.length := p:Posr:Posh:sisters p r = true⊢ List.length p = List.length r
induction p generalizing r with
r:Posh:sisters [] r = true⊢ [].length = List.length r All goals completed! 🐙
i:Natis:List Natih:∀ (r : Pos), sisters is r = true → is.length = List.length rr:Posh:sisters (i :: is) r = true⊢ (i :: is).length = List.length r
cases r with
i:Natis:List Natih:∀ (r : Pos), sisters is r = true → is.length = List.length rh:sisters (i :: is) [] = true⊢ (i :: is).length = [].length All goals completed! 🐙
i:Natis:List Natih:∀ (r : Pos), sisters is r = true → is.length = List.length rj:Natjs:List Nath:sisters (i :: is) (j :: js) = true⊢ (i :: is).length = (j :: js).length
cases is with
i:Natj:Natjs:List Natih:∀ (r : Pos), sisters [] r = true → [].length = List.length rh:sisters [i] (j :: js) = true⊢ [i].length = (j :: js).length
cases js with
i:Natj:Natih:∀ (r : Pos), sisters [] r = true → [].length = List.length rh:sisters [i] [j] = true⊢ [i].length = [j].length All goals completed! 🐙
i:Natj:Natih:∀ (r : Pos), sisters [] r = true → [].length = List.length rk:Natks:List Nath:sisters [i] (j :: k :: ks) = true⊢ [i].length = (j :: k :: ks).length All goals completed! 🐙
i:Natj:Natjs:List Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rh:sisters (i :: i' :: is') (j :: js) = true⊢ (i :: i' :: is').length = (j :: js).length
cases js with
i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rh:sisters (i :: i' :: is') [j] = true⊢ (i :: i' :: is').length = [j].length All goals completed! 🐙
i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rk:Natks:List Nath:sisters (i :: i' :: is') (j :: k :: ks) = true⊢ (i :: i' :: is').length = (j :: k :: ks).length
i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → (i' :: is').length = List.length rk:Natks:List Nath:(i == j) = true ∧ sisters (i' :: is') (k :: ks) = true⊢ (i :: i' :: is').length = (j :: k :: ks).length
All goals completed! 🐙
theorem sisters_not_prefix (p r : Pos)
(h : sisters p r = true) : ¬ p <+: r := p:Posr:Posh:sisters p r = true⊢ ¬p <+: r
induction p generalizing r with
r:Posh:sisters [] r = true⊢ ¬[] <+: r All goals completed! 🐙
i:Natis:List Natih:∀ (r : Pos), sisters is r = true → ¬is <+: rr:Posh:sisters (i :: is) r = true⊢ ¬i :: is <+: r
cases r with
i:Natis:List Natih:∀ (r : Pos), sisters is r = true → ¬is <+: rh:sisters (i :: is) [] = true⊢ ¬i :: is <+: [] All goals completed! 🐙
i:Natis:List Natih:∀ (r : Pos), sisters is r = true → ¬is <+: rj:Natjs:List Nath:sisters (i :: is) (j :: js) = true⊢ ¬i :: is <+: j :: js
cases is with
i:Natj:Natjs:List Natih:∀ (r : Pos), sisters [] r = true → ¬[] <+: rh:sisters [i] (j :: js) = true⊢ ¬[i] <+: j :: js
cases js with
i:Natj:Natih:∀ (r : Pos), sisters [] r = true → ¬[] <+: rh:sisters [i] [j] = true⊢ ¬[i] <+: [j] All goals completed! 🐙
i:Natj:Natih:∀ (r : Pos), sisters [] r = true → ¬[] <+: rk:Natks:List Nath:sisters [i] (j :: k :: ks) = true⊢ ¬[i] <+: j :: k :: ks All goals completed! 🐙
i:Natj:Natjs:List Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rh:sisters (i :: i' :: is') (j :: js) = true⊢ ¬i :: i' :: is' <+: j :: js
cases js with
i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rh:sisters (i :: i' :: is') [j] = true⊢ ¬i :: i' :: is' <+: [j] All goals completed! 🐙
i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i :: i' :: is') (j :: k :: ks) = true⊢ ¬i :: i' :: is' <+: j :: k :: ks
i:Natj:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:i = j ∧ sisters (i' :: is') (k :: ks) = true⊢ ¬i :: i' :: is' <+: j :: k :: ks
i:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i' :: is') (k :: ks) = true⊢ ¬i :: i' :: is' <+: i :: k :: ks
cons.cons.cons.cons i:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i' :: is') (k :: ks) = true⊢ ¬(i = i ∧ i' :: is' <+: k :: ks)
intro ⟨_, hp⟩ cons.cons.cons.cons i:Nati':Natis':List Natih:∀ (r : Pos), sisters (i' :: is') r = true → ¬i' :: is' <+: rk:Natks:List Nath:sisters (i' :: is') (k :: ks) = trueleft✝:i = ihp:i' :: is' <+: k :: ks⊢ False
exact ih _ h hp All goals completed! 🐙
Suponha que p c-comanda q: uma irmã r de p domina q. Prove que
p não domina q e que q não domina p.
Dica: um prefixo de q que não é mais longo do que outro prefixo de q
é prefixo dele (List.prefix_of_prefix_length_le), e um prefixo do mesmo
comprimento é a própria lista (List.IsPrefix.eq_of_length).
theorem cCommand_not_dominates (p r q : Pos)
(hs : sisters p r = true) (hd : r <+: q) :
¬ p <+: q := by p:Posr:Posq:Poshs:sisters p r = truehd:r <+: q⊢ ¬p <+: q
sorry All goals completed! 🐙
theorem cCommand_not_dominated (p r q : Pos)
(hs : sisters p r = true) (hd : r <+: q) :
¬ q <+: p := by p:Posr:Posq:Poshs:sisters p r = truehd:r <+: q⊢ ¬q <+: p
sorry All goals completed! 🐙
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.
def mutualCCommand {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
sorry
theorem mutualCCommand_snowWhite :
mutualCCommand snowWhite = sisterhood snowWhite := by ⊢ mutualCCommand snowWhite = sisterhood snowWhite
sorry All goals completed! 🐙
def precede : Pos → Pos → Bool
| i :: is, j :: js => i < j || (i == j && precede is js)
| _, _ => false
def precedence {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
(posPairs t).filter fun (p, q) => precede p q
#eval precedence snowWhite
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.
def immPrecedence {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
sorry
theorem immPrecedence_snowWhite :
immPrecedence snowWhite =
[([0], [1]), ([0], [1, 0]), ([0], [1, 0, 0]),
([0, 0], [1]), ([0, 0], [1, 0]),
([0, 0], [1, 0, 0]), ([1, 0], [1, 1]),
([1, 0], [1, 1, 0]), ([1, 0, 0], [1, 1]),
([1, 0, 0], [1, 1, 0])] := by ⊢ immPrecedence snowWhite =
[([0], [1]), ([0], [1, 0]), ([0], [1, 0, 0]), ([0, 0], [1]), ([0, 0], [1, 0]), ([0, 0], [1, 0, 0]), ([1, 0], [1, 1]),
([1, 0], [1, 1, 0]), ([1, 0, 0], [1, 1]), ([1, 0, 0], [1, 1, 0])]
sorry All goals completed! 🐙
Defina command supondo que o S mais próximo é sempre a raiz da árvore.
Confira o resultado na árvore snowWhite.
def command {α β : Type} (t : ParseTree α β) :
List (Pos × Pos) :=
sorry
theorem command_snowWhite :
(command snowWhite).length = 28 := by ⊢ (command snowWhite).length = 28
sorry All goals completed! 🐙
end Parsing