사전 지식 ∨ (가장 기본) LR 파싱이란? 더보기 shift-reduce의 문제점 (관련 글: https://splendidlolli.tistory.com/524) Bottom-up 파싱이란? 그리고 shift-reduce parsing (이동-감축 구문분석) Bottom-up parsing Top-down 파싱은 시작기호로부터 인풋 문자열을 최종적으로 유도해간다. 파싱테이블을 이용해 확장, 제거해가며 인풋 문자열을 구성해나간다. 좌단 유도 순서로 구문분석하여 직관 splendidlolli.tistory.com ① 핸들을 어떻게 찾을 건데? == shift를 더 할지, 그만 reduce할지 선택 문제 ② 찾은 핸들에 어떤 생성규칙을 적용할 건데? == reduce 방법이 여러가지 있는 경우 == 스택 ..

Bottom-up parsing Top-down 파싱은 시작기호로부터 인풋 문자열을 최종적으로 유도해간다. 파싱테이블을 이용해 확장, 제거해가며 인풋 문자열을 구성해나간다. 좌단 유도 순서로 구문분석하여 직관적이다. 반면 Bottom-up 파싱은 인풋 문자열에서 시작하여 감축해가며 시작기호를 찾아간다. 우단 유도의 역순으로 구문분석한다. 여기서 배울 것은 Bottom-up parsing이고, 감축과 핸들의 개념을 기본적으로 알고 가야 한다. ∨ 감축, reduce : 생성규칙의 역순으로 대체하는 것 즉 감축 대상이 어떤 규칙의 right hand side와 동일하면 left hand side로 대체한다. ∨ 핸들, handle : 감축 대상 바텀업 파싱을 간단히 말하자면, 핸들을 결정하여 감축감축 해가면..

[사전 개념] 구문분석(파싱), 그리고 결정적 파싱이라는 것과, FIRST와 FOLLOW의 개념 https://splendidlolli.tistory.com/515 구문분석, Top down과 Bottom up 구문분석 어떤 문자열(문장)이 정의된 문법에 의해 생성될 수 있는지의 여부를 결정하는 과정이다. 일련의 token들은 구문분석기(parser)를 통해 문장구조가 파악된다. 구문분석이 가능하다는 것은 splendidlolli.tistory.com https://splendidlolli.tistory.com/516 LL파싱과 First set LL파싱에서 First Set이란? Top down 방식으로 유도하는 과정을 생각해보자. 생성 규칙이 이렇게 존재한다고 하자. S=>aA, S=>Bc, B=>b..

Intro : LL(1) 파서 구현방법 ⓐ Recursive descent parser (재귀적 하강 구문분석기) - 직관적, 쉽다 - 문법이 바뀔 때마다 parser 전체를 바꿔야 한다. ⓑ Predictive parser (예측 구문분석기, LL(1) 구문분석) - 파싱테이블을 이용한다 - 문법이 바뀌어도 parser를 바꾸는게 아니라 파싱테이블만 바꾸면 된다. - recall) LL : Left to Right 스캐닝 & Left 유도 - recall) LL(1) : lookahead가 1이라는 거다. 2, 3만 되어도 파싱테이블이 엄청 커져서 컴파일러에 부적합하여 대부분 1로 한다. 이 글에서 LL이라고 하면 LL(1)을 칭하겠다. . . Predictive parser에서 구문분석할 때 '파싱 ..

LL 파싱할 때 정보가 될 수 있는 것은 First set뿐만 아니라 Follow set도 있다. ↓ 저번에 first set 공부할 때 follow set이 필요한 이유에 대해 그냥 주절주절 써놓은 내용 캡쳐다. 사실 아직 LL파싱에 대해 배우는 극초기 부분이라서 배운대로 이정도만 알고 있겠다. 규칙 두개 (예를 들면 A->a | b)가 있다고 하자. input x만 보고 어떤 규칙을 택할지 결정하게 할 수 있을까? => first, follow가 그 정보를 준다 참고) 그때 쓴 내용 ∨ Intro : 예제 & follow 개념 Let : 생성규칙 S->Aa A->bB S->Aa에서는 일단 FOLLOW(A) ∋ a임이 잘 보인다. 한편 이 생성규칙으로 S=>bBa 과 같이 유도..

