Создание n операторов из контекстно-свободных грамматик

Question

Чтобы не изобретать колесо, я хотел бы знать, что уже сделано для создания случайных операторов из контекстно-свободного языка (например, созданного yacc и т. Д.). Эти грамматики в основном предназначены для синтаксического анализа, но, возможно, кто-то сделал несколько поколений для тестирования парсеров? Благодаря

Answer 1

Отъезд this blog post. В принципе, он рандомизирует RHS, выбранный при каждом применении правила.

Answer 2

Там древняя, но все-таки интересная статья here, которая показывает, почему вам нужно несколько больше ограничений для эффективной генерации случайных предложений, чем вы делаете для разбора - это также предлагает простой способ предоставления этих дополнительных ограничений и дает полный пример программы (... в Fortran IV ... но, эй, это is более 40 лет ...! -).

К сожалению, я не знаю более поздних работ по этой теме (или реализаций на более современных языках), но перекодирование пыльной колоды Фортрана на любой язык, который вам больше всего нравится, не должен быть таким сложным, как придумывать эти концепции на собственном ;-) - это только вид уже древних вещей, которые я просматривал в реальных бумажных библиотеках, когда я учился в колледже, и я поражен тем, что онлайн-службы ACM позволили мне найти ссылку Я смутно помнил, так быстро (kudos, ACM! -). Я никогда не делал никаких оригинальных исследований по этому вопросу.

Answer 3

Генерация последовательности случайных токенов, подобных этому, является довольно сложной задачей; начиная с символа цели, выбирайте любое случайное расширение незаполненных нетерминалов. Вероятно, вы хотите, чтобы какой-либо вид ветвления и привязки проходил по любой ветви генерируемого дерева синтаксического анализа, чтобы вы могли контролировать глубину/размер.

Но я не вижу большой ценности при тестировании парсеров таким образом, по крайней мере, если генератор синтаксического анализа не принимает контекстное описание языка напрямую. Это происходит, когда вы используете полный контекстный генератор/инструмент парсера, такой как GLR (который мы используем в нашей системе преобразования программ, DMS) или анализатор Эрли.

У вас есть еще одна проблема: если вы хотите протестировать парсер, вам нужно прокормить его, что он хочет, и, конечно же, это не токены. Теперь вам нужно создать действующие лексемы для листьев терминала. Это тоже не слишком сложно, но вы хотели быть пуристом в этом подходе, и вы напишете свою грамматику в стиле без сканера.

Но последняя проблема заключается в том, что трудно найти контекстную бесплатную грамматику для большинства языков. Итак, теперь вам нужно также отлаживать свою золотую грамматику; как вы это сделаете? Как только вы попадете на этот этап, вы, скорее всего, просто сдадитесь, отлаживаете парсер и продолжаете свою жизнь.

Порождение случайных поддеревн is полезно при восстановлении ошибок, если вы можете сплайсировать в случайном дереве, чтобы исправить исходный поток. Мы делаем упрощенную форму этого для парсера DMS, а это означает, что у нас есть только один блок обработки ошибок.