Разрешение конфликта сдвига / уменьшения в синтаксическом анализаторе LALR

Question

Я использовал PLY для создания парсера для моего языка, однако у меня возник конфликт сдвига / уменьшения, который вызывает у меня некоторые проблемы. Мой язык имеет универсальные типы с синтаксисом аля шаблоны C ++. Так что сейчас у меня есть правила, такие как:

    expression : expression LESS expression %prec COMPARISON
    expression : template
    template : NAME
             | NAME LESS templates GREATER
    templates : template
              | templates COMMA template

Однако я обнаружил, что он не может разобрать:

a < 2

(что является проблемой по понятным причинам). Ниже приведен вывод отладочной информации:

PLY: PARSE DEBUG START

State  : 0
Stack  : . <Token: 'NAME' 'a'>
Action : Shift and goto state 42

State  : 42
Stack  : NAME . <Token: 'LESS' '<'>
Action : Shift and goto state 81

State  : 81
Stack  : NAME LESS . <Token: 'NUMBER' '2'>
ERROR: Error  : NAME LESS . <Token: 'NUMBER' '2'>

Если мне нужно больше моего парсера, я могу его предоставить. Благодаря.

РЕДАКТИРОВАТЬ: Одним из решений, которое мне было предложено, было создание типов их токена. Это потребует немного работы, потому что мой язык не использует систему включения препроцессора, такую ​​как C / C ++, однако я думаю, что это все еще возможно, однако я бы предпочел решение, ограниченное грамматикой.

Answer 1

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

• Добавить контекст
  Распознавать при синтаксическом анализе типа, устанавливать флаг или вызывать метод, чтобы сообщить об этом сканеру, а затем возвращать другой символ терминала для < и > в этом случае.
• Упрощенная грамматика
  В качестве альтернативы вы можете просто использовать унифицированный синтаксис выражения / шаблона для части создания шаблона и исключать в коде что-либо, кроме синтаксиса шаблона. Синтаксический анализатор является наименее способной частью вашей системы, поэтому старайтесь по возможности вносить изменения в код. (Нет ограничений по коду, много ограничений по yacc.)

Я не говорю, что это ваш единственный выбор. Если бы вы провели дни, ломая голову над таблицами состояний и подправляя грамматику до такой степени, что yacc доволен этим, я думаю, вы были бы «успешны», но это того не стоит. В этот момент вы можете написать рекурсивный синтаксический анализатор. (RD - это больше строк кода, и вы не можете увидеть грамматику, аккуратно разложенную в BNFish yacc, но, по крайней мере, вы можете анализировать что угодно, и вы никогда не будете увязать в головоломках «это не работает».)

Имеет ли Python какой-либо эквивалент Treetop * Ruby * в Ruby? Это решило бы проблему. Функция %glr-parser Bison также может «решать» такие проблемы, хотя и довольно BFI.