프로그래밍 언어 Syntax 표현(기술)
Terminologies
- Alphabet
- String
- Language (알파벳으로 만들 수 있는 모든 String 의 집합)
- Sentence : Language 의 한 String
- Lexeme : 의미적 요소의 최소 단위
- Token : lexeme 의 카테고리
- Language recognizer / generator (인식기, 생성기)
Lexeme (어휘 항목) : 구문 기술이 아닌 어휘 명세에 의해 주어지는 것으로, literal, operator, special word 등으로 이루어짐
즉 프로그래밍 언어는 문자가 아닌 Lexeme 으로 이루어졌다고 말할 수 있음
프로그래밍 언어의 구문 기술에는 Lexeme 은 고려되지 않음
Syntax (구조, 문법) : expression, statement, program units 의 형태
Semantic (의미) : expression, statement, program units 의 의미
Syntax와 Semantic 이 합쳐져야 비로소 언어를 정의할 수 있음 (어느 한가지 만으로는 완전히 정의가 불가능)
Syntax 를 표현하는 방법
CFG(Context Free Grammar)
CFG = (N, T, P, S)
N = Nonterminal symbols ( 변수 목록 )
T = Terminal symbols ( 상수 목록 )
P : Productions ( or Rules 규칙 )
S : Start symbol
A -> B
B -> BB | 1
BNF(Backus-Naur Form)
사실 이 둘은 비슷함. BNF 는 다른 언어를 설명하는 메타언어
<LHS> -> <RHS> 의 꼴
<while-statment> -> while ( <expression> ) <statment>
Derivation
BNF나 CFG 의 규칙에 따라 주어진 문장을 만들어나가는 것을 Derivation 이라 함
그렇게 만들어진 최종 구문을 Sentence 라고 함
언어가 만들 수 있는 모든 Sentence 의 집합을 Language 라고 함
<assign> -> <id> := <expr>
<id> -> A | B | C
<expr> -> <id> + <expr>
| <id> * <expr>
| ( <expr> )
| <id>
위와 같은 언어가 있을 때 A := B * (A + C) 를 Derivation
Leftmost derivation
<assign> -> <id> := <expr>
-> A := <expr>
-> A := <id> * <expr>
-> A := B * <expr>
-> A := B * ( <expr> )
-> A := B * ( <id> + <expr> )
-> A := B * ( A + <expr> )
-> A := B * ( A + <id> )
-> A := B * ( A + C )
Rightmost derivation
<assign> -> <id> := <expr>
-> <id> := <id> * <expr>
-> <id> := <id> * ( <expr> )
-> <id> := <id> * ( <id> + <expr> )
-> <id> := <id> * ( <id> + <id> )
-> <id> := <id> * ( <id> + C )
-> <id> := <id> * ( A + C )
-> <id> := B * ( A + C )
-> <id> := B * ( A + C )
정리
Leftmost derivation 은 왼쪽부터 전개해 나가는거고, Rightmost derivation 은 오른쪽부터 전개해나가는것
이러한 전개 과정은 Parse tree 로도 표현이 가능
Amibuity
하나의 sentence 를 만드는데 두 개 이상의 서로 다른 parse tree 가 만들어질 수 있는 Language를 ambiguious 하다. 라고 함
어떤 언어가 모호함을 보이려면 단 하나의 sentence 라도 모호함을 보이면 되고,
어떤 언어가 모호하지 않음을 보이려면 모든 sentence 가 모호하지 않음을 보여야 하므로 이는 굉장히 어렵다.
연산자 우선순위
Parse tree 로 그렸을 때 아랫쪽에 있을 수록 먼저 평가가 되므로 우선순위가 높다.
따라서
|
곱하기가 우선순위가 더 높은 경우 <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <expr> + <term> | <term> <term> -> <term> * <factor> | <factor> <factor> -> ( <expr> ) | <id> |
더하기가 우선순위가 더 높은 경우 <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <expr> * <term> | <term> <term> -> <term> + <factor> | <factor> <factor> -> ( <expr> ) | <id> |
|
Left recursive <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <expr> + <term> | <term> <term> -> <term> + <factor> | <factor> <factor> -> ( <expr> ) | <id> |
Right recursive <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <term> + <expr> | <term> <term> -> <factor> + <term> | <factor> <factor> -> ( <expr> ) | <id> |
C언어의 if-else 모호함
<if-stat> -> if ( <expr> ) <statement>
| if ( <expr> ) <statement> else <statement>
if ( a ) if ( b ) x := 1; else x := 2;
if ( a ) if ( b ) x := 1; else x := 2;
모호하지 않게 바꾸려면
<stmt> -> <matched> | <unmatched>
<matched> -> if (<logic_expr>) <matched> else <matched>
| any non-if statement
<unmatched> -> if ( <logic_expr> ) <stmt>
| if ( <logic_expr> ) <matched> else <unmatched>
EBNF(Extended BNF)
[] : 옵션. 있어도 되고 없어도 되는 것들
{} : 반복. 1개는 무조건 있고, 여러 개 있어도 되는 것들
(|) : n 개 중 하나를 고르는 것
EBNF 가 설명을 더 잘 하는 것은 아니고, 가독성과 작성력을 올려준 BNF 이다.
|
BNF <expr> -> <expr> + <term> | <expr> - <term> | <term> <term> -> <term> * <factor> | <term> / <factor> | <factor> <factor> -> <exp> ** <factor> | <exp> <exp> -> ( <expr> ) | <id> |
EBNF <expr> -> <term> { ( + | - ) <term> } <term> -> <factor> { ( * | / ) <factor> } <factor> -> { <exp> ** } <exp> <exp> -> ( <expr> ) | <id> |