다음 문맥무관문법(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 로 적은 조합은 우파스를 좌파스 자리에 둔 것이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 프로그래밍언어론] 13년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 프로그래밍언어론 기출문제 암기장 전체 보기