프로그래밍 언어 정의하는 방법

프로그래밍 언어 정의하는 방법

• 언어 인식기(recognizer): 어떤 문자열이 언어 L에 속하는지 판단하는 장치를 의미합니다.
  • 이는 주로 컴파일러의 어휘 분석기, 구문 분석기에서 사용됩니다.
• 언어 생성기(generator): 어떤 문법을 이용하여 언어 L의 문장들을 생성하는 장치를 의미합니다.

그 후, 언어를 정의하는 방법으로 언어 인식기와 언어 생성기의 관점에서 설명하고 있습니다.
여기서는 정규표현식을 이용하여 언어를 정의하는 방법을 언어 인식기 관점에서 다루고, 문법(grammar)을 이용하여 언어를 정의하는 방법을 언어 생성기 관점에서 다루고 있습니다.

마지막으로, 노트에서는 예시를 통해 언어를 생성하는 방법을 설명하고 있습니다. 이 예시에서는 'S -> S10 | 0’이라는 문법을 이용하여 생성된 모든 문자열이 '0’으로 시작하고, '10’의 조합으로 이루어진 언어 L을 생성한다는 것을 보여줍니다.

언어 인식기 : 언어를 어떻게 인식하는가?

• 언어 인식기(recognizer)는 입력된 문자열이 언어 L에 속하는지를 판별하는 역할을 합니다.

언어 인식기에는 어휘 분석기(lexical analyzer)와 구문 분석기(syntax analyzer)가 있습니다.

• 어휘 분석기는 입력된 문자열에서 토큰(token)을 추출하고, 토큰의 타입을 결정합니다.
• 구문 분석기는 추출된 토큰을 바탕으로 입력된 문자열이 문법적으로 올바른지 검사하고, 트리(tree) 구조로 변환합니다.

이러한 과정을 거쳐 언어 인식기는 입력된 문자열이 언어 L에 속하는지를 판별합니다.

언어 인식기가 일을 하는 방법 : 오토마타, 정규 표현식

언어 인식기는 오토마타를 사용합니다.
특히 정규 표현식과 유한 상태 오토마타는 언어 인식기에서 매우 많이 사용됩니다.

오토마타에 직접적으로 토큰을 넣는 것은 아니고, 입력 문자열을 통해 토큰을 인식합니다.

• 문자열을 오토마타(상태 전이도)를 돌렸을 때 파이널 스테이트에서끝나면 작동한다고 볼 수 있다.

예를 들어, 입력 문자열 "if (x > 0) then y = 2_x;"을 처리하는 언어 인식기에서는, 오토마타를 사용하여 "if", "(", "x", ">", "0", ")", "then", "y", "=", "2", "_", "x", ";" 등의 토큰을 인식하게 됩니다.

언어 생성기

언어 생성기는 문법이나 규칙을 통해 언어의 문장들을 생성합니다.
예를 들어, S -> aSb | ε와 같은 문법으로 생성된 언어는 {ε, ab, aabb, aaabbb, …}와 같은 형태가 됩니다.
이러한 언어 생성기는 자연어 처리나 프로그래밍 언어의 문법 등 다양한 분야에서 사용됩니다.

언어 인식기와 언어 생성기는 서로 반대되는 개념으로, 언어 인식기는 주어진 입력 문자열이 언어 L에 속하는지 판별하는 반면 언어 생성기는 언어 L에 속하는 문자열을 생성합니다.

문법을 만들고 어떻게 문자가 작동하는지 테스트 할 때 사용합니다

연습 : 다음 문법은 어떤 언어를 생성하는가?

S -> S10 | 0

• 해석
  • S라는 심볼(symbol)은 S10 또는 0으로 치환(replace)될 수 있다.

즉, 이 문법 규칙을 이용하여 S에서 시작해서 점차적으로 0과 10을 추가하여 만들 수 있는 문자열들의 집합이 이 문법으로 생성할 수 있는 언어입니다.

S => 0
또는 S => S10 => 010
또는 S => S10 => S1010 => S1010…10 => 01010…10 => 0(10)*
따라서, L = {0, 010, 01010, …, 01010…10} = 0(10)*

레퍼런스

• [[Notes/어휘 분석(lexical analysis)|어휘 분석(lexical analysis)]]
• [[Notes/구문 분석(syntax analysis)|구문 분석(syntax analysis)]]
• [[Notes/BNF (Backus-Naur Form)|BNF (Backus-Naur Form)]]