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

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

Я думаю, ваша основная проблема в том, что вы не смогли определить конструктор поддерева в субграмматике вашего объекта. (РЕДАКТИРОВАТЬ: 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 для названный AST_OBJ.

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

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

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

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

id_lookup : IDENTIFIER

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

имя_объекта : IDENTIFIER

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

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

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

./muscle < ./test1.m (это был ваш первый тест)

\-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!