Transforming LR(k) Grammars into LALR(k) Grammars

Abstract

본 연구에서는 임의의 LR(k) 문법을 그와 동일한 언어를 생성하는 LALR(k) 문법으로 변환하는 방법이 개발되었다. 이를 위하여 주어진 LR(k) 문법에 대한 LR(k)-colored 문법을 SLR(k) 성질 또는 LALR(k)성질을 유지하면서 축약시키는 방법들이 연구되었으며, 특히 LR(1) 문법을 LALR(1) 문법으로 효율적으로 변환시키는 알고리즘이 개발되었다.

We present a method of transforming an arbitrary LR(k) grammar G into an equivalent LALR(k) grammar by reducing the LR(k)-colored grammar for G. For this, we develop a few effective methods to reduce the LR(k)-colored grammar, preserving the SLR(k) and/or LALR(k) properties. In particular, an efficient algorithm for the case of k=1 is developed.

We present a method of transforming an arbitrary LR(k) grammar G into an equivalent LALR(k) grammar by reducing the LR(k)-colored grammar for G. For this, we develop a few effective methods to reduce the LR(k)-colored grammar, preserving the SLR(k) and/or LALR(k) properties. In particular, an efficient algorithm for the case of k=1 is developed.