[프로그래밍 언어론] 문법 (4)

정규 문법과 CFG 문법에 대해서 알아보려고 한다.

<id> -> <letter> (<letter> | <digit>)*
<letter> -> a | b | c | ... | z
<digit> -> 0 | 1 | 2 | ... | 9

< > => non-terminal syntax
*는 0번 이상 여러번 반복을 의미하는 메타문자
문법에서 가장 먼저 나타나는 <id>를 시작기호라고 함

언어 인식기

문법 + 파생을 이용해서 언어 인식기를 만들 수 있음
ex) 언어(L) = 0(10)*
       입력 알파벳 = {0, 1}
       입력 문자열 = 01010

오토마타

 

input symbol에 대해 state를 천이하는 모델링 툴을 state trasition diagram이라고 함.
이것을 좀 더 formal하게 나타낸 것이 오토마타라고 한다.

언어 생성기

언어 생성기 역시 문법에 의해 표현된다.
ex) 0(10)*
->는 문법에서 사용되는 'is defined by'라는 의미
=> 는 좌측의 스트링이 우측으로 파생된다는 의미

ex) S-> S10 | 0

답 S => 0
또는 S => S10 = > 010
또는 S => S10 => S1010 => S1010 .... 10 => 01010 ... 10
       => 0(10)*

따라서 L = { 0, 010, 01010, ...., 01010 .... 10 }
            = 0(10)*

left-linear = 정규문법에서 nonterminal이 왼쪽에 있는 경우
right-linear = 정규문법에서 nonterminal이 오른쪽에 있는 경우

CFG

CFG는 BNF과 표기가 조금 다를 뿐 기능에 있어서는 거의 비슷하다.
G = (N, T, S, P)
   N : 논터미널들의 집합
   T : 터미널들의 집합
   S∈N : 시작 기호
   P : 생성규칙들의 집합

<program> -> begin <stmt_list> end                --- CFG 문법
<stmt_list> -> <stmt> | <stmt>; <stmt_list>       --- CFG 문법
<stmt> -> <var> = <expression>                    --- CFG 문법
<expression> -> <var> + <var>                      --- 정규 문법
                      | <var> - <var>
                      | <var>

최좌단 파생 : 유도 과정에서 좌측 방향의 N부터 푸는 방식
최우단 파생 : 유도 과정에서 우측 방향의 N부터 푸는 방식

파스 트리 (parse tree)

파생 과정을 그림으로 표현한 것
구문분석기는 파스트리를 만드는 것. 그래서 파서라고도 한다.
파서가 하는 일이 파싱.
파싱에는 Top-down parsing과 Bottom-up parsing이 있다.