S식

S-expression
S식을 나타내는 트리 데이터 구조(* 2 (+ 3 4))

컴퓨터 프로그래밍에서 S 표현식(또는 기호식, 약칭 sexpr 또는 sexp)은 중첩된 목록(트리 구조) 데이터에 대한 비슷한 이름의 표기법으로 표현된 표현입니다.S-표현식은 데이터뿐만 아니라 소스 코드를 위해 사용하는 프로그래밍 언어 Lisp에 의해 발명되고 대중화되었습니다.

Lisp의 일반적인 괄호화 구문에서, S-표현식은 고전적으로 다음과 같이[1] 정의됩니다.

  1. 형의 원자x, 아니면
  2. 형식의 표현(x . y)여기서 x와 y는 S식입니다.

이 정의는 LISP가 리스트를 일련의 "셀"(각각 순서쌍)로 표현한 것을 반영합니다.일반 목록에서 y는 다음 셀(있는 경우)을 가리키므로 목록을 구성합니다.정의의 재귀적 절은 이 표현과 S 표현 표기법 모두 임의의 이진 트리를 나타낼 수 있음을 의미합니다.그러나 표현은 원칙적으로 순환 참조를 허용할 수 있으며, 이 경우 구조는 트리가 아니라 순환 그래프이며, 교차 참조를 위한 규약이 제공되지 않는 한 고전적인 S 표현 표기법으로 표현할 수 없습니다(SQL 외래 키, SGML/XML IDREF 등과 유사).Common Lisp와[2] Scheme과[3] 같은 현대의 Lisp 방언은 데이텀 레이블을 통해 이러한 구문을 제공하며, 객체를 표시할 수 있으며, 다른 곳에서 중복된 구조가 아닌 공유된 구조를 나타낼 수 있으므로 리더나 프린터가 무한히 재발하지 않고 사이클의 평가 또는 표시를 트리거할 수 있습니다.

#n=(x y . #n#)

원자의 정의는 문맥에 따라 다릅니다. 존 매카시의 원래 정의에서,[1] "문자열과 숫자 문자의 부분 집합"으로 표현되는 "식별 가능한 원자 기호의 무한한 집합"이 존재한다고 가정했습니다.

대부분의 현대 성 표현은 더 일반적인 따옴표로 된 문자열(예: 구두점 또는 전체 유니코드 포함)을 허용하고, 2명 이상의 멤버를 가진 목록을 나타내기 위해 축약된 표기법을 사용합니다.

(x y z)

의 약자

(x . (y . (z . NIL)))

NIL는 특별한 목록 끝 개체입니다(대체로 쓰임).(), 이는 Scheme[4])의 유일한 표현입니다.

리스프 계열의 프로그래밍 언어에서 S 표현식은 소스 코드와 데이터를 모두 나타내는 데 사용됩니다.S 표현의 다른 용도는 DSSSL과 같은 리스프에서 파생된 언어와 IMAP 및 John McCarthy의 CBCL과 같은 통신 프로토콜에서 마크업으로 사용됩니다.WebAssembly의 텍스트 표현으로도 사용됩니다.구문 및 지원되는 데이터 유형에 대한 세부 정보는 언어마다 다르지만 이 언어들 중 가장 일반적인 특징은 S 표현식과 접두사 표기법을 사용하는 것입니다.

데이터 유형 및 구문

S 표현 형식에는 여러 가지 변형이 있으며 다양한 데이터 유형에 대해 다양한 구문을 지원합니다.가장 널리 지원되는 것은 다음과 같습니다.

  • 목록 및 쌍:(1 () (2 . 3) (4))
  • 기호:with-hyphen ?@!$ a symbol with spaces
  • 문자열:"Hello, world!"
  • 정수:-9876543210
  • 부동 소수점 번호:-0.0 6.28318 6.022e23

캐릭터를#는 구문의 확장자를 접두사로 사용하는 경우가 많습니다.#x1016진수 정수의 경우 또는#\C캐릭터용으로

리스프에서 사용

Lisp에서 소스 코드를 표현할 때 S 표현식의 첫 번째 요소는 일반적으로 연산자 또는 함수 이름이며 나머지 요소는 인수로 처리됩니다.이를 "prefix 표기법" 또는 "폴란드 표기법"이라고 합니다.예를 들어, C로 표기된 부울 식을 Lisp의 s-expr 기반 접두사 표기법과 같이 표현합니다.

