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

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 в грамматике испортив поведение парсера [Как-то], и я чувствую, что я игнорирую довольно простой принцип теории языка, который исправит это в jiff, но тот факт, что конфликтов сдвига/сокращения не существует, оставило меня сбитым с толку ,

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

(А вот full grammar file в случае это помогает)

---

UPDATE: Чтобы уточнить, это язык, который компилируется в код время запуска виртуальной машины, вложена в другую систему - игра , в частности. Он имеет скаляры и списки, и нет сложных типов данных. Когда я говорю, что хочу добавить object с языком, это на самом деле неправильно. Я не добавляю поддержку пользовательских типов на мой язык.

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

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

player->name 

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

Answer 1

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

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

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

EDIT: ОК, чем больше я вникнул в него, тем больше я уверен, что лексер не обязательно работает так, как должно быть. Я бы дважды проверял, что поток токенов, которые вы получаете от yylex(), соответствует вашим ожиданиям, прежде чем продолжить. В частности, похоже, что некоторые символы, которые вы считаете специальными (например, «+» и «{»), захватываются некоторыми вашими регулярными выражениями или, по крайней мере, разрешены для передачи идентификаторов.

Answer 2

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

Answer 3

Я думаю, что ваша основная проблема заключается в том, что вы не смогли определить конструктор поддерева в подпрограмме объекта. (EDIT: 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

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

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

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

Answer 5

id_lookup : IDENTIFIER

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

object_name : IDENTIFIER

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

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

Answer 6

Я просто попытался запустить 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!