일기:2024년 10월 6일

BNF

BNF로 람다 계산법을 표현할 수 있다니! 신기하고 아름답고(?) 재밌다.

\[ \begin{align} LcExp &::= Identifier\\ &::= (lambda\ (Identifier)\ LcExp)\\ &::= (LcExp\ LcExp) \end{align} \]

위에 적은 것은 BNF는 아니다. 위에 적은 것은 grammars라고 한다.¹

The Little ~er

이 문단에 제목이 “The Little ~er”과 비슷한 형식인 책의 목록을 정리한다.

• The Little LISPer
• The Little Schemer
• The Seasoned Schemer
• The Reasoned Schemer
• The Little Typer
• The Little Prover
• The Little Haskeller

문맥 자유 문법

아래와 같은 두갈래 나무(binary tree)²에서 노드는 비어 있거나, 정수 하나와 두갈래 나무 두 개를 포함한다.

\[ \begin{align} Binary{\text -}search{\text -}tree\ ::= ()\ |\ (Int\ Binary{\text -}search{\text -}tree\ Binary{\text -}search{\text -}tree) \end{align} \]

위 문법은 각 노드 구조를 정확하게 설명하지만 다음과 같은 두갈래 나무 특성은 표현하지 못한다.

• 왼쪽 자식 나무의 모든 키는 현재 노드의 키보다 작거나 같아야 한다.
• 오른쪽 자식 나무의 모든 키는 현재 노드의 키보다 크거나 같아야 한다.

이와 같이 특성(문맥)을 표현하지 못한 문법을 문맥 자유 문법(Context-free grammar, CFG)이라고 하는 것 같다.

한편 전공자는 위의 내 설명이 맞지 않다고 지적했다.

위키백과의 해당 문서에서는 문맥 자유 문법을 어려운 말로 설명했다.³

영문 위키백과에는 구체적인 정의가 잘 나온다.⁴

교재 Essentials of Programming Languages 10쪽에서는 다음과 같은 설명이 나온다.

These grammars are said to be context-free because a rule defining a given syntactic category may be applied in any context that makes reference to that syntactic category. … Because of this additional constraint, not every syntactic derivation from Binary-search-tree leads to a correct binary search tree. To determine whether a particular production can be applied in a particular syntactic derivation, we have to look at the context in which the production is applied. Such constraints are called context-sensitive constraints or invariants.