# 형식 언어와 유한 오토마타

## 01. 형식 언어

## 02. 형식 문법

## 03. 문법 표기법

### 정규표현

{% hint style="info" %}
정규표현

Regular Expression 은 재귀적으로 정의됨

#### base step

1. ∅ 는 공집합을 나타내는 `정규표현`
2. ε 는 공문자열을 나타내는 `정규표현`
3. 터미널 기호인 a 는 집합 { a } 를 나타내는 `정규표현` 

#### recursive step : r, s 가 정규언어 L(r), L(s) 를 나타내는 정규표현일 때,

1. (r) + (s) 는 L(r) U L(s) 를 나타내는 `정규표현`
2. (r)·(s) 는 L(r)·L(s) 를 나타내는 `정규표현`
3. (r)\*는 {L(r)}\* = {ε} U {L(r)}¹ U {L(r)}² U ... 를 나타내는 `정규표현`
   {% endhint %}

### 구문도표

그림이라 생략..

### BNF 표기법 - Backus-Naur Form

`<, >, ::=, |` 등의 메타기호를 사용해서 문법을 표기함

* 메타기호는 문법기호(`터미널 기호` + `논터미널 기호`) 와는 다르게, 문법 자체와는 상관없는 기호들

{% hint style="danger" %}
C 언어의 식별자identifier 를 BNF 로 나타내보자( \_ 없이)

\<ID> ::= \<E> | **\<ID>** \<E> | **\<ID>** \<N>\
\<E> ::= a | b | ... | z\
\<N> ::= 0 | 1 | ... | 9

시작은 항상 영문이기 때문에, prefix 가 불변이라는 특성이 있음\
이를 재귀적으로 잘 표현하면 됨
{% endhint %}

#### 단점

* 예를 들어, 최대 문자열의 길이가 10이라면?
  * \<E>\<E>\<E>\<E>\<E>\<E>\<E>\<E>\<E>\<E>
  * 너무 번거롭다

### EBNF 표기법 - Extended BNF

* BNF 에 `{, }, [, ]` 메타기호를 추가
* 횟수를 표현하기에 적합함

## 참고링크

* [C 언어의 BNF 표기법](https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm)
* [Cpp eBNF표기법](http://www.externsoft.ch/download/cpp-iso.html)