어휘 및 구문 분석

어휘 및 구문 분석은 컴파일러의 프런트 엔드를 구성하며, 소스 텍스트를 토큰으로 분해하고 구문 분석 트리(parse tree) 또는 구문 트리(syntax tree)로서 문법적 구조를 인식합니다.

Definition

어휘 분석은 입력 문자를 토큰으로 그룹화하는 단계이며, 구문 분석(파싱)은 해당 토큰이 문법에 따라 유효한 프로그램을 구성하는지 여부와 방법을 결정하여 구문 트리를 생성하는 단계입니다.

Scope

이 주제는 정규 언어와 유한 오토마타를 사용하여 문자 스트림을 토큰으로 변환하는 어휘 분석과, 문맥 자유 문법(context-free grammar)에 따라 프로그램의 구문 구조를 인식하는 구문 분석(파싱)을 다룹니다. 여기에는 하향식(LL) 및 상향식(LR) 파싱, 파서 생성기, 모호성 및 오류 복구, 그리고 추상 구문 트리(abstract syntax tree) 구성이 포함됩니다.

Core questions

• 정규 언어와 문맥 자유 언어는 프로그램 구조를 설명하는 데 어떻게 사용됩니까?
• LL 파싱과 LR 파싱 간의 장단점은 무엇입니까?
• 모호성 및 구문 분석 오류는 어떻게 감지되고 처리됩니까?
• 토큰 스트림에서 추상 구문 트리는 어떻게 구축됩니까?

Key theories

LR 파싱

크누스가 도입한 LR 파싱은 선형 시간 내에 광범위한 LR 문법을 결정적으로 파싱하는 상향식 기법으로, 많은 파서 생성기의 기반을 형성합니다.

일반 문맥 자유 파싱

얼리 알고리즘은 모호한 문법을 포함하여 임의의 문맥 자유 문법을 파싱하며, 제한된 결정론적 파서가 불충분할 때 일반적인 방법을 제공합니다.

프런트 엔드의 정규 및 문맥 자유 기반

드래곤 북(The Dragon Book)은 스캐닝을 위한 정규 표현식과 유한 오토마타, 파싱을 위한 문맥 자유 문법의 사용을 체계화하며, 표준 LL 및 LR 구성 알고리즘을 포함합니다.

Clinical relevance

렉싱(lexing)과 파싱(parsing)은 컴파일러뿐만 아니라 인터프리터, 린터(linter), 포맷터(formatter), IDE, 그리고 데이터 형식 처리기에도 필수적인 기반입니다. 우수한 오류 복구 기능을 갖춘 견고한 파싱은 모든 언어 도구의 개발자 경험에 필수적입니다.

History

1950년대 후반 촘스키(Chomsky)의 형식 언어 계층(formal language hierarchy)은 정규 언어와 문맥 자유 언어의 이론적 기반을 제공했습니다. 1965년 크누스(Knuth)는 LR 파싱을 형식화했고, 1970년 얼리(Earley)는 일반적인 문맥 자유 알고리즘을 제시했습니다. yacc와 같은 파서 생성기는 LR 파싱을 실용화했으며, 이후 연구에서는 파싱 표현 문법(parsing expression grammars)과 조합기 기반 파서(combinator-based parsers)를 탐구했습니다.

Debates

생성된 파서 대 수동 작성 파서

실무자들은 간결하고 검증 가능한 형식 문법에서 파서 생성기를 사용하는 것과, 더 많은 코드를 필요로 하지만 종종 더 나은 오류 메시지와 제어를 제공하는 수동 작성 재귀 하강 파서(recursive-descent parsers)를 사용하는 것에 대해 논쟁합니다.

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

렉서(lexer)와 파서(parser)의 차이점은 무엇입니까?

렉서는 원시 문자를 식별자 및 연산자와 같은 토큰으로 그룹화하는 반면, 파서는 해당 토큰을 언어의 문법에 따라 계층적 구문 트리로 배열합니다.

LL 파싱과 LR 파싱의 차이점은 무엇입니까?

LL 파서는 입력 접두사에서 프로덕션(production)을 예측하여 하향식으로 작동하는 반면, LR 파서는 인식된 부분 문자열을 축소하여 상향식으로 작동합니다. LR은 엄격하게 더 넓은 범위의 문법을 처리하지만 구성하기가 더 복잡합니다.