컴퓨터 코드를 구문 분석하는 방법, 코드의 출현 3

나중에 Advent of Code 문제를 해결한 후 흥미로운 구문 분석 문제가 제시된 3일차를 다시 살펴보고 싶었습니다. 이 작업에는 시끄러운 입력에서 유효한 코드를 추출하는 작업이 포함되었으며, 이는 파서 및 어휘 분석기 개발에 있어 훌륭한 연습이었습니다. 이 과제에 대한 나의 접근 방식을 살펴보는 데 참여해 보세요.

Microsoft Copilot이 퍼즐(?)에 대한 애정을 표현하기 위해 생성한 이미지

처음으로 Ruler DSL에 대해 글을 썼을 때 구문 분석을 위해 Hy를 사용했습니다. 그러나 최근 생성 AI에 대한 탐구에서는 funcparserlib 라이브러리를 사용하여 생성된 코드라는 새로운 구문 분석 방법을 도입했습니다. 이번 Advent of Code 챌린지를 통해 funcparserlib의 복잡성을 깊이 파고들어 생성된 코드의 기능을 훨씬 더 잘 이해할 수 있었습니다.

Lexer 구현(어휘 분석)

손상된 입력을 처리하는 첫 번째 단계는 렉싱(또는 토큰화)입니다. lexer(또는 tokenizer)는 입력 문자열을 스캔하여 추가 처리를 위한 기본 구성 요소인 개별 토큰으로 나눕니다. 토큰은 유형별로 분류된 입력의 의미 있는 단위를 나타냅니다. 이 퍼즐에서는 다음 토큰 유형에 관심이 있습니다.

• 연산자(OP): mul, do, dont와 같은 함수 이름을 나타냅니다. 예를 들어, 입력 mul(2, 3)에는 연산자 토큰 mul이 포함되어 있습니다.
• 숫자: 숫자 값입니다. 예를 들어, 입력 mul(2, 3)에서 2와 3은 숫자 토큰으로 인식됩니다.
• 쉼표: 쉼표 문자(,)는 인수 사이의 구분 기호 역할을 합니다.
• 괄호: 여는(및 닫는) 괄호는 함수 호출의 구조를 정의합니다.
• 횡설수설: 이 카테고리에는 다른 토큰 유형과 일치하지 않는 모든 문자 또는 문자 시퀀스가 ​​포함됩니다. 입력의 "손상된" 부분이 들어오는 곳입니다. 예를 들어 %$#@ 또는 임의의 문자는 횡설수설로 간주됩니다.

funcparserlib는 튜토리얼에서 매직 문자열을 자주 사용하지만 저는 좀 더 구조화된 접근 방식을 선호합니다. 매직 문자열은 오타로 이어질 수 있으며 코드 리팩터링을 어렵게 만들 수 있습니다. 토큰 유형을 정의하기 위해 Enum을 사용하면 더 나은 가독성, 향상된 유지 관리 및 향상된 유형 안전성과 같은 여러 가지 이점을 얻을 수 있습니다. Enum을 사용하여 토큰 유형을 정의한 방법은 다음과 같습니다.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

Spec.OP, Spec.NUMBER 등을 사용하여 일반 문자열 사용과 관련된 모호성과 잠재적인 오류를 방지합니다.

Enum을 funcparserlib와 원활하게 통합하기 위해 TokenSpec_이라는 사용자 지정 데코레이터를 만들었습니다. 이 데코레이터는 funcparserlib의 원래 TokenSpec 함수에 대한 래퍼 역할을 합니다. Spec Enum의 값을 사양 인수로 허용하여 토큰 정의를 단순화합니다. 내부적으로는 열거형(spec.name)의 문자열 표현을 추출하고 이를 다른 인수와 함께 원래 TokenSpec 함수에 전달합니다.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

데코레이팅된 TokenSpec_ 함수를 사용하면 토크나이저를 정의할 수 있습니다. 우리는 funcparserlib의 make_tokenizer를 사용하여 TokenSpec_ 정의 목록을 가져오는 토크나이저를 생성합니다. 각 정의는 토큰 유형(Spec ENUM의)과 이에 일치하는 정규식을 지정합니다.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

OP 정규식은 교대(|)를 사용하여 다양한 함수 형식을 일치시킵니다. 구체적으로:

• mul(?=(d{1,3},d{1,3})): 쉼표로 구분된 두 개의 숫자가 포함된 괄호가 뒤에 오는 경우에만 mul과 일치합니다. 긍정적인 예측 어설션(?=...)은 괄호와 숫자가 존재하지만 일치 항목에서 사용되지 않도록 보장합니다.
• do(?=()): 뒤에 빈 괄호가 있는 경우에만 일치합니다.
• don't(?=()): 빈 괄호가 뒤에 오는 경우에만 일치하지 않습니다.

정규식의 그래프 표현

