본문 바로가기

23년 2학기 학교공부

 (82)
[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..
[SE] 클래스 모델링 📁 UML(Unified Modeling Language) 객체지향 소프트웨어를 모델링하기위한 표준 그래픽 언어를 말한다. – 1980년대 말과 1990년대 초반에 객체지향 개발 프로세스 등장함 – 방법론과 표기법의 확산은 상당한 혼란을 초래함 – Rumbaugh와 Booch는 1994년에 그들의 방법을 통합하기로 결정함 • 그들은 Rational Software Corporation에서 함께 일함 – 1995년에는 다른 방법론자인 Jacobson이 팀에 합류 • 그의 방법론은 유스케이스에 중점 – 1997년에 OMG (Object Management Group)는 UML 표준화 프로세스를 시작 📁 UML 다이어그램 1. 클래스 다이어그램(Class diagrams) : 클래스들과 그들의 관계를 기술 2..
[SE] 유스케이스 모델링 📁 유스케이스 유스케이스(use case)란 시스템이 액터(actor)에게 관찰 가능한 가치의 결과를 생산하기 위해 수행하는 일련의 행동 및 그 변형들의 집합을 말한다. 유스케이스는 완전한 기능을 명세해야하고, 이때 기능이란 시스템의 경계를 정의한다. 유스케이스는 프로세스를 묘사하는데, 이때 프로세스란 조직이나 액터에게 가치있는 것을 생산하기 위해 필요한 사건(events), 행동(actions) 및 거래(transactions)의 연속을 말한다. 예를 들면 계좌에서 현금을 인출하는것, 제품을 주문하는 것, 강좌를 등록하는 것이 있다. 시나리오 vs 유스케이스 시나리오는 특정한 목표를 달성하기 위해 수행되는 일련의 행동임에 반해, 유스케이스는 주어진 기능에 대해 가능한 모든 시나리오의 집합을 정의한다. ..
[SE] 요구사항 개발 및 정의 📁 요구사항 분석 과정 '어떻게' 보다는 '무엇을'에 관점을 두어야 한다. 📁 도메인 분석 도메인 분석은 소프트웨어 엔지니어가 문제를 더 잘 이해하기 위하여 도메인에 대해 알아가는 과정이다. 도메인이란, 소프트웨어를 사용할 것으로 예상되는 고객이 일하는 분야의 비즈니스나 기술을 칭한다. 도메인 전문가는 소프트웨어가 사용된 도메인 분야에 깊이 있는 지식을 가진 사람을 말하며, 대부분 사용자이자 고객이다. 도메인 분석을 사용하게 되면 얻을 수 있는 이점 - 빠른 개발 : 이해당사자들과 더욱 효과적으로 의사소통이 가능하고, 빠른 요구사항 파악이 가능하다. - 더 좋은 시스템 구축 가능 : 고객의 문제를 효과적으로 해결하는 솔루션을 결정할 수 있다. - 확장 예견 : 트렌드를 예측하는 능력을 갖추고, 적응도 높..

티스토리툴바