Czy teoria języków formalnych przydaje się pisząc lexery/parsery/generatory syntax tree?

Odpowiedz Nowy wątek
2019-08-09 23:50
1

jakiś przykład?

edytowany 2x, ostatnio: WeiXiao, 2019-08-09 23:55

Pozostało 580 znaków

2019-08-10 00:30
1

Przy obecnej obfitości gotowych bibliotek i parserów wystarcza w zasadzie sama gramatyka w BNF, a gotowy kod robi resztę. W swoim projekcie używałem https://github.com/lark-parser/lark (Python) i byłem zadowolony. Przy innej okazji pisząc na potrzeby projektu parser w Go zaadaptowałem ten tutorial. W obu przypadkach nie było potrzeby odświeżać teoretycznej wiedzy ze studiów. Jet tego więcej - Boost Spirit, Lex&Yacc itd., gotowe do zastosowania w wielu praktycznych przypadkach. Z drugiej strony, te przedmioty z teorii automatów i języków i teorii kompilatorów te lata temu na tych studiach przerabiałem i zaliczyłem, więc może dlatego nie miałem jakichś problemów z konstruowaniem gramatyk, bo po prostu zostało. No ale jak ktoś opanuje pisanie wyrażeń regularnych (co programista raczej znać i umieć powinien) to chyba nie powinien mieć problemu.

Teoria przyda się pewnie jak zechcesz sam napisać jakąś bibliotekę albo jeśli masz jakieś specyficzne potrzeby. Trudno mi powiedzieć co w przypadku, gdy zechcesz implementować własny kompilator/interpreter bo we własny język programowania akurat nigdy się nie bawiłem. Może kiedyś...

edytowany 1x, ostatnio: Spearhead, 2019-08-10 00:31
Czemu "kiedyś"? - Silv 2019-08-10 00:58
W sensie, że możę kiedyś w przyszłości spróbuję - Spearhead 2019-08-10 00:59
No rozumiem, ale czemu kiedyś, a nie teraz? - Silv 2019-08-10 01:01
Jest mnóstwo innych rzeczy jakie mnie interesują, a czasu po odjęciu życia zawodowego i osobistego już nie ma tyle co kiedyś. Teraz np uczę się Rust-a i jednocześnie bawię w gamedev, wgryzając się w shadery GLSL-a. - Spearhead 2019-08-10 01:06
A, jeśli tak, to w porządku. - Silv 2019-08-10 01:06
<zapisuje sobie w notatniku, żeby mu przypomnieć, gdy będzie mieć więcej czasu> - Silv 2019-08-10 01:10

Pozostało 580 znaków

2019-08-10 00:53
0

Chodzi o to, że moje aktualne zabawy z przetwarzaniem tekstu, budowaniem "drzewek" oraz szukaniu jakiegoś większego sensu na podstawie relacji elementów tego drzewa opierają się głównie o jakieś pętelki ify itd.

function get_something(string text)
{
    var values = new List<string>();

    var value = "";
    var startReading = false;

    for (int i=0; i<text.Length; i++)
    {
        if (text[i] == '<')
        {
            startReading = true;
            continue;
        }

        if (text[i] == '>')
        {
            values.Add(value);
            value = "";
            startReading = false;
            continue;
        }

        if (startReading)
        {
            value += text[i];
        }
    }
}

itd. itd.

i mimo, że działa to poprawnie, to wydaje mi się dość amatorskim podejściem (no chociaż chyba inaczej się tego nie da zrobić ręcznie :D), ale z drugiej strony wolę sobie to samemu napisać niż gotowców używać.

Jakbym chciał reimplementnąć podstawy regexa typu znajdź wszystkie znaki pomiędzy "<" i ">", to warto byłoby do tego usiąść? czy to kompletnie nie te zagadnienia, a po prostu zwykłe działanie na tekście?

edytowany 11x, ostatnio: WeiXiao, 2019-08-10 01:09
Poczytaj o tej teorii. - Silv 2019-08-10 00:57

