파이핑을 사용하여 정규 표현식 구문 분석

Question

필자는 pyparsing을 사용하여 단순화 된 정규 표현식 파서를 작성하려고합니다 (결합 외에도 * 및 | 연산자 만 지원). 여기 내 문법은 지금까지의 : 나는 시도하고 간단한 표현 (예를 들어, regular_expression.parseString("a")를) 구문 분석 할 때

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 

나는 무한 재귀를 얻고있다. 연결에 대한 내 정의에 문제가 있습니까?

참고로 나는 this 문법을 적용하려고합니다.

Answer 1

현재 (무한 재귀)보고있는 문제는 문법의 왼쪽 재귀 때문입니다. pyparsing은 문법에서 명시 적으로하지 않는 한 미리보기가없는 순전히 왼쪽에서 오른쪽으로 구문 분석하는 것입니다. 따라서 목록을 다음과 같이 정의하는 경우 :

expr ::= expr | expr 

그러면 먼지가 딱딱해질 것입니다.

저는이 부분이 파서가 많은 반복적 인 재귀 용어로 가득 차 있다고 생각합니다. 파싱하는 내용에 대한 생각을 멈추고 생각할 수 있고 심지어 단순화 된 BNF로 캡쳐하면 생각을 명확히하는 데 도움이됩니다. 여기

은 내가 가진 무엇 :

• 표현이있는 각각의 내부() 단일 문자 또는 표현이다, 조각들로 구성 할 수의, 선택적으로 일부 반복 표시 다음에 ('*' 또는 '?'의 정수 및 {}의 정수 등)
• 이 조각들은 서로 나란히 배치 될 수 있습니다.
• 이 조각들은 '|'로 분리 될 수 있습니다. 대안

이상 공식적으로 약간을 표시하려면 다음 re_expr 만에 여는 괄호 일치 한 후, 회귀 할 수 있기 때문에이 파서에는 왼쪽 재귀가 없다

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

. 대한 파싱로 번역

거의 그대로입니다 :

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