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

문맥-자유 문법  CFG(context-free grammer)

 - 터미널 심볼의 집합  T

 - 넌터미널 심볼의 집합 N

 - 시작 심볼 S

 

어떤 스트링이 문법으로부터 유도 가능하면 문법에 맞는 스트링이고 그렇지 않으면 문법에 맞지 않는 스트링

 

어떤 넌터미널 심볼을 선택해서 문법의 생성 규칙을 한 번 적용하는 것을 직접 유도(direct derivation)이라 하고 => 기호로 표시

 

유도(derivation)는 여러 번의 직접 유도를 연속적으로 하는 것을 말하고 0번 혹은 그 이상의 번의 적접 유도가 가능하다면 =>* 기호로 표시

 

유도 트리(derivation tree)는 유도과정 혹은 구문구조를 보여주는 트리로 파스 트리(parse tree) 또는 구문 트리(syntax tree) 라고 함

 

어떤 스트링에 대해 두 개 이상의 파스 트리를 갖는 문법을 모호한 문법(ambiguous grammer)이라 함

 

프로그래밍을 기술하는 방식중 대표적인 방식은 BNF(Backus-Naur Form) 이며 이를 확장한 EBNF(Extended BNF)를 많이 사용함

구문 다이어 그램(syntax diagram)을 그리는 원리

 - 넌 터미널 심볼을 사각형으로 표시

 - 터미널 심볼은 원으로 표시

 - 생성 규칙 내의 심볼의 순서는 화살표로 표시

 

재귀 하강 파서(recursive descent parsing)를 만드는 기본 원리는 입력 스트링을 좌측 유도하도 다음 문법으로 작성

 - 각 넌 터미널을 위한 하나의 프로시저(함수, 메소드)를 구현

 - 프로시저 내에서 해당 생성 규칙의 우변을 수행하도록 작성

 - 터미널은 어휘 분석기가 읽은 입력 토큰과 일치(match)해야 하며 넌 머니털은 해당하는 프로시저에 대한 호출로 구현

 - 프로시저 내에서 다른 넌 터미널 프로시저를 호출하는 것은 해당 생성 규칙을 적용(expand) 하는 것

 

하향식 파싱(top-down parsing, predictive parsing)

 - 시작 심볼로 부터 시작해서 좌측 유도 방식으로 생성 규칙을 적용하면서 입력 스트링을 유도하는 방법

 - 입력 스트링을 한번에 한 토큰씩 좌에서 우(left to right) 로 읽어가면서 루트 노드에서 시작하여 터미널 노드로 파트 트리 작성

 

상향식 파싱(bottom-up parsing, shift-reduce parsing)

 - 입력 스트링을 한 번에 한 토큰씩 좌에서 우로 읽으면서 터미널 노드에서 시작하여 로트 노드로 파스 트리를 만들어 나가는 방법

 - 입력 스트링에서 리듀스에 의해 시작 심볼을 찾아가는 방법으로 우측 유도의 역순으로 진행하면서 동작