[컴파일러 개론] 구문 분석기

유의점: terminal : token, derivation : parsing

전 시간까지 어휘분석기와 token에 대해서 배웠다. 

먼저 if(b==0) a=b; 라는 식이 있으면 어휘분석기(스캐너)를 통해 token으로 나눠지고 

 

if

(

b

==

0

)

a

=

b

;

여기서 이제 구문분석기(parser)를 통해 파스트리가 완성된다.

어휘 분석때는 정규표현식으로 기술하고 상태전이도로 따라가며 판별했다.

 

구문분석의 핵심 질문들 

1) 프로그래밍 언어 제작자가 문법을 기술(설명) 하는 방법

-CFG(Context Free Grammer): 언어의 문법을 정의하는 일반적인 방법, 간단하고 이해하기 쉽다. 표현된 문법으로부터 자동적으로 인식기를 구현 가능 

 

-etc

 terminal 심벌: token이라고 불림 a,b,c와 같은 알파벳 시작 부분의 소문자와 숫자 0~9; +, - 와 같은 연산자 기호와 세미콜론, 콤마, 괄호와 같은 구분자, "if" , "then" 과 같이 따옴표 사이에 표기된 문법 심벌 

 

nonterminal 심벌: 주어구, 관형어와 같은 역할이며 A,B,C와 같은 알파벳 시작 부분의 대문자로 나타내게 됨 S는 보통 시작 심벌을 나타낸다 <stmt>나  <expr>과 같이 <>로 묶어서 나타내기도 함 .

 

생성규칙 S->T+T로 이루어짐 A-> a1,  A->a2, A->a3 인 경우 A->a1 | a2 | a3 로 표기 

 

시작 심벌(S) 만약 아무런 언급이 없으면 첫번째 생성 규칙의 왼쪽에 있는 것이 시작 심벌 

 

정규표현식은 토큰을 기술하기 좋고 DFA로 변환하여 구현하기도 좋다 하지만 문법 기술에 사용하기에는  Block, expresions, statements.. 등의 Nester구조의 구문을 표현하기에 힘들다. {{{}}} 이런 느낌의 구조..  DFA말이 유한상태 오토마타인데 노드가 유한개가아니라 무한개 필요하게 된다.

 

CFG의 여러가지 표기법

1.BNF(Backus-Naur Form) 

정규표현식 a(a|d)*가 있다고 보자 

이것을 <id>::=<letter> | <id><letter> | <id><digit>

<letter>::= a|b|c|~|z <digit>::=0 | 1 |~ 9 이런식으로 표현할 수 있다.   

생성규칙으로는 S->a|Sa 를 정규표현식으로 보면 aa*이므로 a+로 표현할 수 있다.  

 

2.EBNF(Extended BNF)

메타 심벌 도입: 반복되는 부분이나 선택적인 부분을 간결하게 표현하기 위한 특수 심벌 

<id>::=<letter>{<letter>|<digit>}07 ->  {}안을 7번 반복함 

<letter>::= a|b|c|~|z <digit>::=0 | 1 |~ 9 

 

Class Problem 정규표현식을 CFG로 바꾸기 

1. (a|b)c -> (S-> ac|bc)

2. a+ -> (S -> a|Sa)

3. (1(0|1)*)|0 -> (T-> 1B | 0 , B-> 시그마 | BA , A-> 0|1) ?

4/{{{{}}}} 등 정상적인 괄호 매치에 대한 CFG를 작성하시오 

example-> S-> ab | aSb ->--- aaaabbbb--

 

정답: S->{S}|시그마

 

내 생각:S->{A}  A->{B} B->{C} C->{D}  D-> 시그마 

https://talkingaboutme.tistory.com/entry/Study-Context-Free-Grammar-CFG

[Compiler] Context Free Grammar (CFG)

 

 

 

2) 주어진 input token stream이 기술된 문법에 맞는지 판별하는 방법 

 

정규식(->FSA) - > CFG(->?) - > CSG - >Turing(앨런튜링 이미테이션게임)

 

CFG-> ? 

문법: S-> <주어구><동사구> , <주어구>-><관형구><진 주어> 언어:"똑똑한 3학년이 모였습니다."

유도-문법에서 언어를 생성해내는 것 

구문분석-언어에서 문법을 확인해 가는 것 방법은 유도 되는지 보면 됨.....

 

유도 과정

좌측 유도트리와 우측 유도트리는 같음

class problem 좌측유도, 우측 유도(좌parse, 우parse)

동치임을 증명

#모호성

 

과연 좌측 유도트리, 우측 유도트리는 항상 같을까?  다르면 모호성이 있다.  

모호성 해결 방안 

- 같은 뜻을 가지는 동일한 문법을 만들자!

+와 * 있을시 모호성 생김 -> 우선순위 만들기 

-연산자마다 새로운 Non-retminal을 도입하되 

-회귀를 left나 right 둘 중 하나만 두고, 시작심벌과 가장 가까운 쪽에 연산자 우선순위가 낮은 것을 둠 

 

E-> E+T  E-> T 이건 결국 S->Sa 처럼 T가 계속 반복되는 구조임 T+T+T+T+T+T+T

밑줄은 F*F*F*F ~~ 

이제 예제 적용하기 

트리가 같음 ! 모호한 부분 해결!

두번쨰 방법 결합 법칙 도입 

class problem 우선순위가 주어지고 그것에 맞게  생성규칙 만들기 

`

구문분석(=parse) 

-주어진 스트링이 정의된 문법에 의해 생성될 수 있는지의 여부(적합성)를 결정하는 과정

-유도가 되는지 보면됨 

-올바른 문장에 대해서는 '문장 구조'를,

-틀린 문장에 대해서는 오류 메시지를 나타냄 

 

파스 트리(parse tree) 

-문장 구조를 나타내는 트리

-문법을 나타내는 생성 규칙을 적용한 유도트리와 같은 모양의 트리 

투르노드: 정의된 문법의 시작 심벌(S)

중간노드: 각 생성 규칙의 좌측 nonterminal 심벌 

단말노드(ended): 주어진 스트링을 생성하는 terminal 심벌(token)

 

생성규칙 번호리스트 

- 문법의 생성 규칙을 통해 유도하는 과정에서 적용되어온 일련의 생성 규칙 번호

 

구문 분석의 두 가지 방법 !!!!!!!!!매우 중요

-Top down 방식 : 루트 노드로부터 시작하여 단말노드를 생성하며 확인 

-Bottom-up 방식 : 단말 노드로부터 루트 노드를 향하여 위로 생성하며 확인 

매우중요!

Top down 방식의 문제점: 모든 경우의 수를 다 컴퓨터에게 시킴, 단점이 많음. 

해결방법 

bottom up 건물을 짓듯이 밑에서 위로

java antler 어휘분석도구는 사실 top down 방식을 자주 씀

 

Top down : 좌측 유도와 같은 순서의 생성규칙 적용 

(좌파스란 좌측유도 중 적용된 생성규칙들의 리스트)

Botton up : 우측유도의 역순의 생성규칙 적용과 같음 -입력 스트링의 왼쪽에서 부터 매치하므로 

(우파스란 우측유도 중 적용된 생성규칙들의 리스트의 역순)

예제

우파스 어떻게 나온거임? -> 우측유도 순서 14523 우파스는 우측유도의 역순의 생성규칙 적용 

 

class problem

내가 생각한 답