cfg 파서에서 왼쪽 재귀를 해결하려면 어떻게해야합니까?

Question

어떻게이 왼쪽 재귀를 해결할 수 있습니까? 나는 해결책을 찾는 데 오랜 시간이 걸렸지 만 나는 그것에 투쟁한다. 문장 : Bob은 Max 자동차를 제공합니다. 여기서 보여주고 싶은 요점은 발생하는 왼쪽 재귀입니다. 어떤 NP -> NP, 어떻게이 문제를 해결할 수 있습니까? 지금 python3에서이 코드를 실행하면 충돌이 발생합니다.

import nltk.grammar 

grammar = nltk.CFG.fromstring(""" 
S -> NP VP 
VP -> V NP 
NP -> "cars" | "Bob" | NP | "Max" 
V -> "gives" 
""") 

sent = "Bob gives Max cars".split() 
rd_parser = nltk.RecursiveDescentParser(grammar) 
for tree in rd_parser.parse(sent): 
    print(tree) 

Answer 1

재귀 규칙을 작성하지 않음으로써 문제를 해결하십시오. 당신이 필요로하는 문장을 찾을 수 없다면, 그것을 필요로하지 않습니다.

재귀 규칙은 CFG에서 유효합니다. 그것이 무한한 수의 문장을 생성 할 수있는 방법입니다. 그리고 왼쪽 재귀 문법을 사용하면 재귀 적 파생 구문 은이 일부 입력으로 영원히 돌아갑니다. 그것이 바로 그 것이고, 그래서 더 똑똑한 구문 분석 알고리즘이 있습니다.

Answer 2

NP -> NP은 왼쪽 재귀 규칙입니다. 그러나 그것은 문법에 의해 생성 된 언어를 변경하지 않기 때문에 무의미한 규칙이기 때문에 문법을 모호하게 만듭니다.

그래서 문법에 NP -> NP을 추가하면 "Bob give max car"를 구문 분석 할 수 있다고 생각하는 경우에는 그렇지 않습니다. 그리고 이것은 파서와 아무런 관련이 없지만, 그 문장은 문법에 의해 생성 된 언어가 아닙니다.

해당 문장을 얻기 위해 파싱 트리를 그리십시오. 그 문법을 따르는 사람이 없다는 것을 알게 될 것입니다. 그러나 이 문법에 부합하지 않는을 찾으면 그 문장을 처리하기 위해 문법을 변경하는 방법을 알려야합니다. (문장을 생성 할 수있는 다양한 문법을 ​​반영한 다양한 나무가있을 수 있습니다. 귀하의 직업은 이고은 파서가 처리 할 수있는 문구를 골라야합니다.)