위에서 언급한 바와 같이, "원자"의 정확한 정의는 LISP와 유사한 언어마다 다릅니다.따옴표가 붙은 문자열은 일반적으로 따옴표, 공백 문자, 괄호, 괄호, 대괄호, 백슬래시 및 세미콜론을 제외한 모든 문자열을 포함할 수 있습니다.두 경우 모두 일반적으로 금지된 문자는 이전 백슬래시와 함께 탈출하여 포함될 수 있습니다.유니코드 지원은 다양합니다.

s-expr 정의의 재귀적인 경우는 전통적으로 콘셀을 사용하여 구현됩니다.

S-표현식은 원래 M-표현식에 의해 조작되는 데이터만을 위한 것이었지만, Lisp의 첫 번째 구현은 M-표현식의 S-표현식 인코딩의 해석기였고, Lisp 프로그래머들은 곧 코드와 데이터 모두에 S-표현식을 사용하는 것에 익숙해졌습니다.이것은 리스프가 호모아이코닉하다는 것을 의미합니다. 즉, 프로그램의 주요 표현은 언어 자체의 원시적인 형태의 데이터 구조이기도 합니다.

데이터 S-식 예제

중첩된 목록은 S-식으로 쓸 수 있습니다.((milk juice) (honey marmalade))는 2요소 S표현식이며, 그 요소 또한 2요소 S표현식입니다.Lisp(및 이 기사)에서 사용되는 공백 구분 표기가 대표적입니다.줄 바꿈(새 줄 문자)은 일반적으로 구분자로 지정됩니다.

이것은 S 표현(Gazdar/Melish, Lisp의 자연어 처리)으로 쓰여진 영어의 작은 부분 집합을 위한 간단한 문맥 자유 문법입니다. 여기서 S=sentence, NP=noun 프레이즈, VP=verb 프레이즈, V=verb:

(((S) (NP 부사장))  ((부사장) (V))  ((부사장) (V NP))  ((V) 죽은)  ((V) 고용된)  ((NP) 간호사들)  ((NP) 환자)  ((NP) 메디센터)  ((NP) 닥터 챈))

소스 코드 S-식 예제

프로그램 코드는 보통 접두사 표기법을 사용하여 S 표현식으로 작성할 수 있습니다.

Common Lisp의 예:

(흥을 돋우는 요인 (x)    (한다면 (영점의 x)        1        (* x (요인 (- x 1)))))

S-식은 READ 기능을 사용하여 Lisp로 읽을 수 있습니다.READ는 S 식의 텍스트 표현을 읽고 Lisp 데이터를 반환합니다.PRINT 기능은 S 표현을 출력하는 데 사용할 수 있습니다.출력은 모든 인쇄 데이터 개체가 읽을 수 있는 표현을 가질 때 READ 기능으로 읽을 수 있습니다.Lisp에는 숫자, 문자열, 기호, 목록 및 기타 많은 데이터 유형에 대해 읽을 수 있는 표현이 있습니다.프로그램 코드는 PPRINT(참고: P 2개, 예쁜 인쇄의 줄임말) 기능을 사용하여 예쁘게 인쇄된 S 표현으로 포맷할 수 있습니다.

Lisp 프로그램은 유효한 S 표현이지만 모든 S 표현이 유효한 Lisp 프로그램은 아닙니다.(1.0 + 3.1)는 유효한 S 표현식이지만 유효한 Lisp 프로그램은 아닙니다. 왜냐하면 Lisp는 접두사 표기법을 사용하고 부동 소수점 번호(여기서 1.0)는 연산(식의 첫 번째 요소)으로 유효하지 않기 때문입니다.

S 식 앞에 따옴표 하나가 붙은 식(와 같이)'x, 인용된 S-식에 대한 통사적 설탕입니다. 이 경우에(quote x).

파싱

S 표현식은 종종 XML과 비교됩니다. 주요 차이점은 S 표현식이 점선 쌍이라는 한 가지 형태의 격납 형식만 가지고 있는 반면 XML 태그는 단순 속성, 다른 태그 또는 CDATA를 포함할 수 있으며 각각 다른 구문을 사용한다는 것입니다.단순한 사용 사례의 경우 S 표현이 XML보다 단순하지만 고급 사용 사례의 경우 XML에는 XML 데이터 처리를 단순화하기 위해 XPath라는 쿼리 언어와 많은 도구 및 타사 라이브러리가 있습니다.

표준화

일부 리스프 파생 프로그래밍 언어의 표준에는 S 표현 구문에 대한 사양이 포함되어 있습니다.여기에는 Common Lisp(ANSI 표준 문서 ANSI INTS 226-1994(R2004)), Scheme(R5RS 및 R6RS[5]) 및 ISLISP가 포함됩니다.

리베스트 변종