Pozostało 580 znaków

2019-08-10 02:22
1

Wygodnym rozwiązaniem byłyby pewnie parser combinators, np: http://www.lihaoyi.com/fastparse/

Naklepany na szybko przykład:

package parsing

import fastparse.NoWhitespace._
import fastparse._

object BetweenXmlTags {
  private def betweenTags[_: P]: P[Seq[String]] =
    P(CharPred(_ != '<').rep ~ "<" ~ CharPred(_ != '>').rep.! ~ ">").rep

  private def run(input: String): Unit =
    println(parse(input, betweenTags(_)))

  def main(args: Array[String]): Unit = {
    run("ala ma <kota> i <psa> hey") // Seq("kota", "psa")
    run("<ala>ma</kota>")            // Seq("ala", "/kota")
    run("<a<b>c>")                   // Seq("a<b")
    run(">a>b<c>d<e<f>")             // Seq("c", "e<f")
  }
}

Parser jest jak widać jednolinijkowy :]


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 2x, ostatnio: Wibowit, 2019-08-10 02:43
Z czytelnością tak średnio bym powiedział. Z pattern matchingiem daje radę ładniej https://ideone.com/hPBw1A - hauleth 2019-08-10 11:23
To miał być żart? Tego jednolinijkowca bym zrozumiał kilka razy szybciej niż te rozdmuchane pattern matchingi. - Wibowit 2019-08-10 11:33
Widać to zależy od doświadczenia. Bo O ile ja jeszcze jako tako rozumiem co tutaj jest napisane, to mimo wszystko pattern matching, który podałem jest dla mnie czytelniejszy. W ostateczności zachowanie będzie identyczne. Kwestia doświadczenia z różnymi językami. - hauleth 2019-08-10 15:00
A jak zaimplementujesz przy pomocy pattern matchingu backtracking? - Wibowit 2019-08-10 15:37
Przekazujesz 2 argumenty "gdzie się cofnąć" oraz "obecny match" - hauleth 2019-08-10 18:54

Pozostało 580 znaków

2019-08-10 11:19
2

Czy się przydaje? Tak, bo zwykle i tak musisz napisać gramatykę, a tego nie da się za bardzo zrobic nie rozumiejąc ;) Plus w zależności od generatora którego używasz, będziesz potrzebował LL, LR albo SLR i znów jeśli nie rozumiesz o co chodzi, to nie będziesz umiał "poprawić" swojej gramatyki.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2019-08-10 11:59
1
Shalom napisał(a):

Czy się przydaje? Tak, bo zwykle i tak musisz napisać gramatykę, a tego nie da się za bardzo zrobic nie rozumiejąc ;) Plus w zależności od generatora którego używasz, będziesz potrzebował LL, LR albo SLR i znów jeśli nie rozumiesz o co chodzi, to nie będziesz umiał "poprawić" swojej gramatyki.

Świat nie kończy się na LR, LL, SLR i tym podobnych. Podałem przecież przykład na parser combinator. Parser combinator można porównać w zasadzie do regexpa. Główną różnicą jest to, że regexp jest statyczny, a parser combinator jest konstruowany dynamicznie. Przykładowo na wejściu mamy ciągi do rozpoznania:

  • "a0a"
  • "a1ya"
  • "a2yya"
  • "a3yyya"
  • "a4yyyya"
  • itd w aż do Int.Max

Regexpem tego nie da się ogarnąć, gdyż byłby po prostu zbyt wielki nawet dla tak prostego przykładu. Natomiast parser combinator spokojnie sobie poradzi, bo możemy napisać coś w stylu: "a(\d+)y{groups.last.toInt}a". Parser wygenerowany przez parser combinators sprawdza swoje reguły po kolei i dzięki temu na bieżąco może generować kolejne. Gdy dana reguła zawiedzie to następuje backtracking do miejsca gdzie można wykorzystać inną regułę. Parser combinators nie wykrywają nieścisłości w gramatyce (parser po prostu wypróbowuje kolejne reguły, nie sprawdzając czy jest jakakolwiek niejednoznaczność spowodowana np dwiema regułami, które pasują w danym przypadku). Za to są bardzo proste.

