재귀 적 쓰기 Parsarsing을 사용하는 파서

Question

pyparsing에서 Forward() 요소를 이해하려고합니다. 나는이 간단한 BNF가 있다고 가정 :

identifier = 
    "a..z,$,_" < "a..z,$,_,0..9" > 

package_name = 
    identifier 
/(package_name "." identifier) 

와 난 그냥 java 결과 또는 전혀 재귀에서 반환하거나 얻을 java.lang.String 같은 간단한 패키지를 구문 분석하려고합니다.

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal 

identifier=Word(alphas+"$_",alphanums+"$_") 
dot=Literal(".") 

package_name = Forward() 
definition = package_name+dot+identifier 
package_name << Group(identifier+ZeroOrMore(definition)) 

package_name.parseString("java.lang.String") 

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal 

identifier=Word(alphas+"$_",alphanums+"$_") 
dot=Literal(".") 

package_name = Forward() 
definition = identifier^package_name+dot+identifier 
package_name << definition 

package_name.parseString("java.lang.String") 

재귀 제한

에 도달합니다 [] [ '자바'] 인쇄하는 방법이 Forward 자리 작업을 수행합니다 나는 이런 식으로 그것을 시도?

Answer 1

문제는 Forward이 아니며, 본질적으로 너무 일찍 제한되거나, Pyparsing과 같은 단순한 재귀 적 파생 분석기로 결정할 수없는 방식으로 재귀 적으로 발생합니다.

당신이 왼쪽에서 오른쪽으로 일치하는 경우

package_name = identifier | (package_name "." identifier) 

이 항상 다음과 같은 기간과 일치하도록 시도하지 않고, 정지 한 후 하나의 ID를 일치합니다

당신은이 있습니다. identifier과 일치하도록 주문을 전환 한 경우 :

package_name = (package_name "." identifier) | identifier 

. . package_name과 일치하는지 판단하기 위해서는 우선 package_name과 일치하는지 먼저 결정해야하기 때문에 무한히 반복됩니다. 이것은 left-recursive 문법으로, Pyparsing과 같은 간단한 재귀 - 하강 파서는 처리 할 수 ​​없습니다. Pyparsing은 일치가 후속 일치에 어떤 영향을 주는지 미리 볼 수 없습니다. 경기를 왼쪽에서 오른쪽으로 시도합니다.

당신은 방법 당신의 문법 재귀를 변경하는 방법 Forward 작품의 간단한 예를 얻을 수 있습니다 : 대한 파싱이 incremenetally을 일치시킬 수 있도록 여기에

identifier = pyp.Word(pyp.alphas+"$_", pyp.alphanums+"$_") 
package_name = pyp.Forward() 
package_name << ((identifier + '.' + package_name) | identifier) 

>>> package_name.parseString("java.lang.String") 
[u'java', u'.', u'lang', u'.', u'String'], {}) 

은 재귀가 아닌 왼쪽, 오른쪽에 발생합니다.

(ZeroOrMore의 사용법은 청어입니다. 이와 같은 재귀 문법을 사용하려는 경우 재귀 정의에서 이미 여러 번 일치 할 수 있으므로 ZeroOrMore를 사용하고 싶지는 않습니다. 내 의견에 제안했듯이, 어쨌든 이런 재귀 문법을 정의하는 것이 훨씬 간단하다.)