[프로그래밍 언어론] Language Translation Issues (3)

 

[3] Language Translation Issues

프로그래밍 언어 정의 = 구문 + 의미

구문 (Syntax)
-  Readability
-  Writability
-  Ease of verification
-  Ease of translation
-  Lack of ambiguity

의미 (semantics)
-  Execution behavior

구문 표기법
-  BNF (Backus-Naur Form)
-  EBNF
-  CFG (Context-Free Grammar)
-  Static Semantics

@표기법 표현력
BNF = EBNF = CFG

@Static Semantics
-  Semantics에 포함시키기도함
-  Attribute Grammar로 표현

의미 표기법
-  Axiomatic Semantics (predicate transformer)
-  Denotational Semantics (semantic function evaluation)
-  Operational Semantics (state transformer)

번역 과정
1. Lexical analysis
-  프로그램을 단어로 나눔 (주석 무시)
-  식별자(Identifiers), 키워드(Keywords), 리터럴(Literals), 연산자(Operators) 등이 토큰으로 생성
-  Lexical tokens 생성

2. Syntax analysis
-  구문 구조를 tree로 표현
-  문법 규칙에 따라 토큰들의 순서와 관계를 검사하여 프로그램의 구조를 나타내는 트리를 생성
-  Parse tree 생성

3. Semantic analysis
-  정적 의미 분석 (타입 검사 포함)
-  각 구성요소들이 제대로 사용되었나 검사

4. Code generation
-  Tree로 부터 수행 가능한 코드 생성
-  트리에서 필요한 정보를 추출하여 프로그램의 동작을 정의하는 기계어나 중간 언어로 변환

5. Optimization
-  트리 또는 코드 형태에서 수행 성능을 개선
-  실행 속도, 메모리 사용량, 전력 소모 등의 성능 측면을 개선

BFN
-  Nonterminal (비단말기호)
-  Terminal (단말기호)
-  Start symbol (시작기호)
-  Rules (생성규칙)
-  Replacement Operator (치환 연산)

@BNF If_then_else
-  <stmt> -> <matched> | <unmatched>
-  <matched> -> if <logic> then <matched> else <matched> | any non-if statement
-  <unmatched> -> if <logic> then <stmt> | if <logic> then <matched> else <unmatched>

유도
-  시작기호로부터 치환 연산을 반복하여 적용하는 과정
-  Syntax does not imply correct semantics

용어
-  Sentence : 시작기호로부터 유도된 단말기호의 나열
-  Sentential Forms : 문장이 될 수도 있는 형태
-  Language : 문법의 규칙에 따라 유도 가능한 모든 문장들의 집합

Parse Tree (Derivation Tree)
-  유도 과정을 나타낸 트리

모호성 (Ambiguity)
-  같은 문자열에 대해 두 개 이상의 파스트리가 생성됨

모호한 문법 대처법
-  문법 변경 (L(G) = L(G') 되도록)
-  우선 순위 사용

EBNF
-  BNF + 메타기호들
-  Optional [ ]
-  Alternative ( | )
-  Repeat { }*

Syntax Chart
-  좌측 비단말 기호는 처음 화살표의 시작 부분에
-  단말 기호를 동그라미
-  비단말 기호는 네모
-  나열은 화살표

Finite State Automata
-  언어 인식기
-  Finite Automaton

@Finite Automaton
-  입력 기호를 보고 상태 전이
-  Initial state
-  Final state
-  L(M) = {w | d(초기상태, w) = 최종상태}

DFA (Deterministic Finite Automata)
-  어떤 상태에서 한 입력을 보고 갈 수 있는 상태가 하나

NFA (Nondeterministic Finite Automata)
-  어떤 상태에서 한 입력을 보고 갈 수 있는 상태가 하나 이상

@NFA-DFA 변환
-  NFA에서 갈 수 있는 모든 상태들의 집합을 DFA의 상태로 간주

정규문법 (Regular Grammar)
-  <nt> -> <t><nt> | <t>
-  우변의 특정 위치에만 비단말기호가 올 수 있으며, 개수도 하나만 허용됨

@Left linear, right linear
-  비단말기호가 올 수 있는 특정위치가 우측 끝 또는 좌측 끝

정규식 (Regular Expression)
-  단말기호는 정규식 (a, b)
-  (a|b), (ab), (a*)
-  공문자열, 공집합

정규언어, 정규식, FA
-  정규언어 : 어휘의 패턴을 나타내기 충분한 언어
-  정규식 : 어휘의 패턴을 나타내는 방법
-  FA : 어휘 분석기 (action)

Pushdown Automata
-  FA + Stack
-  상태가 무한하게 늘어나게 됨
-  Current inpt symbol과 stack top을 읽어서
-  상태전이 및 스택에 푸시
-  문자열 다 읽었을 때 최종상태 도달 + 스택이 비어있으면 문자열 인식

PDA와 유도
-  PDA는 leftmost derivation을 흉내낼 수 있다
-  Stack top이 nonterminal이면 생성규칙을 통해 변환후 stack top에 넣는다
-  Stack top이 terminal이고 현재 입력 기호와 같다면, stack top을 pop하고 다음 입력 기호를 읽는다
-  해당 PDA는 스택을 비울 때 다음 입력 문자열을 인식

@PDA의 인식능력 차이
-  Nondeterministic PDA와 Deterministic PDA가 인식하는 언어는 다르다

파싱 기법
1. LR Parsing (Bottom-Up)
-  DPDA가 인식하는 언어는 LR(k)로 표현 가능
-  Left-to-right scan : 입력 문자열을 왼쪽에서 오른쪽으로 스캔
-  Rightmost derivation : 가장 오른쪽에 있는 비터미널먼저 변환
-  K symbol lookahead : 볼 수 있는 입력 기호의 수 K

2. Recursive Descent Parsing (Top-Down)
-  BNF와 파서의 구조가 동일
-  Nonterminal에 해당하는 recursive 프로시저로 구성

@Recursive Descent Parser 구성
-  Nonterminal -> 프로시저 호출
-  Terminal -> lookahead와 일치하지 않으면 syntax error
-  Simple code Generator : 구문 규칙에 대한 코드 생성을 담당