Lexical analysis

어휘 분석(Lexical analysis, Scanning)

• 소스코드를 읽고 토큰으로 나누는 것
  • 토큰 : 의미를 가지는 문자열
  • 토큰은 파서에서 처리
• 토큰 종류
  • 예약어 : if, then
  • 특별한 기호 : +, -, ...
  • integer, double, float, 구분자
• 입력된 문자열에서 토큰을 인식
  • lexeme : 토큰을 구성하는 실제 문자열
  • token : lexeme이 속하는 일반적인 클래스
• 에러가 거의 감지되지 않음
  • 유효한 토큰 or 유효하지 않은 토큰
  • 위치를 벗어난 토큰, 선언되지 않은 변수, 철자가 틀린 키워드 등을 찾을 수 없음

정규 표현의 확장

• 1번 이상 반복
  • $(0+1)(0+1)^* or (0|1)(0|1)^* \rightarrow (0|1)+$
• 어떤 문자
  • 메타문자
    • .(period) : 매칭되는 어떤 문자
    • b를 최소한 한번 가지는 모든 문자열 : .b.
• 문자들의 범위
  • 소문자 : [a-z]
  • 숫자 : [0-9]
  • a|b|c → [abc]
  • 여러 범위 표현 : [a-zA-Z]
• 주어진 집합에 포함되지 않는 문자
  • ~a : not a, ~(a|b|c) : not either a or b or c
  • [^a], [^abc]
• 선택적 표현
  • 특정 문자열에 나타날 수도 있고 안나타날수도 있는 것
  • 메타문자 ? 사용
    • r? : r은 선택적으로 매칭됨

프로그래밍 언어 토큰에 대한 정규표현

• 숫자
  • nat = [0-9]+
  • signedNat = (+|-)?nat
  • number = signedNat(”.”nat)?(E signedNat)?
• 예약어
  • reserved = if | while | do | ...
• 변수
  • letter = [a-zA-Z]
  • digit = [0-9]
  • identifier = letter(letter|digit)*

모호성

• 어떤 문자열들은 여러 개의 다른 정규 표현으로 매치될 수 있다.
  • 정규 표현은 그 자체로는 모호함
• 언어 정의는 모호하지 않은 법칙을 주어야 한다.
  • 예약어 : 변수가 될 수 없음
  • 가장 긴 서브문자열의 원칙
    • 문자열이 하나의 토큰 또는 여러개의 토큰들로 될 수 있을 때 하나의 토큰으로 해석하는 것이 일반적으로 선호됨
    • 토큰 구분자 또는 문자
      • = 은 왼쪽의 문자열을 변수로 구분
      • 빈칸, 새로운 줄, 탭은 구분자로 취급

White space

• 스캐너는 파싱에 기여하지 않는 토큰들을 버린다.
• whitespace = (newline | blank | tab | comment)+

Lookahead

• 구분자는 토큰 문자열을 끝내지만 그들 자체로 토큰이 될 수 없음
• lookahead는 어디서 한 토큰이 끝나고 다음 토큰이 시작될지 결정하기 위해 필요
  • = 은 변수를 인식하는데 쓰임
  • 다음 토큰이 인식되어야 한다는 것을 표현하기 위해 = 은 입력에 남아있어야 함
• 가끔 단일 문자보다 더 많은 lookahead가 필요

TINY language

• ;으로 문장을 나눔
• 모든 변수는 integer형
• 변수 선언은 항상 assign을 받아야 함
• 2가지 제어문
  • if-then
    • else는 선택
    • end로 끝남
  • repeat-until
• read, write 상태
  • read : 입력
  • write : 출력
• Boolean 표현(<, =)
• 산술 표현 (+, -, *, /)
• 주석 : { }
  • 중첩 불가능
• white space : blank, tab, newline
• 가장 긴 substring 인식
• = 같다 / =: 할당