非终结符CTF语法的Python解析器

Question

在Python3中，最常见的解析器生成器（如ANTLR或Lark）通过从字符串的终端派生非终结符来定义语法，并构造一个lexer和一个解析器来计算字符串

相反，我正在寻找一个解析器生成器，它只处理由非终结符和终结符组成的“中间输入”，这意味着我将事先进行词法分析和部分解析

例如，如果输入语法为

S -> AB
A -> a | aA
B -> b | aB

如果大写字母是非终结符，小写字母是终结符，则可能的输入可以是aaaB，然后可以从中构造根为S的解析树

实际上，输入不能仅仅是像aaaB这样的ASCII字符字符串，因为非终端必须存储关于自己子树的信息。因此，至少这些必须是任意对象，并且输入更有可能是对象列表

是否有提供此功能的库或包

Answer 1

注意：这不是背书。可能还有许多其他Python解析包提供类似的功能。它只是作为实现（假定的）目标的一种可能机制

Ply解析包确实包含一个lexer生成器，但您没有义务使用它；你可以自由使用任何你喜欢的函数来提供词法标记。标记只是对象类型，其中包括value属性。但是，除了要求value对象存在外，Ply不会对该对象进行任何假设

引用here和also here手册：

When tokens are returned by lex, they have a value that is stored in the value attribute. Normally, the value is the text that was matched. However, the value can be assigned to any Python object.

If you are going to create a hand-written lexer and you plan to use it with yacc.py, it only needs to conform to the following requirements:

• 它必须提供一个token()方法，返回下一个令牌，如果没有更多的令牌可用，则返回None
• token()方法必须返回具有type和value属性的对象tok。如果正在使用行号跟踪，则令牌还应定义lineno属性

为了将非终端传递到解析器中，需要使它们看起来像终端。最简单的方法是为每个非终端制作一个伪终端，并用一个生产单元转换伪终端。例如，假设伪终端的名称以_结尾（这将使它们很容易以编程方式生成），您可以修改规则

B : b | a B

进入

B : b
  | a B
  | B_

如果我们假设您将正确的AST值注入到B_终端返回的令牌对象中，那么您只需要向语法中添加一个操作函数：

 def p_pseudo_terminals(p):
     '''A : A_
        B : B_
     '''
     p[0] = p[1]

---

下面是一个完整的可运行示例，使用问题中的语法：

文件：inject.py

from ply import yacc
from collections import namedtuple
Token = namedtuple('Token', ['type', 'value'])
Node = namedtuple('Node', ['type', 'children'])

tokens = ['a', 'b', 'A_', 'B_']
def p_S(p):
    '''S : A B'''
    p[0] = Node('S', [ p[1], p[2] ])

def p_A(p):
    '''A : a'''
    p[0] = Node('A', [ p[1] ])

def p_Al(p):
    '''A : a A'''
    p[0] = Node('A', [ p[1], p[2] ])

def p_B(p):
    '''B : b'''
    p[0] = Node('B', [ p[1] ])

def p_Bl(p):
    '''B : a B'''
    p[0] = Node('B', [ p[1], p[2] ])

def p_pseudo(p):
    '''A : A_
       B : B_
    '''
    p[0] = p[1]

class Lexer(object):
    def __init__(self, iter):
        self.iter = iter.__iter__()

    def token(self):
        try:
            retval = next(self.iter)
            if type(retval) == Token:
                # Input is a token, just pass it through
                return retval
            else:
                # Input is an AST node; fabricate a pseudo-token
                return Token(retval.type + '_', retval)
        except StopIteration:
            return None

parser = yacc.yacc()

和一个示例运行：

$ python3
Python 3.6.9 (default, Nov  7 2019, 10:44:02) 
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from inject import *
>>> token_stream = [Token('a', 'a')] * 3 + [Node('B', ['a', Node('B', children=['a', Node('B', children=['b'])])])]
>>> lexer = Lexer(token_stream)
>>> print(parser.parse(None, lexer=lexer))
Node(type='S', children=[Node(type='A', children=['a', Node(type='A', children=['a', Node(type='A', children=['a'])])]), Node(type='B', children=['a', Node(type='B', children=['a', Node(type='B', children=['b'])])])])

在真正的语法中，键入所有这些伪标记名和单元结果可能会很繁琐。您可以利用这样一个事实，即您可以自己生成docstring，只要它在您通过调用yacc.yacc构建解析器之前就已经存在。您还需要将伪令牌名称添加到令牌名称列表中，以便Ply知道B_是一个令牌

Answer 2

Lark支持使用“自定义lexer”，您可以使用它来提供您选择的任何终端流。源不必是字符串

您可以在这里找到此功能的一个简单示例：https://github.com/lark-parser/lark/blob/master/examples/custom_lexer.py