这个 SLY 程序中的 shift/reduce 冲突是什么？

Question

我正在将代码从 pyparsing 移植到 SLY，这是一个 lambda calc 语法。我有这个规则

from sly import Lexer, Parser


class Lex(Lexer):
    tokens = {ID, LAMB, DOT, LPAR, RPAR}
    ID = r"[a-z]"
    LAMB = r"λ"
    DOT = r"\."
    LPAR = r"\("
    RPAR = r"\)"

    ignore = " \t"


class Par(Parser):
    """
    term : abst
         | lamb
         | ID
         | "(" term ")"
    abst | term ID
    lamb | "λ" ID "." term
    """
    tokens = Lex.tokens
    debugfile = 'lamb.out'


    @_("abst", "lamb", "ID")
    def term(self, p):
        return p[0]

    @_("LPAR term RPAR")
    def term(self, p):
        return p.term

    @_("term ID")
    def abst(self, p):
        return (p.term, p.ID)

    @_("LAMB ID DOT term")
    def lamb(self, p):
        return ("λ", p.ID, p.term)


def parse(input_: str):
    return Par().parse(Lex().tokenize(input_))


from pprint import pprint

pprint(parse("x y z"))
pprint(parse("λx.x"))
pprint(parse("(λx.λy.x y) a b"))

我知道这个语法是错误的，因为它强制将 ID 作为应用程序的最后一个元素，而这不是 lambda 演算所必需的。但我的问题是要了解发生在最后一个状态的 shift reduce 冲突，这里是调试输出。

Grammar:

Rule 0     S' -> term
Rule 1     term -> LPAR term RPAR
Rule 2     term -> ID
Rule 3     term -> lamb
Rule 4     term -> abst
Rule 5     abst -> term ID
Rule 6     lamb -> LAMB ID DOT term

Terminals, with rules where they appear:

DOT                  : 6
ID                   : 2 5 6
LAMB                 : 6
LPAR                 : 1
RPAR                 : 1
error                : 

Nonterminals, with rules where they appear:

abst                 : 4
lamb                 : 3
term                 : 1 5 6 0


state 0

    (0) S' -> . term
    (1) term -> . LPAR term RPAR
    (2) term -> . ID
    (3) term -> . lamb
    (4) term -> . abst
    (6) lamb -> . LAMB ID DOT term
    (5) abst -> . term ID
    LPAR            shift and go to state 2
    ID              shift and go to state 3
    LAMB            shift and go to state 6

    term                           shift and go to state 1
    lamb                           shift and go to state 4
    abst                           shift and go to state 5

state 1

    (0) S' -> term .
    (5) abst -> term . ID
    ID              shift and go to state 7


state 2

    (1) term -> LPAR . term RPAR
    (1) term -> . LPAR term RPAR
    (2) term -> . ID
    (3) term -> . lamb
    (4) term -> . abst
    (6) lamb -> . LAMB ID DOT term
    (5) abst -> . term ID
    LPAR            shift and go to state 2
    ID              shift and go to state 3
    LAMB            shift and go to state 6

    term                           shift and go to state 8
    lamb                           shift and go to state 4
    abst                           shift and go to state 5

state 3

    (2) term -> ID .
    ID              reduce using rule 2 (term -> ID .)
    $end            reduce using rule 2 (term -> ID .)
    RPAR            reduce using rule 2 (term -> ID .)


state 4

    (3) term -> lamb .
    ID              reduce using rule 3 (term -> lamb .)
    $end            reduce using rule 3 (term -> lamb .)
    RPAR            reduce using rule 3 (term -> lamb .)


state 5

    (4) term -> abst .
    ID              reduce using rule 4 (term -> abst .)
    $end            reduce using rule 4 (term -> abst .)
    RPAR            reduce using rule 4 (term -> abst .)


state 6

    (6) lamb -> LAMB . ID DOT term
    ID              shift and go to state 9


state 7

    (5) abst -> term ID .
    ID              reduce using rule 5 (abst -> term ID .)
    $end            reduce using rule 5 (abst -> term ID .)
    RPAR            reduce using rule 5 (abst -> term ID .)


state 8

    (1) term -> LPAR term . RPAR
    (5) abst -> term . ID
    RPAR            shift and go to state 10
    ID              shift and go to state 7


state 9

    (6) lamb -> LAMB ID . DOT term
    DOT             shift and go to state 11


state 10

    (1) term -> LPAR term RPAR .
    ID              reduce using rule 1 (term -> LPAR term RPAR .)
    $end            reduce using rule 1 (term -> LPAR term RPAR .)
    RPAR            reduce using rule 1 (term -> LPAR term RPAR .)


