문법과 언어.

Slides:



Advertisements
Similar presentations
기본 자료형 순천향대학교 정보기술공학부 이 상 정. 자료형의 선언 컴퓨터프로그래밍 1 순천향대학교 정보기술공학부 이 상 정 3 자료형 선언 기본 자료형문자형 char 정수형 int 실수형 float double 형없음 void.
Advertisements

멘토링 2 주차 장 프로그래밍을 위한 자바의 자료형  값이 변하지 않는 상수  메모리 기억공간인 변수.
 수학 10- 나  1 학년 2 학기  Ⅰ. 도형의 방정식 1. 평면좌표 (1/24) 두 점 사이의 거리 수업 계획 수업 활동.
Copyright © 2006 The McGraw-Hill Companies, Inc. 프로그래밍 언어론 2nd edition Tucker and Noonan 5 장 타입 “ 타입은 컴퓨터 프로그래밍의 효소이다 ; 프로그래밍은 타입을 통해 소화할만한 것이 된다.” 로빈.
C-aC-bA-bB-aB-bB-cA-aA-c A. Head Section. A-b B-a B-b B-c C A-a A-c Top page.
지적기초측량 경일대학교/부동산지적학과.
고입특강 과학 중학교 1학년 단원 1. 지구의 구조 대기권 지구의 내부.
컴파일러 입문 제 5 장 Context-Free 문법.
제 4 장 변수, 영역, 수명 변수 바인딩 영역 기억장소 할당과 수명 변수와 그 환경 변수 초기화 상수와 변수.
Vision System Lab, Sang-Hun Han
Compiler Lecture Note, Inroduction to FL theory
YACC 응용 예 Desktop Calculator.
제 4 장 구문 분석.
해시 함수.
제 1장 C 언어의 소개.
C++ Espresso 제2장 제어문과 함수.
사회복지법인 실무자 교육.
2014 ITA 8월 강의 C Programming -1주차- C언어 기초 정대진 ( )
제 7 장 문장 구조화 제어문 지정문 조건문 반복문 GOTO 문 비결정적문.
데이터 구조 - 소개 순천향대학교 컴퓨터공학과 하 상 호.
2. 형식언어 (Formal Language)
프로그래밍언어론 2nd edition Tucker and Noonan
예수님 탄생 목자.박사들 경배 (마2:1-12, 눅 2:1-7).
3장 (2) 구문과 의미론 순천향대학교 컴퓨터공학과 하상호.
제 18 강 데이터 타입 타입, 변환, 캐스팅 shcho.pe.kr.
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 02. 프로그램의 기본구성.
재귀 혹은 귀납 Recursive or Inductive Definition 집합을 정의하는 방법
제 6 장 8086 어셈블러 설계.
주요 내용 형식 언어와 문법 정규식과 정규 집합 유한 상태 기계 정규 문법과 유한 상태 기계와 정규집합.
제 3 장 상수와 변수
이재상 기본 논리회로와 불의 대수 이재상
4장 제어문 선택문: if 문, if – else 문, switch 문
2. 형식언어 (Formal Language)
우리생활속의 확률 이용사례탐구 한림초등학교영재학급 6학년 김수민.
Chapter 10 함수 기본.
컴퓨터 개론 및 실습 Dept. Computer Eng. Hankuk University of Foreign Studies
프로그램 식 조합 방법 <expr> ::= <constant> | <name>
프로그래밍 보고서 작성법 순천향대학교 컴퓨터공학과 하 상 호.
김포 한강베네치아 상가분양 3층~5층 오피스텔 226세대 1층~2층 상가 분양문의 : 이효철( )
[INA240] Data Structures and Practice
Ⅶ. 원 의 성 질 1. 원 과 직 선 2. 원 주 각 3. 원 과 비 례.
우리는 부모를 닮지만, 왜 똑같지는 않을까? 유전적 다양성 독립 연관과 교차 무작위 수정.
프로그래밍언어론 2nd edition Tucker and Noonan
3. 정규 언어(Regular Language)
보라 처녀가 잉태하여 아들을 낳을 것이요 그 이름은 임마누엘이라 하리라 (이사야7:14)
4장 자료형.
Chapter 4 변수 및 바인딩.
C 프로그래밍 기초.
Java 3장. 자바의 기본 구조 I : 변수, 자료형, 연산자 public class SumTest {
4. 어휘 분석(Lexical analysis)
평 면 도 형 도형의 작도 삼각형의 작도와 결정조건 도형의 합동 작도와 삼각형의 합동 학습내용을 로 선택하세요
Signature, Strong Typing
Signature, Strong Typing
데이터 구조 - 소개 순천향대학교 컴퓨터공학과 하 상 호.
Chapter 5. Context-Free Language Exercises
요한 계시록 2:12~17 버가모 교회 : 예수님의 모습-좌우에 날썬 검을 가진자 13절-예수님께서 사는 곳을 아신다.
Signature, Strong Typing
동양의 색채 1.인 도 인더스 강 유역에서 고대(B.C 2000 ~ 3000)의 청동기시대에 문화가 이미 발달하였고, 메소포타미아와 유사하고 이는 신에 관한 것이 많고, 도시계획이 이루어져 있었으며, 이 시대부터 모자이크 타일이나 돌에 의한 다채로운 재료가 사용되었다.
진리 나무 Truth-tree  ∧ ∨ → ↔  =.
C언어 프로그래밍의 이해 Ch03. 기본 자료형, 변수와 상수.
제10장 비유동부채 제1절 화폐의 시간가치 제2절 비유동부채의 의의 및 구성 제3절 사채발행과 회계처리
엔화 대환/대출 자금용도 대상 이자 차액 효과 (A,B,C) 환율 리스크 헷징 (A,B) 엔화의 평균환율 (A,B,C)
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
Report #4 (1) (due 4/4) 문제 #1 3개의 막대 A, B, C와 원판 n개를 전달받아 Hanoi 탑 문제를 해결하는데 필요한 원판의 이동 회수를 구하여 반환하는 hanoi_tower(n, A, B, C)를 작성하라. 여기서 원판 n은 막대 A에 쌓여 있고.
printf("Global Korea\n");
제 1장 프로그래밍 언어 소개 1.1 프로그래밍 언어란 무엇인가 1.2 프로그래밍 언어를 배워야 하는 이유
Choi Younghwan CSE HUFS
배열, 포인터, 함수 Review & 과제 1, 2.
표준화 이론 표준형 구조나무 표준화 정리  ∧ ∨ → ↔  =.
Presentation transcript:

문법과 언어

형식 언어 형식 언어(formal language) 구성 요소 연산자 잘 정의된(well-defined) 수학적 언어 문장의 집합으로 정의 구성 요소 알파벳: 심볼들의 유한 집합 스트링: 심볼을 연결한 것 연산자 연결(concatenation) 합집합(union)

알파벳과 연산 알파벳 {a, b, c} 연산자 표기법 심볼: a, b, c 스트링: ab, abc, bc, aa, bb, cb, a 비교: ad, aa (X) 연산자 연결: ab.bc = abbc 합집합: {ab}  {ac} = {ab, ac} 표기법 a2 = aa, a3 = aaa a1 = a, a0 =  (또는 )

언어 = 문장의 집합 문장: 특정한 형태의 스트링 집합 어떤 형태가 특정한 형태인가? 집합의 표기 유한 집합, 무한 집합 원소 나열법 조건 제시법 유한 집합, 무한 집합 무한 집합의 유한 표현?

언어의 예 알파벳이 {a,b}일 때 알파벳이 {0,1}일 때 {a, aa, aaa} {an | n은 짝수} {anbn | n1} {axb | x{a,b}*} 알파벳이 {0,1}일 때 {x | x{0,1}*, x는 ASCII 코드} {x | x{0,1}*, #(x)=65} (aa)* a(a+b)*b #은 2진수를 10진수로 바꾸는 함수

* 심볼, 스트링 집합 0번 이상 반복 a*: a가 0번 이상 반복 집합의 원소로 만들 수 있는 모든 스트링 {a}* = a* = {an | n  0} = {, a, aa, aaa, …} 집합 집합의 원소로 만들 수 있는 모든 스트링 {a}* = a* {a, b}* = {, a, b, aa, ab, ba, bb, aaa, aab, …}

문법 무한 집합의 유한 표현 구성요소 문장 비단말 기호: N 단말 기호: T 생성 규칙:  시작 기호 는 로 대치할 수 있다. 시작 기호 문장 문법으로부터 생성되면 문장이라 한다. <와 >로 싸서 표기하기도 함 ‘와 ’로 싸서 표기하기도 함 대신에 ::=를 사용하기도 함

문맥 무관 문법 생성규칙의 제한 왜 문맥무관인가? 를 비단말 기호로 제한 는 단말기호와 비단말기호의 스트링 즉, A   의 모양 왜 문맥무관인가? A는 항상 로 바뀔 수 있다. 나 에 상관 없이  문맥무관

문법의 예 회문 언어 리스트 표기 S  a S a S  b S b S   L  a | ( K ) K  K , L | L S  a S a | b S b | 

문장 만들기 회문 언어 리스트 S   S  aSa  aa S  aSa  abSba  abba L  a L  (K)  (L)  (a) L  (K)  (K,L)  (K,L,L)  (L,L,L)    (a,a,a)

문장 생성 연습 괄호 수식 P  ( P ) P |  길이가 6인 스트링을 모두 구하시오. E  E + E | E * E | N N  1 | 2 | 3 | 4 | 5 길이가 5인 스트링을 모두 구하시오.

문법 만들기 연습 다음의 언어를 생성하는 문법은? a* {a, b}* {a, aa, aaa} {an | n은 짝수} {anbn | n1} {axb | x{a,b}*}

프로그래밍 언어

프로그래밍 언어 언어의 구성 요소 언어의 존재 구문(syntax): 요소들이 결합하는 방법 의미(semantics): 요소들의 뜻 실용(pragmatics): 언어의 부수적인 옵션 언어의 존재 구문 + 의미 컴파일러

실행문을 위한 문법 프로그래밍 언어에서의 실행문 <Stmt> ::= <AsgnStmt> | <IfStmt> | <WhileStmt> | <ForStmt> | <CallStmt> | <RtrnStmt> | <CompStmt> <AsgnStmt> ::= <Var> = <Expr> <IfStmt> ::= if ( <Cond> ) then <Stmt> | if ( <Cond> ) then <Stmt> else <Stmt> <WhileStmt> ::= while ( <Cond> ) <Stmt> <ForStmt> ::= for ( <Var> = <Expr> to <Expr> ) <Stmt> <CallStmt> ::= call <ProcName> ( <ParamList> ) <RtrnStmt> ::= return ( <Expr> ) <CompStmt> ::= begin <StmtList> end <StmtList> ::= <StmtList> ; <Stmt> | <Stmt>

식을 위한 문법 프로그래밍 언어에서의 조건식과 수식 <Cond> ::= <Cond> & <Rel> | <Cond> ‘|’ <Rel> | ! <Rel> | <Rel> <Rel> ::= <Expr> < <Expr> | <Expr> <= <Expr> | <Expr> > <Expr> | <Expr> >= <Expr> | <Expr> = <Expr> | <Expr> != <Expr> <Expr> ::= <Expr> + <Term> | <Expr> - <Term> | <Term> <Term> ::= <Term> * <Fact> | <Term> / <Fact> | <Fact> <Fact> ::= <Var> | <Number> | <FuncCall> | - <Fact> | ( <Expr> ) <FuncCall> ::= <FuncName> ( <ParamList> ) <ParamList> ::= <ExprList> | <ExprList> ::= <ExprList> , <Expr> | <Expr>

ToyPL 언어의 문법 <Program> ::= program <Name> ; <SubPgmList> main <VarDecl> <CompStmt> . <VarDecl> ::= var <DclList> ; | <DclList> ::= <DclList> ; <Decl> | <Decl> <Decl> ::= <VarList> : <Type> <VarList> ::= <VarList> , <Var> | <Var> <Type> ::= int | long <Var> ::= <Name> <SubPgmList> ::= <SubPgmList> <SubPgm> | <SubPgm> ::= <ProcDecl> | <FuncDecl> <ProcDecl> ::= proc <ProcName> ( <FormParam> ) <VarDecl> <CompStmt> <FuncDecl> ::= func <FuncName> ( <FormParam> ) returns ( <Type> ) <FormParam> ::= <DclList> |

구성요소의 의미 형식매개변수(<FormParam>)는 다시 선언될 필요 없음 함수선언에서 returns는 반환 값의 형임 return 문은 함수선언에서만 필요 프로그램의 실행은 main부터 시작 int는 4-byte, long는 8-byte의 정수 <IfStmt>는 모호

ToyPL 언어의 어휘 키워드 연산자 및 구분자 이름과 숫자 주석 program, main, proc, func, returns, var, int, long, if, then, else, while, for, to, call, return, begin, end 연산자 및 구분자 연산자: = & | ! < <= > >= != + - * / 구분자: ; : ( ) , . 이름과 숫자 이름: 영문자로 시작, 영문자와 숫자가 이어짐 숫자: 정수의 10진수 표기 주석 /*와 */ 사이의 모든 문자열

내장 함수 입출력은 ToyPL에서 정의되지 아니함 입출력은 내장함수에서 처리함 read(): 키보드로부터 숫자를 입력하여 반환 print(x): x를 화면에 출력, x는 변수 또는 상수

ToyPL 프로그래밍 가장 간단한 프로그램을 작성하시오. 필요없이 복잡한 프로그램 조각을 작성하시오. 문법에 맞게 작성 (의미는 고려 안함) 필요없이 복잡한 프로그램 조각을 작성하시오. 예: x+0+0+0+0+0+0+0+0+0+y 계승(factorial) 함수를 작성하시오 반복(iterative)을 이용하여 작성 순환(recursion)을 이용하여 작성

가장 간단한 프로그램 program p main begin a = 1 end .

불필요한 중복 begin begin begin a = 1 end end end (((((a+1))))) -------1

계승함수 - “반복” 버전

계승함수 - “순환” 버전

문법 오류 찾기 program Sample proc Fact (n : long) var m : integer; begin m = n - 1; call Fact(m); end; main var a, b : integer; a = 0; call Fact(a); end .

로봇 제어 언어 로봇 제어 프로그램 로봇의 동작 프로그램으로 로봇을 제어하고자 함 로봇 제어 언어로 작성된 프로그램 프로그램에 지시된 대로 움직임

로봇 제어 언어의 문법 RCP ::= robot at POS in the board { BRD } the control sequence is CTSQ . BRD ::= size = NUM x NUM ; blocks = BLK ; destination = POS BLK ::= POS , BLK | POS POS ::= ( NUM , NUM ) CTSQ ::= CNTL CTSQ | CNTL CNTL ::= go-ahead NUM | go-back NUM | turn-left | turn-right

언어의 의미 언어의 의미 size는 판의 크기로 (가로크기)x(세로크기)임 blocks는 장애물의 좌표임 판의 좌표는 왼쪽 아래가 (1,1) 임 NUM은 1보다 크거나 같은 정수 초기에 로봇은 위쪽(북쪽)을 바라보고 있음

로봇 제어 프로그래밍 로봇 제어 프로그래밍 다음 그림과 같은 배치에서 목적지까지 도달하기 위하여 로봇이 움직여야 하는 방법을 프로그래밍하시오.