[프로그래밍 언어론] BNF/EBNF

CS/프로그래밍 언어론

[프로그래밍 언어론] BNF/EBNF

윤곰이 2024. 4. 26. 00:45

학교에서 들은 프로그래밍 언어론 강의 내용을 복습하면서 작성한 글입니다.
March 25, 2024 12:20 AM

Syntax: 문장이 언어의 문법에 맞게 구성되었는가?
Semantics: 문장의 의미가 타당한가?

Terminology

sentence: string of characters
language: set of sentences
lexeme(어휘): lowest level syntatic unit, 코드에 작성되고 사용되는 모든 문자열, 숫자, 기호 등
- sum, *,,,
⬇️ lexical analyzer(어휘분석기)
token: lexeme을 카테고리로 묶어서 항목별 분류해놓은 것
- identifier, equal sign,,,

프로그래밍 언어 정의 방법

recognizer(언어 인식기): 입력되는 문자열을 읽고, 표준에 맞는 형식이어야함, 어떤 문자열이 어떤 언어에 속하는지 판단!
- 구문 분석기 등
generator(언어 생성기): 문법에 맞는 문장 만들어준다

BNF

context-free grammars: 문법이 정해지면 뜻도 정해져 무조건 하나의 뜻만 가지고 있음
- 인간언어: 문맥에 따라 의미 다른 context sensitive language
BNF(Backus-Naur Form): 다른 언어를 설명하는 메타언어
- terminals - lexemes or tokens : 식별 가능한 단어나 토큰
- 규칙:
  - LHS - nonterminal (규칙의 이름이나 유형)
  - RHS - terminals or nonterminals (할당된 의미나 유형) terminal: 최종적으로 구문분석 결과로 나타나는 단어, 실제로 입력될 수 있는 문자열, 입력으로 직접 사용되는 단어, 작은 따옴표 큰 따옴표로 감쌈 하나 이상의 RHS 가질 수 있음
  - <LHS> → <RHS> 꼴
- non terminal start symbol : <program>
- 메타기호메타 기호 의미
  
  ::== 정의
  
  | OR
  
  <> non-terminal
- recursion: <ident_list> → identifier | identifier**,** <ident_list>

<program> -> <stmts>
<stmts> -> <stmt> | <stmt> ; <stmts> //문장들의 집합인 <stmts> 가 하나의 문장이거나 문장 다음에 세미콜론이 오고 또 다른 문장 집합 <stmts> 가 올 수 있다는 것 나타냄
<stmt> -> <var> = <expr>  //변수 <var>가 등호와 식 <expr>로 유도될 수 있다
<var> -> a | b | c | d  //변수 <var>가 a,b,c,d 중 하나의 값 가질 수 있다
<expr> -> <term> + <term> | <term> - <term> //<expr>이 하나 이상의 <term>과 덧셈, 뺄셈으로 구성
<term> -> <var> | const

derivation(전개, 유도)

<program> => <stmts> => <stmt>
		  => <var> = <expr>
		  => a = <expr> 
		  => a = <term> + <term>
		  => a = <var> + <term>
		  => a = b + <term>
		  => a = b + const

유도과정에서 생성되는 모든 문자열은 sentential form (문장형태)
sentence: 문장형태중에 terminal symbol 만 남은 것 (nonterm이 남아있으면 derivation이 아님)
leftmost derivation: 각 단계에서 가장 왼쪽에 있는 비종단이 선택되어 확장되는 방식
leftmost derivaton, rightmost derivation도 아닌 임의의 방식으로 진행될 수 있음

Parse Tree

Ambiguity in Grammars

문법이 모호하다는 것은 두 개 이상의 구문 트리를 생성할 수 있다는 것 의미
문법을 유용하게 하려면 문법을 모호함이 없도록 개정하거나, 어떤 구조가 의미 있는지를 결정 할 수 있도록 모호성 제거규칙(disambiguating rule)을 함께 첨부

AST(Abstract Syntax Tree)

parse tree 중 derivation 과정을 제외하고 필수적인 정보만 담은 tree

Precendence cascade

컴파일러나 구문분석기에서 연산자의 우선순위를 지정하고 처리하는 프로세스 우선순위가 한 연산자에서 다음 연산자로 전달되는 과정: 한 연산자의 우선순위가 다음 연산자에도 영향을 미치는 것
우선 순위 ⬇️ : root 에 가깝게

parse tree 사용 시, 모호성 방지: 각 노드의 위치와 연산자의 상대적인 위치에 따라 우선순위가 결정되기 때문에 서로 다른 우선순위를 가진 연산자가 동일한 트리 내에서 모호성을 발생시키지 않음

Associativity of Operators

연산자의 결합성은 해당 연산자가 표현식에서 어떻게 결합되는지 (연속적으로 나타나는 같은 연산자들 사이에서 어떤 순서로 계산이 이루어지는지 지정)
- 전자는 a+b+c 를 (a+b)+c , a+(b+c) 두 가지로 해석 가능
- 후자는 무조건 a+(b+c)
<expr> -> <expr> + <expr> | const (ambiguous) <expr> -> <expr> + const | const (unambiguous)
예)
모호함 해결 → left recursion 만 남기고 right recursion 없애버리기

<exp> ::= <exp> - <term> | <term>
<term> ::= <term> * <factor> | <factor>
<factor> ::= (<exp>) | <number>
<number> ::= <number><digit> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
//unambiguous한 BNF 문법

Extended BNF (EBNF)

optional part는 [] 안에 예)<proc_call> -> ident [(<expr_list>)]
RHS의 alternative 부분은 (|) 로 예)<term> → <term> (+|-) const
0회 이상의 반복은 {} 안에 예) <ident> → letter { letter | digit }
- BNF에서는 재귀적 호출인지: 비터미널이 자기 자신을 참조하고 있는지 확인 (우측에 같은 비터미널)

BNF
<expr> -> <expr> + <term>
	| <expr> - <term>
	| <term>
<term> -> <term> * <factor>
	| <term> / <factor>
	| <factor>
EBNF
<expr> -> <term> {(+|-) <term>}
<term> -> <factor> { (*|/) <factor>}

Pascal EBNF

<subpascal> ::=program <ident>；<block> .
<block> ::=[<const_dcl>][<var_dcl>]{<proc_dcl>} <compound-st>
<const_dcl> ::=const <ident> = <number> {；<ident> = <number> }；
<var_dcl> ::=var <ident_list> : <type> {；<ident_list> : <type> }；
<ident_list> ::=<ident> {**,**<ident>}
<proc_dcl> ::=procedure <ident>['('<formal_param>')']；<block>；
<compound-st> ::=begin <statement> {；<statement>} end

::==	정의
\|	OR
<>	non-terminal