state 11

    (6) lamb -> LAMB ID DOT . term
    (1) term -> . LPAR term RPAR
    (2) term -> . ID
    (3) term -> . lamb
    (4) term -> . abst
    (6) lamb -> . LAMB ID DOT term
    (5) abst -> . term ID
    LPAR            shift and go to state 2
    ID              shift and go to state 3
    LAMB            shift and go to state 6

    term                           shift and go to state 12
    lamb                           shift and go to state 4
    abst                           shift and go to state 5

state 12

    (6) lamb -> LAMB ID DOT term .
    (5) abst -> term . ID
  ! shift/reduce conflict for ID resolved as shift
    $end            reduce using rule 6 (lamb -> LAMB ID DOT term .)
    RPAR            reduce using rule 6 (lamb -> LAMB ID DOT term .)
    ID              shift and go to state 7


Conflicts:

shift/reduce conflict for ID in state 12 resolved as shift%

我设置 appl : term ID 来编码应用程序的左关联性，右规则将是 appl : term term 但这创建了一个右关联。我的问题是：

为什么会发生 shift/reduce 以及如何解决。对我来说，因为 ID 是一个终端，它只能被移动，ID 没有减少。我缺少什么？
没有中缀运算符时如何编码左结合性

谢谢@rici，我更新了语法，我无法解析 λx.λy.x 所以我添加了 p 术语作为带括号的最后一条规则。这是我的语法。它按预期工作，但是，我收到了 15 个警告，哈哈

WARNING: 4 shift/reduce conflicts
WARNING: 11 reduce/reduce conflicts
Parser debugging for Par written to lamb.out
(('x', 'y'), 'z')
('λ', 'x', 'x')
((('λ', 'x', ('λ', 'y', 'x')), 'a'), 'b')

因为它像我预期的那样工作，所以我认为我的规则是正确的。我仍在努力获得关于编写正确语法的直觉。核心在这里

from sly import Lexer, Parser


class Lex(Lexer):
    tokens = {ID, LAMB, DOT, LPAR, RPAR}
    ID = r"[a-z]"
    LAMB = r"λ"
    DOT = r"\."
    LPAR = r"\("
    RPAR = r"\)"

    ignore = " \t"


class Par(Parser):
    """
    lamb : LAMB ID DOT term
         | appl
    appl : appl term
         | term
         | pterm
    pterm: LPAR term RPAR
    term : lamb
         | ID
    """
    tokens = Lex.tokens
    debugfile = 'lamb.out'

    @_("LAMB ID DOT term")
    def lamb(self, p):
        return ("λ", p.ID, p.term)

    @_("appl")
    def lamb(self, p):
        return p.appl

    @_("appl term")
    def appl(self, p):
        return (p.appl, p.term)

    @_("term")
    def appl(self, p):
        return p.term

    @_("pterm")
    def appl(self, p):
        return p.pterm

    @_("LPAR term RPAR")
    def pterm(self, p):
        return p.term

    @_("ID")
    def term(self, p):
        return p.ID

    @_("lamb")
    def term(self, p):
        return p.lamb


def parse(input_: str):
    return Par().parse(Lex().tokenize(input_))


from pprint import pprint

pprint(parse("x y z"))
pprint(parse("λx.x"))
pprint(parse("(λx.λy.x) a b"))

这里是调试

Grammar:

Rule 0     S' -> lamb
Rule 1     lamb -> appl
Rule 2     lamb -> LAMB ID DOT term
Rule 3     appl -> pterm
Rule 4     appl -> term
Rule 5     appl -> appl term
Rule 6     pterm -> LPAR term RPAR
Rule 7     term -> lamb
Rule 8     term -> ID

Terminals, with rules where they appear:

DOT                  : 2
ID                   : 2 8
LAMB                 : 2
LPAR                 : 6
RPAR                 : 6
error                : 

Nonterminals, with rules where they appear:

appl                 : 1 5
lamb                 : 7 0
pterm                : 3
term                 : 2 4 5 6


state 0

    (0) S' -> . lamb
    (1) lamb -> . appl
    (2) lamb -> . LAMB ID DOT term
    (3) appl -> . pterm
    (4) appl -> . term
    (5) appl -> . appl term
    (6) pterm -> . LPAR term RPAR
    (7) term -> . lamb
    (8) term -> . ID
    LAMB            shift and go to state 3
    LPAR            shift and go to state 7
    ID              shift and go to state 4

    lamb                           shift and go to state 1
    appl                           shift and go to state 2
    term                           shift and go to state 5
    pterm                          shift and go to state 6

