python - PLY/YACC解析PDF上的冲突

Question

我正在尝试使用PLY lex / yacc解析PDF，而我却遇到了有关yacc解析规则的问题，该规则控制NUMBER标记，数组和indirect_references。

相关资料来源：

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)

我假设实际上是由两个 KEY_R标记组成的数组时，它期待一个 NUMBER标记： [ 486 173]

为了勇敢，将PDF Spec和完整的源代码链接在一起。

[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

Answer 1

这并不是真正的模棱两可；语法是完全明确的。但是，它不是LR（1），并且LR（1）解析器无法确定是对整数进行移位还是缩小（如果后面跟随另一个整数）。 （语法为LR（2），因为第二个下一个标记足以确定；如果为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的归约操作需要从其第一个子代中窃取最后两个数字，使用它们来制造间接引用对象，然后将其添加到第一个子代的末尾。因此带有动作的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对象类型（在我看来这是不必要的）。
语法组织可能看起来有些奇怪，因为我定义的功能是通过操作而不是非终结符来组织的，但是PLY处理得很好（ http://www.dabeaz.com/ply/ply.html#ply_nn25），并且可以使操作更简单。
根据PLY手册，我假设您的 value: empty是空的非终结符，所以删除了 empty。这将导致真正的歧义，因为您不知道在两个非终端之间找到了多少个空字符串。
我用单引号（ http://www.dabeaz.com/ply/ply.html#ply_nn26）替换了单字符文字标记，因为我个人认为它使语法更具可读性。


（我尚未测试该PLY片段；如果有问题，请告诉我。我很容易犯了一些错字。）

其他可能的解决方案

1.使用词法扫描器

正如评论中所建议的那样，一种替代方法是使用词法扫描器来识别整个序列（在这种情况下为间接引用），这需要进行扩展的超前查找。

实际上，这使用词法扫描器来实现后备解决方案。当语法中只有几个LR（2）状态时，这是一种常见的解决方案。例如， bison本身使用此技术来区分作品的左侧和右侧的符号。 （您可以在看到或看不到符号后的冒号时区分开来，但是您必须知道符号本身何时是第一个前瞻。）

在某些情况下，这似乎是一个更简单的解决方案，但在其他情况下，它导致将复杂度从解析器简单导出到扫描仪。例如，在这种特定情况下，您可能使用最长匹配词法消除歧义算法来区分 R和以 R开头的标识符令牌，并且您可能有忽略空白的规则。这些都不会对您识别间接引用的规则有所帮助；您需要显式匹配空白，并且需要显式验证 R之后的内容不能形成更长的标识符。这并不是很复杂，但是也不是简单的。您需要做一些工作来创建适当的测试范围。

随着可能的扩展超前状态的数量增加，您会发现此解决方案变得越来越复杂。 （也不是上面概述的解析器解决方案也不错。）

2.使用GLR解析器

由于语法本身不是模棱两可的，因此，如果您有可以生成GLR解析器的解析器生成器，则可以使用GLR解析器而不是LR（1）解析器。 GLR算法可以解析任何与上下文无关的语法，但要付出代价：GLR算法在某些情况下会稍慢一些，在边缘情况下会稍慢一些情况（在某些语法中，它可能需要二次甚至三次时间），并且典型的实现会延迟语义动作直到歧义得到解决为止，这意味着它们不一定按预期的顺序执行。

在这种情况下，此解决方案的约束力更大：PLY
不产生GLR语法。但是， bison确实具有GLR选项，将野牛解析器包装到python模块中相对简单（如果很重要的话，它可能比PLY解析器更快）。

3.使用堆栈代替CFG

PDF源自Postscript，Postscript是一种堆栈语言。堆栈语言通常不需要解析器。他们只有一个词法扫描器和一个堆栈。每个令牌都有一个关联的动作；对于许多令牌（例如，文字），操作只是将令牌推入堆栈。其他令牌可能具有更复杂的动作。

例如， ]令牌通过弹出堆栈直到找到 [并将弹出的元素放入新创建的数组对象中来创建数组，然后将其压入堆栈。

类似地， R令牌的操作是将两件事从栈顶弹出。检查它们是数字；然后使用这两个数字构造一个间接引用对象，然后将其推入堆栈。

PLY在构造PDF堆栈解析器方面不会有多大帮助，但它至少会为您构建词法分析器，这实际上是解析器中最复杂的部分。不需要太多的堆栈操作，而且它们都不是特别具有挑战性的。