Нужна помощь в создании рекурсивного парсера с использованием pyparsing - PullRequest
Новая
       22

Нужна помощь в создании рекурсивного парсера с использованием pyparsing

2 голосов
/ 11 марта 2009

Я пытаюсь pyparsing python для разбора. Я застрял во время создания рекурсивного парсера.

Позвольте мне объяснить проблему

Я хочу сделать декартово произведение элементов. Синтаксис 

cross({elements },{element})

Я поставил более конкретным способом 

cross({a},{c1}) or cross({a,b},{c1}) or cross({a,b,c,d},{c1}) or

Таким образом, общая форма первой группы будет иметь n элементов (a, b, c, d). Вторая группа будет иметь один элемент, поэтому конечным результатом будет декартово произведение.

Синтаксис должен быть рекурсивным, потому что он может перейти на n уровень, такой как 

cross(cross({a,b},{c1}),{c2})

Это означает пересечение a, b с c1. Скажем, результат нам у. Мы снова скрестим его с c2

Это может быть до уровня n крест (крест (крест (крест ......

)

Я хочу, чтобы объект был инициализирован с помощью setparseAction

Так что у меня будет 2 класса 

class object1(object):
     This will be used by a,b,c,d 

class object2(object):
       This will hold cross elements

Мне нужна помощь в этом, я не могу сделать рекурсивный парсер.

Ответы [ 3 ]

6 голосов
/ 11 марта 2009

Вы должны посмотреть определения других языков, чтобы увидеть, как это обычно обрабатывается.

Например, посмотрите, как определяется умножение.

Это не 

{expression} * {expression}

Потому что с рекурсией трудно иметь дело, и нет никакого подразумеваемого порядка слева направо. Чаще всего вы видите такие вещи, как 

{term} + {factor}
{factor} * {unary-expression}

, который расставляет приоритеты и упорядочивает операторы слева направо.

Посмотрите на что-то вроде http://www.cs.man.ac.uk/~pjj/bnf/c_syntax.bnf, чтобы найти примеры того, как подобные вещи обычно структурированы.

3 голосов
/ 04 ноября 2009

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

from lepl import *

def compile_parser():

    class Cross(Node): pass

    word = Token('[a-z0-9]+')
    par, en, bra, ket = [~Token('\\'+c) for c in '(){}']
    comma = ~Token(',')

    cross  = Delayed()
    vector = bra & word[1:,comma] & ket                 > list
    arg    = vector | cross
    cross += ~word('cross') & par & arg[2,comma] & en   > Cross

    parser = cross.string_parser()
    return lambda expr: parser(expr)[0]


if __name__ == '__main__':

    parser = compile_parser()
    print parser('cross({a},{c1})')
    print parser('cross({a,b},{c1})')
    print parser('cross({a,b,c,d},{c1})')
    print parser('cross(cross({a,b},{c1}),{c2})')

Вывод: 

Cross
 +- [u'a']
 `- [u'c1']

Cross
 +- [u'a', u'b']
 `- [u'c1']

Cross
 +- [u'a', u'b', u'c', u'd']
 `- [u'c1']

Cross
 +- Cross
 |   +- [u'a', u'b']
 |   `- [u'c1']
 `- [u'c2']
3 голосов
/ 11 марта 2009

Я согласен с @ S.Lott, вам следует пересмотреть свою грамматику.

Рекурсивные определения могут быть введены с использованием Forward(): 

from pyparsing import (Literal, Word, OneOrMore, Forward, nums, alphas)

def BNF():
    """
    element      :: id
    elements     :: '{' element [ ',' element ]+ '}' 
                  | 'cross' '(' elements ',' '{' element '}' ')'
    """
    lcb, rcb, lb, rb, comma = [Literal(c).suppress() for c in '{}(),']
    element  = Word(alphas, alphas+nums+"_") # id
    elements = Forward()
    elements << ((lcb + element + OneOrMore(comma + element) + rcb) 
                 | (Literal('cross') + lb + elements + comma
                    + lcb + element + rcb + rb))
    return elements

print BNF().parseString("cross(cross({a,b},{c1}),{c2})")

Выход: 

['cross', 'cross', 'a', 'b', 'c1', 'c2']
...