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

1

jakiś przykład?

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ś...

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?

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 :]

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.

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.

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?

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.

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ń.

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ę.

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.

0

Ja polecam ANTLR: https://www.antlr.org/

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