Техника синтаксического анализа для перечисления всех доступных токенов в любой точке во время анализа

Question

Мне интересно, могу ли я представлять CLI-приглашения, используя грамматику, основанную на CFG или PEG; например, для автоматического создания мастера настройки или опроса. Чтобы добиться этого, анализатор должен запрашивать у пользователя каждый следующий входной токен с учетом того, что он уже ввел. Пример:

customer_info -> "My name is " name_expression " and I'm " %age " years old."
name_expression -> %name %name
                 | %name

name_expression позволяет ввести имя и фамилию или просто одно имя. Строковые константы будут автоматически заполняться приглашением. Эта спецификация скомпилирует следующий пример опыта для гипотетического пользователя:

My name is (enter %name):
>> john
My name is john (1 for "%lastname", 2 for " and I'm "):
>> 2
My name is john and I'm (enter a number):
>> 39
My name is john and I'm [39] years old.
Prompt complete, exiting.

Я прочитал небольшую статью об «обратных парсерах», идея в том, что во время интерактивного диалога все ваши потенциальные ответы выкладываются на каждом этапе разговора (вспомните разговор в видеоигре в стиле RPG с NPC) . Информация об этой технике в Интернете, кажется, скудна, и я не уверен, что она будет делать то, что я хочу полностью.

Я изучил парсеры Эрли, предиктивные парсеры LL и некоторые другие, но изучение каждого из этих кандидатов только для того, чтобы выяснить, подходит ли оно для этого случая, кажется неразумным. Мой вопрос заключается в том, какой метод синтаксического анализа лучше всего позволит мне запросить у пользователя список допустимых токенов с неполным входным предложением?

Хотя мне удобно разбирать рекурсивный спуск и использовать различные генераторы синтаксических анализаторов, я изучал материал только около года, так что извините за мое невежество.

Спасибо.

Answer 1

Эта техника уже существует в LRSTAR , и я думаю, что она встроена в парсеры, сгенерированные ANTLR и Bison / Yacc. Активируется при обнаружении ошибки на входе. Затем в нем перечислены все ожидаемые действительные токены.

Некоторые люди называют это автозаполнением или завершением предложения. Он редко используется для целей, о которых вы спрашиваете. Однако это можно сделать с помощью модифицированного парсера. Синтаксический анализатор должен будет сгенерировать вопросы: «Мое имя - это», а затем прочитать ожидаемый токен, «<имя-первого>» от пользователя.

Это действительно упрощение того, что может сделать парсер. Использование LR-парсера для чего-то такого простого является излишним.

Грамматика может выглядеть так:

Goal      -> Questions <eof>
Questions -> FirstName LastName Street City State Zipcode Age
FirstName -> first name <first_name>
LastName  -> last name <last_name>
Street    -> street <street>
City      -> city <city>
State     -> state <state>
Zipcode   -> zipcode <zipcode>
Age       -> age <age> 

Это верный способ автоматизировать создание вопросников. Парсер сгенерирует слова, которые не заключены в угловые скобки, и попросит пользователя ввести переменную информацию. Или просто поместите угловые скобки в грамматику, чтобы избежать избыточности, и попросите пользователя ввести , и т. Д.

Лучшим и наиболее надежным методом было бы создание синтаксического анализатора Canonical LR (1). Этот вид синтаксического анализатора имеет все ожидаемые токены в каждом состоянии. Не нужно смотреть на другие состояния с помощью сокращений по умолчанию. Пока ваша грамматика не велика, вы должны попробовать синтаксический анализатор CLR (1).

LRSTAR может генерировать синтаксический анализатор CLR (1), который уже имеет встроенный код для вывода списка ожидаемых токенов.

Answer 2

Любая схема синтаксического анализа слева направо, для которой требуется не более одного токена предпросмотра, будет работать нормально при условии, что с этой схемой можно будет проанализировать язык. С реализациями, управляемыми таблицами, вероятно, легче работать при условии, что таблицы синтаксического анализа доступны и документированы (к сожалению, это не относится к большинству генераторов синтаксического анализатора), но вы можете использовать любой синтаксический анализатор черного ящика с интерфейсом «push» и копируемым состоянием, просто перебирая все возможные типы токенов и записывая, какие из них не выдают ошибок.

Логика прогнозирования проще с грамматикой LL (1), чем с грамматикой LR (1), потому что состояние анализатора LL всегда является уникальным элементом. Состояния синтаксического анализатора LR часто представляют собой объединение нескольких элементов, поэтому не совсем понятно, как описать текущий контекст синтаксического анализа. С другой стороны, парсеры LR могут обрабатывать больший набор грамматик.