[사전 개념] 구문분석(파싱), 그리고 결정적 파싱이라는 것과, 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에서 구문분석할 때 '파싱 ..

⭐ FK 컬럼 삭제가 안되는 상황 테이블에서 외래키 컬럼을 다음 방법으로 지우려고하면 문제가 발생한다. 사례1▶ FK컬럼은 일반 컬럼처럼 제거할 수 없음 즉, 아래와 같이 drop할 수 없다. ALTER TABLE DROP 사례2▶ FK를 삭제하려는 부적절한 쿼리문 아래와 같이 을 그대로 입력하는 것은 부적절한 방법이다. alter TABLE DROP FOREIGN KEY 다음과 같은 Error Code가 발생한다. 19:14:38 alter TABLE DROP Error Code: 1828. Cannot drop column '': needed in a foreign key constraint 'FK93exnhdf4698rqy4lmt5yapmr' 0.000 sec ⭐ 해결방법: 컬럼에 걸린 제약조건을 ..

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 구조를 표현할 수 있다. 즉 ..

List에 문자열을 담고 for문 내에서 동적으로 처리(삭제)해야 할때 흔히 Iterator를 사용한다.Iterator의 remove() 메서드를 사용하여 삭제할 수 있다. 내가 오늘 새롭게 알게 된 것은 Iterator객체의 현재 요소를 remove()하면 원본 List에서 삭제된다는 것이다.처음에는 Iterator 객체와 List 객체를 완전히 분리하여 생각했기 때문에 몰랐던 내용인데,Iterator가 컬렉션을 읽는 방법 중 하나이고 컬렉션을 내재하고 있다는 사실을 알게 되고 나서 이해가 잘 되었다. ↓  ● 일단 Iterator라는 것은 뭘까?자바 컬렉션의 요소들을 읽어오는 방법을 표준화한 방법 중 하나이다.즉,  컬렉션 요소를 Iterator로 읽어올 수 있다.그러면 컬렉션이 뭔지 알아야겠다.  ..

Java의 String에 대해 정리한다. 잘 이해하려면 사전지식을 알고 가자. ∨ 사전지식 : 문자열 리터럴 vs 문자열 객체 - 문자열 리터럴 객체 : heap의 상수풀(String constant pool)에 담긴다 (java7 이상 : 상수풀이 heap영역에 위치) : 문자열은 상수풀에 하나만 생성된다. 상수풀에는 동일 문자열이 중복으로 생성될 수 없다. : 문자열 변수가 동일한 문자열을 가리킨다면, 그것은 상수풀 내의 같은 문자열을 참조한다. - 문자열 객체 (리터럴x) : heap에 담긴다 : 동일 문자열이 서로 다른 객체로 존재한다. String 더하기 여러 String을 더할 때 "기본"은 이렇다. 그냥 String 객체끼리 더해주는 것이다. String str1 = "aaaaaa"; Str..