Need help with shift/reduce conflicts

[senyai]

Hi!

I'm trying to parse 1 2 | 3 4 to

OR(
  a =
    AND(
      a = 1
      b = 2
    )
  b =
    AND(
      a = 3
      b = 4
    )
)

The code is working as expected, but I get this warning: 2 shift/reduce conflicts, which I interpret as that my rules aren't all right. The docs say that precedence is the way to solve similar issues, but I don't see how I could apply precedence here. Would appreciate any help.

from sly import Lexer, Parser
from collections import namedtuple


class TestLexer(Lexer):
    tokens = { NUMBER, OR }
    ignore = ' \t'

    NUMBER  = r'\d+'
    OR    = r'\|'


class TestParser(Parser):
    debugfile = 'testparser.out'
    tokens = TestLexer.tokens

    @_('number_group number')
    def number_group(self, p):
        AND = namedtuple('AND', ('a', 'b'))
        return AND(p[0], p[1])

    @_('number_group OR number_group')
    def number_group(self, p):
        OR = namedtuple('OR', ('a', 'b'))
        return OR(p[0], p[2])

    @_('number')
    def number_group(self, p):
        return p[0]

    @_('NUMBER')
    def number(self, p):
        return p.NUMBER


def debug_repr(node, level=0):
    if hasattr(node, '_fields'):
        yield '  ' * level + f'{node.__class__.__name__}('
        for field in sorted(node._fields):
            val = getattr(node, field)
            if isinstance(val, (int, str)):
                yield '  ' * (level + 1) + f'{field} = {val}'
            else:
                yield '  ' * (level + 1) + f'{field} ='
                yield from debug_repr(val, level + 2)
        yield '  ' * level + ')'
    else:
        yield '  ' * level + repr(node)


if __name__ == '__main__':
    lexer = TestLexer()
    parser = TestParser()
    print("\n".join(debug_repr(parser.parse(lexer.tokenize('1 2 | 3 4')))))

[senyai]

Not easy, but I made it work.

class TestParser(Parser):
    tokens = TestLexer.tokens

    # precedence - lower = higher priority
    precedence = (
        ('left', OR),
        ('left', AND),
    )

    @_('expr')
    def number_group(self, p):
        return p[0]

    @_('NUMBER')
    def expr(self, p):
        return p[0]

    @_('number_group OR number_group')
    def number_group(self, p):
        OR = namedtuple('OR', ('a', 'b'))
        return OR(p[0], p[2])

    @_('expr expr %prec AND')
    def expr(self, p):
        AND = namedtuple('AND', ('a', 'b'))
        return AND(p[0], p[1])

I learn from examples, and an example like this would've helped me a lot with understanding %prec and expr expr -> expr.

[bugengine]

Hello. I added an improvement to SLY in a separate branch that gives extra information about the conflicts. Here is the output for your original source file:

shift/reduce conflict for OR in state 6 resolved as shift
   shift using rule number_group -> number_group . OR number_group
   ╭╴
   │ number_group OR number_group ♦ OR number_group
   │                 ╰number_group────────────────╯
   │ ╰number_group────────────────────────────────╯
   ╰╴

   reduce using rule number_group -> number_group OR number_group .
   ╭╴
   │ number_group OR number_group ♦ OR number_group
   │ ╰number_group────────────────╯
   │ ╰number_group────────────────────────────────╯
   ╰╴

This first example shows the two possible interpretation of a sequence with two ORs: the two possible interpretations are to construct the second OR and use the result as the second operand in the first OR. The second option is to first construct the leftmost OR expression and use the result as the left operand in the second OR expression. I believe both results are correct mathematically, the default of the parser is the option labeled SHIFT (so, the first option).
This sort of conflicts is normally solved by associativity rule; operators in programming language normally specify an associativity for the operators that indicate in which order they will be reduced. For instance C++ shows that the OR operator has a left-to-right precedence.

shift/reduce conflict for NUMBER in state 6 resolved as shift
   shift using rule number -> . NUMBER
   ╭╴
   │ number_group OR number_group ♦ NUMBER
   │                              ╰number╯
   │                 ╰number_group───────╯
   │ ╰number_group───────────────────────╯
   ╰╴

   reduce using rule number_group -> number_group OR number_group .
   ╭╴
   │ number_group OR number_group ♦ NUMBER
   │ ╰number_group────────────────╯ ╰number╯
   │ ╰number_group─────────────────────────╯
   ╰╴

In this second conflict, the debug output shows the two possible interpretation of a sequence containing an OR operation followed by an AND operation. The two options are to either execute the AND operation first, using the result as the right operand to the OR operation, or to first reduce the OR operation and use the result as the left operand of the AND operation.
This sort of conflict is normally solved by the priority component of the precedence rule.

Your solution works as you have assigned a higher priority to the AND operator over the OR operator, and you have specified left associativity for each operator, thus making a priority call for all the conflicts.