用字符串捕获不是令牌的所有内容

问题描述 投票：2回答：1

Context：我正在处理布尔表达式和算术表达式的混合，在下面的示例中可能看起来像这样：

b_1 /\ (0 <= x_1) /\ (x_2 <= 2 \/ (b_3 /\ ((/ 1 3) <= x_4))))

我想匹配并提取公式中包含的任何形状为A <= B的约束，该约束必须始终为true。在以上示例中，只有0 <= x_1会满足此条件。

当前目标：我的想法是构建仅基于以下标记的输入公式的简单分析树：和（/\）或（\/），左括号（(）和右括号（)）。给定以上公式，我想生成以下AST：

/\
|_ "b_1"
|_ /\
   |_ "0 <= x_1"
   |_ \/
      |_ "x_2 <= 2"
      |_ /\
         |_ "b_3"
         |_ "(/ 1 3) <= x_4"

然后，我可以简单地遍历AST并丢弃以\/为根的任何子树。

我的尝试：

看着this documentation，我为词法分析器定义的语法如下：

import ply.lex as lex

tokens = (
    "LPAREN",
    "RPAREN",
    "AND",
    "OR",
    "STRING",
)

t_AND    = r'\/\\'
t_OR     = r'\\\/'
t_LPAREN = r'\('
t_RPAREN = r'\)'

t_ignore = ' \t\n'

def t_error(t):
    print(t)
    print("Illegal character '{}'".format(t.value[0]))
    t.lexer.skip(1)

def t_STRING(t):
    r'^(?!\)|\(| |\t|\n|\\\/|\/\\)'
    t.value = t
    return t

data = "b_1 /\ (x_2 <= 2 \/ (b_3 /\ ((/ 1 3) <= x_4))"

lexer = lex.lex()

lexer.input(data)

while True:
    tok = lexer.token()
    if not tok:
        break
    print(tok.type, tok.value, tok.lineno, tok.lexpos)

但是，我得到以下输出：

