LR 파서는 주어진 문장을 인식하는 과정에 있어 파싱 테이블을 참조해 각 단계마다 어느 행동을 취해야하는지 결정적으로 택할 수 있습니다. 파싱 테이블은 상태를 행으로 그리고 심볼을 열로 가져 주어진 상태와 주어진 심볼을 가지고 어느 행동을 파서가 내려야 하는지 알려줍니다. 해당 문법에서 구할 수 있는 모든 서로 다른 reachable closed item sets은 LR 파싱 테이블의 상태가 됩니다. 이는 주어진 문법을 확장해, 원 문법의 시작심볼과 end marker을 유도하는 새로운 시작심볼 그리고 해당 생성규칙을 추가한 문법을 구하고, item S' -> · S eof 에 대해 클로저 연산을 수행해 얻은 closed item set을 다시 거듭 변환해가며 얻을 수 있습니다.


그런데, 그렇게 LR 파싱 테이블의 상태를 구하는 과정을 반복하다보니, 문득 비결정적 유한 오토마타를 결정적 유한 오토마타로 변환하는 과정과 유사한 점이 있지 않나 하는 생각이 들었습니다. 구체적으로, 비결정적 유한 오토마타에서 주어진 입력에 대해 하나의 전이를 구하는 대신 가능한 전이의 집합을 구하지만, 그를 결정적 유한 오토마타로 변환하기 위해 모든 가능한 서로 다른 전이 집합을 새로 변환해 얻어내고자 하는 결정적 유한 오토마타의 각 상태로 보는 부분과 유사하지 않나 싶었습니다. 각 closed item set에 대해 집합 전체를 하나의 연산대상으로 보아 그에 대해 모종의 연산을 가할 경우 어느 다른 closed item set으로 변하게 되는지에 초점을 맞추어 결국 결정성을 얻어냈다는 점이 유사한 것 같았기 때문입니다.


제가 하고자 하는 질문은, 그렇다면 LR 파서는 비결정성을 결정적으로 다루는 한 사례라 볼 수 있을까요?