Chapter3 Language Translation Issues

구문과 의미

• 프로그래밍 언어 정의 = 구문 + 의미
• 구문
  • 어떤게 생긴 것이 '제대로 생긴 프로그램'인가에 대한 규정
  • 가독성
  • 쓰기성
  • 검증의 수움
  • 번역의 쉬움
  • 모호성이 없음 ex) if A if B else ~~ else의 대응점이 어딘지 모호, sum-> 변수인지 함수인지
• 의미
  • 제대로 생긴 프로그램은 어떤 동작을 하는가에 대한 규정

구문 표기법

• 표준적 구문 표기법
  • BNF (Backus-Naur Form)
  • EBNF ( Extended BNF)
  • CFG (Context-Free Grammar)
• Static semantics
  • CFG로 나타낼 수 없는 범위의 구문 규정
  • 혹자는 Smemtics의 범주에 포함시기도 함
  • Attribute Grammar로 표현

의미 표기법

• Axiomatic Semantics
  • 프로그램의 의미를 predicate transformer로 해석
• Denotational Sementics
  • 프로그램의 의미를 state transformer로 해석
  • state는 machine state를 나타냄
• 의미론은 약간 난해한 분야임

번역 과정

1. 분석
2. 종합
   • 최적화
   • 코드 생성

 

번역 각 단계

• 어휘 분석(lexical analysis; scanning)
  • 프로그램을 단어로 나눔
  • 주석 제거
  • ex) x:=a*2+b*(x*3) -> id<x> assign id<a> times int<2> plus id<b> times Iparen id<x> times int<3> rparen
• 구문 분석 (Syntax analysis; parsing)
  • 구문 구조를 tree로 표현
  • parsing tree

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

 

• 코드 생성
  • tree로부터 수행 가능한 코드 생성

 

• 최적화
  • 트리 형태 또는 코드 형태에서 수행 성능을 개선
  • code size, registers, speed, power

 

Formal Translation Models

• Road Map
  • 번역의 모든 단계는 컴파일러 과목 참고
  • 여기서는 구문 분석 단계만 간단히 소개
• Formal Model
  • BNF, EBNF, CFG의 표현력은 모두 동등함
  • BNF로 구문을 표현하는 법 기술
• Implementation
  • Parser 작성: BNF에 입각하여 단어들의 나열을 tree로 생성하도록 작성
  • parser 생성 도구 : BNF와 Tree 생성 routine을 함께 쓰면 프로그램을 만들어 줌 ex.yacc

 

BNF (Backus-Naur Form)

구성요소

1. Nonterminal (비단말 기호)
   
   • 다른 형태로 치환 가능한 기호(변수)들의 유한 집합
   • 꺾은 괄호로 감싸 나타냄
   • 예: <sentence> <subject> <predicate> <verb> <article> <noun>
2. Terminal (단말 기호)
   • 더 이상 치환할 수 없는 기호(상수)들의 유한 집합
   • 그냥 쓰거나 따옴표로 감싸서 나타냄
   • 예: the, boy, girl, ran, ate, cake, "*"
3. Start symbol(시작기호)
   • 특별히 지정된 하나의 비단말기호
   • 예: <sentence>
4. (중요) Rulse (Productions; 생성규칙)
   • 각 비단말기호를 어떻게 바꿔 쓸 수 있는가에 대한 유한 개의 규칙(rewriting rulse)
   • 예시
     1. <sentence> ::= <subject> <predicate>
     2. <subject> ::= <article> <noun>
     3. <precidate> ::= <verb> <article> <noun>
     4. <verv> ::= ran | ate
     5. <article> ::= the
     6. <noun> ::=boy | girl | cake
5. 치환 연산(Replacement Operator)
   • 비단말기호를 규칙에 따라 다시 쓰는 것
   • 기호 => 로 나타냄

유도(Derivation)

• 유도란?
  • 시작기호로부터 치환 연산을 반복하여 적용하는 과정
  • 이렇게 만들어진 단말기호 나열을 문장(sentence)이라고 함
• 유도의 예 : 위의 구성요소4번의 예시를 생성규칙으로한 유도가정

기타 내용

• 다음 <sentence>도 유도 가능하다
  • <sentence> => *the cake ate the boy
  • Syntax does not imply correct semantic
• 다른 표기법
  • Rule <A> ::= <B><C>
  • 위 BNF 규칙은 CFG에서 다음과 같이 표기하기로 함
    • A->BC

몇 가지 용어들

• Sentence(문장)
  • 시작기호로부터 유도된 단말기호의 나열
• Sematial forms(문장형태)
  • 장차 문장이 될 수도 있는 형태(이미 문장일 수도 있음)
• Language(언어)
  • 문법의 규칙에 따라 유도 가능한 모든 문장들의 집합

Parse Tree(유도트리,derivation tree)

