[양PL] 4장 Laxical and Syntax Analysis

(4.1)  서론

컴파일러 앞단 : Lexical analyzer

Syntzx analyzer의 앞단 : Parser

 

Lex에서 lexeme을 찾고, token을 Parser에서 문법에 맞나 검사한다.

 

컴파일레이션, 퓨어 인터프리테이션, 하이브리드 셋 다,

(Laxical and Syntax Analysis)이 필요하다.

ㅡ> 프로그램이 외부에서 입력을 받아와 실행될 때 항상 필요한 과정이다.

(4.2) 어휘 분석

(4.2) Lexical Analysis

ㅡ> lexeme + <token>을 찾는 과정

 

어휘를 찾는다는 것은, 패턴 매칭을 하는 것이다.

e.g.) 자연어 ㅡ> 사전을 보고 패턴매칭

 

Lexical Analyzer

ㅡ> Syntax Anlzer의 앞단 역할 (front-end)

ㅡ> 한 글자씩 input을 읽어가면서 lexeme을 찾고, 그것에 대한 token을 붙여서 Parser에 보내준다.

ㅡ> 스페이스, 코멘트 같은건 skip한다.

 

Identifier 일반적인 규칙 : 알파벳 시작, 숫자허용, 어떤건 언더바 허용

ㅡ> 다른 연산자가 나오면 컴파일러가 끊고, 거기까지를 하나의 단어로 판단

ㅡ> symbol table에 보낸다.

 

State (Transition) Diagram

ㅡ> Lexical analyzer가 작동하는 방식을 표현하는 방법

ㅡ> State를 동그라미로 표시

ㅡ> 다른 State로 넘어가는 것을 Transition이라 함

ㅡ> 일련의 state가 있고, input이 들어오면 action을 취해서 state가 바뀌던가 한다.

ㅡ> final state에 도달해서 끝나면, 다시 시작한다.

 

Lexical Analyzer에서는, input이 char이다.

char을 하나씩 받을 때마다, state가 바뀐다.

일련의 trasition이 끝낫다는 것은, lexeme하나 찾은 것이다.

끝나면 다시시작

 

Finite Automata

ㅡ> 수학에서 부르는 이름

ㅡ> Finite : 상태가 유한하다

 

Figure 4.1

ㅡ> Lexical Analyzer Program을 짜기 위한 보조수단

(교재 191pg 코드 참고)

ㅡ> 갈림길 : switch문 (선택이 여러개일 땐, if보단 switch)

ㅡ> 반복 : do while루프

ㅡ> 프로그램 짜는 것 자체보단, error 걸러내는게 어렵다.

(4.3) The Parsing Problem

Syntax analysis = Parsing = Interchangeably

 

Parsing 방법

1. Top-Down (LL Parsing)

ㅡ> root에서 leaf까지 rule 적용

ㅡ> Start symbol로부터, Rule을 적용하여, 모든 non-terminal이 없어질 때까지

 

2. Bottom-Up (LR Parsing)

ㅡ> leaf에서 root까지 rule 거꾸로 적용

ㅡ> Rule 오른쪽의 패턴(handle)을 왼쪽으로 변환

ㅡ> 마지막엔 root가 남는다.

ㅡ> 이 방법이 더 많이 쓰인다

(4.3.1) Introduction to Parsing 

parse라는 것은, 어떤 프로그램의 parse tree를 만드는 과정과 똑같다.

 

Syntax Analysis 목표

1. 문법검사

• 문법적 오류가 없으면 넘어감
• error 발견시
  • 1, diagonositc message(진단 메세지, 오류 짐작해서 알려줌)
    • 예시) x=y+z
    • 세미콜론(;) 빠짐
  • 2. recover(계속 컴파일한다. syntax error를 하나만 찾는게 아니라, 한번에 다 찾아주기 위함)

2. Parse Tree 생성

ㅡ> code generation할 때 쓰인다.

(4.3.2) Top-Down Parsers (LL)

ㅡ> LL Parsing : Left-to-right scan, Leftmost derivation

ㅡ> preoder를 따른다 : root left right

ㅡ> Rule이 둘 이상이면 상황에 따라 결정

 

※ Left-to-right scan : 입력을 왼쪽부터 오른쪽으로 스캔

(4.3.3) Bottom-Up Parsers (LR)

