렉서 해킹

Lexer hack

컴퓨터 프로그래밍에서, 참조 문법이 문맥에 민감하기 때문에, 렉서 해킹은 ANSI C를 해석하는 문제에 대한 일반적인 해결책이다.C에서 일련의 문자를 변수 이름 또는 유형 이름으로 분류하려면 구문 구조의 컨텍스트 정보가 필요하며, 이로 인해 컨텍스트가 없는 렉서를 가질 수 없습니다.

문제

문제는 다음 코드에서는 의 어휘 클래스가A자세한 컨텍스트 정보가 없으면 판별할 수 없습니다.

(A)*B

이 코드는 두 변수의 곱셈일 수 있으며, 이 경우A변수는 다음과 같습니다.

A * B

또는, 이 값은 다음 값보다 낮은 값일 수 있습니다.B타입에 맞게A이 경우A는 typedef 이름입니다.구체적으로 기재되어 있습니다.

(A) (*B)

더 자세히 말하면, 컴파일러에서, 렉서는 소스 코드를 프로그램으로 변환하는 초기 단계 중 하나를 수행합니다.텍스트를 검색하여 단어, 숫자 및 문자열과 같은 의미 있는 토큰을 추출합니다.파서는 토큰의 시퀀스를 루프나 변수 선언 등의 언어 구조를 나타내는 구문 규칙과 대조하려고 합니다.여기서 문제가 발생하는 것은 토큰 시퀀스가 여러 구문 규칙과 모호하게 일치할 수 있는 경우입니다.

이 모호성은 렉서가 변수 [1]식별자와 typedef 식별자를 구분하지 않으면 C에서 발생할 수 있습니다.예를 들어, C 식에서 다음과 같이 입력합니다.

(A) * B

렉서는 다음 토큰을 찾을 수 있습니다.

  1. 왼쪽 괄호
  2. 식별자 'A'
  3. 오른쪽 괄호
  4. 연산자 '*'
  5. 식별자 'B'

문제는 A의 어휘 클래스는 더 이상의 컨텍스트가 없으면 판별할 수 없다는 것입니다.파서는 이를 변수A에 B를 곱한 것으로 해석하거나 타입A에 B의 참조되지 않은 값을 캐스팅한 것으로 해석할 수 있습니다.이것은 문제가 있는 프로덕션 [2]규칙의 이름 때문에 "typedef-name: identifier" 문제로 알려져 있습니다.

해킹 솔루션

솔루션은 일반적으로 의미 기호 표의 정보를 다시 렉서에 공급하는 것으로 구성됩니다.즉, 렉서에서 파서로 가는 순수한 단방향 파이프라인으로 기능하는 것이 아니라 의미 분석에서 렉서로 돌아가는 백채널이 존재한다.이러한 해석과 의미 분석의 혼합은 일반적으로 부적절하다고 간주되며, 이것이 "핵"이라고 불리는 이유입니다.

컨텍스트가 추가되지 않으면 모든 식별자의 형식이 동일하기 때문에 렉서는 유형 식별자를 다른 식별자와 구별할 수 없습니다.위의 예에서 해킹을 사용하면 렉서가 식별자 A를 발견하면 토큰을 유형 식별자로 분류할 수 있어야 합니다.언어 규칙은 타입캐스트에 타입 식별자가 필요하며 모호성이 사라지도록 지정함으로써 명확해집니다.

이 문제는 C++에서도 발생하며 파서는 동일한 해킹을 [1]사용할 수 있습니다.

대체 솔루션

이 문제는 렉서리스 해석 기술을 사용할 때 발생하지 않습니다(따라서 해결하기 위해 "해킹"을 필요로 하지 않습니다).이것은 본질적으로 문맥적인 것이기 때문입니다.그러나 이것들은 파이프라인에 [citation needed]동시 렉서 및 파서를 갖는 모듈성이 부족하기 때문에 일반적으로 덜 우아한 디자인으로 여겨진다.

byacc에서 파생된 BtYacc("Backtracking Yacc")와 같은 일부 파서 생성기에서는 생성된 파서가 토큰의 해석을 여러 번 시도할 수 있습니다.여기서 설명하는 문제에서는 ID에 대한 의미정보로 인해 시도가 실패하면 역추적하여 다른 [3]규칙을 시도할 수 있습니다.

Clang 파서는 완전히 다른 방식으로 상황을 처리합니다. 즉, 참조되지 않는 어휘 문법을 사용합니다.Clang의 렉서는 유형 이름과 변수 이름을 구분하지 않습니다. 현재 토큰을 식별자로 보고할 뿐입니다.그런 다음 파서는 Clang의 의미 분석 라이브러리를 사용하여 식별자의 특성을 판단합니다.이것에 의해, 렉서나 파서의 염려와 캡슐화가 한층 더 깔끔하게 분리되고 있기 때문에, 일부 컴파일러 개발자는,[4] 렉서 해크보다 훨씬 우아한 솔루션으로 간주하고 있습니다.이것은 또한 대부분의 다른 현대 언어에서 사용되는 접근법이며, 어휘 문법에서 다른 종류의 식별자를 구별하지 않고, 충분한 정보를 이용할 [example needed]수 있을 때 구문 분석 또는 의미 분석 단계로 미루게 된다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b Roskind, James A. (1991-07-11). "A YACC-able C++ 2.1 GRAMMAR, AND THE RESULTING AMBIGUITIES". Archived from the original on 2007-06-22. Retrieved 2008-11-27.
  2. ^ Bendersky, Eli (2007-11-24). "The context sensitivity of C's grammar".
  3. ^ "BtYacc 3.0". 크리스 도드와 바딤 마슬로프가 수정한 버클리 야크를 기반으로 합니다.
  4. ^ Bendersky, Eli. "How Clang handles the type / variable name ambiguity of C/C++".

인용문