Разбор регулярных выражений с pyparsing

Я пытаюсь написать упрощенный парсер регулярных выражений (только для операторов * и | в дополнение к конкатенации) с использованием pyparsing. Вот моя грамматика до сих пор:Разбор регулярных выражений с pyparsing

from pyparsing import alphas, Word, Forward 

regular_expression = Forward() 

character = Word(alphas, max=1) 
group  = '(' + regular_expression + ')' 
star  = (character | group) + '*' 

# A 'concat_expression' is any string concat of the above 
# String concat with a 'concat_expression' also produces a 'concat_expression' 
concat_expression = Forward() 
concat_expression << ((character | group | star | concat_expression) + 
         (character | group | star)) 

or_expression = regular_expression + '|' + regular_expression 

regular_expression << or_expression | concat_expression

Я получаю зацикливание, когда я пытаюсь разобрать простые выражения (например, regular_expression.parseString("a")). Что-то не так с моим определением конкатенации?

Для справки, я пытаюсь адаптировать грамматику this.

источник

2016-10-04 rookie

Вопрос, который вы смотрите на данный момент (бесконечная рекурсия), обусловлен левой рекурсией в вашей грамматике. pyparsing - чисто левый-правый разбор, без взгляда (если вы не делаете это явно в своей грамматике). Таким образом, вы, если определите список как:

expr ::= expr | expr

тогда он будет просто спрятаться в грязь.

Я думаю, что часть этого состоит в том, что ваш синтаксический анализатор является разновидностью повсюду со множеством избыточных рекурсивных терминов. Если вы можете остановиться и подумать о том, что вы разбираете, и даже захватить его в какой-то упрощенный BNF, это должно помочь прояснить ваше мышление.

Вот что я получил:

выражение может состоять из частей, каждая из которых представляет собой отдельный символ или выражение в() «s, возможно, с последующим некоторым индикатором повторения (» *» или '?' и/или целое число в {} и т. д.)
эти части могут быть соединены друг с другом друг с другом
эти части могут быть разделены на '|' указать альтернативы

или чуть более формально:

re_item  ::= (character | '(' re_expr ')') [repetition] 
re_item_seq ::= re_item+ 
repetition ::= '*' | '?' 
re_expr  ::= re_item_seq [ '|' re_item_seq ]...

Там нет левой рекурсии в этом парсер, так как re_expr может быть Рекурсия только после согласования в открывающую скобку.

Переводя на Pyparsing почти дословно:

from pyparsing import (alphas, Word, Forward, oneOf, OneOrMore, Optional, 
    delimitedList, Group) 

character = Word(alphas, exact=1).setName("character") # <- use 'exact', not 'max' 

regular_expression = Forward() 
group  = Group('(' + regular_expression + ')') 
repetition = oneOf("* ?") 

re_item = Group((character | group) + repetition) | character | group 
re_item_seq = OneOrMore(re_item) 

regular_expression <<= delimitedList(re_item_seq, '|')

Тестирование это:

regular_expression.runTests(""" 
    a 
    a? 
    sdlfj*(b|c)? 
    """)

дает:

a 
['a'] 


a? 
[['a', '?']] 
[0]: 
    ['a', '?'] 


sdlfj*(b|c)? 
['s', 'd', 'l', 'f', ['j', '*'], [['(', 'b', 'c', ')'], '?']] 
[0]: 
    s 
[1]: 
    d 
[2]: 
    l 
[3]: 
    f 
[4]: 
    ['j', '*'] 
[5]: 
    [['(', 'b', 'c', ')'], '?'] 
    [0]: 
    ['(', 'b', 'c', ')'] 
    [1]: 
    ?

TL; DR - читать на "левой рекурсии", также вы можете посетить этот пример повторного разбора (который инвертирует re в список строк-кандидатов, который может соответствовать re): http://pyparsing.wikispaces.com/file/view/invRegex.py/111533811/invRegex.py

источник

2016-10-05 00:28:10 PaulMcG

Разбор регулярных выражений с pyparsing

ответ

Смежные вопросы