정규 LR (1) 파서 닫음을 결정하기 위해 전이 폐쇄에 대한 Warshall의 알고리즘을 사용하는 방법은 무엇입니까?

Question

저는 LR (1) 클로저를 빨리 계산할 수있는 Warshall의 알고리즘을 구현하려고합니다. 그래프의

• 노드는, LR items 있습니다 A → B • C
• 처럼 가장자리가 A → B • C에서 C → • D
에 시작 "전환"은 다음과 같습니다

나는 내가 (0)이 LR 작동 방식을 이해 생각

문제는 LR (1)은 미리보기 계산이 필요하며 알고리즘에 알고리즘을 통합하는 방법을 알 수 없습니다. 그게.
내가 알고 있더라도 주어진 LR 항목의 전이 폐쇄 I 여전히은 각 항목에 대해 설정된 미리보기가 무엇인지 알아 내기 위해 동일한 계산을 거쳐야합니다.

Warshall의 알고리즘을 사용하여 정규 LR (1) 클로저를 계산할 수 있습니까? 아니면 LR (0), SLR (1) 등과 같이 제한된 경우에만 가능합니까?

Answer 1

새 항목을 추가 할 때마다 Warshall의 알고리즘을 사용할 수 있다고 생각하지 않습니다. 다른 항목을 추가해야 할 수도 있기 때문입니다. 그것은 반복적 인 과정입니다. 유향 그래프 또는 연결 행렬은 계속 변화합니다. 나는 이것에 대해 잘못 될 수있다. 클로저 세트에 이미 포함 된 항목의 배열을 유지하면서 반복적 인 프로세스로 LR (1) 항목 세트의 클로저를 계산했습니다. 원하는 경우 내 LRSTAR Parser Generator을 다운로드하고 소스 코드를 살펴보십시오. 자신 만의 파서 생성기를 작성하고 LRSTAR를 사용할 필요가 없다고 결정할 수 있습니다. 참고 : 저는 Warshall의 알고리즘 대신에 DeRemer의 논문의 Digraph 알고리즘을 사용하여 미리보기 세트를 계산했습니다. list of papers implemented in LRSTAR on the website을 참조하십시오.