Generowanie instrukcji n z gramatyk bezkontekstowych

Question

Aby nie odkrywać koła, chciałbym się dowiedzieć, co już zostało zrobione w sprawie generowania losowych instrukcji z języka bez kontekstu (np. Języka Yacc itp.). Te gramatyki są przeznaczone głównie do analizowania, ale może ktoś zrobił jakieś pokolenie do testowania analizatorów składni? Dzięki

Answer 1

Zapoznaj się z this blog post. Zasadniczo losuje on RHS wybrany dla każdej aplikacji reguły.

Answer 2

Istnieje starożytna ale nadal ciekawy artykuł here który pokazuje, dlaczego trzeba jeszcze kilka ograniczeń dotyczących skutecznego generowania losowych zdań niż ty do parsowania - to również sugeruje prosty sposób dostarczania tych dodatkowych ograniczeń i daje pełny przykładowy program (... w Fortran IV ... ale, hej, to jest od ponad 40 lat ...! -).

Niestety nie jestem świadomy nowszych prac na ten temat (lub implementacji w nowocześniejszych językach), ale transkodowanie zakurzonej talii Fortranu na dowolny język, który najbardziej lubisz, nie powinien być tak trudny jak wymyślanie tych pojęć. na własną rękę ;-) - to jest po prostu rodzaj już starożytnych rzeczy, które przeglądałem w rzeczywistych bibliotekach papierowych, kiedy byłem w college'u, i jestem zdumiony, że internetowe możliwości wyszukiwania ACM pozwoliły mi zlokalizować odniesienie Niejasno pamiętałem, tak szybko (kudos, ACM!). Nigdy nie przeprowadzałem żadnych oryginalnych badań na ten temat.

Answer 3

Generowanie sekwencji losowych tokenów, takich jak ten, jest w pewnym stopniu skierowane w przód; zaczynając od symbolu celu, wybierz dowolne rozwinięcie niewypełnionych nieterminali. Prawdopodobnie potrzebujesz jakiegoś odgałęzienia i ograniczonego wyszukiwania w dół dowolnej gałęzi wygenerowanego drzewa analizy, abyś mógł kontrolować głębokość/rozmiar.

Ale nie widzę dużej wartości w testowaniu analizatorów składowych w ten sposób, przynajmniej nie, jeśli generator parsera bezpośrednio akceptuje opis języka bez kontekstu. Dzieje się tak, gdy używasz generatora/narzędzia do generowania parsera bez kontekstu, takiego jak GLR (którego używamy w naszym systemie transformacji programów, DMS) lub parsera Earley.

Masz kolejny problem: jeśli chcesz przetestować analizator składni, musisz go podać, czego chce, a na pewno nie jest tokenem. Teraz musisz wygenerować prawidłowe leksemy na liście terminali. To też nie jest trudne, ale chciałeś być purystyczny w tym podejściu, że napiszesz swoją gramatykę w stylu bez skanowania.

Ale ostatni problem polega na tym, że trudno jest znaleźć gramatykę wolną od kontekstu dla większości języków. Teraz musisz również debugować swoją gramatykę złota; jak to zrobisz? Gdy dojdziesz do tego etapu, prawdopodobnie po prostu się poddasz, debugujesz parser i zaczniesz życie.

Generowanie losowych poddrzew jest użyteczne przy odzyskiwaniu po błędzie, jeśli możesz splicować w losowym drzewie, aby naprawić strumień źródłowy. Robimy to w uproszczonej formie dla parsera DMS, co oznacza, że ​​mamy tylko jedną maszynę do obsługi błędów.