3주차 - 3장 Describing Syntax and Semantics

• 퀴즈

  1. 렉서름(lexeme)과 토큰(token)을 정의하시오.
     • 렉서름(lexeme): 언어에서 의미 있는 최소 단위의 문자열입니다.
     • 토큰(token): 프로그래밍 언어에서 렉서름의 집합으로 이루어진 구조체입니다. 프로그램의 의미를 분석하고 처리하기 위해 사용됩니다.
  2. 프로그래밍 언어는 어떻게 형식적으로 정의되나요?
     • 프로그래밍 언어는 구문(syntax)과 의미(semantics)로 정의됩니다. 구문은 문법으로, 의미는 의미론으로 정의됩니다.
  3. 프로그래밍 언어 구문은 일반적으로 어떤 형식으로 기술되나요?
     • 프로그래밍 언어 구문은 BNF나 EBNF와 같은 형식 문법으로 기술됩니다.
  4. 메타언어(metalanguage)란 무엇인가요?
     • 메타언어는 다른 언어를 기술하기 위한 언어로, 언어를 정의하거나 기술하는 데 사용됩니다.
  5. 문법의 문맥에서 파생(derivation)이란 무엇인가요?
     • 문법에서 파생이란 문법 규칙에 따라 문장을 생성하는 과정을 말합니다.
  6. 모호한 문법이란 무엇인가요?
     • 모호한 문법이란 하나 이상의 문장을 두 가지 이상의 방법으로 파생할 수 있는 문법입니다.
  7. 왼쪽 재귀 문법이란 무엇인가요?
     • 왼쪽 재귀 문법이란 규칙의 왼쪽에 동일한 기호가 있는 문법입니다.
  8. EBNF에서 메타기호의 사용법을 설명하세요.
     • EBNF에서 메타기호는 문법 기호와 다른 메타기호를 설명하기 위해 사용됩니다.
  9. 예측 함수(predicate function)의 목적은 무엇인가요?
     • 예측 함수는 구문 분석 중 규칙이나 토큰이 일치하는지 확인하기 위해 사용됩니다.
  10. 파스 트리(parse tree)가 완전히 속성 부여되었다고 할 수 있는 경우는 언제인가요?
      • 파스 트리가 완전히 속성 부여되었다는 것은 모든 노드가 속성을 가지고 있으며, 이 속성이 상위 노드와 일치한다는 것입니다.

• 0309

• 0314 35분 경

Syntax (문법)

구성이 어떻게 되어야 하냐.

최소한의 렉시컬 하나하나가 렉심!

렉심 = 하나의 어휘 요소

id 라고 하는 토큰

토큰하나에 하나의 랙심이 대응

렉시컬 분석 =토큰 분석

렉심 Lexime

= 하나하나 코드를 구현하는 시텍스 유닛이다.

1. Recognizers 만들기 = 인터프리터 만들기
2. Generators = 생성기 만들기
   1. 생성 방법을 주고 센텐스를 만들게함
   2. CFG 혹은 BNF

CFG

→ 현재 문장 그대로. 앞뒤 문맥을 고려하지 않고 문장 그대로 해석

BNF

→ Formal Language을 Generators 방식으로 정의함

1. non terminal → rule을 적용하면 더 이상 바뀔 수 있음
2. terminal → 더 이상 바뀔 수 없음! 최종 결과는 다 터미널임
3. start symbol →논터미널
4. production rule 규칙은 n

4개가 있어야 BNF임

BNF는 제너레이터로, 문장을 생성할 수 있음

룰을 적용해서 베리데이션 할 수 있음

논터미널→ 논터미널 / 터미널로 유도할 수 있음

코드를 입력 → BNF로 표현. 내가 작성한 문장이 나온다 = 신텍스에 맞는 문장인것임

유도를 계속 했을때 주어진 문장이 안만들어지면 문법에 안 맞는 것임

CFG

대문자와 문자/ 소문자는x 숫자가 소문자임

• 대문자 : 넌터미널
• 숫자 : 터미널

터미널집합 소문자 / 논터미널 대문

BNF

• 소문자 : 터미널 =랙심 아니면 토큰
• 대문자 : 논터미널

터미널 : 꺽쇠없이. / 논터미널 : 꺽외있음

리커젼 Recursion

문법 : 문법의 집합

여러개의 논터미널 중에 특별한거 하나를 스타트 심볼이라고 함

데리베이션이 끝나면 센텐스가 나옴 → 센텐스는 터미널로만 구성되어 있음

재귀에서 가장 왼쪽게 바뀌면

leftmost derivation → right hand side의 가장 왼쪽의 논터미널을 계속해서 바꿔가는 것

다이렉트 데이베이션 (직접 유도) → 룰이 한 번만 적용

트리가 만들어지면 성공!

트리가 안만들어지면 실패

루트는 스타트심볼

인터널 노드는 넌터미널

리프노드는 터미널만 나와야함

→ 이게 만들어지면 신텍스 분석이 이루어진것임

BNF를 줬을때 나올 수 없는 스트링은?

좌측유도 / 우측유도 → 결과물 다름!

어떻게 트리를 만들었냐에 따라서 시맨틱스가 달라짐!

• 0316

bnf → 문법을 기술하는 포멀한 방법

• terminal
• non terminal
• start symbol
• rule

automation → 자동적으로 이루어지도록 하기 위한 모델을 만들기

정형화

