구문법
문맥 자유 문법(CFG)
1. 터미널 심볼의 집합 T
-> 자체로 기초 심볼, 이후로 작성법 정의X, 문법 규칙의 왼쪽에는 위치 불가능
2. 넌터미널 심볼의 집합 N
-> 스트링들의 작성법이 문법 규칙에 의해 정의, 문법 규칙의 왼쪽에 위치 가능
3. 시작 심볼 S
4. 생성 규칙의 집합
유도
- 입력된 문장이나 프로그램이 문법에 맞는지 검사하는 것
- 어떤 스트링이 문법으로부터 유도 가능하면 문법에 맞는 스트링
- 컴파일러가 하나의 문장을 해석하기 위해 특정 규칙을 가지고 있어야 함
유도 방법
- 시작 심볼 S부터 시작한다.
- 넌터미널 심볼 X를 생성규칙을 적용하여 Y1~Yn으로 대치한다
- 넌터미널 심볼이 없을때까지 반복
- 터미널 심볼의 경우 대치할 규칙이 없으므로 일단 생성되면 끝이며, 터미널 심볼은 그 언어의 토큰이다
모호성 제거 방법
1) 모호성 트리 분석
- 언어 문장의 모호성(비대칭 선택문 문제)
2) 언어 구문의 일부 변경(if-then외엔 end를 붙여주기)
BNF
- 구문에 대한 형식 정의
- 생성 규칙들의 집합
비단말 기호 : 각괄호<>로 묶인 기호, 다시 정의될 대상
단말 기호 : 각괄호로 묶이지 X 기호, 예약어
메타 기호 : 언어를 표현하려고 사용된 특수 기호, ->(정의), |(택일)
- 모호성이 제거된 파스트리를 그리는 법
1. 우선순위를 판단하여 묶는다
2. 가장 낮은 연선자부터 넌터미널 심볼을 부여
3. 좌결합,우결합 따지며 문법 형성
EBNF
- 추가된 메타 기호
{} : 0번 이상 반복
() : 여러개 중에서 하나는 반드시 선택
[] : 옵션, 선택하거나 버리거나 둘 중 하나
BNF vs EBNF
| <number> -> <number><digit> | <digit> | <number> -> <digit>{<digit>} |
재귀 하강 파싱
- 파서 : 입력 스트링을 유도하여 문법에 맞는지 검사하는 프로그램
- 토큰 : 파서에서는 문법의 터미널 심볼을 의미
- 어휘 분석기 : 파서는 필요할때마다 어휘 분석기를 호출
, 어휘 분석기는 입력 스트링을 토큰 단위로 분리하여 리턴
, 파서는 어휘 분석기가 읽은 현재 토큰을 전역 변수에 저장
재귀 하강 파서 구현
- Parser : 재귀 하강 파서에서 구문 분석을 수행
- Lexer : 어휘 분석, 입력된 코드에서 토큰을 추출하는 역할, 코드를 문자열 단위로 읽어오고 문자열에서 토큰 추출 -> 이걸 token클래스의 인스턴스로 반환
- Token : 추출된 토큰의 정보를 담고있는 역할, 토큰의 종류를 나타내는 상수값과 토큰에 해당하는 문자열을 가지고있음
Parsing과 Lexing의 정확한 차이
- Lexing : 입력된 코드를 토큰으로 나누는 과정, 입력된 코드를 문자 단위로 읽어와서 토큰 단위로 분할, 각 토큰의 유형을 식별 -> 입력된 코드를 작은 단위로 나눠 의미를 파악하는 과정
- Parsing : 위에서 추출된 토큰을 사용하여 문법을 검사하고 코드의 의미를 해석함, 문법 규칙을 가진 구문 트리를 생성하고 구문구조 검사 -> 나눠진 작은 단위를 조합하여 코드의 의미를 이해하는 과정
PushbackInputStream
- 지금 보니까 Lexer클래스의 역할을 대신 해줌
- 특정 문자를 읽어올때 알아서 전처리도 해주고 이전 문자도 읽을수있게 해주는 클래스
입력스트림에서 읽는것과 문자열에서 읽는것은 무슨차이?
- 입력 스트림을 사용하면 파일 또는 네트워크와 같은 외부 장치에서 데이터를 읽어올수 있으니 입력 데이터의 크기가 매우 큰 경우에도 처리 가능
댓글