막시말 뭉치

Maximal munch

컴퓨터 프로그래밍과 컴퓨터 과학에서, "최대의 일치" 또는 "가장 긴 일치"는 어떤 구성을 만들 때, 가능한 많은 가용 입력물을 소비해야 한다는 원칙이다.

이 용어의 가장 먼저 알려진 용어는 컴파일러용 코드 생성기의 자동 파생에 관한 박사 논문에서[1] R.G. Cattell에 의해 사용된다.

적용

예를 들어, 많은 프로그래밍 언어의 어휘 구문은 토큰을 입력 스트림에서 가능한 최대 문자 수에서 빌드할 것을 요구한다.이는 다음과 같이 일반적으로 사용되는 정규 표현에서 내재된 애매성 문제를 해결하기 위해 행해진다.[a-z]+(하나 이상의 소문자).[2]

이 용어는 또한 중간 언어로 프로그램을 나타내는 구조화 트리를 어떻게 선형 기계 코드로 변환해야 하는지를 결정하는 "타일링" 방법을 설명하기 위해 지침 선택 단계의 컴파일러에서도 사용된다.전체 하위 트리는 하나의 기계 명령으로 변환될 수 있으며, 문제는 어떻게 트리를 각각 하나의 기계 명령을 나타내는 겹치지 않는 "타일"로 분할하는가에 있다.효과적인 전략은 단순히 주어진 지점에서 가장 큰 하위 트리의 타일을 만드는 것인데, 이것을 "맥시멀 뭉치"[3]라고 한다.

단점

어떤 상황에서는 "최대 씹기"가 바람직하지 않거나 비양심적인 결과로 이어진다.예를 들어, C 프로그래밍 언어에서 문x=y/*z;(공백 없이) 는 아마도 구문 오류로 이어질 것이다./*문자 시퀀스는 종료되지 않았거나 종료 토큰에 의해 종료된 주석을 시작함*/일부 후자의 관련 없는 실제 의견(C의 설명은 내포되지 않음)그 진술에서 실제로 의미하는 것은 변수에 할당하는 것이었다.x값을 나눈 결과y비참조 포인터로 얻은 값 z; 이것은 완벽히 유효한 코드일 것이다(매우 흔하지는 않지만).공백을 사용하거나, 공백을 사용하여 표시할 수 있다.x=y/(*z);.

C++의 다른 예에서는 "각도 괄호" 문자를 사용한다.<그리고>템플릿 전문화를 위한 구문(연속 2개)>문자는 오른쪽 시프트 연산자로 해석된다.>>.[4] C++11 이전에 다음 코드에서 구문 분석 오류가 발생할 수 있는데, 이는 두 개의 오른쪽 각도-브래킷 토큰 대신 오른쪽 이동 연산자 토큰이 발생하기 때문이다.

    찌꺼기::벡터<찌꺼기::벡터<인트로>> my_mat_11; //C++03에서 잘못 수정, C++11에서 수정.     찌꺼기::벡터<찌꺼기::벡터<인트로> > my_mat_03; //C++03 또는 C++11에서 수정.

2011년 8월에 채택된 C++11 표준은 문법을 개정하여 오른쪽 교대 토큰이 한 쌍의 직각괄호(자바에서와 같이)와 동의어로 받아들여지도록 했는데, 문법은 복잡하지만 최대 문법 원리는 계속 사용할 수 있게 되었다.

대안

프로그래밍 언어 연구자들 또한 최대 뭉치의 원리를 다른 어휘적 해소 전술로 대체하거나 보완하는 방식으로 대응해왔다.한 가지 접근방식은 "제한을 따르는 것"을 활용하는 것인데, 가장 긴 경기를 직접 치르는 대신에 어떤 캐릭터가 유효한 경기를 따를 수 있는지에 대해 약간의 제한을 가할 것이다.예를 들어, 문자열이 일치하도록 규정하는 경우[a-z]+알파벳 문자는 그 규칙적인 표현으로 최대의 뭉침과 같은 효과를 얻을 수 없다.([5]정칙적인 표현 맥락에서 최대 뭉침 원리를 탐욕이라고 하며 게으름과 대비한다.)또 다른 접근방법은 최대 뭉치의 원리는 유지하되, 문맥과 같은 일부 다른 원리에 종속되게 하는 것이다(예: 자바에서 오른쪽 시프트 토큰은 구문적으로 무효인 제네릭 표현식의 맥락에서 일치하지 않을 것이다).[6]

참조

  1. ^ Cattell, R. G. G. "코드 생성기의 공식화 및 자동 파생"박사학위 논문, 1978년.미국 펜실베이니아 주 피츠버그의 카네기 멜론 대학교
  2. ^ 아호 외, 168세
  3. ^ 470페이지.
  4. ^ 반데보오르드
  5. ^ Van Den Brand 외, 26세.
  6. ^ 밴 와이크 외, 63세

참고 문헌 목록

  • Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2007). Compilers: Principles, Techniques & Tools (2nd ed.). Boston: Addison-Wesley. ISBN 978-0-321-48681-3.
  • Page, Daniel (2009). "Compilers". Practical Introduction to Computer Architecture. Texts in Computer Science. London: Springer. pp. 451–493. doi:10.1007/978-1-84882-256-6_11. ISBN 978-1-84882-255-9.
  • Van den Brand, Mark G.J.; Scheerder, Jeroen; Vinju, Jurgen J.; Visser, Eelco (2002). Disambiguation Filters for Scannerless Generalized LR Parsers. Lecture Notes in Computer Science. Vol. 2304/2002. Berlin/Heidelberg: Springer. pp. 21–44. doi:10.1007/3-540-45937-5_12. ISBN 978-3-540-43369-9. ISSN 0302-9743.
  • Vandevoorde, Daveed (14 January 2005). "Right Angle Brackets". Retrieved 31 March 2010.
  • Van Wyk, Eric; Schwerdfeger, August (2007). Context-Aware Scanning for Parsing Extensible Languages. GPCE '07: Proceedings of the 6th International Conference on Generative Programming and Component Engineering. New York: ACM. pp. 63–72. doi:10.1145/1289971.1289983. ISBN 9781595938558.