On the Efficient Resolution of LALR(1) Parsing Conflicts

Abstract

LR(1) 문법이지만 LALR(1) 문법이 아닌 문법을 파싱하기 위해서는 그 문법을 LALR(1) 문법으로 변형시키거나 LR(1) 파싱 테이불을 형성하여야 한다. 본 연구에서는 LALR(1) 문법이 아닌 LR(1) 문법의 LALR(1) 파싱에서 발생하는 충돌을 효율적으로 해결하는 새로운 방법을 개발하였다. 주어진 문장을 RALR(1) 파싱하는 과정에서 파싱충돌을 만나면 먼저 현재의 파싱 스택의 내용과 현재의 LR(0) 상태 (파싱 스텍의 top)에 대해 미리 구성된 충돌해결자(conflict-resoving automaton)를 이용하여, 만일 LR(1) 파싱이 행해졌다면 도달했을 LR(1) 상태를 식별하고, 또한 미리 계산된 파싱충돌을 내포하고 있는 LR(0) 상태들의 LR(1) 상태에서의 Lookhead 정보를 이용하여 파서의 올바른 행동을 결정하므로써 파싱충돌을 해결한다. 이를 위하여, LR 파싱의 여러 특성을 잘 기술할 수 있도록 개발된 LR(k)-colored grammar의 성질을 이용하여 먼저 위와 같이 LR(1) 상태를 식별할 수 ?獵? 방법을 성형적으로 기술한다. 이러한 성형론을 바탕으로 파싱충돌을 내포하고 있는 LR(0) 상태들에 대하여 현재의 파싱 스택을 입력으로 하는 유한자동기계(finite automaton)인 충돌해결자를 구성하는 방법을 개발하였다.

For a given LR(1) grammar which is not LALR(1), we propose a new method for resloving parsing conflicts which may occur while the LALR(1) parser for the grammar processes an input string. When a parsing conflict occurs at an LR(0) state, the method identifes the LR(1) state, which would be the top of the parsing stake if LR(1) parsing was performed, by the use of the current content of the parsing stack and a conflict-resolving automaton for the LR(0) state; and then the method selects the correct the correct parsing action with the previously computed LR(1) lookahead information. For this, we establish the formalism for identifying LR(1) states by utilizing the properties of the LR(1)-colored grammar for the given grammar. On the basis of the formalism, we present a method for constructing the conflict-resolvin gautomata for LR(0) states which exhibit LALR(1) parsing conflicts.

For a given LR(1) grammar which is not LALR(1), we propose a new method for resloving parsing conflicts which may occur while the LALR(1) parser for the grammar processes an input string. When a parsing conflict occurs at an LR(0) state, the method identifes the LR(1) state, which would be the top of the parsing stake if LR(1) parsing was performed, by the use of the current content of the parsing stack and a conflict-resolving automaton for the LR(0) state; and then the method selects the correct the correct parsing action with the previously computed LR(1) lookahead information. For this, we establish the formalism for identifying LR(1) states by utilizing the properties of the LR(1)-colored grammar for the given grammar. On the basis of the formalism, we present a method for constructing the conflict-resolvin gautomata for LR(0) states which exhibit LALR(1) parsing conflicts.