~$ python3 lex.py
LexToken(error,'b_1 /\\ (x_2 <= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,0)
Illegal character 'b'
LexToken(error,'_1 /\\ (x_2 <= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,1)
Illegal character '_'
LexToken(error,'1 /\\ (x_2 <= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,2)
Illegal character '1'
AND /\ 1 4
LPAREN ( 1 7
LexToken(error,'x_2 <= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,8)
Illegal character 'x'
LexToken(error,'_2 <= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,9)
Illegal character '_'
LexToken(error,'2 <= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,10)
Illegal character '2'
LexToken(error,'<= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,12)
Illegal character '<'
LexToken(error,'= 2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,13)
Illegal character '='
LexToken(error,'2 \\/ (b_3 /\\ ((/ 1 3) <= x_4))',1,15)
Illegal character '2'
OR \/ 1 17
LPAREN ( 1 20
LexToken(error,'b_3 /\\ ((/ 1 3) <= x_4))',1,21)
Illegal character 'b'
LexToken(error,'_3 /\\ ((/ 1 3) <= x_4))',1,22)
Illegal character '_'
LexToken(error,'3 /\\ ((/ 1 3) <= x_4))',1,23)
Illegal character '3'
AND /\ 1 25
LPAREN ( 1 28
LPAREN ( 1 29
LexToken(error,'/ 1 3) <= x_4))',1,30)
Illegal character '/'
LexToken(error,'1 3) <= x_4))',1,32)
Illegal character '1'
LexToken(error,'3) <= x_4))',1,34)
Illegal character '3'
RPAREN ) 1 35
LexToken(error,'<= x_4))',1,37)
Illegal character '<'
LexToken(error,'= x_4))',1,38)
Illegal character '='
LexToken(error,'x_4))',1,40)
Illegal character 'x'
LexToken(error,'_4))',1,41)
Illegal character '_'
LexToken(error,'4))',1,42)
Illegal character '4'
RPAREN ) 1 43
RPAREN ) 1 44

t_STRING令牌未正确识别。

问题：如何为t_STRING设置catch all正则表达式，以获得有效的令牌生成器？

regex python-3.x parsing lex ply
1个回答
0
投票

您对T_STRING的正则表达式肯定不会满足您的要求。它的作用是很难回答。

原则上，它仅由两个零长度的断言组成：^，仅在字符串的开头为真（除非提供了re.MULTILINE标志，否则不为），以及长的负数前瞻性断言。

仅包含零长度断言的模式，如果完全匹配任何内容，则只能匹配空字符串。但是词法分析器模式不能匹配空字符串。 Lexers将输入分为一系列标记，以便输入中的每个字符都属于某个标记。每个比赛-都是比赛，而不是搜索-恰好在上一场比赛的末尾开始。因此，如果一个模式可以匹配空字符串，那么词法分析器将在相同的位置尝试下一个匹配项，并获得相同的结果，这将是一个无休止的循环。

某些词法生成器通过使用内置的全部捕获错误模式来强制最小字符匹配来解决此问题，但是如果模式匹配空字符串，Ply只会拒绝生成词法器。但是Ply并没有抱怨这个词法分析器规范。唯一可能的解释是该模式无法匹配任何内容。

关键是Ply使用re.VERBOSE标志编译所有模式，这使您可以使用空格分隔正则表达式中的项目，从而使正则表达式不易读。如Python文档所示：

模式内的空格将被忽略，除非是在字符类中，或以未转义的反斜杠开头，或在诸如*?，(?:或(?P<...>之类的标记中。

空白包含换行符甚至注释（以#字符开头，因此您可以将模式分成几行并为每段插入注释。

事实上，我们可以按照您的模式来做：

def t_STRING(t):
    r'''^         # Anchor this match at the beginning of the input
        (?!       # Don't match if the next characters match:
           \)   | # Close parenthesis
           \(   | # Open parenthesis
           \    | # !!! HERE IS THE PROBLEM
           \t   | # Tab character
           \n   | # Newline character
           \\\/ | # \/ token
           \/\\   # /\ token
        )
     '''
    t.value = t
    return t

因此，当我在您的模式中添加空格和注释时，我必须注意到原始模式试图将空格字符与| |替代。但是由于该模式被编译为re.VERBOSE，所以该空格字符将被忽略，从而留下一个与空字符串匹配的空替代字符。该替代方法是否定超前断言的一部分，这意味着如果在该点匹配的字符串以空字符串开头，则断言将失败。当然，每个字符串以空字符串开头，因此否定超前断言总是失败，解释了为什么Python不抱怨（以及为什么它从不匹配任何东西）。

不管那种特殊的故障，该模式都无法使用，因为正如已经提到的，词法分析器模式必须与某些字符匹配，因此仅与空字符串匹配的模式是无用的。我们想要做的是匹配任何字符，前提是负前瞻（已更正，如下所示）允许这样做。因此，这意味着否定的超前断言显示后跟.，它将与下一个字符匹配。

但是您几乎可以肯定不希望只匹配一个字符。大概您想匹配不与任何其他标记匹配的字符串。因此，这意味着将否定的超前断言和后续的.放入重复项。并且请记住，它必须是非空重复（+，而不是*），因为模式不得具有空匹配项。

最后，绝对没有必要使用锚断言，因为这会将模式限制为仅在输入的开头进行匹配，而这肯定不是您想要的。目前还不清楚它在做什么。 （我已经看到一些建议，这些建议建议使用带有负前瞻search的锚点，我认为这通常是被误导的，但是该讨论超出了此问题的范围。）]

并且在编写模式之前，让我们进行更多调整：在Python正则表达式中，如果可以用字符类替换一组替代项，则应该这样做，因为它效率更高。即使只有一些替代品可以替代，这也是事实。

因此会产生以下内容：

def t_STRING(t):
    r'''(
         (?!            # Don't match if the next characters match:
            [() \t\n] |   # Parentheses or whitespace
            \\\/      |   # \/ token
           \/\\           # /\ token
         ) .            # If none of the above match, accept a character
        )+              # and repeat as many times as possible (at least once)
     '''
    return t

我删除了t.value = t。 t是令牌对象，而不是字符串，并且值应该是它匹配的字符串。如果使用循环引用覆盖该值，则将无法找出匹配的字符串。

这有效，但与您预期的方式不完全相同。由于T_STRING中不包含空格字符，因此不会获得表示(/ 1 3) <= x_4的单个标记。相反，您获得了一系列令牌：

STRING b_1 1 0
AND /\ 1 4
LPAREN ( 1 7
STRING x_2 1 8
STRING <= 1 12
STRING 2 1 15
OR \/ 1 17
LPAREN ( 1 20
STRING b_3 1 21
AND /\ 1 25
LPAREN ( 1 28
LPAREN ( 1 29
STRING / 1 30
STRING 1 1 32
STRING 3 1 34
RPAREN ) 1 35
STRING <= 1 37
STRING x_4 1 40
RPAREN ) 1 43
RPAREN ) 1 44

但是我认为这是合理的。词法分析器如何分辨(x_2 <= 2和(b_3中的括号是括号标记，而(/ 1 3) <= x_4中的括号是T_STRING的一部分？该确定将需要在解析器中进行。

实际上，即使您不需要（但还）不需要完整的标记化，我的意愿是将输入完全标记化。正如整个问答所显示的那样，试图识别“除了...以外的所有东西”实际上比识别所有标记要复杂得多。与使所有令牌令牌化并通过解析器相比，试图让令牌发布者找出哪些令牌有用而哪些令牌不是通常[[更困难。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.