[프로그래밍언어론] 4주차 수업정리: lexical and syntax analysis

1.

소개글

 

모든 언어시스템은 소스코드를 분석해야한다.

 

분석하는 데 두 가지 방식으로 나뉜다.

 

lexical analysis와 syntax analysis(bnf, context free grammar을 따른다.)다.

 

lexical analyzer은 low level part로 변수명, 숫자 등 작은 단위 구조에 따라 처리한다.

 

syntax analyzer은 high level part로 expressions, statements, program units 와 같은 큰 단위 구조를 처리한다.

 

2.

syntax를 bnf를 통해 기술하면 3가지의 장점이 있다.

 

1) 간단 명료하다.

2) parser가 bnf를 통해서 바로 실행될 수 있다.

3) parser가 modularity덕분에 유지보수성이 좋아진다.

 

3.

그렇다면 lexical, syntax analysis를 구분하는 이유는 무엇일까

이것도 3가지가 있다.

 

1)간단성: 둘이 분리하면서 lexical에 간단한 접근법을 사용할 수 있다, parser를 간단하게 만든다.

2)효율성: lexical이 컴파일시간을 많이 차지하기때문에, 분리는 lexical analyzer의 최적화를 용이하게 만든다.

3)휴대성: lexical은 읽어들이기때문에 I/O 등 하드웨어에 의존적이다.(platform dependent)

따라서, 분리하면 parser은 휴대성이 좋아진다.

 

4.

lexical analysis

 

주어진 스트링의 각 문자들을 하나하나 읽어들이면서  logical grouping을 통해 lexeme과 token을 만든다.

ex. sum은 lexeme이고, 그 토큰은 ident이다.

(식별자는 코드에 존재하는 변수, 자료형, 서브루틴 등을 가리키는 토큰이다.)

 

동작과정을 살펴보자면...

parser가 다음 토큰이 필요하면 lexical analyzer을 호출한다. 그러면 input string으로 부터 lexeme을 extract하여 일치하는 token을 생산한다. 그리고 두 개를 모두 출력한다. (return)

 

이 과정에는 3가지 사항을 포함하고 있다.

1) 주석과 white space는 스킵한다.

2) symbol table에 lexeme을 저장한다.

3) 에러를 발견하고 리포트한다.

 

5.

lexical analysis에서 자주 사용하는 메소드는 4가지가 있다.

(utility subprograms for common tasks)

 

getchar

 

addchar

 

getnonblank

 

lookup

 

6.

reserved words, identifiers가 함께 인식된다.

-> 변수명, 예약어가 비슷해서 그것을 구분해야하는데...

 

우선, 같이 인식을 하고 나중에 look up을 사용한다 그러면 symbol table을 사용하여 identifier가 reserved word인지 구분한다.

(symbol table은 사용자가 정의한 변수타입, 값, 범위 등을 저장한다.)

 

7.

keywords vs reserved words

전자는 begin처럼 변수명으로 쓸 수도 있다. 후자는 그렇지 않다.

 

8.

state transition diagram(상태 전이도 다이아그램)

 

우리 토큰의 패턴을 설명하는 다이어그램이다.

(identifier, 숫자 등을 인식하는 과정이다)

 

특징1. 전이에 필요한 action도 포함한다.

 

9.

syntax analysis (parsing)

 

구문적으로 오류가 있는지 확인하고 파스트리를 만들기 위한 목적으로 쓰인다.

 

루트에서 잎으로 가는 탑-다운 방식과 잎에서 루트로 가는 바텀업 방식이 있다.

 

10.

top down방식

- 주어진 문장형태에서 leftmost방식으로 rule을 적용하며 문장형태(sentential form)를 확장한다.

- 그러면 주어진 룰 중에서 한 가지를 꼭 정해야한다. 이때를 parsing decision problem이라고 한다.

- 선택할때, 이제 들어올 토큰과 룰에 있는 RHS의 첫 symbol을 비교하여 무엇을 선택할지 결정한다.

 

bottom up 방식

-처음 주어진 문장의 substring 중 RHS인 것을 찾는다. 이때, RHS 중에서도 옳은 것을 handle이라고 한다.

-옳은 것은 무엇일까? 이전의 sentential form을 얻을 수 있는 LHS를 얻을 수 있는 RHS를 말한다.

 

그니깐 RHS를 잘 결정하면 이전의 sentetial form을 얻을 수 있는 LHS로 reduce할 수 있다.

 

11.

코드의 관점으로 살펴보자

syntax analyzer의 코드버전은 recursive descent parser이다.

 

-recursive한 subprograms로 구성되어있다.

-각 nonterminal을 위한 subprograms..

-LL