다음 문맥무관문법(context-free grammar)에서 문장 a*… | [7급 국가직 프로그래밍언어론] 13년 1회차 기출문제 상세 페이지
1[7급 국가직 프로그래밍언어론] 13년 1회차
다음 문맥무관문법(context-free grammar)에서 문장 a*(a+a)의 좌파스(left parse)와 우파스(right parse)로 옳은 것은?1. E → E + T좌파스 우파스
2. E → E * T
3. E → T
4. T → ( E )
5. T → a
1
2 3 5 4 1 3 5 5 2 4 1 5 3 5 3 5
2
2 3 5 4 1 3 5 5 5 3 5 3 5 1 4 2
3
2 4 1 5 3 5 3 5 2 3 5 4 1 3 5 5
4
5 3 5 3 5 1 4 2 2 3 5 4 1 3 5 5
해설
좌파스는 2 3 5 4 1 3 5 5, 우파스는 5 3 5 3 5 1 4 2이다.
좌파스는 좌단 유도에 쓴 규칙의 순서다. E ⇒ E*T(2) ⇒ T*T(3) ⇒ a*T(5) ⇒ a*(E)(4) ⇒ a*(E+T)(1) ⇒ a*(T+T)(3) ⇒ a*(a+T)(5) ⇒ a*(a+a)(5)
우파스는 우단 유도 규칙 순서의 역순이다. E ⇒ E*T(2) ⇒ E*(E)(4) ⇒ E*(E+T)(1) ⇒ E*(E+a)(5) ⇒ E*(T+a)(3) ⇒ E*(a+a)(5) ⇒ T*(a+a)(3) ⇒ a*(a+a)(5) 이므로 이를 뒤집어 5 3 5 3 5 1 4 2 가 된다.
- 우파스를 2 4 1 5 3 5 3 5 로 적은 조합은 우단 유도 순서를 뒤집지 않은 것이다.
- 좌파스를 2 4 1 5 3 5 3 5 로 적은 조합은 좌단이 아닌 우단 유도 순서를 쓴 것이다.
- 좌파스를 5 3 5 3 5 1 4 2 로 적은 조합은 우파스를 좌파스 자리에 둔 것이다.
오류나 개정된 내용이 보이면 알려주세요