LALR

LALR(Look-Ahead LR)은 구문 분석 방식의 한 종류이며 선행 예측(Lookahead) LR 파서의 특별 버전이다. 단순 LR 파서(Simple LR, SLR) 구문 분석기보다 더 많은 문맥 문법을 다룰 수 있다. 구문 분석을 위한 테이블(table, 사양)이 간단하여 많은 구문 문법을 처리할 수 있으므로 가장 일반적인 구문 분석 방식으로 사용하고 있다. yacc나 bison과 같은 컴파일러 컴파일러와 같은 소프트웨어가 이 방식을 이용하여 처리하고 있다.

단순 LR 방식과 마찬가지로, LALR은 LR(0)의 구문 분석 테이블을 사용한다. 단순 LR 방식은 Follow 집합을 사용해 reducing하는 반면, LALR 방식은 선행 예측 집합(Lookahead set)을 사용한다.

참고 문헌

• Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison--Wesley, 1986. (LALR(1) 구문 분석기의 제작에 관한 기존 기법의 해설)
• Frank DeRemer and Thomas Pennello. Efficient Computation of LALR(1) Look-Ahead Sets. ACM Transactions on Programming Languages and Systems(TOPLAS) 4:4, pp. 615 649. 1982. (보다 효율적인 LALR(1) 구문 분석기 구축 기법의 설명)
• Richard Bornat Understanding and Writing Compilers, Macmillan, 1979. (구문 분석과 구문 분석 테이블등의 기본 원리 해설)

같이 보기

• yacc
• bison
• ANTLR
• LALR 구문 분석기