1. Parse Tree
- 파스트리 : 앞에 프로그래밍 언어 설명에 잠깐 소개가 되었다.
- 간단히 파스트리의 특징에 대해서 알아보자
ⓐ 트리의 Leap에 속하는 것은 모두 사용자의 눈에 보이는 Terminal Symbol이다.
ⓑ Leap속성을 제외한 모든 노드는 Non-Terminal Symbol이다.
ⓒ 아래로 내려갈 수록 실행 순서가 빨라진다.
- 이러한 파스트리는 컴파일러가 컴파일시 작성을 하여, Leap노드의 원소를 보아서
ⓐ 모두 Terminal Symbol이다. 라면 문법이 성립
ⓑ Non-Terminal Symbol이 하나라도 있다. 라면 문법이 성립하지 않음
을 정한다.
2. Ambiguous(Ambiguity 애매 모호함)
- 어떠한 문법은 같은 형태의 식을 2가지 이상의 파스트리로 나타낼수 있을 수 있다.
> 이 경우를 모호한 상태. 라고 한다.
- 모호한 문법이 존재하면 컴파일러는 해당 문법에 대해서 작동하지 못한다.
> 기계란, 하나의 방법만을 가지고 반복 실행하는 것이 원칙
ex)
<expr> -> <expr>
<expr> -> <expr> <op> <expr> | const
<op> -> / | - 이 문법을 가지고 3-3/3을 표현해보아라.
다음 예를 한번더 보자.
ex) <stmt> -> if <expr> then <stmt> | if <expr> then <stmt> else <stmt>
이 문법을 가지고 다음을 표현해보아라.
if expr1 then if expr2 then s1 else s2
이 경우 또한 두가지의 parse트리로 표현이 가능하다.(문법성립X)
- 위의 두 예를 보았을때, Parse Tree가 2개 이상임을 보이면 그 언어가 모호함을 밝히는 것이다
- 즉 파스트리가 2개이상일때는 그 문법은 성립하지 않는다.
3. 모호함을 없에는 방법
- 모호함을 없에는 방법에는 2가지 방법이 있다. 일단, 수학적 연산일 경우를 살표본다.
- 수학적 연산인 경우 모호함을 없에는 순서
ⓐ 연산자 분석 - 우선순위로 배치(같은 우선순위는 같은 그룹)
ⓑ 각각의 그룹에 이름을 Non-terminal 심볼을 준다.
ⓒ 좌결합이냐, 우결합이냐에 대해서 생각하면서 문법을 형성해준다.
> 문법형성시 한단계 높은 우선순위를 가진 곳으로 갈수 있는 것도 만들어줘야한다.
> 또한 연산시 상위 연산의 non-terminal 신볼을 포함한다.
ex)
<expr> -> <expr>
<expr> -> <expr> <op> <expr> | const
<op> -> / | - 이 문법을 가지고 3-3/3을 표현해보아라.
이것을 일련의 순서를 가지고 표현해보겠다. 일단 수학적 연산에 따지면 '/'가 먼저나와야한다.
또한 자식으로 갈수록 먼저 실행되는 것에 따지면, 위의 예에서 나온 사진에서 파란 파스트리가 정답이된다.
ⓐ 연산자 분석 및 각 연산자에 non-terminal symbol주기
- : <expr>
/ : <term>
ⓑ 좌결합이냐 우결합이냐에 의거하여 문법을 재정립해준다.
<expr> -> <expr> - <term> | <term>
//연산시(expr-term)상위 연산자 포함. 또한 상위 연산자로 가는 길도 있음.
<term> -> <term> / const | const
문제의 해결!!
또 다른 예...
