Python/YACC：解决移进/归约冲突

Question

我正在使用PLY。这里是我从parser.out中得到的一个状态：

state 3

    (5) course_data -> course .
    (6) course_data -> course . course_list_tail
    (3) or_phrase -> course . OR_CONJ COURSE_NUMBER
    (7) course_list_tail -> . , COURSE_NUMBER
    (8) course_list_tail -> . , COURSE_NUMBER course_list_tail

  ! shift/reduce conflict for OR_CONJ resolved as shift
    $end            reduce using rule 5 (course_data -> course .)
    OR_CONJ         shift and go to state 7
    ,               shift and go to state 8

  ! OR_CONJ         [ reduce using rule 5 (course_data -> course .) ]

    course_list_tail               shift and go to state 9

我想把它解析成：

if OR_CONJ is followed by COURSE_NUMBER:
    shift and go to state 7
else:
    reduce using rule 5 (course_data -> course .)

我该如何修改我的解析器文件来实现这个呢？我需要通过回溯来处理语法错误并尝试不同的规则吗？

文档中提到：

这些值会用来给每个语法规则附加一个数字优先级和结合方向。这总是通过查看最右边的终结符号的优先级来决定的。

如果这个规则没有终结符号呢？

更新：完整的语法：

Grammar

Rule 0     S' -> statement
Rule 1     statement -> course_data
Rule 2     or_phrase -> statement OR_CONJ statement
Rule 3     or_phrase -> course OR_CONJ COURSE_NUMBER
Rule 4     statement -> or_phrase
Rule 5     course_data -> course
Rule 6     course_data -> course course_list_tail
Rule 7     course_list_tail -> , COURSE_NUMBER
Rule 8     course_list_tail -> , COURSE_NUMBER course_list_tail
Rule 9     course -> DEPT_CODE COURSE_NUMBER

Answer 1

你的基本问题是，你需要提前看两个标记才能完成你想做的事情——当你看到的输入是一个 course，而下一个标记是 OR_CONJ 时，你不知道是应该把 course 简化成 course_data 还是继续往下看下一个标记。为了处理这个问题，有几种方法可以选择：

• 使用 LR(2) 或 LR(k) 或 GLR 解析器生成器——这些都能处理这个问题。

• 使用词法分析的小技巧来进行提前查看——基本上让词法分析器根据后面的标记是 COURSE_NUMBER 还是其他，返回两种不同的 OR_CONJ 标记。

• 调整语法以消除冲突，这可能会导致语法解析出与你想要的稍微不同的内容（需要一些额外的后处理检查来拒绝一些无效的结构），而且通常会让语法变得更难理解。

需要注意的是，你给出的语法在处理三个或更多课程在一个语句中如何关联时也是模糊的。这个问题可以通过将语法重写为更清晰的左递归形式来轻松解决：

Rule 1    statement -> course
Rule 2    statement -> statement OR_CONJ course
Rule 3    course -> DEPT_CODE course_list
Rule 4    course -> DEPT CODE course_list OR_CONJ COURSE_NUMBER
Rule 5    course_list -> COURSE_NUMBER
Rule 6    course_list -> course_list , COURSE_NUMBER

这也可以重写为右递归形式以适应 LL 解析器生成器，但它仍然存在两个标记提前查看的问题。解决这个问题的一种方法是让 COURSE_NUMBER 本身成为一个有效的 course，然后在后续处理中与之前的 course 重新组合（或者如果它是一个 statement 中的第一个 course 就报错）。那么规则 4 变成：

Rule 4    course -> COURSE_NUMBER

这样就没有冲突了。