state 1

    (0) S' -> lamb .
    (7) term -> lamb .
  ! reduce/reduce conflict for $end resolved using rule 0 (S' -> lamb .)
    ID              reduce using rule 7 (term -> lamb .)
    LAMB            reduce using rule 7 (term -> lamb .)
    LPAR            reduce using rule 7 (term -> lamb .)


state 2

    (1) lamb -> appl .
    (5) appl -> appl . term
    (7) term -> . lamb
    (8) term -> . ID
    (1) lamb -> . appl
    (2) lamb -> . LAMB ID DOT term
    (3) appl -> . pterm
    (4) appl -> . term
    (5) appl -> . appl term
    (6) pterm -> . LPAR term RPAR
  ! shift/reduce conflict for ID resolved as shift
  ! shift/reduce conflict for LAMB resolved as shift
  ! shift/reduce conflict for LPAR resolved as shift
    $end            reduce using rule 1 (lamb -> appl .)
    RPAR            reduce using rule 1 (lamb -> appl .)
    ID              shift and go to state 4
    LAMB            shift and go to state 3
    LPAR            shift and go to state 7

    appl                           shift and go to state 2
    term                           shift and go to state 8
    lamb                           shift and go to state 9
    pterm                          shift and go to state 6

state 3

    (2) lamb -> LAMB . ID DOT term
    ID              shift and go to state 10


state 4

    (8) term -> ID .
    $end            reduce using rule 8 (term -> ID .)
    ID              reduce using rule 8 (term -> ID .)
    LAMB            reduce using rule 8 (term -> ID .)
    LPAR            reduce using rule 8 (term -> ID .)
    RPAR            reduce using rule 8 (term -> ID .)


state 5

    (4) appl -> term .
    $end            reduce using rule 4 (appl -> term .)
    ID              reduce using rule 4 (appl -> term .)
    LAMB            reduce using rule 4 (appl -> term .)
    LPAR            reduce using rule 4 (appl -> term .)


state 6

    (3) appl -> pterm .
    $end            reduce using rule 3 (appl -> pterm .)
    ID              reduce using rule 3 (appl -> pterm .)
    LAMB            reduce using rule 3 (appl -> pterm .)
    LPAR            reduce using rule 3 (appl -> pterm .)
    RPAR            reduce using rule 3 (appl -> pterm .)


state 7

    (6) pterm -> LPAR . term RPAR
    (7) term -> . lamb
    (8) term -> . ID
    (1) lamb -> . appl
    (2) lamb -> . LAMB ID DOT term
    (3) appl -> . pterm
    (4) appl -> . term
    (5) appl -> . appl term
    (6) pterm -> . LPAR term RPAR
    ID              shift and go to state 4
    LAMB            shift and go to state 3
    LPAR            shift and go to state 7

    term                           shift and go to state 11
    lamb                           shift and go to state 9
    appl                           shift and go to state 2
    pterm                          shift and go to state 6

state 8

    (5) appl -> appl term .
    (4) appl -> term .
  ! reduce/reduce conflict for $end resolved using rule 5 (appl -> appl term .)
  ! reduce/reduce conflict for ID resolved using rule 5 (appl -> appl term .)
  ! reduce/reduce conflict for LAMB resolved using rule 5 (appl -> appl term .)
  ! reduce/reduce conflict for LPAR resolved using rule 5 (appl -> appl term .)
  ! reduce/reduce conflict for RPAR resolved using rule 5 (appl -> appl term .)
    $end            reduce using rule 5 (appl -> appl term .)
    ID              reduce using rule 5 (appl -> appl term .)
    LAMB            reduce using rule 5 (appl -> appl term .)
    LPAR            reduce using rule 5 (appl -> appl term .)
    RPAR            reduce using rule 5 (appl -> appl term .)


state 9

    (7) term -> lamb .
    $end            reduce using rule 7 (term -> lamb .)
    ID              reduce using rule 7 (term -> lamb .)
    LAMB            reduce using rule 7 (term -> lamb .)
    LPAR            reduce using rule 7 (term -> lamb .)
    RPAR            reduce using rule 7 (term -> lamb .)


state 10

    (2) lamb -> LAMB ID . DOT term
    DOT             shift and go to state 12


state 11

    (6) pterm -> LPAR term . RPAR
    (4) appl -> term .
  ! shift/reduce conflict for RPAR resolved as shift
    RPAR            shift and go to state 13
    ID              reduce using rule 4 (appl -> term .)
    LAMB            reduce using rule 4 (appl -> term .)
    LPAR            reduce using rule 4 (appl -> term .)


state 12

    (2) lamb -> LAMB ID DOT . term
    (7) term -> . lamb
    (8) term -> . ID
    (1) lamb -> . appl
    (2) lamb -> . LAMB ID DOT term
    (3) appl -> . pterm
    (4) appl -> . term
    (5) appl -> . appl term
    (6) pterm -> . LPAR term RPAR
    ID              shift and go to state 4
    LAMB            shift and go to state 3
    LPAR            shift and go to state 7

    term                           shift and go to state 14
    lamb                           shift and go to state 9
    appl                           shift and go to state 2
    pterm                          shift and go to state 6

state 13

    (6) pterm -> LPAR term RPAR .
    $end            reduce using rule 6 (pterm -> LPAR term RPAR .)
    ID              reduce using rule 6 (pterm -> LPAR term RPAR .)
    LAMB            reduce using rule 6 (pterm -> LPAR term RPAR .)
    LPAR            reduce using rule 6 (pterm -> LPAR term RPAR .)
    RPAR            reduce using rule 6 (pterm -> LPAR term RPAR .)


state 14

    (2) lamb -> LAMB ID DOT term .
    (4) appl -> term .
  ! reduce/reduce conflict for $end resolved using rule 2 (lamb -> LAMB ID DOT term .)
  ! reduce/reduce conflict for ID resolved using rule 2 (lamb -> LAMB ID DOT term .)
  ! reduce/reduce conflict for LAMB resolved using rule 2 (lamb -> LAMB ID DOT term .)
  ! reduce/reduce conflict for LPAR resolved using rule 2 (lamb -> LAMB ID DOT term .)
  ! reduce/reduce conflict for RPAR resolved using rule 2 (lamb -> LAMB ID DOT term .)
    $end            reduce using rule 2 (lamb -> LAMB ID DOT term .)
    ID              reduce using rule 2 (lamb -> LAMB ID DOT term .)
    LAMB            reduce using rule 2 (lamb -> LAMB ID DOT term .)
    LPAR            reduce using rule 2 (lamb -> LAMB ID DOT term .)
    RPAR            reduce using rule 2 (lamb -> LAMB ID DOT term .)


Conflicts:

shift/reduce conflict for ID in state 2 resolved as shift
shift/reduce conflict for LAMB in state 2 resolved as shift
shift/reduce conflict for LPAR in state 2 resolved as shift
shift/reduce conflict for RPAR in state 11 resolved as shift
reduce/reduce conflict in state 1 resolved using rule S' -> lamb
rejected rule (term -> lamb) in state 1
reduce/reduce conflict in state 8 resolved using rule appl -> appl term
rejected rule (appl -> term) in state 8
reduce/reduce conflict in state 14 resolved using rule lamb -> LAMB ID DOT term
rejected rule (appl -> term) in state 14%

Answer 1

lamb是term的推导之一。但是 lamb 中的最后一件事本身就是一个 term。 term ID 是一个 term（通过 abst）。

假设我们已经处理了 λ x . <term>，其中 <term> 已经被缩减为 term。（例如，它可能是一个简单的 ID。）假设下一个标记是 y，这是一个 ID。由于 λ x . <term> 是 term，我们可以将其理解为 λ x . <term> 对 y 的应用。为此，我们必须将 λ x . <term> 减少到 term 才能继续 abst。这就是减少。（注意：“ID冲突”并不是说ID可以减少，ID是先行符号，冲突是前行是否要移位，或者栈顶的句柄是不是-- 还不包括前瞻 -- 应该减少。）

冲突是由于语法也允许 ID 在不减少的情况下移动的可能性的结果。移动 ID 将允许将 <term> 应用到 y (abst: term ID) 作为 lambda 主体的一部分。

这更像是一个运算符优先级问题（在 lamb 和 abst 之间），而不是关联性问题。我想你会想要支持转变，使应用程序的优先级高于 lambda。

(顺便说一句，你所说的lamb实际上是一个函数抽象，据我理解这个概念。abst是一个应用程序。LISP语法强制应用程序用括号括起来，但是我猜你的目标是更接近 Haskell 语法，并在一系列术语中自动柯里化。不过只是猜测。）

您说得对，语法在不允许应用任意术语方面存在缺陷。这可以用“通常的方式”解决，通过使用一系列非终端，每个代表一个优先级别。所以我猜你会有类似

的东西

lamb: LAMB ID DOT lamb   # Lowest precedence
    | appl               # cascade
appl: appl term          # left-associative
    | term               # cascade
term: '(' lamb ')'       # base
    | ID

这个 SLY 程序中的 shift/reduce 冲突是什么？

What is the shift/reduce conflict in this SLY program?

python

parsing

lalr