code the world

문제나도 재미있게 본 영화 콘택트를 배경으로 하는 문제이다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ N ≤ 200)의 범위를 갖는다. 각 테스트 케이스에 대해 주어진 전파가 문제에서 제시한 패턴이면 “YES”를 그렇지 않은 경우는 “NO”를 출력한다. 출력 문자열은 모두 대문자로 구성되어 있다.풀이문제에서 제시한 찾아야하는 패턴은 (100+1+ | 01)+ 이다.정규표현식을 안다면 쉽게 이해할 수 있을 것이다. 나는 state transition graph를 그려서 풀었다.원래는 NFA에서 DFA로 바꿔서 그리려고 했지만 밑의 그래프도 코드로..

LR grammar는 left-recursive, right-most derivation의 약자이다.이 문법을 사용해 만들어진 파서는 shift-reduce parser라고 부른다. Shift & Reducebottom-up parser는 derivation의 우변에 있는 내용을 좌변으로 되돌린다. 이 과정을 reduce라고 한다.즉 시작을 최종 식에서부터 하여 역으로 시작 심볼로 변환하는 방법이다. right-most derivation은 변환해야될 식에서 오른쪽부터 살펴보며 reduce를 한다는 뜻이다.int*int+int라는 에시에 대해 단계별로 parser가 동작하는 과정을 나타낸 것이다.shift는 당장 reduce가 될 수 없을 때 stack에 임시 저장해놓는 행동이다.Action Select..

2025.11.20 - [컴파일러] - [컴파일러] 1. lexical analysis, scanner, regular expression [컴파일러] 1. lexical analysis, scanner, regular expression보통 우리가 코딩을 하면 어셈블리어로 컴파일되어 기계가 알아들을 수 있게 변환된 다음 코드가 실행된다. 이 과정에서 분명 사람은 거의 영어에 가까운 언어로 코딩을 하는데, 기계가 이걸 어april2901.tistory.com 이전 글에서 RE를 사용해 각 token의 pattern을 만드는 것까지 알아봤었다.이번에는 이 pattern들을 인식하는 법을 알아보자.Finite State Automata(FSA)먼저 Finite State Automata(FSA)라는 개념에..