[프로그래밍언어] Ch4 Lexical and Syntax Analysis

Lexical Analysis와 Syntax Analysis를 구분하는 이유

• 단순성 - 덜 복잡한 접근 방식을 어휘 분석에 사용할 수 있다. 이를 분리하면 파서가 단순해진다.
• 효율성 - 분리를 통해 어휘 분석기를 최적화할 수 있다.
• 이식성 - 어휘 분석기의 일부는 다른 언어로 이식이 불가능할 수 있지만 파서는 항상 이식이 가능하다.

Lexical Analysis

어휘 분석이란 소스 프로그램을 읽어 들여 token이라는 의미 있는 문법 단위(문법에서 터미널 심볼에 해당함)로 분리하는 것을 말한다.

즉, 보통 구문을 분석하면서 다음 토큰이 필요할 때마다 어휘 분석기를 호출하는 것이다.

이렇게 구분된 token들에 에러가 있는지 검사하고 또한 문자열에서 공백을 제거하기도 한다.

어휘를 분석하는 방법

 

Syntax analysis

구문 분석은 파싱이라고도 불린다.

 expression, statement, program unit 단위로 문법 검사를 하며 해당 입력의 AST(추상 구문 트리)를 생성하여 반환한다.

 

파싱의 목적은 끝까지 오류를 찾아내고 AST를 생성하는 것이다.

 

Recursive-Descent Parser

(= RD 파서)

1. Top-down Parser

LL 파싱

: 가장 대표적인 하향식 파싱이다.

입력 문자열의 왼쪽(Left to Right)에서부터 읽으며, 좌측유도(Leftmost derivation) 방식으로 동작한다.

 

FISRT(A)란 넌터미널 심볼 A로부터 유도되어 첫 번째로 나타낼 수 있는 터미널 심볼들의 집합을 의미한다.

또한 빈스트링이 유도 가능하면 ε (입실론)도 가능하다.

 

2. Bottom-up Parser

개념 정리

• phrases: 부분 parse tree의 모든 leap 노드들로 구성된 문자열
• simple phrases: 단 한 번의 derivation을 통해서 만들어진 어구  
• handle: rightmost의 역순으로 올 수 있는 nonterminal과 terminal의 조합으로 handle은 simple phrase에 해당한다.

LR 파싱

:가장 대표적인 상향식 파싱이다.

LR 파싱에서 L은 왼쪽부터 오른쪽으로 입력 스트링을 읽어들이는 것을, R은 우측 유도 방식으로 동작하는 것을 의미한다.

 

LR 파서는 Shift-Reduce 파싱 형식을 사용한다.

이 방식은 이전에 파싱된 상황을 기록하고 있는 파싱 스택을 사용한다.

이 파서는 스택의 내용과 다음 입력 토큰을 미리 보고, parsing table을 참조하여 다음에 취해야 할 action을 결정한다.

 

 

예시를 들어보겠다.

 

다음과 같은 BNF Rule이 있다고 하자.

1. E -> E+ T
2. E -> T
3. T -> T * F
4. T -> F
5. F ->(E)
6. F -> id

 

그리고 소프트웨어 툴이 다음과 같은 parsing table을 줬다고 하자.

 

그러면 LR 파싱의 과정은 아래와 같다.

자세히 설명해보자면 스택의 초기상태는 0으로 둔다.

그리고 Input을 통해 Lexical Analyzer가 Input의 제일 앞에 있는 값을 알려준다.

그리고 현재의 토큰과 상태를 보고 Parsing Table 통해 Action을 취할 수 있다.

 

Shift는 Input에서 앞의 부분을 빼서 stack에 넣어주는 역할을 한다.

Shift 다음에 오는 숫자는 현재 상태를 의미한다.

 

Reduce는 BNF 규칙을 반대로 적용하는 것이다.

BNF 규칙을 통해 stack에 있는 값을 줄여나갈 수 있다.