Ważną cechą parser combinators jest to, że nie są ograniczone do gramatyk bezkontekstowych (LR, LL, LALR, etc są ograniczone do gramatyk bezkontekstowych). Może być to wadą i zaletą. Zaleta jest taka, że daje to większą elastyczność co pokazałem na przykładzie. Wadą jest w ogólnym przypadku brak możliwości wykrycia niejednoznaczności w gramatyce.
https://en.wikipedia.org/wiki/Parser_combinator

Shortcomings and solutions
Parser combinators, like all recursive descent parsers, are not limited to the context-free grammars and thus do no global search for ambiguities in the LL(k) parsing Firstk and Followk sets. Thus, ambiguities are not known until run-time if and until the input triggers them. In such cases, the recursive descent parser may default (perhaps unknown to the grammar designer) to one of the possible ambiguous paths, resulting in semantic confusion (aliasing) in the use of the language. This leads to bugs by users of ambiguous programming languages, which are not reported at compile-time, and which are introduced not by human error, but by ambiguous grammar. The only solution that eliminates these bugs is to remove the ambiguities and use a context-free grammar.

Z drugiej strony, ręcznie zaklepane parsery takie jak np zrobił @WeiXiao kilka postów wcześniej, też nie mają wbudowanego wykrywania niejednoznaczności (i nie są ograniczone do gramatyk bezkontekstowych). Wykrycie niejednoznaczności jest w nich trudniejsze niż w parser combinators, bo kodu jest więcej.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 11x, ostatnio: Wibowit, 2019-08-10 12:09

Pozostało 580 znaków

2019-08-10 15:14
0
Shalom napisał(a):

Czy się przydaje? Tak, bo zwykle i tak musisz napisać gramatykę, a tego nie da się za bardzo zrobic nie rozumiejąc ;) Plus w zależności od generatora którego używasz, będziesz potrzebował LL, LR albo SLR i znów jeśli nie rozumiesz o co chodzi, to nie będziesz umiał "poprawić" swojej gramatyki.

Jako że w temacie jestem kompletnie zielony, to pójdę przykładami:

Załóżmy, że mamy taką składnie (wymyślona notacja)

<Thread/Post> IfThread<title> <content>

input:

Thread "Jaki Język programowania najlepszy??" "Czy java nadal najlepsza?"
Post "tak"
Post "nie"
Post "zależy"
Thread "15k w data science - is this real??" "www.data-science.bootcamp"
Post "potwierdzam, po miesiącu na tym bootcampie pracuje jako senór data engineer"
Thread "ddd to najlepsze co mogło powstać?" "https://martinfowler.com/tags/domain%20driven%20design.html"
Post "tak"

I generujemy na podstawie tego takie coś

{
    Threads:
    [
        {
            Id: 1
            Title: "Jaki Język programowania najlepszy??"
            Posts:
            [
                {
                    Id: 1
                    Content: "Czy java nadal najlepsza?"
                },      
                {
                    Id: 2
                    Content: "tak"
                },      
                {
                    Id: 3
                    Content: "nie"
                },  
                {
                    Id: 4
                    Content: "zależy"
                },
            ]
        },
        {
            Id: 2
            Title: "15k w data science - is this real??"
            Posts:
            [
                {
                    Id: 1
                    Content: "www.data-science.bootcamp"
                },      
                {
                    Id: 2
                    Content: "potwierdzam, po miesiącu na tym bootcampie pracuje jako senór data engineer"
                }
            ]
        },  
        {
            Id: 3
            Title: "ddd to najlepsze co mogło powstać?"
            Posts:
            [
                {
                    Id: 1
                    Content: "https://martinfowler.com/tags/domain%20driven%20design.html"
                },      
                {
                    Id: 2
                    Content: "tak"
                }
            ]
        }
    ]
}

