컴파일러 CH3. Syntax Analysis

Alpha, Orderly·2023년 4월 3일

컴파일러

목록 보기

2/5

Context Free Grammar

예시 : 주어 동사 목적어로 이루어진 영어 문장

Sentence / Subject / Object
- 결과로 Non-Terminal Symbol또한 가진다.
Noun / Verb
- 결과로 Terminal Symbol만 위치한다.

생성 예시

Subject / Verb / Object / Noun 순서로 Terminal Symbol로 대체되어 진다.

형태

Left hand side = Non-terminal / Right hand side = Non-Terminal or Terminal

Grammar의 Terminal은 Token이다.
Token의 구조화를 Parser가 진행한다.

Derivation / 유도

문법으로부터 문자열을 유도(Derive) 한다.
각각의 유도 단계(Derivation Step) 에서 Nonterminal Symbol은 우측의 Terminal Symbol 혹은 Non-Terminal Symbol 로 교체된다.
마지막 문자열 형태는 Terminal Symbol / Token 만을 가진다.
- Non-terminal Symbol을 포함해선 안된다.
CFG는 Context-Free-Language의 생성기로, 문법으로 정의되는 모든 언어는 곧 유도될수 있는 모든 문자열과 같다.

CFG는 주어진 프로그래밍 언어의 가능한 문자열을 정의한다.

-> 프로그래밍 언어 문법의 Formal Description

CFG Element

Terminal Symbol
- Token
- <=, while, if, INTLITERAL
Nonterminal Symbol
- 언어의 특정 Class 문구
- Program, Command, Expression, ...
Start Symbol
- Nonterminal 중 하나면서 첫번째 유도 과정에 왼쪽으로 들어간다.
- EX/ Micro English에서 Sentence
- 컴파일러에서는 프로그램 그 자체를 의미.
Productions
- CFG의 Rule
- 예시 : sentence ::= noun verb
- sentence가 noun verb로 치환된다.

BNF

CFG를 표현하는 방법
; 의 의미 : Command와 single-Command가 이어짐.

Micro-English의 표현

EBNF

편의상 BNF와 Regex를 합친 EBNF를 사용한다.

Kleene star clouser를 사용한다

Leftmost Derivation

가장 왼쪽 끝에 있는 Nonterminal 먼저 치환한다.

Rightmost Derivation

가장 오른쪽 끝에 있는 Nonterminal 먼저 치환한다.

CFG 작성 Convention

Start Symbol

첫번째 Production의 왼쪽 방향 값.
어디서든 문자 S로 표기한다.

Nonterminal

"sentence"나 "expr"처럼 소문자로 이루어져있다.
A, B, C 처럼 대문자로도 이루어진다.

Terminal

ID와 INTLITERAL과 같이 볼드체로 작성한다.
숫자, 연산자, 괄호 등을 포함한다.

파스칼에서의 문법 예시

PROGRAM, integer, VAR 등은 Terminal으로 더이상 Derivation 되지 않는다.

Extended BNF

BNF에 Regex가 합쳐진 형태
LHS ::= RHS 와 같은 형태로 표현된다.
BNF에 아래와 같은 표현을 추가한다
- (...) - 그룹
- * - 0번 혹은 추가 반복
- + - 1번 혹은 추가 반복
- ? - 0 ~ 1 번 반복

예시

Kleene clouser ${}^*$ 사용법

Positive clouser ${}^+$ 사용법

Option ? 사용법

Grammar Transformation

Left Factorization

$N ::= XY | XZ$ == $N ::= X(Y|Z)$
왼쪽의 공통되는 부분을 묶어준다.

if Expression then single-Command 가 중복되어 묶어 주었다. 뒤에 나오는것은 ? 로 처리해도 될듯

Elimination of Left Recursion

왼쪽 재귀호출이 제거 된다.
X로 재귀가 종료된다.
$N ::= X | NY$ == $N ::= XY^*$

Substitutuin of non-terminal symbol

$N ::= X$ & $M ::= a N B$
$N ::= X$ & $M ::= a X b$
Terminal Symbol이 바로 될수 있는 N을 Terminal Symbol인 X로 치환한다.

to-or-dt를 terminal symbol인 (to|downto)로 치환한 모습이다

Parse Tree

Rightmost derivation

Derivation과 Parse Tree

Parse Tree의 내부 노드는 Nonterminal이다.
노드의 Child는 Production에서의 우측 Non-terminal 혹은 Terminal이다.
Parse tree의 Leaves는 전부 Terminal/Token 이다.
왼쪽에서 오른쪽으로 leaves들을 읽을시 Derivated Sentence가 만들어진다.

Ambiguous Grammar

두가지 이상의 방법으로 문자열이 Derive 될수 있으면, 문법이 모호(Ambiguous) 한 것이다.
위 경우는 연산자 우선순위로 인해 모호함이 생겨났다.

해결

우선순위가 다른 두 경우에 따라 경우를 나눈다.
우선순위가 낮은것이 파싱트리의 상단에 위치하도록 한다.

