얌생

📌 구문 분석

어휘 분석을 통해 잘라낸 토큰을 비선형 트리 구조로 그린다.

비선형 트리 구조에서 문법 오류를 찾아낸다.

while b ≠ 0:
    if a > b:
        a := a - b
    else:
        b := b - a
return a

위 코드를 비선형 트리 구조인 Abstract_syntax_tree로 나타내면 아래 그림과 같다.

컴파일러는 프로그래밍 언어로 작성된 소스 코드를 기계어로 변환하는 프로그램이다.

📌 어휘 분석

컴파일러의 첫 번째 단계를 어휘 분석 또는 스캐닝이라 한다.

어휘 분석이란 소스 프로그램을 읽어들여 토큰이라는 의미 있는 문법적 단위로 분리하고 토큰 스트림을 생성하는 것이다.

이러한 어휘 분석을 담당하는 도구를 '어휘분석기' 또는 '스캐너'라고 한다.

언어마다 사용하는 토큰이 다르지만 일반적인 프로그래밍 언어에서 사용하는 토큰은 if, for, while과 같은 예약어, 3, 2.5와 같은 상수, +, -, *, /, =와 같은 연산자, 프로그래머가 정의한 식별자, 그리고 괄호나 쉼표(,), 세미클론(;)과 같은 구분자 등이 있다.

이러한 토큰은 다음 단계인 구문 분석에서 효율을 높이기 위해 순서쌍( 토큰 번호, 속성 값 )의 형태로 전달한다.

• 토큰 번호는 모든 토큰을 구별하기 위한 유일한 번호를 말한다.
• 속성 값은 기호표에 저장된 항목을 가리킨다.

형식 언어란, 인간과 기계 사이에 의사소통을 하는 언어로서 인위적으로 만들어진 언어다.

📌 종류

촘스키가 제안한 촘스키 위계에 따라 형식 언어를 네 가지로 계층을 나눠 분류 할 수 있다.

1. 재귀 열거 언어( Recursively Enumerable Language, REL )

🔹 개념

• 튜링 기계에 의해 인식 될 수 있는 언어다.
• 모든 계산 가능한 문제가 포함되고, 튜링 기계가 정답을 찾을 수 있는 언어다.
• 튜링 기계가 항상 멈추는 것은 아니므로, 특정 문자열이 언어에 속하지 않는지 판별하는 것은 불가능 할 수 있다. (즉, 언어에 속하는 문자열은 확인할 수 있지만, 속하지 않는다고 확정할 수 없음)

🔹 특징

• 가장 강력한 언어 클래스로, 모든 다른 언어를 포함한다.
• 비결정적 튜링 기계로도 인식이 가능하다.
• 어떤 문자열이 언어에 속자히 않는지를 결정하는 것은 불가능 할 수 있다. ( 정지 문제와 관련 )

형식 언어 중 컴퓨터와의 의사소통에 사용되는 언어를 프로그래밍 언어( = 컴퓨터 언어 )라고 한다.

프로그래밍 언어는 사용 목적, 형태와 기능, 세대 등에 따라 여러 가지로 분류할 수 있다.

• 형태와 기능에 따라 저급 언어와 고급 언어로 나눈다.
  • 저급 언어에는 기계어와 어셈블리어가 있다.
  • 고급 언어에는 C, 파스칼, 코볼 등이 있다.