i takie coś można łatwo od ręki napisać, a jak można byłoby tu zastosować w/w przez ciebie zagadnienia? czy to zbyt trywialny przykład na coś "ciekawszego" do użycia?

edytowany 12x, ostatnio: WeiXiao, 2019-08-10 15:30

Pozostało 580 znaków

2019-08-10 15:30
1

Przecież to co pokazałeś można by parsować regexpem i to dość trywialnie. Ale spróbuj sparsować tak jakiś uproszczony język programowania (if, else, while, proste wyrażenia arytmetyczne no i oczywiście bez ograczenia na poziomy zagnieżdżenia) i zrobić interpreter.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2019-08-10 15:31
no wiem że prosto, nawet napisałem na końcu. Dlatego się zastanawiałem czy w ogóle wypadałoby użyć czegoś z j/formalnych tutaj - WeiXiao 2019-08-10 15:32
Wyrażenia regularne to część języków formalnych :P - Shalom 2019-08-10 15:48

Pozostało 580 znaków

2019-08-10 16:19
1

Podkręciłem lekko trudność i dodałem (z gotowca) pełne parsowanie stringów włącznie z unikodem i innymi escape'ami:

import fastparse.MultiLineWhitespace._
import fastparse._
import parsing.ParsingFacilities._

object ForumParser {
  case class ForumThread(title: String, content: String, posts: Seq[ForumPost])

  case class ForumPost(content: String)

  def main(args: Array[String]): Unit = {
    val Parsed.Success(forumThreads, _) = parse(input, parseThreads(_))
    forumThreads.foreach(println)
  }

  def parseThreads[_: P]: P[Seq[ForumThread]] =
    P("Thread" ~ string.! ~ string.! ~ parseTopics).map(ForumThread.tupled).rep

  def parseTopics[_: P]: P[Seq[ForumPost]] =
    P("Post" ~ string.!.map(ForumPost)).rep

  private val input =
    """Thread "Jaki \"Język\" programowania najlepszy??" "Czy java nadal najlepsza?"
      |Post "ta\u0372k"
      |Post "ni\te"
      |Post "za\\leży"
      |Thread "15k w data science - is this real??" "www.data-science.bootcamp"
      |Post "potwierdzam, po miesiącu na tym bootcampie pracuje jako senór data engineer"
      |Thread "ddd to najlepsze co mogło powstać?" "https://martinfowler.com/tags/domain%20driven%20design.html"
      |Post "tak"
      |""".stripMargin
}

object ParsingFacilities {
  def stringChars(c: Char): Boolean = c != '\"' && c != '\\'

  def space[_: P]: P[Unit] = P(CharsWhileIn(" \r\n", 0))

  def hexDigit[_: P]: P[Unit] = P(CharIn("0-9a-fA-F"))

  def unicodeEscape[_: P]: P[Unit] =
    P("u" ~ hexDigit ~ hexDigit ~ hexDigit ~ hexDigit)

  def escape[_: P]: P[Unit] = P("\\" ~ (CharIn("\"/\\\\bfnrt") | unicodeEscape))

  def strChars[_: P]: P[Unit] = P(CharsWhile(stringChars))

  def string[_: P]: P[String] =
    P("\"" ~/ (strChars | escape).rep.! ~ "\"")
}

Na wyjściu dostajemy:

ForumThread("Jaki \"Język\" programowania najlepszy??","Czy java nadal najlepsza?",ArrayBuffer(ForumPost("taͲk"), ForumPost("ni\te"), ForumPost("za\\leży")))
ForumThread("15k w data science - is this real??","www.data-science.bootcamp",ArrayBuffer(ForumPost("potwierdzam, po miesiącu na tym bootcampie pracuje jako senór data engineer")))
ForumThread("ddd to najlepsze co mogło powstać?","https://martinfowler.com/tags/domain%20driven%20design.html",ArrayBuffer(ForumPost("tak")))