• 파스트리
  • 유도 고정을 나타낸 트리
  • 유도 트리라고도 함
• 유도트리의 예
  • Grammar: B -> 0B | 1B | 0 | 1
  • Derivation: B => 0b => 01b => 010
• 유일한 표현(?)
  • S -> SS | (S) | ()
  • S => SS => (S)S => (())S => (())()
  • S => SS => S() =>(S)() => (())()

Ambiguity

• 모호성
  • 어떤 문법에서는 같은 문자열에 대해 두 개 이상의 파스트리가 얻어질 수 있음
  • 이러한 문법을 모호한 문법이라고 함
• 모호한 문법의 예
  • S -> SS | (S) | ()

왜 모호성이 문제가 되는가?

• 다음 식의 값은? 2*3+4*5    
  1. 26
  2. 70
  3. 50
• 구문은 어느 정도의 의미를 내포하고 있다.
  • 구문이 모호하다면 다른 의미를 내포할 가능성이 있음
  • ALGOL 시대에는 BNF로 의미를 표현할 수 있다고 생각했었음
• 위와 같은 수식을 위한 BNF?
  • E -> E+E
  • E -> E*E

모호한 문법에 대한 대처법

• 문법 변경
  • 모호한 뭄법 G를 모호하지 않은 문법 G'으로 변경하되 L(G) = L(G')이 되도록 한다.
• 파서 변경
  • 파서에서 특정 트리를 선택하도록 한다 

• 컴파일러을 만들 때 어떤 작업을 먼저할지 선택해준다

 

EBNF

• EBNF = BNF + 메타기호 세가지 더
  • BNF의 메타기호  ::= , |, <>
  • 그렇지만 EBNF의 표현력은 BNF의 표현력과 같음
  • 조금 더 편리함
• EBNF의 메타기호
  • 생략가능, 조건문에서 사용됨: [...] 
    • <number> ::= <digits> [.<digits>]
  • or : (...|...|...)
    • <signed number> ::= (+|-) <number>
  • 반복: {...}*
    • <identifier> ::= <letter> { <letter> | <digit> }*

 

EBNF와 BNF의 표현력은 같다. 다만 EBNF가 간결하고 편할 뿐

 

Syntax Chart

• Syntax Chart(Diagram)
  • 구문규칙을 그림으로 표현
  • 좌측 비단말기호는 가장 처음 화살표의 시작 부분에
  • 단말기호를 동그라미로
  • 비단말기호를 네모로
  • 나열은 화살표로
• 예:  <expr> ::= <term> { (+|-)<term>}*

 

More Realistic Syntax Chart

BNF
<if문> ::= if <논리식> then <문장> else <문장> | if <논리식> then <문장>

EBNF
<if문> ::= if <논리식> then <문장> [ else <문장> ]

 

 

 

Finite State Automata

• Grammar and Automata
  • 문법은 언어 생성기
  • 오토마타는 언어 인식기
• Finite Automation
  • 유한 개의 상태로 문자열을 인식하는 자동 기계
  • Finite State Machine의 일종
  • 초기상태(initioal state)로부터 시작하여 입력 기로를 보고 상태전이
  • 최종상태(final state)에 도달하면 그때까지 읽은 입력 기호 문자열 인식
  • FA M이 인식하는 언어 L(M)={w |δ(A,w) =C}, 여기서 A는 초기상태, C는 최종상태 중 하나
  • FA= {Q,∑,δ,q0,F}
    Q= state의 유한집합
    ∑=유한 input character
    δ= QX∑ ->Q
    q0= 초기state (Q에 포함됨)
    F= 유한 states의 집합 (Q의 부분집합)
• FA의 예
  • 홀수개의 1을 인식하는 오토마타
  • 입력 100101이 주어졌을때
    move(A,100101)
    = move(B,00101)
    = move(B,0101)
    = move(B,101)
    = move(A,01)
    = move(A,1)
    =B
  • B가 종결상태이므로 홀수개임으로 인식함

 

DFA와 NFA

• DFA (deterministic finite automata)
  • 어떤 상태에서 한 입력 기호를 보고 갈 수 있는 상태가 단 하나
• NFA (nondeterministic finite automata)
  • 어떤 상태에서 한 입력 기호를 보고 갈 수 있는 상태가 여러 개 일 수 있음
  • 모든 DFA는 NFA의 일종
  • 여러 가능성 중에서 하나라도 최종 상태에 도달하면 인식
• NFA의 예
  • move(A,01) = move(B,1)=C
  • move(A,01) =move(B,1)=D (인식)

NFA에서 DFA로의 변환

 

 

정규문법(Regular Grammar)

• 다음과 같은 형태의 생성 규칙으로만 이루어진 문법
  <nonterminal> ::= <terminal><nonterminal>|<terminal>
• 우변의 특정 위치(우측끝)에만 비단말기호가 올 수 있으며, 개수도 하나만 허용됨
• 정규문법의 예)
  A -> 0A | 1A | 0
