Compiler Design - Syntax Analysis

Syntax and Semantic

In English Language

Syntax : The form or structure of English sentences
No concern about meaning, specified by only grammar

Semantic : The meaning of English sentences

In Programming Language

Syntax : The form or structure of programs
No concern about meaning, specified by context-free grammar <- Now... we need to know this...

Semantic : The meaning of programs

Context-Free Grammar

Grammar를 정의하는 방법중 하나로, Recursion을 이용한 정의라고 생각하자. 어떤 format을 사용하는지 간단한 예시로 함께 보자. 편의상 간단한 English를 context-free grammar로 표현해본다.

Sentence ::= Subject Verb Object .
Subject ::= I | A Noun | The Noun
Object ::= me | a Noun | the Noun
Noun ::= cat | mat | rat | $\epsilon$
Verb ::= like | is | see | sees
여기서 Red text가 아닌 것들은 non-terminal ($\epsilon$ 제외), red text로 표시한 것들은 Terminal이라고 부른다. Terminal은 더이상 grammar를 참고하지 않는 마지막 단계라고 생각할 수 있다. (Recursion을 이용한 정의라고 생각했을 때 return이 시작되는 단계라고 생각할 수 있다.)

Derivation

Derivation step마다 nonterminal을 그러한 nonterminal을 설명(정의)하고 있는 right-hand side로 대체한다. 이때 나타나는 string들을 sentential forms라고 한다. sentence는 sentential forms가 모두 terminal인 string이라고 볼 수 있다.

derivation이 불가능한 sentence는 illegal하다고 볼 수 있다. -> CFG specified all valid strings(Programs) of a given programming language!

Elements of CFG

• Terminal Symbols : terminal string들이다. "while", "if", "<=", ID, INTLITERAL과 같은 것들이 있다.
• Nonterminal Symbols : nonterminal string들이다. Program, Command, Expression, Declaration등이 있다.
• Start Symbol : 보통 첫 production의 left-hand side이다.
• Productions : nonterminal ::= (non)terminals 꼴의 모든 것들

Leftmost & Rightmost Derivation

Derivation step마다 두가지의 'choice'가 생긴다.

• 어떤 nonterminal을 derivation할 것인지
• 그 nonterminal을 어떤 (non)terminal로 derivation할 것인지

유용한(하다고 알려진) 두가지 derivation을 소개하고 있다.
1. Leftmost derivation : always replace leftmost nonterminal
2. Rightmost derivatoin : always replace rightmost nonterminal

BNF, EBNF and more CFG

특별할 것 없다. 그냥 CFG를 표현하는 방법일 뿐이다. Full name은 Backus-Naur Form. 위에서 들었던 예시도 BNF에 포함되는 듯 하다.

Program ::= Command
Command ::= ~~
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$| ~~ ; ~~

EBNF는 Extended BNF의 약자이다. BNF에 REs를 합친것. $X^*$같은 표현들을 차용한 것이다.

CFG의 관용적인 부분들 - 위의 Elements of CFG와 큰 차이는 없다.

• Start Symbol : The letter S, whenever it appears (예시를 봐야 납득할듯)
• Non-terminals : lower case names, capital letters(A, B, ...)
• Terminals : boldface names such as digits, operators, ...

A little bit usefull theory

Parser를 구현할 때 필요하다고 한다. 기본적인 집합 규칙과 비슷하다.
Grammar Transformations

• N ::= XY | XZ -> N ::= X(Y|Z) 결합법칙 성립함.
• N ::= X | NY -> N ::= XY$^*$
• N ::= X, M ::= $\alpha$N$\beta$ -> N ::= X, M ::= $\alpha$X$\beta$ 치환도 됨

Parsing

Derivation and parse tree

예시 한 번 보면 이해 가능할 듯 하다. 결국 terminal만 남아야 한다.

Ambiguous Grammars

이것도 예시로 보는게 편할듯! 어떤 nonterminal을 어떤 (non)terminal로 replace하냐에 따라 결과가 달라질 수 있다는 얘기다.

이렇게 several distinct parse tree가 존재한다면 ambiguous 하다고 얘기한다. 이러한 경우를 대비하기위해 CFG 단계에서 연산들에 우선순위를 고려한다.

IF ELSE문 또한 ambiguous grammar가 될 수 있는데 아래와 같은 예시가 있다.
IF $\underline{a}$ THEN IF $\underline{b}$ THEN x = false; ELSE x = true;
위에서 ELSE가 첫 번째 IF에 속하는지 두 번째 IF에 속하는지 모호하기 때문이다. 이를 방지하기 위해 아래와 같은 CFG를 사용한다.
stmt ::= IF expr THEN expr stmt END IF
$\;$$\;$$\;$$\;$$\;$$\;$$\;$$\;$$\;$| IF expr THEN stmt ELSE stmt END IF

cf. 여기까지가 2022-2 CSI4104 Midterm 범위였다.

Recursive Descent Parsing