Странная проблема с контекстно-свободной грамматикой

Question

Я начинаю с хорошо сформированной (и хорошо работающей) грамматики для языка.Переменные, бинарные операторы, вызовы функций, списки, циклы, условные выражения и т. Д. К этой грамматике я хотел бы добавить то, что я называю конструкцией object:

object
  : object_name ARROW more_objects
  ;

more_objects
  : object_name
  | object_name ARROW more_objects
  ;

object_name
  : IDENTIFIER
  ;

Дело в том, чтобывозможность доступа к скалярам, ​​вложенным в объекты.Например:

car->color
monster->weapon->damage
pc->tower->motherboard->socket_type

Я добавляю object как primary_expression:

primary_expression
  : id_lookup
  | constant_value
  | '(' expression ')'
  | list_initialization
  | function_call
  | object
  ;

---

Теперь вот пример сценария:

const list = [ 1, 2, 3, 4 ];
for var x in list {
  send "foo " + x + "!";
}
send "Done!";

До добавления нетерминала object в качестве primary_expression все это солнце и щенки.Даже после того, как я добавлю это, Бизон не жалуется.Не сообщается о сдвиге и / или уменьшении конфликтов.И сгенерированный код компилируется без звука.Но когда я пытаюсь запустить приведенный выше пример сценария, мне говорят error on line 2: Attempting to use undefined symbol '{' on line 2.

Если я изменю сценарий на:

var list = 0;
for var x in [ 1, 2, 3, 4 ] {
  send "foo " + x + "!";
}
send "Done!";

Тогда я получу error on line 3: Attempting to use undefined symbol '+' on line 3.

Очевидно, что присутствие object в грамматике портит поведение синтаксического анализатора [SOMEhow], и я чувствую, что игнорирую довольно простой принцип теории языка, который исправит это в один миг, но тот факт, чтоРазве любые конфликты сдвига / уменьшения не оставили меня в замешательстве.

Есть ли лучший (грамматически) способ написать эти правила?Что мне не хватает?Почему нет никаких конфликтов?

(А вот и полный файл грамматики , если он помогает)

---

ОБНОВЛЕНИЕ: Кпоясните, этот язык, который компилируется в код, выполняемый виртуальной машиной, встроен в другую систему, в частности, в игру.У него есть скаляры и списки, и нет сложных типов данных.Когда я говорю, что хочу добавить object s к языку, это на самом деле неправильно.Я не добавляю поддержку пользовательских типов в свой язык.

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

Поэтому, когда на моем языке я пишу:

player->name

Это кодируется только компилятором.«player» и «name» не являются традиционными identifier s, потому что они не добавляются в таблицу символов, и с ними ничего не делается во время компиляции, кроме как для преобразования запроса имени игрока в 3-адресный код.

Answer 1

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

Answer 2

Вы не получаете конфликтов сдвига / уменьшения, потому что ваши правила, использующие object_name и more_objects, являются праворекурсивными, а не леворекурсивными правилами, которые Yacc (Bison) обрабатывает наиболее естественно.

В классическом Yacc вы обнаружите, что можете исчерпать пространство стека с достаточно глубокой вложенностью нотации 'object->name->what->not'. Bison расширяет свой стек во время выполнения, поэтому вам нужно исчерпать память, что в наши дни намного сложнее, чем когда у машин было несколько мегабайт памяти (или меньше).

Одним из результатов правильной рекурсии является то, что никаких сокращений не происходит, пока вы не прочитаете последнее из имен объектов в цепочке (или, точнее, один символ за этим). Я вижу, что вы использовали правильную рекурсию и со своим правилом statement_list - и в ряде других мест.

Answer 3

Я думаю, что ваша главная проблема в том, что вы не смогли определить конструктор поддерева в вашей подпрограмме объекта.(РЕДАКТИРОВАТЬ: OP говорит, что он оставил семантические действия для объекта из своего примера текста. Это не меняет следующий ответ).

Возможно, вам придется искать объекты вПорядок встречается тоже.Возможно, вы намеревались:

primary_expression 
   : constant_value                                        { $$ = $1; } 
   | '(' expression ')'                                    { $$ = $2; } 
   | list_initialization                                   { $$ = $1; } 
   | function_call                                         { $$ = $1; } 
   | object                                                { $$ = $1; } 
   ; 



object
   : IDENTIFIER    { $$ = LookupVariableOrObject( yytext ); } 
   |  object ARROW IDENTIFIER  { $$ = LookupSubobject( $1, yytext ); } 
   ; 

Я предполагаю, что если кто-то сам встречает идентификатор X, ваша интерпретация по умолчанию такова, что это имя переменной.Но, если вы встретите X -> Y, то даже если X является именем переменной, вам нужен объект X с подобъектом Y.

Что LookupVarOrObject делает, это ищет Крайний левый идентификатор, обнаруженный для определения, является ли он переменным (и возвращает ли оно, по существу, то же значение, что и idlookup, который должен создать узел AST типа AST_VAR), или посмотреть, является ли оно допустимым именем объекта, и вернуть узел AST, помеченный как AST_OBJили жаловаться, если идентификатор не является одним из них.

Что LookupSuboject делает, так это проверяет свой левый операнд, чтобы убедиться, что это AST_OBJ (или AST_VAR, имя которого совпадает с именемобъект).и жаловаться, если это не так.Если это так, то он ищет объект yytext-child названного AST_OBJ.

