[PL] 03. Lexical and Syntax Analysis

기본 개념

언어 구현 시스템은 특정 구현 방법과 관계없이 소스 코드(문자 파일_Character가 연속적으로)를 분석해야 합니다.

• Lexical Analysis : 캐릭터를 받아들이고 패턴 매칭. 내가 정의한 키워드, 연산자, id 등이 맞는지 패턴이 유효한지 판
  단해서 유효한 것들을 뽑아내는 것. 유효한 것 하나하나 => lexeme (/ token)
• Syntax Analysis : BNF(구문의 형식적 설명)에 맞는지 판단해서 파스 트리를 생성

BNF를 쓰는 이유

• 명확하고 간결한 Syntax 묘사
• 파서가 직접적으로 BNF 이용 가능
• BNF 사용 파서는 유지 보수가 쉬움
• Lexical Analysis의 입력은 소스 코드, 출력은 Syntax Analysis의 입력, Syntax의 출력은 Syntax Tree

---

Lexical Analysis

Syntax Analysis와 Lexical Analysis를 분리한 이유

1. 간결함 : 어휘 분석에 덜 복잡한 접근이 가능, 파서가 단순화됨
2. 효율성 : 분리는 Lexical analyzer의 최적화를 가능하게 함
3. 이식성 : 파서는 항상 이식이 가능하다. 입력받는 부분은 기계에 따라 달라진다. 그래서 분리하여 이식성 높임

소스 코드를 받아서 파스 트리를 만드는데 파스 트리가 맞는지 틀린지 판단은 BNF를 기준으로 한다

 

Lexical 분석의 결과인 token의 그룹으로 Syntax Analysis를 하는 것이 일반적

• String 파일이 입력으로 들어옴
• 들어온 문자열로 패턴 매칭을 한다.
• 문법적으로 유효한 패턴인지를 분석한다.
• 문법적으로 유효하다고 판단한 것이 Lexeme이 된다.

Lexical analyzer를 만드는 3가지의 접근 방법

1. 패턴을 테이블로 두면 소프트웨어 tool을 통해 자동으로 Lexical 분석기 소스 코드가 생성. / 돈이 든다.
2. 패턴 매칭을 하기 위한 State diagram을 만든다. -> 있는 그대로 코드로 변환. state가 많으면 코드가 길다.
3. State diagram을 만든다. -> state를 압축할 수 있는 테이블을 생성. 그 테이블 기반으로 렉시컬 분석기 코딩을 한다. => 많은 경우, transition(전이)를 사용하여 state diagram을 단순하게 결합할 수 있다. (문자 클래스, 숫자 클래스 등) 예약어와 식별자(identifier)를 같이 인식 가능. 가능한 식별자가 실제로 예약어인지 확인하기 위해 테이블 조회

Lexical Analyzer가 파서에게 토큰을 줄 때 바로 바로 하나씩 주는 종류가 있고 분석을 다 완료하고 한 번에 주는 종류가 있는데 파일 입출력은 시간이 오래 걸리기 때문에 한 번에 주는 것은 비효율적

 

Lexical Analyzer(어휘 분석기)가 입력 스트링을 읽어서 토큰 형태로 분리해서 반환

파서는 어휘 분석기가 넘긴 토큰들을 파스 트리 형태로 만든다 (파싱한다) 파서의 출력은 AST.(추상 구문 트리)

 

AST(abstract syntax tree) : Terminal만 가지고 입력 스트링의 구문 구조를 추상적으로 보여주는 트리 (NonT 없음)
위 3단계를 거쳐서 출력된 AST로 실행이 되는 것이 컴파일러 혹은 인터프리터. 

---

The Parsing Problem

파싱의 목적

• 모든 구문 오류를 찾고 에러 메시지를 띄우고 빠르게 복구
• 파스 트리를 만들어 가는 것

파싱의 접근 방법 (둘 다 테이블 기반이다) (성능 순으로는 LR . LL . RD)

• Top down : 파스 트리를 루트에서부터 생성 / Leftmost derivation (Recursive Descent, LL parser) / 파스 트리를 생성
• Bottom Up : 파스 트리를 잎(노드)에서부터 생성 / Reverse of Rightmost derivation (LR parser)

유용한 파서는 입력에서 다음 토큰을 하나만 미리 본다.

---

Top-down Parsers
영문 소문자는 Terminal, 영문 대문자는 Nonterminal, α 등은 혼합

xAα라는 Sentential form에서 A앞은 다 Terminal이므로 Derivation이 끝남

파서는 A라는 Nonterminal에만 관심을 가짐. A를 바꿀 규칙을 찾아나감

 

Recursive Descent

• Non-Terminal 하나 하나를 Function으로 매핑해서 구현해 나가는 함수 (구현은 간단, 속도는 느림)
• BNF가 간단할수록 좋다. 즉 EBNF가 더 좋다. 
• BNF 룰에 LHS 대해 해당하는 RHS에 똑같은 터미널로 시작하는 것을 하나만 만들어야 한다.
• Left recursion이 발생할 수 있다.
• Match and Expend

LL parsers

• 정보를 미리 완성된 파싱 테이블에서 읽어와서 Left Most Derivation을 해 나간다.
• 미리 파싱 테이블을 만들어서 빠름

---

Bottom-up Parsers

previous sentential form in the right derivation을 찾는 것이 목표

 

LR parsers

소프트웨어 툴을 통해서 미리 만들어둔 파싱 테이블을 활용해서 input 버포와 스택을 활용해서 리프노드에서 루트노드까지 파싱을 한다. 

 

파싱의 복잡도 : 모호하지 않은 문법에 대해 동작하는 파서는 복잡, 비효율적O(n3), 요즘은 O(logn)
컴파일러의 복잡도 : 모든 모호하지 않은 문법에 대해 동작하는 파서가 아니라 일부 문법에 대해서만 동작, 선형 시간 O(n)

---

Top-down Parsers의 문제점

---

Bottom-up Parsing