LL파싱에서 First Set이란? Top down 방식으로 유도하는 과정을 생각해보자. 생성 규칙이 이렇게 존재한다고 하자. S=>aA, S=>Bc, B=>bx 시작 심볼 S로부터 유도를 시작해야 한다. S로 시작하는 생성 규칙이 두개 존재하는데, 둘 중 어떤 생성 규칙을 선택하여 유도해야 할까? 이때 입력값을 보고 선택하면 된다. 만약 a가 입력으로 들어왔다면 S=>aA라는 생성 규칙을 선택해야 한다. ++ recall : 단순한 Top down 방식과 달리 LL파싱은 생성규칙을 결정적으로 선택하므로 하나의 입력문자에 대해 유일한 생성규칙을 선택할 수밖에 없다. 반면 결정적으로 선택하지 않는 Top down 방식의 구문분석은 하나의 입력문자에 대해 가능한 생성규칙을 모두 적용해보고 되는대로 구문분석을..

구문분석 어떤 문자열(문장)이 정의된 문법에 의해 생성될 수 있는지의 여부를 결정하는 과정이다. 일련의 token들은 구문분석기(parser)를 통해 문장구조가 파악된다. 구문분석이 가능하다는 것은 정의된 문법에 의해 유도가 가능하다는 것이다. 구문분석 과정에서 계속해서 생성규칙을 적용해나가며 다시쓰기를 반복한다. 그러다가 최종적으로 유도가 되어 구문분석이 된다면 정의된 문법에 대해 "올바른 문장"이라는 것이고, 올바른 문장은 "문장 구조"를 가진다. 구문분석에 실패하면 틀린 문자열이다. 문장구조를 나타내기 위한 자료구조는 "파스트리" 그리고 "생성규칙 번호 리스트"가 있다. 생성규칙 번호 리스트는 유도해나갈 때 적용된 일련의 생성규칙 번호 리스트다. 좌측유도인지 우측유도인지만 알면 이 리스트만 가지고도..

좌측유도와 우측유도 문맥자유문법에 대한 유도에서 nonterminal을 어느 순서로 대체해나갈 것인가에 따라 "좌측유도"와 "우측유도"가 있다. 좌측으로 유도하든지 우측으로 유도하든지 적용된 생성규칙은 동일하다. 다만 생성규칙들이 적용된 순서가 다를 뿐이다. 예시 아래 예제를 통해 좌측유도, 우측유도를 구해보고, 적용된 생성규칙을 살펴보자. :: 문제 :: 문자열 a + a * a 에 대해 아래와 같은 생성규칙들이 있다. 1. E -> E + T 2. E -> T 3. T -> T * F 4. T -> F 5. F -> ( E ) 6. F -> a 좌측유도와 우측유도를 구하시오 :: 풀이 :: - 좌측유도 E => E + T (규칙1) => T + T (규칙2) => F + T (규칙4) => a + T..

▶ 서론 겸 사전지식 세상 언어를 표현하는 문법은 네단개로 표현할 수 있다 (by Chomsky) recursively enumerable ⊃ context-sensitive ⊃ context-free ⊃ regular 이때 가장 오른쪽의 regular, 정규언어는 세상의 모든 언어를 표현할 수 없다. 흔한 예를 들어, 괄호 구조(), {}는 열린괄호와 닫힌괄호의 수가 동일해야 한다. 하지만 정규표현식을 통해서는 특정 요소의 개수를 파악할 방법이 없다. 즉, 정규표현식으로는 괄호와 같은 nested 구조를 표현할 수 없다. + 또한 FSA로 나타낼 수도 없다는 것도 중요하다. 한편 regular language를 포괄하는 context-free language는 nested 구조를 표현할 수 있다. 즉 ..

어떤 입력이 들어오면 상태를 바꿔야 할 수 있다. 예를 들면 : A상태에서 어떤 입력이 들어오면 B상태로 전이하고 싶은 경우 이 경우 '상태 전이도'로 나타낼 수 있고, 유한상태오토마타(FSA)로 상태전이를 표현할 수 있다. 지금부터 정규표현식을 인식하는 과정을 FSA로 나타낼 것이다. 정규표현식을 상태 전이도를 통해 인식하겠다는 것이다. 어떤상태에서 어떤 입력(표현)이 들어오면 다음 상태로 전이하고, 무언가에서 또 어떤 입력(표현)이 들어오면 다음상태로 전이하고... 이런 전이도를 통해 정규표현식을 인식해낼 수 있다. FSA는 컴파일러 제작에도 쓰인다. 컴파일러 제작시 token을 인식해야 한다. 지금부터 token 인식을 예시로 FSA를 공부해보겠다. token은 식별자, 키워드, 상수, 연산자, 문..