마지막으로 토큰화 기능은 토큰화 중에 GIBBERISH 토큰을 필터링하여 추가 처리를 위해 입력의 관련 부분에 집중합니다.

코드 해석 프로세스에는 일반적으로 어휘 분석(또는 어휘 분석)과 구문 분석이라는 두 가지 주요 단계가 포함됩니다. 우리는 이미 첫 번째 단계를 구현했습니다. 토큰화 함수는 어휘 분석기 역할을 하여 입력 문자열을 가져와 이를 일련의 토큰으로 변환합니다. 이러한 토큰은 파서가 코드의 구조와 의미를 이해하는 데 사용하는 기본 구성 요소입니다. 이제 파서가 이러한 토큰을 어떻게 사용하는지 살펴보겠습니다.

파서 구현

토큰화 함수에서 반환된 구문 분석된 토큰은 추가 처리를 위해 구문 분석기로 전송됩니다. Spec Enum과 tok 함수 사이의 간격을 메우기 위해 tok_이라는 데코레이터를 소개합니다.

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

예를 들어 Spec.NUMBER 토큰이 있는 경우 반환된 파서는 토큰을 수락하고 다음과 같은 값을 반환합니다.

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

반환된 값은 >> 연산자는 아래와 같습니다.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

일반적으로 잠재적인 보안 취약성을 방지하기 위해 알 수 없는 입력을 구문 분석할 때 ast.literal_eval을 사용하는 것이 가장 좋습니다. 그러나 이 특별한 코드 출현 퍼즐의 제약 조건, 특히 모든 숫자가 유효한 정수라는 제약으로 인해 문자열 표현을 정수로 변환하는 데 더 직접적이고 효율적인 int 함수를 사용할 수 있습니다.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

특정 토큰 시퀀스를 적용하고 이를 의미 있는 객체로 변환하는 구문 분석 규칙을 정의할 수 있습니다. 예를 들어, mul 함수 호출을 구문 분석하려면 왼쪽 괄호, 숫자, 쉼표, 다른 숫자, 오른쪽 괄호 순서가 필요합니다. 그런 다음 이 시퀀스를 Mul 객체로 변환합니다.

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

이 규칙은 필수 토큰(OP, LPAREN, COMMA, RPAREN)에 대한 tok_ 파서를 숫자 파서와 결합합니다. >> 그런 다음 연산자는 일치하는 시퀀스를 Mul 객체로 변환하여 인덱스 2와 4의 튜플 요소에서 두 숫자를 추출합니다.

동일한 원칙을 적용하여 해야 할 작업과 하지 말아야 할 작업에 대한 구문 분석 규칙을 정의할 수 있습니다. 이러한 작업은 인수(빈 괄호로 표시)를 사용하지 않으며 조건 개체로 변환됩니다.

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

do 규칙은 can_proceed = True인 조건 개체를 생성하는 반면, 하지 않음 규칙은 can_proceed = False인 조건 개체를 생성합니다.

마지막으로 | (또는) 연산자:

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

이 expr 파서는 입력을 각 규칙에 대해 차례로 일치시키려고 시도하여 첫 번째 성공적인 일치 결과를 반환합니다.

expr 파서는 mul(2,3), do() 및 don't()와 같은 완전한 표현식을 처리합니다. 그러나 입력에는 이러한 구조화된 표현식의 일부가 아닌 개별 토큰이 포함될 수도 있습니다. 이를 처리하기 위해 everything이라는 포괄적인 구문 분석기를 정의합니다.

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

이 파서는 | (또는) NUMBER, LPAREN, RPAREN 또는 COMMA 유형의 단일 토큰과 일치하는 연산자입니다. 이는 본질적으로 더 큰 표현의 일부가 아닌 떠돌이 토큰을 캡처하는 방법입니다.

모든 구성요소가 정의되었으므로 이제 완전한 프로그램을 구성하는 요소를 정의할 수 있습니다. 프로그램은 하나 이상의 "호출"로 구성됩니다. 여기서 "호출"은 잠재적으로 떠돌이 토큰으로 둘러싸인 표현입니다.

호출 파서는 이 구조를 처리합니다. 즉, 임의 개수의 떠돌이 토큰(many(everything)), 단일 표현식(expr), 임의 개수의 추가 이탈 토큰을 일치시킵니다. 그러면 Operator.itemgetter(1) 함수는 결과 시퀀스에서 일치하는 표현식을 추출합니다.

number = tok_(Spec.NUMBER) >> int

프로그램 파서로 표시되는 전체 프로그램은 0개 이상의 호출로 구성되므로 완성된 파서를 사용하여 전체 입력이 소비됩니다. 그런 다음 구문 분석된 결과는 표현식의 튜플로 변환됩니다.

from enum import Enum, auto

class Spec(Enum):
    OP = auto()
    NUMBER = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    GIBBERISH = auto()

