프로그래밍 언어론 (구문트리)

작성일

모호성 해결

  1. 우선순위 부여 -> nonterminal 추가

  2. 결합법칙 -> 왼쪽 또는 오른쪽

구문트리 푸는 방법 정확히 알게 됌

(a+b)*c라고 한다면 a+b가 먼저 이루어져야 하므로 트리의 가장 하단부에 위치할 것이고 곱하기는 상단부에 위치할 것

추상구문트리 -> 기본적 비단말 기호 제거 + 괄호 같은 것들 불필요하니 제거 + 플러스 연산기호 같은 것들이 먼저 나오고 그 아래에 a와 b가 나오는 순서

EBNF

BNF + 메타심볼 -> 판독성 증가

BNF는 recursive한 표현이 어려움

메타기호 {} -> 임의 연속 처리 [] -> 선택적인 요소 선택 혹은 사용 안함 () -> 나열된 것 중 하나는 필히 사용

문법 cfg와 csg 비교

문맥자유문법(context-free) 문법

  • S-> aSb ab
  • L(S) = {a의n승 *b의 n승 >= 1}

문맥유관문법(context-sensitive) 문법

  • S -> abc aAbc
  • Ab -> bA
  • Ac -> Bbcc
  • bB -> Bb
  • aB -> aa aaA
  • L(s) = {a의 n승 * b의 n승 * c의 n승 >=1}

대표적 cfl과 csl (역순서 사례)

  • L1 = {wcw (오른쪽 w의 r승) w ∈ (a ∪ b)* }
    • ex) aabcbaa (가운데 기준 거울 대칭)
  • L2 = {wcw w ∈ (a ∪ b)* }
    • ex) aabc aab -> 앞 뒤 일치 x

참고자료

프로그래밍 언어 개념 - 원유헌 저

0%