컴파일러 - 형식언어

Posted Dec 4, 2024 Updated Dec 5, 2024

By Blake Woo 5 min read

형식언어와 유한 오토마타

구조, 범위 등이 명확히 규정되어 있는 언어. 자연 언어의 문법 구조를 수학적 측면에서 형식화한 것으로서 자연 언어보다 훨씬 간단한 구조의 인공 언어로 볼 수 있다. 형식 언어의 이론은 알골 등의 프로그램 작성 언어에서 제반 문제로 응용되고 있다.

언어는 문법에 의해서 생성되고 정의된다. 이런 문법의 차이에 따라 인식되는 기계의 종류가 다른데 문법과 인식기의 관계는 아래와 같다.

문법	언어	인식기
type 0(무제약 문법)	재귀 열거 언어	튜링 기계(turing machine)
type 1(문맥인식 문법)	문맥인식 언어	선형한계 오토마타(linear-bounded automata)
type 2(문맥자유 문법)	문맥자유 언어	푸시다운 오토마타(push-down automata)
type 3(정규 문법)	정규 언어	유한 오토마타(finite automata)

$V_{N}$ : non-terminal 기호들의 유한 집합(직접 사용되지 않는 표현 - ex: “수식”, “질의”)
$V_{T}$ : terminal 기호들의 유한 집합(직접 사용되는 표현- ex: “if”, “else”)
$V_{N} \cap V_{T} = \varnothing, V_{N} \cup V_{T} = V$
P : 생성 규칙(production rule)의 집합으로 다음과 같다.
$ \alpha \to \beta, \alpha \in V^{*} , \beta \in V^{*} $
$\alpha$를 왼쪽 부분, $\beta$를 오른쪽 부분, $\to$는 왼쪽부분에 있는기호가 오른쪽 부분에 있는 기호로 단순히 대체
S : $V_{N}$에 속하는 기호로서 다른 non-terminal 기호들과 구별하는 start symbol

$\Rightarrow$는 유도한다는 뜻으로 만약 $\alpha \to \beta $가 존재하고, $\gamma$, $\gamma , \delta \in V^{*}$이면 $\gamma \alpha \delta \Rightarrow \gamma \beta \delta$로 표시
즉, 한 문자열에서 생성규칙을 한번 적용해서 다른 문자열로 바꾸는 것을 나타낸다.
$\overset{*}{\Rightarrow }$ : 영 번 이상의 유도(zero or more derivation)
$\overset{+}{\Rightarrow }$ : 한 번 이상의 유도(one or more derivation)

$S \overset{*}{\Rightarrow} w$이고 $w$가 $V^{*}$에 속하면 $w$를 문장 형태(sentential form)라고 한다. $w$가 $V_{T}^{*} $에 속할 경우, $w$를 문장(sentence)이라 한다.

프로그래밍 언어의 formal definition을 위해 가장 널리 사용되는 방법
이 표기법은 메타 기호(meta-symbol : 표현하려는 언어의 일부분이 아니라, 그 언어를 표현하려고 사용된 특수기호)로서 세가지 기호를 사용
- 논터미널 기호는 <와>로 묶어서 사용
- 대체(relplacement)를 나타내기 위해 ::=를 사용
- 양자 택일을 나타내기 위해 |를 사용

구문 도표는 순서도와 유사하게 그림(도표)으로 구문을 표현하는 것이다.
EBNF와 일대일 대응이 된다.
초기 Pascal의 사용자 설명서에 사용되었다.

가령 EBNF로 아래와 같은 수식이 있다고 해보자. A :: = $X_{1}X_{2}…X_{n}$ (단, $X,X_{1}…,X_{n}$은 비단말 기호이다.)

위의 수식은 아래의 구문도표로 표현이 가능하다.

This post is licensed under CC BY 4.0 by the author.