마지막으로 이러한 모든 정의를 구문 분석 기능으로 그룹화합니다. 이 함수는 토큰 튜플을 입력으로 사용하고 구문 분석된 표현식 튜플을 반환합니다. 모든 파서는 전역 네임스페이스 오염을 방지하고 숫자 파서가 tok_ 함수에 의존하기 때문에 함수 본문 내에 정의됩니다.

from funcparserlib.lexer import TokenSpec

def TokenSpec_(spec: Spec, *args: Any, **kwargs: Any) -> TokenSpec:
    return TokenSpec(spec.name, *args, **kwargs)

퍼즐 풀기

파서를 사용하면 파트 1을 쉽게 해결할 수 있습니다. 모든 mul 연산을 찾고, 곱셈을 수행하고, 결과를 합산해야 합니다. Mul 표현식을 처리하는 평가 함수를 정의하는 것부터 시작합니다

from funcparserlib.lexer import make_tokenizer

def tokenize(input: str) -> tuple[Token, ...]:
    tokenizer = make_tokenizer(
        [
            TokenSpec_(
                Spec.OP, r"mul(?=\(\d{1,3},\d{1,3}\))|do(?=\(\))|don\'t(?=\(\))"
            ),
            TokenSpec_(Spec.NUMBER, r"\d{1,3}"),
            TokenSpec_(Spec.LPAREN, r"\("),
            TokenSpec_(Spec.RPAREN, r"\)"),
            TokenSpec_(Spec.COMMA, r","),
            TokenSpec_(Spec.GIBBERISH, r"[\s\S]"),
        ]
    )

    return tuple(
        token for token in tokenizer(input) if token.type != Spec.GIBBERISH.name
    )

1부 문제를 해결하기 위해 입력을 토큰화하고 구문 분석한 다음 방금 정의한 estimate_skip_condition 함수를 사용하여 최종 결과를 얻습니다.

from funcparserlib.parser import tok

def tok_(spec: Spec, *args: Any, **kwargs: Any) -> Parser[Token, str]:
    return tok(spec.name, *args, **kwargs)

2부에서는 '하지 않음' 조건이 발생한 경우 mul 작업 평가를 건너뛰어야 합니다. 이를 처리하기 위해 새로운 평가 함수인 estimate_with_condition을 정의합니다.

>>> from funcparserlib.lexer import Token
>>> number_parser = tok_(Spec.NUMBER)
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
'123'

이 함수는 사용자 정의 감속기 함수와 함께 축소를 사용하여 누계 및 부울 플래그(조건)를 유지합니다. 조건 플래그는 조건 표현식(실행 또는 수행하지 않음)이 발견되면 업데이트됩니다. Mul 표현식은 조건이 True인 경우에만 평가되어 합계에 추가됩니다.

이전 반복

처음에 나의 구문 분석 접근 방식에는 두 가지 별도의 단계가 포함되었습니다. 먼저 전체 입력 문자열을 토큰화하여 유형에 관계없이 모든 토큰을 수집합니다. 그런 다음 별도의 단계에서 특히 mul 작업을 식별하고 처리하기 위해 두 번째 토큰화 및 구문 분석을 수행합니다.

>>> from funcparserlib.lexer import Token
>>> from ast import literal_eval
>>> number_parser = tok_(Spec.NUMBER) >> literal_eval
>>> number_parser.parse([Token(Spec.NUMBER.name, '123'])
123

향상된 접근 방식은 단일 패스에서 토큰화 및 구문 분석을 수행하여 이러한 중복성을 제거합니다. 이제 mul, do, don't 및 기타 개별 토큰과 관련된 토큰을 포함하여 모든 토큰 유형을 처리하는 단일 파서가 있습니다.

number = tok_(Spec.NUMBER) >> int

다중 작업을 찾기 위해 입력을 다시 토큰화하는 대신 초기 토큰화 중에 식별된 토큰 유형을 활용합니다. 이제 구문 분석 기능은 이러한 토큰 유형을 사용하여 적절한 표현식 개체(Mul, Condition 등)를 직접 구성합니다. 이는 입력의 중복 스캔을 방지하고 효율성을 크게 향상시킵니다.

이번 주 Advent of Code에 대한 구문 분석 모험을 마무리합니다. 이 게시물을 작성하려면 상당한 시간이 필요했지만 어휘 분석 및 구문 분석에 대한 지식을 다시 살펴보고 확고히 하는 과정을 통해 가치 있는 노력을 할 수 있었습니다. 이것은 재미있고 통찰력 있는 퍼즐이었습니다. 앞으로 몇 주 안에 더 복잡한 문제를 해결하고 제가 배운 내용을 공유하고 싶습니다.

늘 그렇듯 읽어주셔서 감사드리며, 다음 주에 다시 글을 쓰도록 하겠습니다.

위 내용은 컴퓨터 코드를 구문 분석하는 방법, 코드의 출현 3의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!