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