0xDEADBEEF

RSS odkazy english edition
««« »»»

Rekurze, regexy a kombinátory parserů

7. 9. 2020

Začalo to, když jsem psal nějakou celkem jednoduchou rekurzi, ale nemohl jsem přijít, jak na to. Nešlo o nijak komplikovanou věc, jen mi mozek nefungoval, jak by měl. Snažil jsem se něco parsovat a kdybych ignoroval všechny detaily, speciální případy, odbočky a alternativy, kostra se nesla v duchu:

fs = ( 'X' | '<' fs '>' )*

Nešlo o zpracování textu, ale obecných kolekcí. Symboly '<', 'X' a '>' zastupují objekty s určitými vlastnostmi.

Dokázal jsem to snadno popsat skoro-regexem, ale intelekt nespolupracoval dost, aby to dokázal vyjádřit rekurzí. V noci jsem si sedl s papírem v ruce, daleko od jakéhokoli výpočetního stroje a přemýšlel. Nakonec jsem to ±dal. Rekurze je triviální, jen poněkud rozvleklá.

fs(xs) =
  Nil =>
    Nil, Nil

  'X' :: rest =>
    ss, rs = fs(rest)
    x :: ss, rs

  '<' :: rest =>
    ss, rs = f(rest)
    ss2, rs2 = fs(rs)
    Nest(ss) :: ss2, rs2

  '>' :: rest =>
    Nil, rest

f(xs) =
  'X' :: rest =>
    ss, rs = f(rsest)
    x :: ss, rs

  '<' :: rest =>
    fs(rest)

  '>' :: rest =>
    Nil, rest

To ale není důležité. Nikdy jsem to nepřepsal do formy spustitelného programu, protože začaly být zřejmé korespondence mezi rekurzí a regexem. fs se stará o opakování, porovnání s Nil zachycuje případ nuly opakování v *, druhé dvě větve vystihují alternativy (|), f pak parsuje fs obalené počátečním a koncovým tokenem. Nebo by aspoň zhruba mělo.

Podobnosti vynikají ještě více, když regex přepíšu do této formy:

fs = ε | ( 'X' | '<' fs '>' ) fs

V té pozdní hodině mě napadlo, jestli by nebylo jednodušší místo pachtění s repetitivními rekurzemi, vytvořit interpretr regexů na obecných kolekcích, který by ty rekurze udělal sám (jak padlo v poznámce pod tímhle článkem).

Ukázalo se, že je to snadné (kdyby nebylo, tak tenhle článek nikdy nevznikne). Interpretr 'regexů' je záležitost 67 triviálních řádků Scala kódu a takhle nějak vypadá reálná implementace programu:

trait AST
case class Body(x: String) extends AST
case class Nest(xs: Seq[AST]) extends AST

val f: Node[String, Seq[AST]] =
  Rep(
    Alt(
      One("<") ~> Rec(f) <~ One(">")           map Nest,
      One((l: String) => l != "<" && l != ">") map Body
    )
  )

val (ast, _) = f.apply(Vector("root", "<", "xxx", "<", "22", ">", "xx", "xx", ">", "root2"))

Výsledek je mnohem kratší a jasně je z něj vidět, o co v něm jde.

Tam ale tento příběh nekončí. Scala historicky měla ve standardní knihovně přibaleny kombiátory parserů, ty byly časem vyčleněny do samostatného balíčku, ale stále existují. Umožňují psát parsery přímo ve Scale prostřednictvím DSL, která syntaxí imituje EBNF nebo regexy. Standardně jsou určeny pro parsování textu, ale není těžké je adaptovat pro obecné sekvence objektů. S tím se pak dá stejný problém vyjádřit takhle:

import scala.util.parsing.input._
import scala.util.parsing.combinator._

object MyParser extends Parsers {
  type Elem = String

  def parser: Parser[Seq[AST]] = rep(
    (elem("<") ~> parser <~ elem(">")                      ^^ Nest) |
    (elem("body", { (l: String) => l != "<" && l != ">" }) ^^ Body)
  )
}

val input = readerOf(Vector("root", "<", "xxx", "<", "22", ">", "xx", "xx", ">", "root2"))
val result = MyParser.parser(input)

Jde o stejnou myšlenku a téměř identickou reprezentaci problému, liší se jen jména metod a ostatní podružnosti.

Když to shrnu: Regexové parsování a pattern matching na kolekcích objektů, což je něco, co by se mi mnohokrát hodilo pro uvedení struktury do sekvenčních dat, jsou nejen možné, ale i snadné, jak na implementaci, tak na použití. Problém vyjádřený deklarativně je stručnější a mnohem jasnější.

píše k47 (@kaja47, k47)