구문 분석 : 주어진 문장이 문법규칙에 올바른지 아닌지를 검사하는 것. top-down 방식과 bottom-up 방식으로 나눠지는데 일반적으로는 비교적 문법의 제약이 없는 bottom-up 방식을 주로 사용
핸들(handle) : Bottom-up 구문분석에서 reduce 되는 부분
reduce : 유도과정을 거꾸로 적용한 것. 즉, S ‗⇒ αAw ‗⇒ αβ w의 유도과정이 존재할 때, 문장형태 αβw 에서 β를 A로 대체하는 것
shift : 입력기호를 스택에 넣는 것
follow : FOLLOW(A) ＝ {a ∈ VT ∪ {＄} | S ‗⇒ αAaβ, α, β ∈ V＊} 즉, 어떤 문장형태에 있어서, 논터미널 A 다음에 나타 나는 터미널 기호들의 집합. 여기서 $기호는 입력 문자열의 끝을 나타내는 기호
first : 문자열 α로부터 유도되어, 첫 번째로 나타날 수 있는 터미널기호들의 집합
내용 정리
구문분석 방법은 크게 Top-down 방법과 Bottom-up 방법의 두 종류로 나누어 볼 수 있다. Top-down방법은 시작기호로부터 시작하여 정의된 문법 의 규칙(rule)들을 적용하여 유도에 의한 주어진 문자열을 찾아가는 방법이 고, 반대로 Bottom-up 방법은 입력된 문자열에서 감축(reduce)에 의해 시 작기호를 찾아가는 방법이다.
Bottom-up 구문분석의 방법으로 스택과 입력 버퍼 등을 사용하는 Shift-reduce 구문분석이 있다. shift와 reduce를 사용하여 진행하는데 시작 기호가 나오면 올바른 문장으로 accept 된 것이다.
Shift-reduce 구문분석에서 shift 는 입력기호를 스택에 넣어주는 것이고 reduce 는 스택에 있는 입력기호를 가져와서 문법에 맞게 reduce 해주는 것을 의미한다.
Shift-reduce 구문분석에서 문법에 맞게 reduce 해주는 기호가 가장 중요한데 그 것을 e핸들(handle) 이라고 한다.
FOLLOW(A) 는 어떤 문장형태에 있어서, 논터미널 A 다음에 나타나는 터미널 기호들의 집합이다. FIRST(A)는 A로부터 유도되어 첫 번째로 나타날 수 있는 터미널기호들의 집합이다.
