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

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


parsing yacc lalr ply
person Alex Gaynor    schedule 27.11.2009    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

person DigitalRoss    schedule 27.11.2009
comment
К сожалению, без использования определенного правила шаблона грамматика становится более неоднозначной и не работает в более тривиальных случаях. Я думаю, вы правы, что мне нужно добавить контекст, что легко для простых случаев (встроенные типы или типы, определенные в этом файле), но сложно для вещей, включенных с помощью моей системы импорта. Ну что ж :) - person Alex Gaynor; 27.11.2009