Samo mięcho, tzn wysokopoziomowa logika do parsowania to tylko:

  def parseThreads[_: P]: P[Seq[ForumThread]] =
    P("Thread" ~ string.! ~ string.! ~ parseTopics).map(ForumThread.tupled).rep

  def parseTopics[_: P]: P[Seq[ForumPost]] =
    P("Post" ~ string.!.map(ForumPost)).rep

W object ParsingFacilities znajduje się logika do parsowania stringów.

Moim zdaniem, im trudniejszy problem to tym fajniej te parser combinators (przynajmniej te co pokazałem powyżej) wyglądają w porównaniu do innych rozwiązań.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 4x, ostatnio: Wibowit, 2019-08-10 16:27
brakuje id ;) i mocno overengineered - WeiXiao 2019-08-10 17:23
Co jest przeinżynierowane? - Wibowit 2019-08-10 17:26

Pozostało 580 znaków

2019-08-10 18:36
1

Wersja poprawiona (jest id w ForumPost) i uproszczona (stringi nie mogą mieć wyescape'owanych ciapek w środku, bo to podobno przeinżynierowanie?):

import fastparse.MultiLineWhitespace._
import fastparse._

object ForumParser {
  case class ForumThread(title: String, content: String, posts: Seq[ForumPost])
  case class ForumPost(id: Int, content: String)

  def main(args: Array[String]): Unit = {
    val forumThreads = parse(input, parseThreads(_)).get.value
    forumThreads.foreach(println)
  }

  def parseThreads[_: P]: P[Seq[ForumThread]] =
    P("Thread" ~/ string.! ~ string.! ~ parseTopics).map(ForumThread.tupled).rep

  def parseTopics[_: P]: P[Seq[ForumPost]] =
    P("Post" ~/ string.!).rep.map(_.zipWithIndex.map {
      case (content, id) => ForumPost(id + 1, content)
    })

  def string[_: P]: P[String] =
    P("\"" ~/ CharsWhile(_ != '"').rep.! ~ "\"")

  val input: String =
    """Thread "Jaki Język programowania najlepszy??" "Czy java nadal najlepsza?"
      |Post "tak"
      |Post "nie"
      |Post "zależy"
      |Thread "15k w data science - is this real??" "www.data-science.bootcamp"
      |Post "potwierdzam, po miesiącu na tym bootcampie pracuje jako senór data engineer"
      |Thread "ddd to najlepsze co mogło powstać?" "https://martinfowler.com/tags/domain%20driven%20design.html"
      |Post "tak"
      |""".stripMargin
}

Wynik:

ForumThread("Jaki Język programowania najlepszy??","Czy java nadal najlepsza?",ArrayBuffer(ForumPost(1,"tak"), ForumPost(2,"nie"), ForumPost(3,"zależy")))
ForumThread("15k w data science - is this real??","www.data-science.bootcamp",ArrayBuffer(ForumPost(1,"potwierdzam, po miesiącu na tym bootcampie pracuje jako senór data engineer")))
ForumThread("ddd to najlepsze co mogło powstać?","https://martinfowler.com/tags/domain%20driven%20design.html",ArrayBuffer(ForumPost(1,"tak")))

Teorii tutaj wiele nie trzeba, w zasadzie wystarczy mieć ogarnięte regexpy (i wpływ ich konstrukcji na wydajność) oraz przerobić tutorial do FastParse od Li Haoyi.

Jeśli ktoś ma bardziej zwięzłe czy wygodniejsze rozwiązanie to chętnie się przyjrzę.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2019-08-10 18:52

Pozostało 580 znaków

2019-08-11 10:34
2

jakiś przykład?

function get_something(string text)

Teoria się przydaje choćby do tego by poprawnie nazywać pojęcia. Tu wyraźnie zabrakło ci nazwy skoro nazwałeś to po prostu “something”. Za chwilę zabraknie ci innego słowa i już będziesz miał dwa somethingi o różnym znaczeniu.

edytowany 1x, ostatnio: Azarien, 2019-08-11 10:35

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 0, botów: 1

Robot: Yandex