• Left Linear, Right Linear
  • 어떤 정규문법에서는 우변의 좌측 끝에만 비단말기호가 올 수 있다고 정의하고 있음(left linear문법)
  • 위 예는 right linear 문법

정규식(Regular Expression)

• 정규식의 정의
  • 단말기호는 정규식
  • a와 b가 정규식이면 (a|b),(ab),(a*)도 정규식
  • 공문자열ε ,공집합∅도 정규식
• 정규식의 장점
  • 정규언어를 간단한 식으로 표현할 수 있음
• 정규식의 예
  • 2로 나누어 질 수 있는 이진 문자열
    (0|1)*0
  • 01을 포함한 이진 문자열
    (0|1)*01(0|1)*

정규식(Regular Expression)

• 정규언어 (Regular Language)
  • 일반적으로 프로그래밍 언어 어휘의 패턴을 나타내기에 충분한 언어
• 정규식(Regular Expression)
  • 어휘의 패턴을 나타내는 방법
• FA(Finite Automata)
  • 어휘를 인식하기 위한 기계 -> 어휘 분석기
• 정규식 -> NFA -> DFA
• FA에서 공집합, 공문자열표현

 

Grammar and Automata

• 문법(grammar)
  • 언어 L(G)에 대한 설계도 G
  • 문장(문자열) 생성기
• 오토마타(automata)
  • 문자열 인식기
  • 패턴(예 정규식으로 나타낸 패턴) 인식기
• a(a|b)*b를 인식하는 프로그램을 작성하라
  • ab -> Yes
  • abba -> No
• 수식 계산기를 작성하라
• infix ->postfix 번역기를 작성하라 
  • 12+(24+3)
  • 12 24 3 ++
• 위와 같은 문제들을 어떻게 해결 할 것인가?
  • 문자열 인식기 작성
  • 여기에 필요한 작업 추가
    • 수식 계산기의 경우 계산 작업
    • inpix->postfix 변역기의 경우 출력 작업

Pushdown Automata

• PDA = FA + Stack
  • 여기서 stack은 pushdown list 라고도 함
  • 결과적으로 상태가 무한하게 늘어나게 됨
• PDA 동장
  • 입력기호(current input symbol)와 스택기호(stack top)를 읽음
  • 상태전이 및 스택변경(0개이상의 스택기호 푸시)
  • 입력문자열을 모두 읽고 스택이 비어 있으면 입력 문자열 인식 (또는 입력문자열을 모두 읽고 최종 상태에 도달하면 입력문자열 인식)
• PDA가 FA보다 강력한 점
  • 입력 문자 개수를 셀 수 있음 (a^n b^n)

PDA 예

 

PDA와 유도

• PDA가 인식하는 언어 = ? = BNF가 나나내는 언어
• PDA는 좌측 유도를 흉내낼 수 있다.
  • 초기상태: Stack Top에 시작기호가 들어 있음
  • 상태 전이
    • stack top이 terminal이고 현재 입력기호롸 같으면, stack top을 pop하고 혐재 입력을 하나 읽는다.
    • stack top이 nonterminal X 이면 , 생성규칙 X ->a 에 대하여 a를 X대신 stack top에 넣는다. 입력 문자는 읽지 않는다.
  • 주의
    • 위 PDA는 비결정적임(임의의 nonterminal X에 대해 X가 좌변인 생성규칙은 많을 수 있음)
    • 위 PDA는 스택을 비울 때 입력 문자열을 인식

NDPDA != DPDA

• PDA의 인식능력차이
  • Nondeterministic PDA와 Deterministic PDA가 인식하는 언어는 다르다.
• Palindrome 예시
  • Deterministic PDA로 인식가능한 Palindrome:
    S -> 0S0 | 1S1 | 2
    1. 0과 1은 읽을 때마다 스택에 넣음
    2. 2를 읽으면 다른 상태로 이동
    3. 스태그이 기호를 빼내며 입력과 같은가 확인
  • Nondeterministic PDA로 인식 가능한 Palindrome
    S -> 0S0 | 1S1 | 0 | 1
    이 경우에는 중간에 0과 1 중에 무엇이 올 지 알 수 없음
  • 따라서 중간 문자를 예측해야함

 

Recursive Desent Parsing

• 순서 하강 파서
  • 간단한 하향식 구문 분석 방법
  • 문법(BNF 또는 CFG)과 파서의 구조가 동일
  • nonteminal에 해당하는 재쥐적 프러시저들로 구성됨
• 순환하강 파서 구성 방법
  • 각 생성규칙에 대해 생성규칙의 우변을 따라하는 프로시저 구성
  • nonterminal -> 프로시저 호출
  • terminal -> lookahead와 일치하는가 검사하고 일치하면 skip 그렇지 않으면 신택스 에러