목차
📁 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)은 입력 토큰을 하나만 보고 결정한다는 뜻이다.
LOOKAHEAD에 대해 더 자세한 내용은 해당 포스팅 하단에서 확인할 수 있다.
아래와 같은 CFG는 절대 LL(1)문법이 될 수 없다.
1. 모호한 문법(ambiguous)
2. left-factoring이 될 부분을 갖고있는 문법
3. left-recursive한 문법
위 세 문제를 해결하면 LL문법에 가까워질 수 있지만, 꼭 LL문법이 될 수 있다는 보장은 없다.
🌱 모호성 해결
모호성을 해결하는 방법은 연산자 우선순위를 주거나 결합법칙을 반영하여 같은 언어를 생성하는 다른 문법을 사용하는 것이다.
더 자세한 내용은 아래 포스팅에서 확인할 수 있다.
🌱 Left Factoring 수행
Left Factoring이란, 공통 앞부분(common prefix)을 새로운 nonterminal을 도입하여 인수분해 하는 방식을 말한다.
즉 left factoring이 될 부분을 갖고있다는 뜻은 규칙에 공통 앞부분을 가진 규칙이 존재한다는 뜻이다.
예를 들어 아래와 같이 left-factoring 할 수 있다.
예제 1)
예제 2)
예제 3)
🌱 Left-Recursion 해결
예를 들어 아래 문법으로 스트링 "1 + 2 + 3 + 4"를 유도해 보자.
위 방법과 같이 스트링 "1 + 2 + 3 + 4"이 유도될 수 있는데, 위 과정은 사람이 직접 판단한 과정일 뿐이다.
4 -> 5 과정을 보면, E -> E + T 규칙이 아닌 E-> T를 유도해야하는데, 컴퓨터는 첫번째 규칙인 E -> E + T를 계속 유도할 테니 무한 루프에 빠질 가능성이 있다.
이러한 무한 루프의 가능성은 Left recursion을 Right recursion으로 바꿈으로써 해결할 수 있다.
LHS의 Nonterminal이 RHS의 첫 심벌에 나타나는 경우, 다음과 같이 변경하여 직접 left-recursion을 제거할 수 있다.
⬇
결과적으로, left-recursion을 right-recursion으로 변경 가능하다.
예를 들어 아래와 같은 문법에서 left-recursion을 제거하면, 오른쪽과 같은 결과를 도출할 수 있다.
📁 LOOKAHEAD(...)
LOOKAHEAD란, 어떤 규칙이 적용되었을 때 맨 처음 나올 수 있는 terminal 심벌의 집합이다.
위 정의를 보면 알수있듯이, LOOKAHEAD와 FIRST는 다른 개념이다.
🌱 Strong LL의 조건
임의의 택일 규칙 A -> a | b 에 대해 아래 조건을 strong LL 조건이라고 한다.
한 마디로, 주어진 상황에서 LOOKAHEAD가 유일하게 결정되는 것으로, strong LL조건은 곧 LL(1) 조건과 동일하다.
📁 LL(1) 파서 구현
LL(1) 파서를 구현하는 방법은 두가지가 있다.
1. Recursive Descent parser
recursion을 이용하는 방법으로, 각 Nonterminal마다 한 개의 procedure를 둔다.
이때 procedure란 보통 반환타입이 void인 메서드를 가리킨다.
직관적이고 쉬운 장점을 가진 반면,
생성규칙이 바뀌면 구문분석기를 뜯어고쳐야하는 단점이 있다.
기본적으로 recursive descent parser의 수도코드는 아래와 같다.
예를 들어, 아래 문법을 파싱하는 코드는 c언어를 이용하여 구현해보자.
1) Terminal Symbols
이때 get_nextSymbol()은 getToken()과 같은 역할을 하며,
nextSymbol은 전역변수이다.
2) Nonterminal Symbols
실제 쓰이는 파서들 중에서는, gcc의 파서가 recursive descent parser 방식을 사용한다.
실제로 gcc 파서의 내부를 살펴보면, 각 nonterminal마다 procedure가 존재하고, 내부에서 각 심벌에 맞춰 파싱하는 코드를 확인할 수 있다.
ANTLR란 자바에서 사용하는 파서를 만들어주는 도구로, ANTLR로 만든 파서도 recursive descent parser 방식을 사용한다.
ANTLR에게 위와 같은 입력을 주면, 아래와 같은 자바 코드로 바꾸어준다.
2. Predictive parser
이론적으로 PDA(push down automata)에 기반하는 방식이다.
어휘 분석 때 문법을 RE로 구술하고 이를 FSA로 표현한 것과 마찬가지로,
구문 분석 시 문법을 CFG로 구술하고 이를 표현력이 동일한 PDA로 표현할 수 있다.
생성 규칙이 바뀌더라도 구문 분석기는 고치지 않고, 구문 분석기의 행동을 나타내는 파싱 테이블만 수정해도 된다는 장점이 있다.
Predictive parser는 테이블을 이용하여 파싱을 진행하는 방식이다.
LL(1)은 LOOKAHEAD에 따라 적용할 생성규칙이 결정적으로 선택되므로 주어진 문자열에 대해 기계적인 파싱이 가능하다. 때문에 nonterminal과 terminal의 각 조합에 하나씩의 생성규칙이 대응될 것이며, 이를 테이블로 나타낼 수 있다.
예를 들어, 다음과 같이 문법에 대한 테이블로 생성할 수 있다.
파싱 테이블은 기본적으로, Nonterminal과 terminal이 만나는 지점에 적용될 규칙 번호를 써넣는 방식으로 생성한다.
적용될 규칙을 찾는 과정은 아래 절차를 따른다.
예를 들어, 아래 문법에 대한 파싱 테이블은 다음과 같이 만들 수 있다.
🌱 모호성과 테이블
만약, 파싱 테이블 한 칸에 두 개 이상의 생성규칙이 들어갈 수 있는 경우는 결정적 선택이 불가능하므로 LL(1)이 아니다.
(backtracking이 일어날 수도 있다.)
예를 들어 다음과 같은 경우가 있다.
📁 기계적 파서 구조
push down automata를 사용하면 생성 규칙이 바뀌더라도 구문 분석기는 고치지 않고 파싱 테이블만 바꿔도 되도록 파서를 만들 수 있다.
이때 push down automata는 FSA와 비슷한데, stack이 존재하고, PDA는 스택을 연습장으로 사용한다.
예를 들어 '(()(()))'와 같이 nesting이 필요한 문법을 통해 나온 스트링을 인식할 때 보통 스택을 사용하는 것과 같은 원리이다.
위 스트링처럼 CFG로 나타내기 적합한 언어는 CFG와 표현력이 동일한 PDA로 표현해도 적합하다.
📁 구문 분석기 Action
1. pop(제거)
스택의 top은 입력 symbol이다.
이때 pop을 한다는 것은 스택의 top 심벌을 스택에서 제거하고, 현재 입력 심벌은 입력 스트링에서 제거하는 행동을 말한다.
2. expand(확장)
스택의 top이 Nonterminal인 경우, 생성 규칙을 적용하여 확장시킨다.
예를 들어 M[A, a] = {A -> XYZ}일 때, A를 스택에서 제거하고 ZYX 차례로 스택에 넣는 작업이 확장이다.
3. accept(인식)
스택의 top 심벌과 현재 입력 심벌 모두 $ 인 경우, 주어진 입력 스트링이 올바른 스트링임을 알리는 행동이다.
4. error(오류)
스택의 top이 Nonterminal 심벌인 경우, 그 심벌로부터 현재 보고있는 입력 심벌을 결코 유도할 수 없음을 알리는 행동이다.
다음은 구분 분석기 action 중 어떤 파싱행동을 수행하는지를 나타내는 표 중 하나의 예시이다.
스택의 내용은 왼쪽으로 갈수록 스택의 bottom, 오른쪽으로 갈수록 스택의 top이라고 생각하면 된다.
