복습

-포트란,코볼,Lisp

• algol:현대언어의 기반-> C,paskal
  -80년대 객체지향 시작,smalltalk80
  -c언어가 객체지향 영향받아 c++
  -90년대 인터넷 시대, 스크립트 언어 출현, html,js...
  -ada 국방목적,임베디드 시스템 호환

-함수언어,논리언어

3. 문법과 semantics(의미)

bnf: 노테이션을 만든 사람이 만든, 문법을 표기하는 표기법
bnf처음소개-> algol60

3.2문법 묘사의 일반적 문제

sentence는 단어의 집합.->lexemes.(어휘), 품사(tokens)
while,if등의 제어문->keyword :identifier의 이름으로 쓰지말아라

language recognizers

language generators

3.3 문법묘사의 formal한 방법들

문장을 어떻게 써야하나.
여러 rule들이 있다. 이 룰의 집합->문법(grammer)
문법의 표현을 어케하나

3.3.1 bnf와 context-free 문법

noam 촘스키가 자연어를 연구함. 4개의 난이도에 따라 등급으로 나눔.
시제가 없는 언어,단어가 여러 의미가 있는 언어 등은 문맥으로 유추한다(context-sensitive). 이런 context로부터 독립적으로 정확히 문장이 해석될 수 있으려면 단어는 한가지의 의미만 가져야한다.이것이 context-free문법이고 프로그래밍언어 문법은 context-free해야한다.

bnf는 일종의 메타언어이다. 다른언어에 대한 정보를 표현하는 언어이다.
bnf는 3가지의 기호가 있다.
-> /<>(pointed blocket)/ l (bar)
rule/non-terminal / or

non-terminal도 정의가 되어야 한다.

- <assign>-><var>=<expression>
여기서 terminal은 =만 이 존재한다.
terminal?-> 어휘들을 말한다.
  
- <if_stmt>->if(<logic_expr>)<stmt>
if,(,)가 terminal이다.

-3.3.1.4
list를 표현.
recursive로 eclipsis를 대신한다.

• derivations(유도)
  -> 왼쪽의 non-termininal을 우측으로 바꾸기(정의하기)

-non-terminal의 개수는 문법에서 왼편의 것 개수를 세면된다.

컴파일러의 전단계: 어휘분석,문법 분석
2단계: 기계어로 바꾸기

문법의 제일 위에 있는 non-terminal:start symbol
오른쪽의 non-terminal들이 모두 유도되도록 이어지며 rule이 작성된다.
프로그래밍은 terminal로 작성된다.

figure3.1 parse-tree
처음에 start symbol 마지막에는 terminal
derivation 하는 과정이 parse-tree이다.
non-terminal이 없어질 떄까지 terminal의 조합으로 derivation한다.

3.3.1.7 모호성

무섭게 생긴 그 사람의 강아지를 보았다.
-> 사람이 무서운지 강아지가 무서운지 모호함.

마찬가지로 2가지의 parse-tree가 나올 수 있음.
example 3.3을 보자.
figure 3.2를 보자.
두 가지가 가능하다. 결과도 다르게 나온다.
-> 모호하다.
이 때문에 우선순위,결합법칙이 있어야 한다.
example 3.4

• procedence
  우선순위가 높은 연산자 일수록 아래에서 정의됨
• associativity
  결합법칙 ()괄호는 일반적으로 최우선이므로 맨 아래에서 정의됨

LHS가 또 그것의 RHS의 시작에 나타나면 left-recursive한다.
LHS가 RHS의 끝에 나타나면 right-recursive한다.
ex) 234 ->우결합법칙 적용

이로써 parse-tree가 하나만 도출될 수 있어야 한다.

if-else의 모호성 제거

if에 then이 2개이고 else가 하나이면 else는 어느 then에 매치되나
-> else는 가장 가까운 then에 매치된다.

앞에꺼에 else를 붙이고 싶으면 중간 꺼를 블락으로 하나로 처리되게한다.

BNF확장(EBNF)

BNF를 좀 더 써서 더 간편히 나타내보자는 시도.
ex)
[] 나와도 되고 안나와도 됨.option
{} zero or more 재귀를 표현
(A|B) A가 나올 수도 B가 나올수도 있다.

grammars and recognizer

컴파일러 컴파일러라고도 하는 문법은 해석하는 recognizer가 있다.
대표적으로 yacc이 있다.