Semântica computacional com Lean

10.3. Parsers e combinadores de parsers🔗

namespace Parsing abbrev Parser (α β : Type) := StateT (List α) List β example {α β : Type} : Parser α β = (List α → List (β × List α)) := rfl [(1, ['a', 'b'])]#eval (pure 1 : Parser Char Nat).run "ab".toList []#eval (failure : Parser Char Nat).run "ab".toList def symbol {α : Type} [BEq α] (c : α) : Parser α α | x :: xs => if x == c then [(x, xs)] else [] | [] => [] def token {α : Type} [BEq α] (cs : List α) : Parser α (List α) | xs => if cs == xs.take cs.length then [(cs, xs.drop cs.length)] else [] def satisfy {α : Type} (p : α → Bool) : Parser α α | x :: xs => if p x then [(x, xs)] else [] | [] => [] def digit : Parser Char Char := satisfy Char.isDigit [('a', ['b'])]#eval (symbol 'a').run "ab".toList [(['a', 'b'], ['c'])]#eval (token "ab".toList).run "abc".toList [('4', ['2'])]#eval digit.run "42".toList
Exercício★(symbol-satisfy)

Defina symbol', que faz o mesmo que symbol, usando satisfy.

def declaration uses `sorry`symbol' {α : Type} [BEq α] (c : α) : Parser α α := sorry theorem declaration uses `sorry`symbol'_eq_symbol {α : Type} [BEq α] (c : α) (xs : List α) : symbol' c xs = symbol c xs := α:Typeinst✝:BEq αc:αxs:List α⊢ symbol' c xs = symbol c xs All goals completed! 🐙
def just {α β : Type} (p : Parser α β) : Parser α β | xs => (p xs).filter fun (_, ys) => ys.isEmpty example {α β : Type} (p q : Parser α β) (xs : List α) : (p <|> q) xs = p xs ++ q xs := rfl example {α β γ : Type} (p : Parser α β) (q : β → Parser α γ) (xs : List α) : (p >>= q) xs = (p xs).flatMap fun (r, ys) => q r ys := rfl def pD : Parser String String := symbol "every" <|> symbol "some" <|> symbol "no" def pN : Parser String String := symbol "dwarf" <|> symbol "wizard" def pVP : Parser String String := symbol "smiled" <|> symbol "laughed" def pNP : Parser String (List String) := (do let w ← symbol "Alice" <|> symbol "Dorothy" return [w]) <|> (do let d ← pD let n ← pN return [d, n]) def pS : Parser String (List String) := do let np ← pNP let vp ← pVP return np ++ [vp] [(["every", "wizard", "smiled"], [])]#eval pS.run ["every", "wizard", "smiled"] [(["Alice", "laughed"], ["loudly"])]#eval pS.run ["Alice", "laughed", "loudly"] example {α β γ : Type} (f : β → γ) (p : Parser α β) (xs : List α) : (f <$> p) xs = (p xs).flatMap fun (r, ys) => [(f r, ys)] := rfl def digitize : Parser Char Nat := (fun c => c.toNat - '0'.toNat) <$> digit [(4, ['2'])]#eval digitize.run "42".toList def epsilonT {α β : Type} : Parser α (ParseTree α β) := pure .ep def symbolT {α β : Type} [BEq α] (s : α) : Parser α (ParseTree α β) := .leaf <$> symbol s def collect {α β : Type} : List (Parser α β) → Parser α (List β) | [] => pure [] | p :: ps => do let r ← p let rs ← collect ps return r :: rs def parseAs {α β : Type} (label : β) (ps : List (Parser α (ParseTree α β))) : Parser α (ParseTree α β) := .branch label <$> collect ps def det : Parser String (ParseTree String Char) := symbolT "every" <|> symbolT "some" <|> symbolT "no" def cn : Parser String (ParseTree String Char) := symbolT "man" <|> symbolT "woman" def vp : Parser String (ParseTree String Char) := symbolT "smiled" <|> symbolT "laughed" def np : Parser String (ParseTree String Char) := symbolT "Alice" <|> symbolT "Dorothy" <|> parseAs 'N' [det, cn] def sent : Parser String (ParseTree String Char) := parseAs 'S' [np, vp] ["[.S [.N every man] laughed]"]#eval (just sent).run ["every", "man", "laughed"] |>.map (toString ·.1) partial def palindrome : Parser Char (ParseTree Char Char) := epsilonT <|> symbolT 'a' <|> symbolT 'b' <|> symbolT 'c' <|> parseAs 'A' [symbolT 'a', palindrome, symbolT 'a'] <|> parseAs 'A' [symbolT 'b', palindrome, symbolT 'b'] <|> parseAs 'A' [symbolT 'c', palindrome, symbolT 'c'] ["[.A a [.A b c b] a]"]#eval (just palindrome).run "abcba".toList |>.map (toString ·.1) [("[]", "aba"), ("a", "ba"), ("[.A a b a]", "")]#eval palindrome.run "aba".toList |>.map fun (t, ys) => (toString t, String.ofList ys) partial def many {α β : Type} (p : Parser α β) : Parser α (List β) := (do let r ← p let rs ← many p return r :: rs) <|> pure [] [(['a', 'a'], ['b']), (['a'], ['a', 'b']), ([], ['a', 'a', 'b'])]#eval (many (symbol 'a')).run "aab".toList
Exercício★(parse-many-as)

Para ter uma árvore, a repetição precisa ficar sob um rótulo. Defina parseManyAs l p, que aplica p quantas vezes for possível e põe as árvores obtidas sob um nó com rótulo l. Confira o resultado com adjectives, uma sequência de adjetivos sob o rótulo J.

def declaration uses `sorry`parseManyAs {α β : Type} (l : β) (p : Parser α (ParseTree α β)) : Parser α (ParseTree α β) := sorry def adjectives : Parser String (ParseTree String Char) := parseManyAs 'J' (symbolT "happy" <|> symbolT "evil") theorem declaration uses `sorry`adjectives_happy_evil : ((adjectives.run ["happy", "evil", "dwarf"]).map fun (t, ys) => (toString t, ys)) = [("[.J happy evil]", ["dwarf"]), ("[.J happy]", ["evil", "dwarf"]), ("[.J ]", ["happy", "evil", "dwarf"])] := ⊢ List.map (fun x => match x with | (t, ys) => (toString t, ys)) (StateT.run adjectives ["happy", "evil", "dwarf"]) = [("[.J happy evil]", ["dwarf"]), ("[.J happy]", ["evil", "dwarf"]), ("[.J ]", ["happy", "evil", "dwarf"])] All goals completed! 🐙
partial def leftRec : Parser Char (ParseTree Char Char) := parseAs 'A' [leftRec, symbolT 'a'] <|> symbolT 'b' end Parsing