Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #32240 > unrolled thread
| Started by | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| First post | 2019-01-04 00:17 +0100 |
| Last post | 2019-01-06 13:23 +0100 |
| Articles | 3 — 2 participants |
Back to article view | Back to pl.comp.programming
Porównywanie gramatyk Borneq <borneq@antyspam.hidden.pl> - 2019-01-04 00:17 +0100
Re: Porównywanie gramatyk J-23 <Baczeklu@poczta.fm> - 2019-01-05 22:53 +0100
Re: Porównywanie gramatyk Borneq <borneq@antyspam.hidden.pl> - 2019-01-06 13:23 +0100
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2019-01-04 00:17 +0100 |
| Subject | Porównywanie gramatyk |
| Message-ID | <q0m55q$cok$1@node1.news.atman.pl> |
Dość nietrywialny problem. O ile porównanie plików tekstowych jest szeroko znane, to jak jest z gramatykami zdefiniowanymi przez rozszerzone produkcje EBNF, takie ze znakami + (1 i więcej razy potarzaj) czy * (0 i więcej razy potarzaj) ? Przy porównywaniu ma nie zważać na kolejność reguł ani na kolejność produkcji w regule. Tak samo na nazwy nieterminalne. Trochę co innego niż stwierdzenie, że dwie gramatyki generują taki sam język, bo nie tylko tak trzeba porównać, ale i wskazać różnice, na szczęście dla większych zmian generujących ten sam język (na przykład eliminacja rekurencji, łączenie reguł) można stwierdzać różnice, było by to nawet wskazane, byle by szybko "łapać synchronizację". Co takiego aby można było stwierdzić jakie różnice są w różnych plikach gramatyk dla tego samego języka, Pascala,Javy, C,itd.. a także porównać np. definicje C i C++ - jakie podobieństwa i jakie różnice, a także Javy i C# itp.(to ostatnie oznacza że musiałby być w pewnym stopniu ślepy również na symbole terminalne generujące inne języki, byle by mógł wyłapać różnice w strukturze i filozofii języka - ale to trudniejszy warunek niż porównywanie dla tego samego języka)
[toc] | [next] | [standalone]
| From | J-23 <Baczeklu@poczta.fm> |
|---|---|
| Date | 2019-01-05 22:53 +0100 |
| Message-ID | <5c31274b$0$496$65785112@news.neostrada.pl> |
| In reply to | #32240 |
W dniu 04.01.2019 o 00:17, Borneq pisze: > O ile porównanie plików tekstowych jest szeroko znane, to jak jest z > gramatykami zdefiniowanymi przez rozszerzone produkcje EBNF, takie ze > znakami + (1 i więcej razy potarzaj) czy * (0 i więcej razy potarzaj) ? Daj więcej szczegółów bo to co napisałeś to tylko tyle wiadomo że chcesz przetworzyć jakąś gramatyke ale pod jakim kątem? to już wychodzi masło maślane bez konkretnego przykładu Pozdrawiam J-23
[toc] | [prev] | [next] | [standalone]
| From | Borneq <borneq@antyspam.hidden.pl> |
|---|---|
| Date | 2019-01-06 13:23 +0100 |
| Message-ID | <q0svfv$suq$1@node1.news.atman.pl> |
| In reply to | #32271 |
W dniu 05.01.2019 o 22:53, J-23 pisze: > Daj więcej szczegółów bo to co napisałeś to tylko tyle wiadomo że chcesz > przetworzyć jakąś gramatyke ale pod jakim kątem? to już wychodzi masło > maślane bez konkretnego przykładu Na przykład: mam dwie gramatyki Pascala z różnych źródeł, bardzo się różnią tekstowo - zupełnie inne nazwy nieterminali, chcę zobaczyć czym faktycznie się różnią. Być może jest to problem NP-zupełny. A może wręcz coś jeszcze gorszego, bo problemy NP-zupełne nie można wykonać w czasie wielomianowym, ale sprawdzenie poprawności jest w czasie wielomianowym, natomiast tu nie tylko nie można by tego wykonać ale nawet sprawdzić poprawności w czasie wielomianowym.
[toc] | [prev] | [standalone]
Back to top | Article view | pl.comp.programming
csiph-web