Возможно ли иметь грамматику, в которой "ключевое слово" также можно рассматривать как "не ключевое слово"?
У меня есть следующая грамматика в ANTLRWorks 1.4. Я играю с идеями по реализации парсера в создателе текстовой приключенческой игры, где пользователь будет указывать различные допустимые команды для своей игры.
grammar test;
parse : cmd EOF;
cmd : putSyn1 gameObject inSyn1 gameObject;
putSyn1 : Put | Place | Drop ;
inSyn1 : In | Into | Within;
gameObject : det obj;
det : The | A | An | ;
obj : Word obj | Word;
Space : (' ' | '\t' | '\r' | '\n'){$channel=HIDDEN;};
Put : 'put';
Place : 'place';
Drop : 'drop';
In : 'in';
Into : 'into';
Within : 'within';
The : 'the';
A : 'a';
An : 'an';
Word : ('a'..'z' | 'A'..'Z')+;
Я просто чувствую различные тонкости (как я сделал здесь).
На этот раз, используя ANTLR, мне интересно, могу ли я проанализировать ввод, такой как:
put wood in fire place
То есть "дрова" и "камины" являются объектами игры выше. Тем не менее, "место" также является синонимом "положить". Так что это будет в равной степени справедливо:
place wood in fire place
ANTLR выдает мне исключение NoViableAltException при попытке проанализировать последний токен "place". Я хочу распознать "камин" как игровой объект.
Так возможно ли такое в ANTLR? Это возможно в грамматике?
На стороне, я работаю над ручной реализацией, которая использует странную пользовательскую структуру данных с битами NFA, Dictionary и еще много чего. Но мне все еще нужно больше времени и я должен пожертвовать несколькими клетками мозга, чтобы разработать необходимые алгоритмы поиска и вставки.
Но если это возможно в ANTLR, я мог бы просто использовать сгенерированный файл C#, да?
2 ответа
Конечно. PL/1 известен тем, что не имеет никаких зарезервированных слов, например, вы можете использовать ключевые слова (например, IF) в качестве имени переменной везде, где это не нужно в качестве ключевого слова:
IF IF = 1 THEN ELSE=3; ELSE END=4;
Построить парсер, который делает это сложнее. Вы не можете сделать это "просто" в лексере, потому что он не знает контекста, в котором идентификатор может быть ключевым словом или нет.
Есть несколько выходов. Когда идентификатор, подобный сущности, найден:
1) Заставьте лексера спросить парсер: " Вы хотите ключевое слово сейчас? ". В этом случае создайте ключевое слово. Заставить парсер сотрудничать здесь может быть сложно. Может также случиться так, что парсер не знает, потому что он должен видеть больше входных данных, чтобы принять решение. Рассмотрим знаменитое утверждение формата Фортрана:
FORMAT ( A1, I2, ... ) X
Вы не можете сказать, когда видите слово "FORMAT", является ли оно ключевым словом или идентификатором; Вы должны сканировать произвольно далеко вперед, чтобы осмотреть X. Если X - это не конец инструкции, слово FORMAT - это имя идентификатора массива; если X - конец статистики, это ключевое слово FORMAT и оператор.
2) Выдать и ключевое слово (если идентификатор совпадает с одним) и идентификатор, и заставить парсер попробовать оба. Большинство парсеров не справятся с этим хорошо, но парсеры GLR могут справиться с этим с апломбом, если они разумно спроектированы. Это решает проблему FORMAT тривиально, подталкивая к возможностям синтаксического анализа синтаксического анализатора. (ANTLR - это не GLR. Наш инструментарий реинжиниринга программного обеспечения DMS имеет именно такой анализатор GLR, и мы часто используем этот прием).
3) Поместите все подобные идентификатору вещи в хеш-таблицу. Используйте парсер рекурсивного спуска (ANTLR - один); когда этот синтаксический анализатор хочет ключевое слово, он просто проверяет полученный идентификатор, чтобы убедиться, что это ключевое слово, в котором он нуждается. Если ему не нужно ключевое слово, он просто использует идентификатор в качестве идентификатора. Я не знаю, как реализовать этот трюк с ANTLR, так как я не использую его. Это не справится с делом "не могу решить без предвкушения".
Я бы обработал что-то подобное с помощью лексера вместо парсера - пусть лексер выполняет "максимальное жевание", поэтому он распознает "камин" как один токен и распознает "место" как отдельный токен, если он не сразу предшествует "огонь".
При этом парсер не должен замечать, что одна и та же последовательность символов во входных данных образует все или часть двух совершенно отдельных токенов.