Jeśli masz model gramatyki w znormalizowanej formie (wszystkie zasady jak ten):
LHS = RHS1 RHS2 ... RHSn ;
i język PrettyPrinter (np AST narzędzie do konwersji tekstu), można zbudować jeden z nich dość z łatwością.
Po prostu zacznij od symbolu celu jako drzewa jednostek.
Repeat until no nonterminals are left:
Pick a nonterminal N in the tree;
Expand by adding children for the right hand side of any rule
whose left-hand side matches the nonterminal N
dla terminali, które przenoszą wartości (na przykład nazw zmiennych, liczby, ciągi, ...) musisz wygenerować losową zawartość.
Powikłaniem powyższego algorytmu jest to, że nie kończy się on w sposób wyraźny. To, co naprawdę chcesz zrobić, to wybrać jakiś limit rozmiaru twojego drzewa i uruchomić algorytm, aż znikną wszystkie nieterminale lub przekroczysz limit. W drugim przypadku cofnij, cofnij ostatnią zamianę i spróbuj czegoś innego. Dzięki temu uzyskasz ograniczoną liczbę głębokości - najpierw wyszukaj AST o ustalonym rozmiarze.
Następnie wystarczy wydrukować wynik. Jest to prettyprinter part, które trudno jest uzyskać.
[Możesz zbudować wszystkie te rzeczy samodzielnie, w tym ślicznotkę, ale to sporo pracy. Buduję narzędzia, które obejmują wszystkie te maszyny bezpośrednio w sparametryzowanym języku; zobacz mój bio].
Nieprzyjemny problem nawet z dobrze uformowanymi AST polega na tym, że mogą one być bezsensowne; możesz utworzyć deklarację liczby całkowitej X i przypisać jej literalną wartość, dla języka, który na to nie pozwala.Prawdopodobnie można wyeliminować niektóre proste problemy, ale semantyka języka może być niewiarygodnie złożona, za przykład należy uznać C++. Zapewnienie, że skończysz z semantycznie znaczącym programem, jest niezwykle trudne; w istocie, musisz przeanalizować wynikowy tekst, a także wykonać rozpoznanie nazwy i typu/sprawdzenia. W przypadku C++ potrzebny jest kompletny front-end C++.
Ale ... dlaczego?: p Przypuszczam, że mógłbyś - jeśli podążasz za specyfikacją CFG, masz gwarancję znalezienia co najmniej syntaktycznie poprawnego kodu C. Ale ja nie wiem. Sądzę, że ktokolwiek kiedykolwiek próbował coś takiego zrobić - prawdopodobnie musiałbyś napisać coś w rodzaju odwrotnego parsera ... – Robert
Pracowałem z kilkoma ... (to żart; Kocham wszystkich moich kolegów). –
Czy jest jakiś powód, dla którego ktoś chciałby losowego, bezsensownego kodu źródłowego, który (najprawdopodobniej) nie zrobiłby nic? –