에 대해서

는 모호한 구문이다.

왜?

( IF a THEN ) ( IF b THEN x=false; ) ( ELSE x=true);
( IF a THEN ) ( IF b THEN x=false; ELSE x=true );
맨 끝부분의 ELSE가 IF a에 소속되는가, IF b에 소속되는가에 대한 모호함이 생긴다.

해결

중괄호와 같은 코드 블럭을 적용 혹은 indent를 통해 코드블럭을 적용한다.
명시적으로 END IF 라는 키워드를 도입한다.

Terminology

Recognition

입력이 언어의 문법에 맞아 떨어지는가?
Recognizer가 CFG를 이용해 프로그램의 문법을 확인한다.

Parsing

입력 프로그램 Recognize
입력 프로그램의 구문 구조를 확인한다.
- 파서는 CFG를 통해 프로그램의 문장을 파싱한다.
  - 프로그램이 문법에 대해 유효한가, 유효하지 않은가를 판단한다.
- AST를 만든다.
  - AST : 추상구문트리
  - 프로그래밍 언어로 작성된 소스 코드의 추상 구문 구조의 트리이다.

Context Free Grammar Classes

n : 프로그램의 사이즈

임의의 CFG에 대해 파싱은 $O(n^3)$ 의 시간이 소요될수 있다, 이는 너무 느리다.
몇몇 문법의 클래스에 따라 $O(n)$ 에 파싱할수 있다.
- Top Down - LL grammar - Leftmost derivation
- Bottom up - LR grammar - Rightmost derivation

Top - Down Approach

위에서부터 파싱 시작해 나감

Bottom - Up Approach

Terminal Token으로부터 파싱을 시작해 나감

Grammar Classes

LL 문법에 대해 LL 파싱 알고리즘을 통해 파싱
LR 문법에 대해 LR 파싱 알고리즘을 통해 파싱
LL 문법은 LR 문법의 부분집합이다.

LL 문법과 Top-Down parser

예측성 파서 / Predictive parser
왼쪽에 재귀하는 Production을 포함할수 없다, Left recursive production을 포함할수 없다.
두개 이상의 production이 동일한 prefix를 가져선 안된다 ( Common Prefix )
위 2개는 Grammar Transformation을 통해 제거 할수 있다.
Parse Tree가 Root로부터 만들어진다.
토큰을 하나씩 보기 때문에 LL(1) Parser이라고도 부른다.

Recursive Descent Parsing

직접 LL/Top-down을 파싱하는 방법

EBNF로 부터 Recursive Descent Parser를 만들어 내기

예시

EBNF 구조가 주어진다

1. 각각의 Left Hand Side의 Non-Terminal N에 대해 parseN 함수 만들기

parseSentence(); 를 먼저 실행해야 할 것이다.

클래스

Auxiliary method : 보조 메소드

Terminal / Token 을 받아들이는 함수.
현재 토큰과 받아온 기대 토큰을 비교한다.

Parsing method : 파싱 메소드

Sentence를 파싱할때 Subject > Verb > Object 순으로 파싱 하고 "." 을 받아들인다.

- 파싱 메소드 예시

각각의 예시에 따라 Terminal은 accpet로 받고, Non-Terminal의 경우 다시 parseXXX(); 재귀적으로 호출한다.
모든 경우에 해당하지 않을경우 문법 에러를 리턴한다.

- 명사/ Noun 파싱 예시

전체가 Terminal/Token 으로 끝나기에 parseXXX()는 호출되지 않고 전부 accept로 받아진다.

RD 파서의 체계적 개발(Systemetic Development)

EBNF로 문법을 표기하기
Left Factorization / Left Recursion Elimination 를 통해 정리하기 - Grammar transformation
파서 클래스 만들기
- private variable : currentToken
- 스캐너 호출 메소드 : accept and acceptIt
EBNF를 RD 파서로 변환하기
- Nonterminal N에 대해 parseN(); 함수 만들기
- parseS(); 실행하기 - Starting symbol의 Production function
- parseS(); 의 리턴 결과 확인하기.
- FIRST[x] : x Nonterminal이 RHS에서 처음으로 가질수 있는 Terminal들의 집합.
- 복합적 예시
- acceptIt() : 토큰 확인 하지 않고 받아오기
- accept(TokenType) : 토큰 타입을 확인하고 받아오기
FIRST 함수
- 주어진 Non-Terminal Symbol에 대해 처음으로 올수있는 Terminal Symbol 들의 집합
- 만약 문자열이 사라지면 { $\epsilon$ } 을 추가해준다.
- FIRST 집합이 겹친다 == 두 집합의 교집합이 공집합이 아니다. == Common prefix가 존재한다 == LL(1) 문법이 아니다.
FOLLOW 함수

FOLLOW(A)
- 주어진 Non-Terminal Symbol A에 대해 다음에 올 Terminay Symbol들의 집합.