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

В 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 при попытке проанализировать последний токен «места». Я хочу распознать «камин» как gameObject.

Возможно ли такое в ANTLR? Возможно ли это в грамматике?

Попутно я работаю над ручной реализацией, в которой используется странная настраиваемая структура данных с битами NFA, словаря и многого другого. Но мне все еще нужно больше времени, и я должен пожертвовать несколькими клетками мозга, чтобы разработать необходимые алгоритмы поиска и вставки.

Но если это возможно в ANTLR, я мог бы просто использовать сгенерированный файл C #, да?


antlr parsing grammar antlrworks
person Rao    schedule 02.10.2010    source источник
comment
возможно, ваш пример - это просто пример, но для этого, в частности, вы можете использовать «камин» (одно слово) вместо «камин»   -  person Nathan Koop    schedule 02.10.2010
comment
Что ж, это текстовый адвенчур creator, и я надеюсь позволить пользователю иметь в своих созданных комнатах игровые объекты, состоящие из нескольких слов.   -  person Rao    schedule 02.10.2010

Ответы (2)


arrow_upward
4
arrow_downward

Конечно. PL / 1 известен тем, что не имеет зарезервированных слов, например, вы можете использовать ключевые слова (например, IF) в качестве имени переменной везде, где это не нужно в качестве ключевого слова:

 IF  IF = 1  THEN  ELSE=3;  ELSE END=4;

Создать синтаксический анализатор, который сделает это, сложнее. Вы не можете сделать это «просто» в лексере, потому что он не знает контекста, в котором идентификатор может быть ключевым словом или нет.

Есть несколько выходов. Когда найден такой идентификатор, как объект:

1) Заставьте лексер спрашивать синтаксический анализатор: «вы хотите ключевое слово сейчас?». В этом случае создайте ключевое слово. Заставить синтаксический анализатор сотрудничать здесь может быть сложно. Также может быть, что синтаксический анализатор не знает, потому что ему нужно больше входных данных, чтобы принять решение. Рассмотрим известное заявление формата Fortran:

     FORMAT ( A1, I2, ... ) X

Когда вы видите слово «FORMAT», вы не можете определить, является ли оно ключевым словом или идентификатором; вы должны сколь угодно далеко продвинуться вперед, чтобы проверить X. Если X не является концом оператора, слово FORMAT - это имя идентификатора массива; если X - конец состояния, это ключевое слово и оператор FORMAT.

2) Выведите и ключевое слово (если идентификатор совпадает с одним), и идентификатор, и заставьте синтаксический анализатор попробовать оба. Большинство парсеров не справятся с этим должным образом, но парсеры GLR могут справиться с этим апломбом, если они спроектированы разумно. Это тривиально решает проблему FORMAT, вставляя в функцию упреждающего анализа синтаксического анализатора. (ANTLR не является GLR. Наш DMS Software Reengineering Toolkit имеет именно такой GLR parser, и мы часто пользуемся этим трюком).

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

person Ira Baxter    schedule 02.10.2010
comment
Спасибо за хороший ответ. Вариант 2) - это то, что происходит в моей попытке ручной реализации. - person Rao; 02.10.2010

arrow_upward
1
arrow_downward

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

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

person Jerry Coffin    schedule 02.10.2010
comment
Мне нужно подумать над этим. В настоящее время (не думая с точки зрения ANTLR) моя цель - распознать только синтаксис команд, например, поместить GO в GO, и позволить GO вообще быть чем угодно. Затем каждый GO будет сопоставлен с объектами, находящимися в комнате. То есть имена реальных игровых объектов не будут присутствовать в файле грамматики. - person Rao; 02.10.2010