РЕДАКТИРОВАТЬ: Основываясь на комментариях к обсуждению в другом ответе, правая рекурсия в исходной грамматике OP может быть проблематичной, если семантические проверки OPпроверить глобальное состояние лексера (yytext).Это решение является леворекурсивным и не столкнется с этой конкретной ловушкой.

Answer 4

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

1. Получите наименьший (с точки зрения количества токенов) возможный рабочий ввод и наименьший возможный нерабочий ввод на основе правил, которые вы ожидаете применить.
2. Создайте копию файла грамматики, включающую только проблемные правила и как можно меньше других поддерживающих правил (т. Е. Вам нужен язык, который допускает только построение последовательностей, состоящих из правил object и more_object , к которому присоединилась стрелка. Работает ли это так, как вы ожидаете?
3. Работает ли правило, в котором оно вложено, как вы ожидаете? Попробуйте заменить object на другое очень простое правило (используя некоторые токены, которых нет в других местах) и посмотрите, можете ли вы включить эти токены, не нарушая все остальное.
4. Запустите бизона с --report=all. Проверьте выходные данные, чтобы попытаться отследить добавленные вами правила и состояния, на которые они влияют. Попробуйте удалить эти правила и повторите процесс - что изменилось? Это очень часто отнимает много времени, и это огромная боль, но это хорошее последнее средство. Я рекомендую карандаш и немного бумаги.

Глядя на структуру вывода вашей ошибки - '+' распознается как маркер идентификатора и поэтому рассматривается как символ. Возможно, стоит проверить свой лексер, чтобы увидеть, как он обрабатывает идентификаторы токенов. Вы можете просто случайно получить слишком много. В качестве дальнейшего метода отладки вы можете рассмотреть возможность преобразования некоторых из этих литералов токенов (например, '+', '{' и т. Д.) В реальные токены, чтобы отчеты об ошибках Bison могли помочь вам немного больше.

РЕДАКТИРОВАТЬ: ОК, чем больше я копался в этом, тем больше я убежден, что лексер не обязательно работает, как должно быть. Я бы дважды проверил, что поток токенов, которые вы получаете от yylex (), соответствует вашим ожиданиям, прежде чем продолжить. В частности, похоже, что набор символов, которые вы считаете специальными (например, '+' и '{'), захватывается некоторыми вашими регулярными выражениями или, по крайней мере, разрешается передавать для идентификаторов.

Answer 5

Я только что попробовал запустить muscl в Ubuntu 10.04, используя bison 2.4.1, и я смог запустить оба ваших примера без синтаксических ошибок.Я предполагаю, что у вас есть ошибка в вашей версии зубров.Дайте мне знать, если я как-то неправильно запускаю ваш парсер.Ниже приведен вывод из первого примера, который вы дали.

./muscle < ./test1.m (this was your first test)

\-statement list
  |-declaration (constant)
  | |-symbol reference
  | | \-list (constant)
  | \-list
  |   |-value
  |   | \-1
  |   |-value
  |   | \-2
  |   |-value
  |   | \-3
  |   \-value
  |     \-4
  |-loop (for-in)
  | |-symbol reference
  | | \-x (variable)
  | |-symbol reference
  | | \-list (constant)
  | \-statement list
  |   \-send statement
  |     \-binary op (addition)
  |       |-binary op (addition)
  |       | |-value
  |       | | \-foo 
  |       | \-symbol reference
  |       |   \-x (variable)
  |       \-value
  |         \-!
  \-send statement
    \-value
      \-Done!

 +-----+----------+-----------------------+-----------------------+
 |   1 | VALUE    | 1                     |                       |
 |   2 | ELMT     | @1                    |                       |
 |   3 | VALUE    | 2                     |                       |
 |   4 | ELMT     | @3                    |                       |
 |   5 | VALUE    | 3                     |                       |
 |   6 | ELMT     | @5                    |                       |
 |   7 | VALUE    | 4                     |                       |
 |   8 | ELMT     | @7                    |                       |
 |   9 | LIST     |                       |                       |
 |  10 | CONST    | @10                   | @9                    |
 |  11 | ITER_NEW | @11                   | @10                   |
 |  12 | BRA      | @14                   |                       |
 |  13 | ITER_INC | @11                   |                       |
 |  14 | ITER_END | @11                   |                       |
 |  15 | BRT      | @22                   |                       |
 |  16 | VALUE    | foo                   |                       |
 |  17 | ADD      | @16                   | @11                   |
 |  18 | VALUE    | !                     |                       |
 |  19 | ADD      | @17                   | @18                   |
 |  20 | SEND     | @19                   |                       |
 |  21 | BRA      | @13                   |                       |
 |  22 | VALUE    | Done!                 |                       |
 |  23 | SEND     | @22                   |                       |
 |  24 | HALT     |                       |                       |
 +-----+----------+-----------------------+-----------------------+
foo 1!
foo 2!
foo 3!
foo 4!
Done!

Answer 6

id_lookup : ИДЕНТИФИКАТОР

формально идентичен

object_name : ИДЕНТИФИКАТОР

и имя_объекта будет принимать все, что не делает id_lookup, поэтому assertLookup (yytext); вероятно, работает на всем, что может выглядеть как IDENTIFIER и не принимается по другому правилу, просто чтобы выбрать между 2, а затем имя_объекта не может быть принято, потому что одиночный просмотр запрещает это.

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