PLY/YACC PDF 解析冲突
PLY/YACC parsing conflicts on PDF
我正在尝试使用 PLY lex/yacc 解析 PDF，但我遇到了关于管理 NUMBER 标记、数组和 indirect_references 的 yacc 解析规则的障碍。
相关出处：
def p_value_list(t):
r'''value_list : value_list value
| value'''
if t.slice[0] == 'item_list':
t[0] = {'type':'value_list', 'children' : t[0]['children'] + [t[1]] }
else:
t[0] = {'type':'value_list', 'children' : [t[1]] }
pass
def p_value(t):
r'''value : dictionary
| array
| indirect_reference
| NUMBER
| HEX
| STREAM
| TEXT
| BOOL
| empty'''
t[0] = t[1]
pass
def p_indirect_reference(t):
r'''indirect_reference : NUMBER NUMBER KEY_R'''
t[0] = {'type':'indirect_reference', 'children' : [t[1], t[2]] }
pass
def p_array(t):
r'''array : LBRACKET value_list RBRACKET'''
t[0] = {'type':'array', 'children' : t[2] }
pass
这导致关于 NUMBERS 的规则不明确（你有列表 NUMBER NUMBER 还是有间接参考 NUMBER NUMBER KEY_R）——我得到的错误范围从意外 NUMBER 解析简单数组时的标记 [0 0 0]
ERROR: Error : obj_list NUMBER NUMBER OBJ LTLT key_value_list ID LBRACKET NUMBER NUMBER . LexToken(NUMBER,'0',1,166273)
像这样的错误
ERROR: Error : obj_list NUMBER NUMBER OBJ LTLT key_value_list ID LBRACKET NUMBER NUMBER . LexToken(RBRACKET,']',1,88)
我认为当它实际上是一个包含两个 NUMBER 标记的数组时需要一个 KEY_R 标记：[ 486 173]
对于勇敢的人，PDF 规范和完整的源链接。
[1] https://github.com/opticaliqlusion/pypdf/blob/master/pypdf.py
[2]http://wwwimages.adobe.com/content/dam/Adobe/en/devnet/pdf/pdfs/pdf_reference_1-7.pdf
这真的不是模棱两可；语法是完全明确的。但是，它不是 LR(1)，并且 LR(1) 解析器无法判断如果一个整数后跟另一个整数，是移位还是归约。 （语法是 LR(2)，因为 second-next 标记足以决定；如果是 R，则整数是间接引用中的第一个标记，应该移位。
解决这个问题要棘手得多。理论上，您可以将任何 LR(2) 文法转换为 LR(1) 文法，但这种转换很麻烦，而且我不知道有任何自动化工具可以做到这一点。基本思想是扩展产生式以避免在遇到足够的上下文之前需要减少，然后根据需要修复解析树。
（有关此问题的其他一些可能的解决方案，请参见下文。最后一个选项是我个人最喜欢的。）
这是 LR(2)→LR(1) 技术的示例；您可以看到 NUMBER 代币是如何累积的，直到它们的处置已知：
value_not_number
: dictionary
| array
| HEX
| STREAM
| TEXT
| BOOL
| empty
value_list
: value_list_ends_non_number
| value_list_ends_one_number
| value_list_ends_two_numbers
| value_list_ends_indref
|
value_list_ends_one_number
: value_list_ends_non_number NUMBER
value_list_ends_two_numbers
: value_list_ends_non_number NUMBER NUMBER
| value_list_ends_two_numbers NUMBER
value_list_ends_indref
: value_list_ends_two_numbers 'R'
value_list_ends_non_number
: value_list value_not_number
array : '[' value_list ']'
请注意，语法生成的解析树不太准确，因为它将 0 0 R 解析为 value_list_ends_two_numbers 后跟 R。为了检索真正的解析树，value_list_ends_indref 的缩减操作需要从它的第一个 child 中窃取最后两个数字，用它们制造一个间接引用 object，然后添加到第一个 child 的结尾。所以带有动作的 PLY 语法可能看起来像这样：
def p_unit_productions(t):
r'''value_not_number
: dictionary
| array
| HEX
| STREAM
| TEXT
| BOOL
value_list
: value_list_ends_non_number
| value_list_ends_one_number
| value_list_ends_two_numbers
| value_list_ends_indref'''
t[0] = t[1]
def p_value_list_empty(t):
r'''value_list:'''
t[0] = []
def p_value_list_push(t):
r'''value_list_ends_one_number
: value_list_ends_non_number NUMBER
value_list_ends_two_numbers
: value_list_ends_two_numbers NUMBER
value_list_ends_non_number
: value_list value_not_number'''
t[0] = t[1]
t[0].append(t[2])
def p_value_list_push2(t):
r'''value_list_ends_two_numbers
: value_list_ends_non_number NUMBER NUMBER'''
t[0] = t[1]
t[0].append(t[2])
t[0].append(t[3])
def p_indirect_reference(t):
r'''value_list_ends_indref
: value_list_ends_two_numbers 'R' '''
t[0] = t[1]
gen = t[0].pop()
obj = t[0].pop()
t[0].append({'type': 'indirect_reference',
'children': [obj, gen] })
def p_array(t):
r'''array : '[' value_list ']' '''
t[0] = {'type':'array', 'children' : t[2] }
这和你的不太一样：
value_list object 类型（在我看来没有必要）。- 语法组织可能看起来有点奇怪，因为我定义的函数是按动作而不是按 non-terminal 组织的，但是 PLY 处理得很好 (http://www.dabeaz.com/ply/ply.html#ply_nn25) 并且它导致更简单的操作。
- 根据 PLY 手册，我假设您的
empty 是空的 non-terminal，因此删除了 value: empty；这将导致真正的歧义，因为您无法知道在两个 non-terminal 之间找到了多少个空字符串。
- 我用 single-quoted 符号 (http://www.dabeaz.com/ply/ply.html#ply_nn26) 替换了 single-character 文字标记，因为我个人认为它使语法更具可读性。
（我还没有测试过那个 PLY 片段；如果有问题请告诉我。我很容易出现一些错别字。）
其他可能的解决方案
1。使用词法扫描仪
正如评论中所建议的，一种替代方法是使用词法扫描器来识别整个序列（在本例中为间接引用），这需要扩展前瞻性。
实际上，这使用词法扫描器来实现 fall-back 解决方案。当语法中只有几个 LR(2) 状态时，这是一种常见的解决方案。例如，bison 本身就使用这种技术来区分产生式的 left-hand 端和 right-hand 端的符号使用。 （当您看到 - 或看不到 - 符号后的冒号时，您可以分辨出区别，但您必须知道符号本身何时是第一个先行。）
在某些情况下，这似乎是一个更简单的解决方案，但在其他情况下，它只是将复杂性从解析器导出到扫描器。在这种特殊情况下，例如，您可能使用 longest-match 词法消歧算法来区分 R 和以 R 开头的标识符标记，并且您可能有一个忽略的规则空格。这些都不会帮助您识别间接引用的规则；您需要明确匹配空格，并且需要明确验证 R 后面的任何内容都不能形成更长的标识符。这不是非常复杂，但也不是微不足道的。您需要做一些工作来创建适当的测试覆盖率。
随着可能的 extended-lookahead 状态数量的增加，您会发现此解决方案越来越复杂。 （并不是说上面概述的解析器解决方案也很棒。）
2。使用 GLR 解析器
由于语法本身没有歧义，如果您有可以生成 GLR 解析器的解析器生成器，则可以使用 GLR 解析器而不是 LR(1) 解析器。 GLR 算法可以解析任何 context-free 语法，但要付出代价：在常见情况下速度稍慢，在边缘情况下慢得多（在某些语法中，它可能需要二次甚至立方时间），并且典型的实现延迟歧义得到解决之前的语义操作，这意味着它们不一定按预期顺序执行。
在这种情况下，对这个解决方案有更强的抑制作用：PLY
不生成 GLR 语法。但是，bison 确实有一个 GLR 选项，将 bison 解析器包装到 python 模块中相对简单（如果重要的话，这很可能比 PLY 解析器更快）。
3。使用堆栈而不是 CFG
PDF 源自 Postscript，这是一种堆栈语言。堆栈语言一般不需要解析器；他们只有一个词法扫描器和一个堆栈。每个令牌都有一个关联的动作；对于许多令牌（例如文字），操作只是将令牌压入堆栈。其他令牌可能有更复杂的操作。
例如，] 标记通过弹出堆栈直到找到 [ 并将弹出的元素放入 newly-created 数组 object 来创建一个数组，然后将其压入堆栈。
类似地，R 令牌的操作是从堆栈顶部弹出两个东西；检查它们是数字；然后使用这两个数字构造一个间接引用 object，然后将其压入堆栈。
PLY 在构建 PDF 堆栈解析器时不会帮助你太多，但它至少会为你构建词法分析器，这实际上是解析器中最复杂的部分。需要的栈操作不多，其中none个特别有挑战性。
我正在尝试使用 PLY lex/yacc 解析 PDF，但我遇到了关于管理 NUMBER 标记、数组和 indirect_references 的 yacc 解析规则的障碍。
相关出处：
def p_value_list(t):
r'''value_list : value_list value
| value'''
if t.slice[0] == 'item_list':
t[0] = {'type':'value_list', 'children' : t[0]['children'] + [t[1]] }
else:
t[0] = {'type':'value_list', 'children' : [t[1]] }
pass
def p_value(t):
r'''value : dictionary
| array
| indirect_reference
| NUMBER
| HEX
| STREAM
| TEXT
| BOOL
| empty'''
t[0] = t[1]
pass
def p_indirect_reference(t):
r'''indirect_reference : NUMBER NUMBER KEY_R'''
t[0] = {'type':'indirect_reference', 'children' : [t[1], t[2]] }
pass
def p_array(t):
r'''array : LBRACKET value_list RBRACKET'''
t[0] = {'type':'array', 'children' : t[2] }
pass
这导致关于 NUMBERS 的规则不明确（你有列表 NUMBER NUMBER 还是有间接参考 NUMBER NUMBER KEY_R）——我得到的错误范围从意外 NUMBER 解析简单数组时的标记 [0 0 0]
ERROR: Error : obj_list NUMBER NUMBER OBJ LTLT key_value_list ID LBRACKET NUMBER NUMBER . LexToken(NUMBER,'0',1,166273)
像这样的错误
ERROR: Error : obj_list NUMBER NUMBER OBJ LTLT key_value_list ID LBRACKET NUMBER NUMBER . LexToken(RBRACKET,']',1,88)
我认为当它实际上是一个包含两个 NUMBER 标记的数组时需要一个 KEY_R 标记：[ 486 173]
对于勇敢的人，PDF 规范和完整的源链接。
[1] https://github.com/opticaliqlusion/pypdf/blob/master/pypdf.py
[2]http://wwwimages.adobe.com/content/dam/Adobe/en/devnet/pdf/pdfs/pdf_reference_1-7.pdf
这真的不是模棱两可；语法是完全明确的。但是，它不是 LR(1)，并且 LR(1) 解析器无法判断如果一个整数后跟另一个整数，是移位还是归约。 （语法是 LR(2)，因为 second-next 标记足以决定；如果是 R，则整数是间接引用中的第一个标记，应该移位。
解决这个问题要棘手得多。理论上，您可以将任何 LR(2) 文法转换为 LR(1) 文法，但这种转换很麻烦，而且我不知道有任何自动化工具可以做到这一点。基本思想是扩展产生式以避免在遇到足够的上下文之前需要减少，然后根据需要修复解析树。
（有关此问题的其他一些可能的解决方案，请参见下文。最后一个选项是我个人最喜欢的。）
这是 LR(2)→LR(1) 技术的示例；您可以看到 NUMBER 代币是如何累积的，直到它们的处置已知：
value_not_number
: dictionary
| array
| HEX
| STREAM
| TEXT
| BOOL
| empty
value_list
: value_list_ends_non_number
| value_list_ends_one_number
| value_list_ends_two_numbers
| value_list_ends_indref
|
value_list_ends_one_number
: value_list_ends_non_number NUMBER
value_list_ends_two_numbers
: value_list_ends_non_number NUMBER NUMBER
| value_list_ends_two_numbers NUMBER
value_list_ends_indref
: value_list_ends_two_numbers 'R'
value_list_ends_non_number
: value_list value_not_number
array : '[' value_list ']'
请注意，语法生成的解析树不太准确，因为它将 0 0 R 解析为 value_list_ends_two_numbers 后跟 R。为了检索真正的解析树，value_list_ends_indref 的缩减操作需要从它的第一个 child 中窃取最后两个数字，用它们制造一个间接引用 object，然后添加到第一个 child 的结尾。所以带有动作的 PLY 语法可能看起来像这样：
def p_unit_productions(t):
r'''value_not_number
: dictionary
| array
| HEX
| STREAM
| TEXT
| BOOL
value_list
: value_list_ends_non_number
| value_list_ends_one_number
| value_list_ends_two_numbers
| value_list_ends_indref'''
t[0] = t[1]
def p_value_list_empty(t):
r'''value_list:'''
t[0] = []
def p_value_list_push(t):
r'''value_list_ends_one_number
: value_list_ends_non_number NUMBER
value_list_ends_two_numbers
: value_list_ends_two_numbers NUMBER
value_list_ends_non_number
: value_list value_not_number'''
t[0] = t[1]
t[0].append(t[2])
def p_value_list_push2(t):
r'''value_list_ends_two_numbers
: value_list_ends_non_number NUMBER NUMBER'''
t[0] = t[1]
t[0].append(t[2])
t[0].append(t[3])
def p_indirect_reference(t):
r'''value_list_ends_indref
: value_list_ends_two_numbers 'R' '''
t[0] = t[1]
gen = t[0].pop()
obj = t[0].pop()
t[0].append({'type': 'indirect_reference',
'children': [obj, gen] })
def p_array(t):
r'''array : '[' value_list ']' '''
t[0] = {'type':'array', 'children' : t[2] }
这和你的不太一样：
value_listobject 类型（在我看来没有必要）。- 语法组织可能看起来有点奇怪，因为我定义的函数是按动作而不是按 non-terminal 组织的，但是 PLY 处理得很好 (http://www.dabeaz.com/ply/ply.html#ply_nn25) 并且它导致更简单的操作。
- 根据 PLY 手册，我假设您的
empty是空的 non-terminal，因此删除了value: empty；这将导致真正的歧义，因为您无法知道在两个 non-terminal 之间找到了多少个空字符串。 - 我用 single-quoted 符号 (http://www.dabeaz.com/ply/ply.html#ply_nn26) 替换了 single-character 文字标记，因为我个人认为它使语法更具可读性。
（我还没有测试过那个 PLY 片段；如果有问题请告诉我。我很容易出现一些错别字。）
其他可能的解决方案
1。使用词法扫描仪
正如评论中所建议的，一种替代方法是使用词法扫描器来识别整个序列（在本例中为间接引用），这需要扩展前瞻性。
实际上，这使用词法扫描器来实现 fall-back 解决方案。当语法中只有几个 LR(2) 状态时，这是一种常见的解决方案。例如，bison 本身就使用这种技术来区分产生式的 left-hand 端和 right-hand 端的符号使用。 （当您看到 - 或看不到 - 符号后的冒号时，您可以分辨出区别，但您必须知道符号本身何时是第一个先行。）
在某些情况下，这似乎是一个更简单的解决方案，但在其他情况下，它只是将复杂性从解析器导出到扫描器。在这种特殊情况下，例如，您可能使用 longest-match 词法消歧算法来区分 R 和以 R 开头的标识符标记，并且您可能有一个忽略的规则空格。这些都不会帮助您识别间接引用的规则；您需要明确匹配空格，并且需要明确验证 R 后面的任何内容都不能形成更长的标识符。这不是非常复杂，但也不是微不足道的。您需要做一些工作来创建适当的测试覆盖率。
随着可能的 extended-lookahead 状态数量的增加，您会发现此解决方案越来越复杂。 （并不是说上面概述的解析器解决方案也很棒。）
2。使用 GLR 解析器
由于语法本身没有歧义，如果您有可以生成 GLR 解析器的解析器生成器，则可以使用 GLR 解析器而不是 LR(1) 解析器。 GLR 算法可以解析任何 context-free 语法，但要付出代价：在常见情况下速度稍慢，在边缘情况下慢得多（在某些语法中，它可能需要二次甚至立方时间），并且典型的实现延迟歧义得到解决之前的语义操作，这意味着它们不一定按预期顺序执行。
在这种情况下，对这个解决方案有更强的抑制作用：PLY
不生成 GLR 语法。但是，bison 确实有一个 GLR 选项，将 bison 解析器包装到 python 模块中相对简单（如果重要的话，这很可能比 PLY 解析器更快）。
3。使用堆栈而不是 CFG
PDF 源自 Postscript，这是一种堆栈语言。堆栈语言一般不需要解析器；他们只有一个词法扫描器和一个堆栈。每个令牌都有一个关联的动作；对于许多令牌（例如文字），操作只是将令牌压入堆栈。其他令牌可能有更复杂的操作。
例如，] 标记通过弹出堆栈直到找到 [ 并将弹出的元素放入 newly-created 数组 object 来创建一个数组，然后将其压入堆栈。
类似地，R 令牌的操作是从堆栈顶部弹出两个东西；检查它们是数字；然后使用这两个数字构造一个间接引用 object，然后将其压入堆栈。
PLY 在构建 PDF 堆栈解析器时不会帮助你太多，但它至少会为你构建词法分析器，这实际上是解析器中最复杂的部分。需要的栈操作不多，其中none个特别有挑战性。