ㅡ> LL Parsing : Left-to-right scan, Rightmost derivation

ㅡ> preoder를 따른다 : root left right

ㅡ> Rule이 둘 이상이면 상황에 따라 결정

(4.4) Recursive-Descent Parsing

(4.4.1) The Recursive-Descent Parsing Process

Top-Down Parsing

= The Recursive-Descent Parsing

= 재귀하면서 내려오는 파싱

 

(expr 등 200pg 코드 그림)

모든 non-terminal을 함수로 구현

그 함수는, 입력이 rule에 맞게 들어왔느냐를 체크

처음엔 start symbol 함수를 호출

expr ㅡ> term ㅡ>factor ㅡ> expr 처럼 재귀할 수도 있음

(괄호 재귀 그림)

 

(F 4.2 그림)

바닥에 도달했다 = 문법에 맞게 쓰였다

(4.5) Bottom-Up Parsing

ㅡ> 이건 Top-down보다 이해가 어렵지만, 실제로는 이걸 더 많이 씀

ㅡ> 빠르기 때문이다

ㅡ> Top-down은 함수를 계속 호출하지만, Bottom-Up은 shift하고 reduce밖에 없기 때문이다

ㅡ> Parsing Table만드는 것만 빡셀 뿐이다.

ㅡ> 근데 Rule을 주면 Parsing Table을 자동생성 해주는 프로그램은 널렸다

ㅡ> Table의 빈공간이 error라 error도 바로 찾는다

 

Handle

ㅡ> rule의 오른편의 패턴

ㅡ> 이것을 rule의 왼편으로 바꾸는 것을 'reduce'라고 부름

 

(4.5.3) LR Parsers + 보충자료

여기서는 대문자가 non-terminal

 

(BNF Rules 그림)

E = <expression>

T = <term>

F = <factor>

 

Bottom-Up Parsing은, Parsing Table이라는 것을 먼저 만든다.

ㅡ> Action Table

ㅡ> Goto Table

 

(LR 파싱테이블 그림)

Action Table

ㅡ> 파서가 terminal을 하나 받아들였을 때, 어떤 action을 취할 것인가에 대한 정의가 되어있음

ㅡ> $ : 여기까지 오면 파싱이 끝난다.

ㅡ> 이것을 하기 위해서는 State-Transition Diagram을 그림

ㅡ> S5 : 입력을 스택에 push 후에, state를 5로 바꾼다

ㅡ> R5 : 5번째 Rule을 적용해서 reduce해라. 그 후에 Goto table을 보고 state를 바꾼다

ㅡ> 빈공간으로 가면 error

 

Goto Table

ㅡ> non-terminal

ㅡ> reduce후에 사용

ㅡ> $ : 여기까지 오면 파싱이 끝난다.

ㅡ> 이것을 하기 위해서는 State-Transition Diagram을 그림

 

(LR 파서 그림)

ㅡ> $가 나왔을 때, start symbol만 남아 있어야 함

 

Stack

ㅡ> state - term/non-t - state  - term/non-t - state  - term/non-t - state ...

ㅡ> 스택의 특징 : 입출구가 하나

ㅡ> (pre-fix, in-fix, post-fix) : 일상의 연산자는 in-fix를 씀, 컴파일러는 post-fix

ㅡ> (연산) : 연산자가 발견되면, 피연산자를 스택에서 꺼내서 계산하고 다시 넣는다 (reduce)

ㅡ> (파싱) : handle이 발견되면 스택에서 꺼내서 rule의 왼편으로 바꾸어 다시 넣는다 (reduce)

ㅡ> 마지막에 start symbol하나남고, $가 들어오면 끝

 

State 생성 방법

(그림)

ㅡ> I0가 initial state

ㅡ> start symbol의 프라임(')에서 시작 (E`)

ㅡ> 점이 뒤에 기다림~(?)

ㅡ> 점이 rule의 맨 오른쪽에 와있다~ handle 찾아졌다~ reduce해라~(?)

 

YACC

ㅡ> 컴파일러 컴파일러

ㅡ> Parsing Table을 만들어주는 Program

 

파싱과정

(그림)

ㅡ> 0에서 $ 들어오면 accept

 

컴파일러가 중요한 이유

ㅡ> 컴파일러의 원리의 확장이, AI 자연어 처리의 원리임