Генерация последовательности случайных токенов, как эта, довольно проста; начиная с символа цели, выберите произвольное расширение незаполненных нетерминалов. Вы, вероятно, хотите какой-то поиск по веткам и границам по любой ветви сгенерированного дерева разбора, чтобы вы могли контролировать глубину / размер.
Но я не вижу большого смысла в тестировании парсеров таким образом, по крайней мере, если ваш генератор парсера напрямую принимает описание языка без контекста. Это происходит, когда вы используете полностью контекстный генератор / инструмент синтаксического анализа, такой как GLR (который мы используем в нашей системе преобразования программ, DMS) или анализатор Earley.
У вас есть другая проблема: если вы хотите протестировать парсер, вам нужно кормить его тем, что он хочет, и, конечно же, это не токены. Теперь вам нужно сгенерировать действительные лексемы для листьев терминала. Это тоже не сложно, но если вы хотите быть осторожным с этим подходом, вы бы написали свою грамматику в стиле без сканера.
Но последняя проблема в том, что для большинства языков трудно найти грамматику без контекста. Так что теперь вы должны отладить свою золотую грамматику тоже; как ты это сделаешь?
Как только вы доберетесь до этой стадии, вы, скорее всего, просто сдадитесь, отладите анализатор и продолжите свою жизнь.
Генерация случайных поддеревьев полезна при восстановлении после ошибок, если вы можете соединить случайное дерево, чтобы исправить исходный поток. Мы делаем упрощенную форму для парсера DMS, что означает, что у нас есть только один механизм обработки ошибок.