참고 항목: 표준 S-식

1997년 5월, Ron Rivest는 RFC로서 출판을 고려할 인터넷 초안을[6] 제출했습니다.이 초안은 Lisp S 표현식에 기반을 둔 구문을 정의했지만 특별히 프로그래밍을 위한 것이 아니라 범용 데이터 저장 및 교환(XML과 유사)을 위한 것이었습니다.RFC로 승인된 적은 없지만, 그 이후로 다른 RFC(예: RFC 2693) 및 여러 간행물에서 인용 및 사용되고 있습니다.[7]원래는 SPKI에서 사용하기 위한 것이었습니다.

Rivest의 형식은 S 표현식을 옥텟 문자열(바이트의 연속) 또는 다른 S 표현식의 유한한 목록으로 정의합니다.이 구조를 표현하기 위한 세 가지 교환 형식에 대해 설명하고 있습니다.하나는 "어드밴스드 트랜스포트(advanced transport)"인데, 형식 면에서 매우 유연하고, 구문적으로 리스프식 표현과 유사하지만 동일하지는 않습니다.예를 들어 고급 전송 기능을 사용하면 옥텟 문자열을 verbatim(문자열의 길이 뒤에 콜론과 전체 원시 문자열)으로 나타내거나, 이스케이프 문자, 16진수, Base64 또는 특정 조건을 충족하는 경우 "토큰"으로 직접 배치할 수 있습니다. (리베스트의 토큰은 리스프 토큰과 다릅니다.t는 편리함과 미학을 위해, 그리고 다른 문자열들과 똑같이 취급되는 반면 후자는 특정한 구문적 의미를 가지고 있습니다.)

리베스트의 초안은 "디지털 서명 목적으로" 표준 표현을 정의하고 있습니다.추상적인 S 표현을 위해 콤팩트하고 구문 분석이 용이하며 고유하게 설계되었습니다.버바텀 문자열만 허용하고 외부 문자열의 형식 지정은 금지합니다.마지막으로 "기본 전송 표현"이 있는데, 이는 표준 형태 또는 Base64와 동일하게 인코딩되고 가새로 둘러싸여 있으며, 후자는 간격을 변경할 수 있는 시스템에서 표준적으로 인코딩된 S-표현식을 안전하게 전송하기 위한 것입니다.80자 길이의 행이 있고 그 이상의 길이를 가지는 이메일 시스템).

이 형식은 SPKI 이외의 사용자(일부 사용자는 GnuPG, libgcrypt, Nettle, GNU lsh 등)에 널리 적용되지 않았습니다.Rivest의 S-expressions 웹 페이지는 파서 및 제너레이터(MIT 라이선스 하에서 사용 가능)에 대한 C 소스 코드를 제공하며, 이 코드는 다른 프로그램에 적용되고 내장될 수 있습니다.[8]또한 포맷을 독자적으로 구현하는 데에도 제약이 없습니다.

참고 항목

참고문헌

  1. ^ a b 존 매카시 (1960/2006).상징식의 재귀적 함수 웨이백 머신에서 2004-02-02 보관.ACM의 Communications에 게재되었습니다.
  2. ^ "Common Lisp HyperSpec: 22.4 - The Printer Dictionary: *PRINT-CIRCLE*". 2018-12-28.
  3. ^ "Revised7 Report on the Algorithmic Language Scheme: Section 2.4: Datum Labels" (PDF). 2013-07-06.
  4. ^ "Revised^5 Report on the Algorithmic Language Scheme". schemers.org.
  5. ^ Sperber, Michael; Dybvig, R. Kent; Flatt, Matthew; Van Straaten, Anton; Findler, Robby; Matthews, Jacob (Aug 12, 2009). "Revised6 Report on the Algorithmic Language Scheme". Journal of Functional Programming. 19 (S1): 1–301. CiteSeerX 10.1.1.372.373. doi:10.1017/S0956796809990074.
  6. ^ S-expressions, Network Working Group, 인터넷 초안, 1997년 11월 4일 만료 - R. Rivest, 1997년 5월 4일 초안-Rivest-exp-00.txt, Ronald L. Rivest, CSAIL MIT 웹사이트
  7. ^ revest sexp, Google Scholar (검색)
  8. ^ "SEXP (S-expressions)". people.csail.mit.edu.

외부 링크

  • sfexp는 GitHub의 C/C++를 위한 작고 빠른 S 표현 라이브러리입니다.
  • 레옹 보투의 미니리스프.
  • 로제타 코드의 S-표현식에는 독자와 작가가 여러 언어로 구현되어 있습니다.