모호성

아래 세 개는 모두 같은 문법

 

각 규칙을 기반으로 a-b-c를 파싱하면 다음과 같다.

G1의 경우 a-b부터 시작할지 b-c부터 시작할지 모호해진다

그러므로 파싱 트리는 중요하다 semantic(의미)를 결정하니까

 

Operator

operand 개수에 따라

- unary : -1

- binary : 1+2

- ternary : a?b:c

 

위치에 따라

- infix : a+b

- prefix : +ab

- postfix : ab+

 

operator마다 parentheses를 기반으로

precedence level이 언어를 결정할 수 있지만

그래도 *이 +보다 먼저 계산되야하니까

규칙을 한 단계 내리면서 정할 수 있다

Associativity

- Left associative: left to right - ((a+b)+c)+d

- Right associative: right to left - a+(b+(c+d))

대부분의 operator는 left associative

 

//C
a<<b<<c //left
a=b=0 //right

//ML
3-2-1
1::2::nil (list builder)

//Fortran
a/b*c 
a**b**c (exponentiation)

 

위의 G6는 +, *은 왼쪽부터 계산해 나가야 함이 정의된 것

 

Ambiguity in Dangling Else

ex) if e1 then if e2 then s1 else s2

뒤쪽 else가 어느 if의 것인지 알기 어렵다

그래서 then 뒷를 <full-stmt>로 교체하였다.

 

파이썬은 이러한 문제점이 없다

들여쓰기로 구분하기 때문 + elif

C Java는 {}로 구분

Algol은 then 다음에 if를 허용하지 않아서 else는 가까운 if만 따라가면 되도록 함

 

Clutter

층위를 깊게 하니 non-terminal이 많아져서 떡져보인다

그래서 이에 대한 설명을 덧붙여서 모호성을 제거한다

아니면 EBNF를 사용해서 표현

convention 을 정의하면서 그 언어만의 context-free 문법이 다 다르니까 잘 읽어봐야 함

Abstract Syntax Tree

나머지 생략하고 terminal만 적어서 표현

 

용어와 내용 중요!

 

 

Developing Scanner

Scan: divide input into tokens

 = lexical analyzer

Developing Parser (중요)