derivation유도과정을 통해서 트리를 만들어ㅏㄴ감

파싱. 그 트리가 되는지를봄

트리 → 루트 제너레이션

파스트리=신텍스 트리 = derivation 트리

유도기법

• 좌측유도
• 우측유도
• 제일 좋은거는 둘 중에 어느것을 하든 항상 동일한 문장을 주면 제일 좋긴함 → 근데 이렇게 하면 개 복잡함

규칙을 정할 수도 있음. 좌측유도할건지, 우측유도를 할건지

모호한 문법

제거해야한다!

연산자의 우선순위가 결정되지 않아았음

우선순위를 만들려면?

우선순위가 높은 애가 밑으로 내려가게 해야함. 먼저 수행하고 싶으면 depth를 깊이

결합성

앞에부터 하는걸 left associativity → 보통 이렇게 함

BNF의 모호성을 갖게하는 요인

1. 연산자의 우선순위
2. 연산자의 associativity

EBNF

• 대괄호 → 없거나 한번 나오거나 0 or 1 Optional (선택)
• { } 중괄호 → 무한 반복일 수도 이씀 1 or N 반복
• () 소괄호 → 또는 택 1

non terminal → 사각형

terminal → 동그라미

실제 문법이 통과가 되었으면 명령어들이 수행됨

static symmetic→ 의미도 아니고 신텍스도 아닌 애매하고 부가적인 것들

언어 문장의 뜻하고는 상관이 없음

BNF로는 표현이 안되는 부가적인 속성 등을 나타내고자함

Attribute Grammars (AGs)

static semmentic(문법으로 표현하긴 어려운데 symentic도 아닌것) 할 수 있음

시멘틱 룰을 추가 → attribute (속성) + attribute computation function(속성이 어떻게 계산되는지에 대한 명확한 정의)

predicate (boolean 수식)가 F 면 static 시멘틱스에서 에러가 난다는 소리

조금더 명확하게 정형화된 방식으로 포머한 방식으로 표현할 수 있음

Attribute grammar = BNF(or CFG) + Symmetic

• synthesized attributes : 계산해서 올라감. 아래서 위로 올라감
• inherited attributes : 위에서 줌. 위에서나 옆에 있는 애한테 영향을 받으면

actual_type → 이나 의 속성 중에서 계산되서 얻어지는 속성. 트리의 밑에서 실제 수식이 계산된 결과에 의해 만들어진 타입

expected_type → 애초에 선언된 타입.

파스트리를 장식 한다 = 파스트리를 데코레이션 한다

→ 각각의 노드의 attrbute를 계산한다.

예제 3.6

1. 어휘분석.
   1. 랙심과 토큰 분석을 위한 lexical analsis
2. 신텍스 분석
   1. 파스트리 생성
   2. BNF→ 신텍스 분석의 기본 모델
      1. 터미널
      2. 논터미널
      3. 스타트심볼
      4. 룰

다이나믹 시멘틱스 → 이 문장이 의미하는 바를 분석

스테틱 시멘틱스 →

AGs = BNV+ 어트리부트 /

강한 타입 체킹 → int는 int끼리의 덧셈 등

• 0321

dynamic Semantics 가지

1. Operational Semantics 오퍼레이션 → 우리가 생각하는 시뮬레이션
2. Denotational Semantics디노테이션 → 수학적인 함수기반
   • 함수 기반
   • 프레이티브 명시
3. 엑시옴
   • 반드시 참이되는 명제.(공리)
4. (트렌스포메이션 )
   1. 작성한 언어 → 기계어(바이트코드) 변환

시멘틱스Semantics 완벽 → 테스트 비용 줄일 수 있음

Operation Semantics

비용 입장에서 말이 안됨

하드웨어 기반으로 내가 어떤 문장을 실행했을때 어떤 의미를 가지는지 보여줌

정확하긴하지만 비용도 많이 들고 효율성 낮음

그래서! HW 안쓰고 Virtual Mechine을 사용해서 가상으로 구현해놓기

natural operation → 시뮬레이터! SW (하드웨어 대로 동작하는 SW)

ex. 기상 예측을 하기 위한 기상 변화 시뮬레이션

결과 예측하기.

좋은 시뮬레이터라면 시뮬레이터에 나오는 결과는 하드웨어에 나오는 결과랑 유사할 것임

사유 : 하드웨어코딩은 비용이 많이 들어..

HW → VM → SW(시뮬레이터) cpu와 똑같이 동작하는 코드를 만들기

SW 비용은 적게 들겠지만 정확도는 떨어지겠지

Denotation 수학적

내 언어 문장이 어떤 의미를 보이는지를 각각 매핑하는 함수를 만드는 것

정의역 : 입력. 내가 만들 수 있는 모든 문장 , 치역 :함수의 결과. 컴퓨터

내가 변화하는것만 보면 됨. 필요한 것만 살피기

치역 → [ 데이터/힙/스택 ] : 변수

함수 : 문장 → 변수. 변수들이 어떻게 상태가 바뀌는지 함수의 매핑을 통해서 추적하기.

function

이터레이션 모델링

1. 반복적인 수행
2. 이터레이션→ 자기호출(재귀) 바꿀 수 있음

Axiomatic semantics 논리식기반

• login

• predicate (=assertion. 내가 조건으로 삼는 것들 )

• precondition (포함되는 것. 가능한 제약조)

• weakest precondition (제일 제약조건이 낮은 것)

• 0323 중간 까지