Возможно ли иметь грамматику, в которой «ключевое слово» также можно рассматривать как «не ключевое слово»? - PullRequest
Новая
       49

Возможно ли иметь грамматику, в которой «ключевое слово» также можно рассматривать как «не ключевое слово»?

5 голосов
/ 02 октября 2010

У меня есть следующая грамматика в 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 ]

4 голосов
/ 02 октября 2010

Конечно. 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, так как я не использую его. Это не справится с делом «не могу решить без предвкушения».

1 голос
/ 02 октября 2010

Я бы обработал что-то подобное с помощью лексера вместо парсера - пусть лексер выполняет «максимальное жевание», поэтому он распознает «камин» как один токен и распознает только «место» как отдельныйтокен, если ему непосредственно не предшествует «огонь».

При этом парсеру не нужно замечать, что одна и та же последовательность символов во входных данных образует все или часть двух совершенно отдельных токенов.

...