Chapter 4 : 구문(Syntax) Lexical Structure Syntactic Structure: BNF, EBNF, Syntax Diagrams Parse Tree, Syntax Tree, and Ambiguity Parsing Techniques and Tools Lexics vs. Syntax vs. Semantics
Introduction 언어의 계층 구조, due to Chomsky ~ Regular Grammar : Type-3 ~ Context-Free Grammar(CFG) : Type-2 ~ Context-Sensitive Grammar : Type-1 ~ Unrestricted Grammar : Type-0 프로그래밍 언어의 구문적 구조 ~ 어휘 구조(structures of words) 정규 표현(regular expressions) ~ 문법 구조(structures of sentences) Context-Free Grammar BNF(Backus-Naur Form) kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 2
어휘 구조(Lexical Structure) Lexical Structure ~ 어휘(lexicon) = 토큰(token) ~ 토큰 : 문법적으로 의미를 가진 최소 단위 technically, a token is a set of words 정규 표현(Regular Expression) ~ 토큰의 패턴(pattern)을 기술하기 위해 사용 ~ frequently used for text searching kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 3
Token의 종류(categories) 일반 형태 ~ 프로그래머에 의해 결정 ~ 명칭(identifier) - stk, ptr, sum1, sum2 등 ~ 상수(constant) - 526, 2.3, 0.1234e-10, 'string' 등 특수 형태 ~ 언어를 정의할 때 언어 설계자가 정의 ~ 지정어(keyword) : begin, end, for, goto, if 등 ~ 연산자 기호(operator symbol) : +, -, *, /, <, := 등 ~ 구분자(delimiter) - ;,,, (, [, : 등 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 4
토큰의 개수? if X < Y then X := 10 ; 토큰 분류 ~ 일반 형태 : ~ 특수 형태 : 토큰 저장 형태 ~ (토큰 번호, 토큰값)의 순서쌍 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 5
The number of significant characters of identifiers mostly imposed ~ not by the language ~ but by the implementation 사전-정의 식별자(predefined identifier) ~ 처음 부여된 의미를 재정의 식별자의 길이 ~ 제한(=고정된 최대 크기) ~ 무제한 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 6
정규 표현(regular expression) 패턴 기술 언어(Pattern Description Language) ~ 토큰의 패턴을 기술하기 위한 표현 방법 Examples of Regular Expressions ~ sequence of digits [0-9]+ ~ unsigned floating-point literals [0-9]+(\.[0-9]+)? kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 7
정규 표현의 예 ~ 정규 표현 : ab * a가 나오고 b가 0번 이상 나오는 스트링 {ab n n 0} ~ 정규 표현 : (0+1) * {0,1} * ~ 정규 표현 : (a+b) * abb a와 b로 이루어지는 모든 스트링 뒤에 abb가 나오는 언 어 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 8
명칭(identifier)의 정규 표현 ~ 특정한 형태의 스트링을 표현하는데 유용 ~ letter={a,b,..., Z,a,b,...,z}, digit={0,1,2,..., 9} ~ letter(letter+digit) * kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 9
어휘 분석기(scanner) 토큰 인식(Token-Recognizing) 프로그램 ~ 스케너(scanner) 원시 프로그램을 읽어들여 토큰을 인식하고 (토큰번호, 토큰값)을 다음 단계인 구문 분석 단계에 전달 ~ 어휘 분석기 생성기 = 스케너 생성기 = LEX, flex 정규 표현의 기술된 스케너의 명세(specification)를 입력으로 받아 특정 언어에 대한 스케너 생성 Scanner Example (Figure 4.1) ~ token categories: TokenType ~ the scanner: TokenType gettoken(void) ~ the scanner driver: main() kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 10
렉스(LEX) 렉스 ~ 레스크(Lesk, M.E.), 1975 ~ 어휘 분석기 생성기, 컴파일러 자동화 도구 ~ 소스 프로그램에 대해 정규 표현으로 기술된 토큰을 찾아내 는 프로그램을 작성하는데 유용한 도구 렉스의 기능 ~ 입력 : 사용자가 정의한 정규 표현과 실행 코드 ~ 출력 : C 언어로 쓰여진 프로그램 => lex.yy.c 입력 스트림에서 정규 표현에 해당하는 토큰을 찾았을 때 실행 코드를 수행 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 11
렉스의 역할 Lex source (*.ᅵ) LEX input text lex.yy.c (scanner) tokens kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 12
렉스의 입력 렉스의 입력(lex source)의 구성 { 정의 부분 } %% { 규칙 부분 } %% { 사용자 부프로그램 부분 } %% 각 부분의 구분자 각 부분은 반드시 순서적으로 기술 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 13
<정의 부분> %{ %} /* This part is merely copied onto the generated program */ 이름1 치환식1 이름2 치환식2... 이름n 치환식n kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 14
%{ 와 %} 사이 ~ 실행 코드를 C 언어로 기술할 때 필요한 자료 구조, 변수, 상 수정의 ~ 렉스의 출력인 lex.yy.c의 앞 부분에 복사 이름 정의 부분 ~ 특정한 정규 표현을 하나의 이름으로 정의 ~ 정규 표현에 대한 마크로 이름 치환식 ~ 이름에 해당하는 정규 표현 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 15
예 L [a-za-z_] D [0-9] %% {L} ( {L} {D} )* return IDENT; [a-za-z_]([a-za-z_] [0-9])*로 확장 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 16
<규칙 부분> ~ 렉스 입력의 핵심 부분 ~ 규칙 ::= 정규 표현 + 실행코드 정규 표현 : 토큰의 형태를 표현 실행 코드 : 토큰이 인식되었을 때 처리할 행위 %% R 1 {A 1 } R 2 {A 2 } : R n {A n } kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 17
%% ~ 정의 부분과 규칙 부분을 구분하는 구분자 R i ~ 정규 표현 A i ~ 정규 표현에 대해 어휘 분석기가 해야 할 행위를 표현하는 실행 코드 ~ C 프로그램 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 18
규칙 부분의 예 integer printf("found keyword INT"); ~ 입력 스트림에서 문자열 integer를 매칭했을 때"found keyword INT"라는 메시지를 출력 <사용자 부프로그램 부분> ~ 렉스의 입력 작성시 사용되는 부프로그램을 정의 ~ 렉스에 의한 어떤 처리 없이 렉스의 출력인 lex.yy.c에 복사 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 19
렉스의 정규 표현 렉스의 정규 표현 ~ 텍스트 문자 + 연산자 문자 ~ 텍스트 문자 : 입력 스트림에서 실제로 매칭되는 부분 ~ 연산자 문자 : 반복 또는 선택 등을 나타내는 특수 문자 연산자 문자의 종류와 의미 ~ " \ [ ] ^ -?. * + ( ) $ / { } % < > kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 20
" (double quote) ~ " 사이에 있는 모든 문자는 텍스트 문자 ~ a "*" b => 문자열 a*b \ ~ 한개의 문자를 에스케이프 ~ 한개의 문자를 텍스트 문자로 취급하고자 하는 경우, 특 수 문자 앞에 덧붙임. ~ XYZ++에대한정규표현 ~ XYZ"++", "XYZ++", XYZ\+\+ kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 21
[ ] : 문자 클래스 정의 ~ [ a b c ] : a,b,c 중 한 문자 ~ [ ]내에 사용된 연산자 문자의 의미는 무시 ~ -, ^, \ 문자는 [ ]내에서 특별한 의미를 갖음 ~ - : 범위(range)를 나타내는 연산자 문자 [a-z]: a부터z사이의문자중한문자 [-+0-9] : 부호와 숫자를 포함하는 숫자 클래스 [A-Za-z0-9] : 영문자와 숫자중의 한 문자 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 22
^ : 여집합(complement) ~ [^*], *를 제외한 모든 문자 ~ [^a-za-z], 영문자를 제외한 모든 문자 \ : C 언어의 에스케이프 문자열 ~ [ \t\n] : 공백, 탭, 개행 문자중 하나 ~ [\40-\176] : ASCII 값 40인 공백(blank)부터 176인 ~(tilde)까지의 모든 인쇄 가능한 문자 클래스 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 23
* : 0번이상반복 ~ a* : a가0번이상반복 ~ [a-za-z][a-za-z0-9]* : 첫문자가 영문자인 단어 + : 한번이상반복 ~ a+ : 문자a가한번이상반복 ~ [a-z]+ : 소문자로 이루어진 단어? : 선택을 의미하는 연산자 ~ ab?c는 b가 선택적, abc 또는 ac kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 24
: 택일을 위한 연산자 ~ (ab cd) : ab 또는 cd를 인식 ~ 괄호, 복잡한 식을 표현 (ab cd+)?(ef)* : abefef, efefef, cdef, cddd 등 ('+' '-')[0-9]+ : 부호가 있는 정수 ^ : 라인의 시작에서만 인식 ~ ^abc : 라인의 시작에 문자열 abc가 나타났을 때에만 토큰 으로 abc를 처리 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 25
$ : 오직 라인의 끝에서만 인식 / : 접미 문맥을 명시 ~ ab/cd, ab 다음에 cd가 이어서 나타날 때만 ab가 토큰으 로처리. : ~.(period)는 newline 문자를 제외한 모든 문자 ~ "--".* 는 -- 부터 한 라인의 끝 { } : 정의된 이름을 치환식으로 확장 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 26
렉스의 실행 코드(actions) 실행 코드 부분 ~ 토큰이 인식되었을 때 수행해야 할 행위를 C 언어로 기술 ~ 인식되지 않은 모든 문자에 대해서는 입력을 출력으로 복사 ~ 널 문장(null statement) 어떤 행위도 수행할 필요가 없는 문자열에 대한 처리 ~ [ \t\n] ; 공백, 탭, 개행 문자를 입력에서 무시하고자 할 경우 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 27
yytext ~ 렉스의 전역 변수, 문자 배열형(character array) ~ 정규 표현에 의해 실제로 매칭된 문자열 값을 저장 [a-z]+ printf( %s, yytext) ; ~ 토큰 값이 필요한 경우, 변수 yytext의 내용을 사용 ~ 매칭된 문자열을 출력 ~ [a-z]+ ECHO ; kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 28
전역 변수 ~ yytext : ~ yyleng : 매칭된 문자열의 길이를 저장하고 있는 변수. 함수 ~ yymore() ~ 매칭된 문자열의 끝에 다음에 인식될 문자열 첨가 ~ yyless(n) ~ n개의 문자만을 yytext에 남겨두고 나머지는 다시 처리 하기 위하여 입력 스트림으로 되돌려 보내는 함수. kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 29
~ yywrap() 렉스가 입력의 끝을 만났을 때 호출하는 함수 정상적인 경우에 이 함수의 복귀값은 1 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 30
입출력 함수 ~ input() 입력 스트림으로부터 다음 문자를 읽는 함수. ~ output(c) 출력 스트림으로 문자 c를 내보내는 함수. ~ unput(c) 함수 input()에 의해 다시 읽혀지도록 문자 c를 입력 스 트림으로 되돌려 보내는 기능을 하는 함수. kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 31
스캐너 생성 및 동작 렉스를 이용한 스캐너 생성 과정 Lex source Lex lex.yy.c cc a.out library 사용법(usage) lex test.l cc lex.yy.c -o test -ll test < test.dat kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 32
4.2 Context-Free Grammar BNF Example (simple English sentences) (1) sentence noun-phrase verb-phrase. (2) noun-phrase article noun (3) article a the (4) noun girl dog (5) verb-phrase verb noun-phrase (6) verb sees pets kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 33
Terminologies ~ a grammar : a set of rewriting rules metasymbols:, ~ Nonterminals : LHS es of the arrow ~ Terminals : tokens (.) ~ the start symbol: a designated nonterminal, often the LHS of the first rule (sentence) kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 34
CFG generates languages 언어(language) ~ 언어 : 문장(sentences)의 집합 ~ 문장 : 연속된 터미널의 집합 유도(derivation) ~ 시작 심볼로부터 시작하여 생성 규칙을 적용하여 문장을 생 성하는 과정 ~ 우측 유도 vs. 좌측 유도 ~ CFG에 의해 기술된 언어는 유도를 통해 정의 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 35
Derivation Example sentence noun-phrase verb-phrase. article noun verb-phrase. the noun verb-phrase. the girl verb-phrase. the girl verb noun-phrase. the girl sees noun-phrase. the girl sees article noun. the girl sees a noun. the girl sees a dog. kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 36
CFG s can be 순환(recursive) Simple Repetition number number digit digit digit 0 1 2 3 4 5 6 7 8 9 Derivation Example number number digit number digit digit digit digit digit 2 digit digit 23 digit 234 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 37
Structure Repetition expr expr + expr expr * expr ( expr ) NUMBER NUMBER = [0-9]+ Derivation Example expr expr * expr ( expr )* expr ( expr + expr ) * expr... (2 + 3) * 4 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 38
4.3 Parse Tree Rationale ~ 동일한 문장을 생성하는 다양한 유도 과정이 존재 ~ number number digit digit digit digit 3 23 ~ number number digit digit digit 2 digit 23 number number digit digit 3 2 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 39
파스 트리(parse tree) ~ 시작 심볼로 부터 문장을 유도하는 과정을 트리 형태로 표 현 파스 트리 구성 ~ root node corresponds to the start symbol ~ internal nodes correspond to nonterminals ~ leaf nodes correspond to terminals kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 40
A xyz A x y z... kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 41
Abstract Syntax Tree 파스 트리의 단점 ~ 파스 트리에는 불필요한 비단말 노드가 존재 추상화 구문 트리(AST) ~ 파스 트리의 간결한(condensed) 표현 ~ 파스 트리의 불필요한 비단말 노드 제거 ~ 단말 노드가 내부(internal) 노드로 표현 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 42
Example of Parse Tree and AST expr expr ( ) expr * expr number expr + expr digit 4 * number number + 4 digit digit 2 3 2 3 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 43
4.4 모호성(ambiguity) 모호한 문법(ambiguity grammar) ~ 문장 생성에 대해 하나 이상의 유도 과정이 존재 ~ 생성된 문장이 유일한(unique) 의미를 갖지 않음 Dealing with Ambiguity ~ Semantics help in determining which parse tree is correct. ~ Often the grammar can be rewritten to make the correct choice kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 44
Example of Ambiguity Grammar: expr expr + expr expr * expr ( expr ) NUMBER Sentence: 2 + 3 * 4 expr expr expr + expr expr * expr NUMBER (2) expr * expr expr + expr NUMBER (4) NUMBER (3) NUMBER (4) NUMBER (2) NUMBER (3) kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 45
4.5 Extended BNF 배경 ~ BNF의 선택, 반복 부분 등을 보다 용이하게 표현하기 위해 새로운 메타 심볼 도입 ~ Additional Metasymbols [ ], 선택(optional) structures { }, 반복(repetitive) structures kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 46
반복 부분(repetitive part) 표현 ~ { } ~ {a} a가 영번 이상 반복 정규 표현 a * 와같은의미 콤마로 구분되는 명칭 리스트 : BNF 및 EBNF ~ BNF <id_list> ::= <id_list>, <id> <id> ~ EBNF <id_list> ::= <id> {, <id> } kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 47
선택적인 부분(optional part) ~ [ ] ~ [x] x가 나타나지 않거나 한번만 나타날 수 있음 [x]는 {x} 1 ~ 예 <if_st> ::= if <cond> then <stat> [else <stat>] kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 48
EBNF Examples 반복(repetition) ~ BNF: expr expr + term term ~ EBNF: expr term { + term } 선택(optional) ~ BNF: if-stmt if ( expr ) stmt if ( expr ) stmt else stmt ~ EBNF: if-stmt if ( expr ) stmt [ else stmt ] kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 49
Syntax Diagram 문법 흐름도(Syntax diagram) ~ 문법을 도식화하여 표현 초보자가 프로그래밍 언어의 문법을 쉽게 이해 ~ 구성 사각형 :Nonterminal 타원 : Terminal 지시선 : 문법이 움직이는 경로(path) kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 50
Syntax Diagram Examples Repetition ~ EBNF: expr term { + term } Optional ~ EBNF: if-stmt if ( expr ) stmt [ else stmt ] if-stmt if ( expr ) stmt else stmt kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 51
Nonterminal A ~ 사각형 안을 A ~ terminal의 경우와 같이 지시선 ~ 사각형의 내용은 그 안의 이름에 의해 참조 A Terminal a ~ 타원안을 a ~ 지시선으로 연결 a kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 52
생성 규칙 A ::= X 1 X 2 ~ X i 가 Nonterminal인 경우... X n X 1 X 2 X 3... X n ~ X i 가terminal인경우 x1 x2 x3... x n kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 53
A ::= α 1 α 2... α n α 1 A α i α n kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 54
EBNF A ::= {α} A α EBNF A ::= [ α ] A α kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 55
EBNF A ::= ( α 1 α 2 ) β α 1 A β α 2 kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 56
4.6 파싱(parsing) parsing 이란? ~ 소스 프로그램의 문법을 검사 ~ 오류 없는 프로그램에 대해 파스 트리 구성 파싱 방법의 종류(categories) ~ Top-down parsing 좌측 유도, 좌파스, 확장, recursive-descent parsing, LL parsing ~ Bottom-up parsing 우측 유도, 우파스, 축약(reduce), shift-reduce parsing kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 57
파서 생성기(parser generators) ~ 복잡한 파서를 자동 생성하는 도구 ~ YACC, Bison, kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 58
Scanner/Parser Generators scanner generator ~ produces a scanner code from the given regular expression specification file parser generator ~ produces a parser code from the given grammar specification file Typical Examples ~ Unix tools : LEX and YACC ~ GNU : Flex( Fast lex ) and Bison kkman@sangji.ac.kr (Sangji Univ., Fall Semester 2007) 59