PLT - Lecture 1 ( CFG & syntax )

Syntax

변환기는 '반드시' 코드를 이해하고 같은 지시의 순서를 제공해야한다.
Codes in high level language >> Translater(complier, interpreter) >> Machine codes(binary code)

어떻게 체계적으로 PL(Programming Language)을 정의할까?
1. 누구나 문법을 이해할 수 있어야한다. (=human-friendly)
2. 변환기 역시 이해하고 실행할 수 있어야한다. (=mathmetical)

PL은 두가지 방법으로 정의된다.
1. Syntax(문법론) : The structure/form
2. Semantics(의미론) : The meaning

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

CFG는 프로그래밍 언어의 해석 및 핵심 이론으로, 언어의 흐름을 정의하고, 문장의 구조를 분석하는 데 사용하는 도구이다.

구성요소 : terminal, non-terminal symbols, start symbol(the first non-terminal)

terminal symbol : 설명할 필요 X
non-terminal symbol : 설명할 필요 O

<assign> -> <id>=<int>
<id> -> a|b|c
<int> -> 1|2|3

위 규칙을 따라서 한 프로그램에는 하나의 코드만 존재할 수 있다.

terminal : =,a,b,c,1,2,3
non-terminal : ,,
start-symbol :

PL은 single CFG에 의해 정의될 수 있어야한다.

A formal definition of CFG :
G=( V ,Σ ,R, S)
V : non-terminal (Variable)
Σ : terminals
R : V x ( V and Σ)* : Rules
S : start symbols

간단한 정수 산술 표현식 :

100 + 32

<expr> -> <int> + <int>
<int> -> 100 | 32

HOW? - Recursive rule (재귀)

<expr> -> <expr> + <int>
       -> <expr> + <int> + <int>
       -> <int> + <int> + <int>

32
100+32
20+95+107
12+414+123+1132

<expr> -> <int>
  		| <expr> + <int>

CFG-EXAMPLE

32
100+a
count+95+107
count

<expr> -> <term>
  		| <expr> + <term>
<term> -> <int>
  		| <id>

begin
a = 2;
b = 10;
c = a + b;
d = 100 - c + a;
end

  <prog> -> begin <stmt> end
  <stmts> -> <stmt>
    		| <stmts> <stmt>
  <stmt> -> <id> = <expr>
  <expr> -> <term>
    		| <expr> + <term>
    		| <expr> - <term>
  <term> -> <int>
    		| <id>

a = 2;
b = 10;
if (a>=b) c = a - b;
if (a<b) c = b - a;

    <prog> -> <stmt>
    		| <prog> <stmt>
    <stmt> -> <assign>
      		| <if stmt>
    <assign> -> <expr> = <expr>
    <if stmt> -> if(<cond>) <assign>
    <expr> -> <int>
      		| <expr> + <int>
      		| <expr> - <int>
      		| <id>
    <cond> -> <expr> <op> <expr>
    <op> -> >|>=|<=|<|==|!=