본문 바로가기

전체 글

 (231)
[CP] 구문분석 도구 : Yacc 📁 Yacc Yacc은 Yet Another Compiler Compiler의 약자로, LALR 파서 생성기이다. Lex와 함께 사용되는 유용한 도구이며, Confilxt 발생 시 대처하는 손쉬운 방법을 제공한다. Lex와 함께 AT&T Bell Lab.에서 70년대 유닉스 운영체제 용으로 개발되어, 유닉스 표준으로 채택되었지만 최근에는 GNU Flex/Bison을 더 많이 사용하고 있다. .y 파일 형태는 lex, flex 파일과 동일하며 다음과 같다. 예를 들어 Example.y 라는 파일이 있다고 가정할 때, 내부 형태는 다음과 같다. 📁 LR Conflict 모호한 문법은 파싱 테이블에 shift-reduce 나 reduce-reduce conflict를 야기한다. 이러한 conflict는 우선순..
[CP] Bottom-up 파싱, Reduce와 Shift-Reduce 파싱 📁 Bottom-up으로 구문 분석(Parsing)하기 Bottom-up의 파싱 결과는 우파스로, 우측 유도의 역순이다. terminal 심벌들로부터 시작해서 시작 심벌을 유도하는 방식이며, 생성 규칙의 RHS와 매치되는지 확인하고, 매치되면 LHS로 바꿔치기를 반복하여 진행한다. 예를 들어 아래 문법을 Bottom-up 방식으로 파싱하면 다음과 같다. 📁 LL, LR 1. LL(k) LL이란 입력을 Left-to-right, 왼쪽에서 오른쪽으로 스캔하여, Left-most를 유도하는 것?을 말한다. k개의 심벌을 LOOKAHEAD로 사용한다. 2. LR(k) LR이란 입력을 Left-to-right, 왼쪽에서 오른쪽으로 스캔하여, Right-most를 유도하는 것을 말한다. 마찬가지로 k개의 심벌을 L..
[CP] LL(1) 문법 📁 LL 조건 LL조건이란 LL 파싱을 할 수 있는 조건으로, 즉 문법이 결정적으로 파싱될 수 있는 조건을 말한다. 즉, input만 보고 A -> a와 A -> b 중 어떤 규칙을 따라야하는지 결정할 수 있으려면 만족해야하는 조건이다. FIRST에 공통 원소가 없으므로, 각 순간에 적용할 생성규칙이 유일하게(결정적으로) 정해진다. 또한, 생성규칙이 null을 유도할 수 있으면 FOLLOW에 대해서도 고려해야하므로, FOLLOW(A)와 FIRST(b)는 분리된 집합이어야 한다. 📁 LL(1) 문법 LL(1) 문법이란, 임의의 생성규칙 A -> a | b 에 대해 LL 조건을 만족하는 CFG를 말한다. 이때 괄호안의 숫자는 LookAHead의 수를 말한다. 즉 (1)은 입력 토큰을 하나만 보고 결정한다는 ..
[CP] FOLLOW in LL Parsing 📁 FIRST의 한계 LL파싱은 결정적 파싱이 되는 문법을 선별하여, 각 입력 문자당 적용될 생성규칙을 미리 뽑아두고 시작한다. 이를 위해 규칙으로부터 여러 정보들이 필요한데, FIRST 집합만으로는 한계가 있다. A -> XXX과 같은 생성규칙이 있다고 할 때, Nonterminal A가 Nullable한 경우 FIRST만 가지고 생성규칙을 결정적으로 선택할 수 없다는 문제가 생긴다. 이때 FIRST 말고도, A의 다음에 나오는 심벌의 집합을 수집할 필요가 생기고 이를 FOLLOW 집합이라고 한다. 📁 FOLLOW FOLLOW(A)란 시작 심벌로부터 유도될 수 있는 모든 문장 형태에서 A 다음에 나오는 terminal 심벌의 집합을 말한다. 이때 $는 입력 스트링의 끝을 표기하는 마커 심벌이다. FIR..
[CP] FIRST in LL Parsing LL파싱은 결정적 파싱이 되는 문법을 선별하여, 각 입력 문자당 적용될 생성규칙을 미리 뽑아두고 시작한다. 이를 위해 규칙으로부터 필요한 정보들에는 FIRST 집합이 있다. 📁 FIRST FIRST란 Nonterminal A로부터 유도되어 첫번째로 나타날 수 있는 terminal들의 집합을 말한다. 예를 들어, 다음 문법의 FIRST(S), FIRST(A), FIRST(B)는 다음과 같다. 📁 FIRST(X)를 계산하는 방법 정의 1. X가 terminal이면 FIRST(X)는 자기 자신이 된다. 이때 X는 Nonterminal이어야하지만, 위 규칙은 계산의 편의를 위해 확장한 개념이다. 정의 2. X-> aα 와 같이 맨 처음이 terminal인 생성규칙이 존재하면 해당 terminal a가 FIRST..
[CP] Top-down 구문 분석, LL파싱 📁 Top-down으로 구문 분석하기 Top-down 방식은 직관적이고, 좌측 유도 과정과 유사하다. 진행 과정은 다음과 같다. 1) 시작 심벌이 왼쪽(lhs)에 존재하는 생성규칙 중 첫번째 생성규칙으로 유도하여 문자열을 생성한다. 2) 유도를 통해 생성된 문자열과 입력 문자열을 차례로 비교한다. 3) 유도된 문자열과 입력 문자열이 같으면 계속 비교해나간다. 4) 유도과정에서 생성된 문자열에 Nonterminal이 나오면, 이 Nonterminal의 첫번째 생성규칙으로 또 다시 유도해서 새 문자열을 생성한 후 비교해간다. 5) 유도된 문자열과 입력 문자열이 다른 경우, backtraking을 수행한다. 🌱 backtracking 비교한 두 문자열이 동일하지 않을 경우, 직전 생성규칙을 잘못 적용한 것이므..
[CP] 구문 분석에서 문법의 모호성(Ambiguity) 📁 모호성(Ambiguity) 문법 G에 의해 생성되는 어떤 문장이 두 개 이상의 유도트리를 갖는다면 문법 G는 모호하다고 말한다. 즉, 좌측유도와 우측유도의 유도트리가 같으려면 문법이 모호하지 않은 문법이어야 한다. 예를 들어 "if b then if b then a else a"라는 문장을 아래 문법을 이용하여 유도해보자. 위 문장은 여러 유도과정이 나올 수 있고, 그에 따라 여러가지의 유도 트리가 나올 수 있다. 위 두 유도트리는 다르게 생겼지만, 둘 다 "if b then if b then a else a"라는 문장을 나타내고 있다. 또한 "a + a * a" 입력을 아래 문법을 이용하여 유도해보자. 이 예시 또한 두 개의 유도트리가 나올 수 있다. 이처럼 하나의 문장을 유도하는 과정이 여럿 나올..
[CP] 구문 분석 (Syntax Analysis) 📁 구문 분석(Syntax Analysis) 구문 분석이란 어휘 분석을 통해 토큰으로 나눈 것을 구조를 분석해서 트리모양으로 만드는 작업이다. 위 그림에서, 처음 코드를 어휘분석기(스캐너)를 통해 배열 형태의 토큰들로 만드는 것은 어휘 분석에서 하는 일이고, 어휘 분석의 결과로 얻은 토큰들의 구조를 분석해서, 이를 파스트리(Parse Tree)라는 결과물로 만드는 것이 구문 분석에서 하는 일이다. 구문 분석의 예를 들어보자. 우리말 구문, 즉 문법을 분석할 때 위와 같은 트리모양으로 분석할 수 있다. 📁 How to describe the syntax? 프로그래밍 언어 제작자가 문법을 기술(설명)하는 방법 참고로 어휘분석 때 위 질문에 대한 답은 "정규표현식"으로 기술하는 것이었다. 🌱 CFG(Conte..

티스토리툴바