Рекурсия в Pyparsing

Question

Im неспособна перевести это выражение EBNF в Pyparsing, любую идею?

token:: [A-Z] 
P:: !|token;P|(P^P)|(P*P) 

Проблема заключается в использовании рекурсии, переводчик терпит неудачу. Expression, как это должно быть в силе:

(ASD;!^FFF;!) 
A;B;C;! 
(((A;!^B;!)^C;D;!)*E;!) 

Answer 1

Чтобы построить рекурсивную грамматику с Pyparsing, вы должны думать немного наизнанку, используя Форвард класс Pyparsing в. В Forward вы определяете пустой заполнитель для выражения, которое будет определено позже. Вот начало в Pyparsing для этого BNF:

EXCLAM,SEMI,HAT,STAR = map(Literal,"!;^*") 
LPAR,RPAR = map(Suppress,"()") 
token = oneOf(list(alphas.upper())) 

Я использую Буквальный для определения ваших операторов, но подавление группировки() 's, мы будем использовать Pyparsing Группы физически группу результатов в подсписки.

Теперь определим выражение шаблонного с Forward:

expr = Forward() 

И теперь мы можем построить выражение с помощью этого заполнитель (мы должны использовать «< < =» как оператор присваивания, так что выражение поддерживается в вперед, а не отскок к самому выражению). Вот мой первый проход, используя свой BNF как есть:

expr <<= (EXCLAM | 
      token + SEMI + expr | 
      Group(LPAR + expr + HAT + expr + RPAR) | 
      Group(LPAR + expr + STAR + expr + RPAR)) 

Это дает следующие результаты:

(ASD;!^FFF;!) 
^
Expected ";" (at char 2), (line:1, col:3) 

A;B;C;! 
['A', ';', 'B', ';', 'C', ';', '!'] 

(((A;!^B;!)^C;D;!)*E;!) 
[[[['A', ';', '!', '^', 'B', ';', '!'], '^', 'C', ';', 'D', ';', '!'], '*', 'E', ';', '!']] 

Кажется, есть неписаное правило в вашей BNF, что один или несколько маркеров может вместе присутствовать также легко фиксируется как:

expr <<= (EXCLAM | 
      OneOrMore(token) + SEMI + expr | 
      Group(LPAR + expr + HAT + expr + RPAR) | 
      Group(LPAR + expr + STAR + expr + RPAR)) 

Теперь дает:

(ASD;!^FFF;!) 
[['A', 'S', 'D', ';', '!', '^', 'F', 'F', 'F', ';', '!']] 

A;B;C;! 
['A', ';', 'B', ';', 'C', ';', '!'] 

(((A;!^B;!)^C;D;!)*E;!) 
[[[['A', ';', '!', '^', 'B', ';', '!'], '^', 'C', ';', 'D', ';', '!'], '*', 'E', ';', '!']] 

Но похоже, что мы могли бы выиграть от дополнительной группировки, так что операнды для двоичных операторов «^» и «*» более четко сгруппированы. Поэтому я остановился на:

expr <<= (EXCLAM | 
      Group(OneOrMore(token) + SEMI + ungroup(expr)) | 
      Group(LPAR + expr + HAT + expr + RPAR) | 
      Group(LPAR + expr + STAR + expr + RPAR)) 

И я думаю, что эта версия вывода будет более легко обрабатывается в настоящее время:

(ASD;!^FFF;!) 
[[['A', 'S', 'D', ';', '!'], '^', ['F', 'F', 'F', ';', '!']]] 

A;B;C;! 
[['A', ';', 'B', ';', 'C', ';', '!']] 

(((A;!^B;!)^C;D;!)*E;!) 
[[[[['A', ';', '!'], '^', ['B', ';', '!']], '^', ['C', ';', 'D', ';', '!']], '*', ['E', ';', '!']]] 

Вот полный скрипт:

from pyparsing import * 

EXCLAM,SEMI,HAT,STAR = map(Literal,"!;^*") 
LPAR,RPAR = map(Suppress,"()") 
token = oneOf(list(alphas.upper())) 
expr = Forward() 
expr <<= (EXCLAM | 
      Group(OneOrMore(token) + SEMI + ungroup(expr)) | 
      Group(LPAR + expr + HAT + expr + RPAR) | 
      Group(LPAR + expr + STAR + expr + RPAR)) 

tests = """\ 
(ASD;!^FFF;!) 
A;B;C;! 
(((A;!^B;!)^C;D;!)*E;!)""".splitlines() 

for t in tests: 
    print t 
    try: 
     print expr.parseString(t).dump() 
    except ParseException as pe: 
     print ' '*pe.loc + '^' 
     print pe 
    print 

Последнее примечание: Я предположил, что «AAA» было 3 последовательных токена «А». Если вы указали на токены, чтобы быть словом, состоящим из 1 или более альфов, измените «OneOrMore (токен)» в выражении на «Word (alphas.upper())», - тогда вы получите этот результат для своего первого теста :

[[['ASD', ';', '!'], '^', ['FFF', ';', '!']]] 

Answer 2

Это делает обозначение Lisp xd !!

from pyparsing import * 

def pushFirst(strg, loc, toks): 
    toks[0][2], toks[0][1] = toks[0][1], toks[0][2] 

def parseTerm(term): 
    """ 
    EBNF syntax elements 
    EXCLAM = ! 
    HAT =^
    STAR = * 
    SEMI = ; 
    LPAR = (
    RPAR = ) 
    """ 

    EXCLAM,HAT,STAR = map(Literal,"!^*") 
    LPAR,RPAR = map(Suppress,"()") 
    SEMI = Suppress(";") 

    token = oneOf(list(alphas.upper())) 
    expr = Forward() 
    expr <<= (
        EXCLAM | 
        Group(Word(alphas.upper()) + SEMI + ungroup(expr)) | 
        Group(LPAR + expr + HAT + expr + RPAR).setParseAction(pushFirst) | 
        Group(LPAR + expr + STAR + expr + RPAR).setParseAction(pushFirst) 
       ) 
    try: 
     result = expr.parseString(term) 
    except ParseException as pe: 
     print ' '*pe.loc + '^' 
     print pe 
    return result[0] 



def computeTerm(term): 
    print term 


term = (parseTerm("(((AXX;!^B;!)^C;D;!)*E;!)")) 

computeTerm(term)