Python 来自非终结符的 CTF 语法解析器
Python parser for CTF grammar from nonterminals
在 Python3 中,最常见的解析器生成器(例如 ANTLR 或 Lark)通过从字符串的终结符派生非终结符来定义语法,并构造词法分析器和解析器来评估字符串。
取而代之的是,我正在寻找一个解析器生成器,它可以在 "intermediate input" 上工作,该 "intermediate input" 仅由非终结符和终结符组成,这意味着我会事先进行词法分析和部分解析。
例如,如果输入语法是
S -> AB
A -> a | aA
B -> b | aB
其中大写字母是非终结符,小写字母是终结符,可能的输入可能是 aaaB
,然后可以从中构建根为 S
的解析树。
输入实际上不能只是像 aaaB
这样的 ASCII 字符串,因为非终结符必须存储有关它们自己的子树的信息。所以至少那些必须是任意对象,输入更可能是对象列表。
是否有提供此功能的库或包?
注意:这不是背书。 Python 可能有许多其他解析包提供类似的功能。它只是作为实现(假定的)目标的可能机制提出的。
Ply 解析包确实包含词法分析器生成器,但您没有义务使用它;您可以自由使用任何您喜欢的函数来提供词法标记。令牌只是对象类型,其中包含 value
属性。但是,除了要求对象存在之外,Ply 不对 value
对象做任何假设。
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()
方法来 return 下一个标记或 None
如果没有更多可用的标记。
token()
方法必须 return 对象 tok
具有 type
和 value
属性。如果使用行号跟踪,则令牌还应定义 lineno
属性。
为了将 非终端 传递给解析器,您需要使它们看起来像终端。最简单的方法是为每个非终端制作一个伪终端,并将伪终端转换为单元生产。例如,假设伪终端的名称以 _
结尾(这将使它们很容易以编程方式生成,您可以修改规则
B : b | a B
进入
B : b
| a B
| B_
如果我们假设您将正确的 AST 值注入到使用 B_
终端 returned 的令牌对象中,您所需要的只是向语法中添加一个动作函数:
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'])])])])
在真正的语法中,键入所有这些伪标记名称和单元产生式可能会很乏味。您可以利用这样一个事实,即只要在通过调用 yacc.yacc
构建解析器之前它就位,您就可以自己生成文档字符串。您还需要将伪令牌名称添加到令牌名称列表中,以便 Ply 知道 B_
是一个令牌。
Lark 支持使用 "custom lexer",您可以使用它来提供您选择的任何终端流。来源不必是字符串。
您可以在此处找到此功能的简单示例:https://github.com/lark-parser/lark/blob/master/examples/custom_lexer.py
在 Python3 中,最常见的解析器生成器(例如 ANTLR 或 Lark)通过从字符串的终结符派生非终结符来定义语法,并构造词法分析器和解析器来评估字符串。
取而代之的是,我正在寻找一个解析器生成器,它可以在 "intermediate input" 上工作,该 "intermediate input" 仅由非终结符和终结符组成,这意味着我会事先进行词法分析和部分解析。
例如,如果输入语法是
S -> AB
A -> a | aA
B -> b | aB
其中大写字母是非终结符,小写字母是终结符,可能的输入可能是 aaaB
,然后可以从中构建根为 S
的解析树。
输入实际上不能只是像 aaaB
这样的 ASCII 字符串,因为非终结符必须存储有关它们自己的子树的信息。所以至少那些必须是任意对象,输入更可能是对象列表。
是否有提供此功能的库或包?
注意:这不是背书。 Python 可能有许多其他解析包提供类似的功能。它只是作为实现(假定的)目标的可能机制提出的。
Ply 解析包确实包含词法分析器生成器,但您没有义务使用它;您可以自由使用任何您喜欢的函数来提供词法标记。令牌只是对象类型,其中包含 value
属性。但是,除了要求对象存在之外,Ply 不对 value
对象做任何假设。
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()
方法来 return 下一个标记或None
如果没有更多可用的标记。 token()
方法必须 return 对象tok
具有type
和value
属性。如果使用行号跟踪,则令牌还应定义lineno
属性。
为了将 非终端 传递给解析器,您需要使它们看起来像终端。最简单的方法是为每个非终端制作一个伪终端,并将伪终端转换为单元生产。例如,假设伪终端的名称以 _
结尾(这将使它们很容易以编程方式生成,您可以修改规则
B : b | a B
进入
B : b
| a B
| B_
如果我们假设您将正确的 AST 值注入到使用 B_
终端 returned 的令牌对象中,您所需要的只是向语法中添加一个动作函数:
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'])])])])
在真正的语法中,键入所有这些伪标记名称和单元产生式可能会很乏味。您可以利用这样一个事实,即只要在通过调用 yacc.yacc
构建解析器之前它就位,您就可以自己生成文档字符串。您还需要将伪令牌名称添加到令牌名称列表中,以便 Ply 知道 B_
是一个令牌。
Lark 支持使用 "custom lexer",您可以使用它来提供您选择的任何终端流。来源不必是字符串。
您可以在此处找到此功能的简单示例:https://github.com/lark-parser/lark/blob/master/examples/custom_lexer.py