이 섹션에서는 일반적인 파서 기반 생성으로 초점을 이동하고 CFG로 제공되는 Python과 유사한 문법에 대한 간단한 연습부터 시작합니다.
암시적 CFG에 따라 Python과 유사한 구문을 생성하기 위해 결합될 수 있는 "d" 및 "ef"와 같은 문자열로 구성된 어휘를 고려하고 이러한 문자열이 알고리즘 1과 같은 프로세스에 따라 순차적으로 샘플링되고 연결된다고 가정합니다.
또한 문자열 "def"에 해당하고 간단한 정규식 def에 의해 제공되는 CFG의 터미널 기호 DEF를 고려하세요. 또한 정규식 [^\W\d]\w*(예: Python 식별자)로 제공되는 NAME 기호를 고려하세요. 우리는 Python 구문을 준수하는 방식으로 앞서 언급한 어휘에서 샘플링된 문자열을 순차적으로 구문 분석하려고 합니다.
예를 들어, 다음은 그러한 시퀀스 중 하나일 수 있습니다: ["d", "ef", " f", "oo(", "):", " ", "pass"]. 시퀀스의 모든 요소는 정의상 어휘 요소입니다. 시퀀스를 연결하면 함수를 정의하는 유효한 토큰 시퀀스인 "def foo(): pass"가 생성됩니다. 우리가 고려하고 있는 상황에서 우리는 특정 지점까지 모든 토큰을 관찰했지만 그 지점 이후의 토큰에 대해서는 아무것도 알지 못할 것입니다.
예를 들어, 예제 시퀀스의 세 번째 관찰에는 연결된 문자열 "def f"가 있습니다. 이 문자열을 lex/parse한다면 전통적인 접근 방식은 "f"를 완전한 NAME 토큰으로 잘못 식별하는 기호 시퀀스 DEF NAME을 반환합니다. 나머지 시퀀스에서 볼 수 있듯이 올바른 NAME 토큰은 "foo"입니다.
일반적으로 어휘에서 샘플링할 수 있는 다음 유효한 문자열은 다음 중 하나입니다.
현재 "f"로 시작하는 NAME을 계속 확장/전진합니다(예제의 전체 시퀀스처럼). 및/또는
"("로 시작하는 모든 항목, 즉 정규 표현식이 있는 LPAR 기호 (– 유효한 인수 서명을 지정합니다.
첫 번째 경우, "f"는 Python에서 부분적으로 일치하는 NAME 기호로 볼 수 있으며 정규 표현식이 [^\W\d]\w*라는 점을 기억하면 두 하위 패턴 모두와 일치한다고 말할 수 있습니다. (즉, [^\W\d] 및 \w*)를 정규식으로 사용합니다. FSM을 사용하면 FSM 상태를 통해 하위 패턴의 개념이 공식화됩니다. 이 경우 NAME에 대한 정규식은 0(즉 초기 상태 q0), 1(즉 [^\W\d]) 및 2(즉 \w*)의 세 가지 상태를 갖는 FSM M으로 표시될 수 있습니다. , 여기서 1, 2 ∈ F입니다.
알고리즘 3을 사용하면 "f"에 대한 FSM 상태 시퀀스 (0, 1), (1, 2), (2, 2)와 NAME 기호에 해당하는 FSM M을 얻을 수 있습니다. "f"에 대한 이러한 FSM 시퀀스는 이 어휘 문자열에 대해 상태 0, 1 또는 2에서 일치가 시작될 수 있고 상태 1 또는 2에서 끝날 수 있음을 알려줍니다.
위의 사례 1에 따르면 이전에 상태 1 또는 2에서 끝난 후 NAME 기호에 대한 구문 분석이 계속될 수 있습니다. 사례 2에 따르면 다음 문자열도 LPAR로 시작하거나 LPAR을 포함할 수 있으며 이는 M이 종료되었음을 암시합니다. , 이는 1과 2가 "f"를 읽은 후 구문 분석이 중지되는 M의 최종 상태임을 알 수 있습니다. M 종료는 또한 NAME 기호가 완료되었으며 LPAR을 허용하는 상태로의 전환이 문법에 의해 허용되었음을 나타냅니다.
이 그림에서 다음 유효한 어휘 문자열은 적어도 "d", "ef", "pass", " ", "oo("입니다. 왜냐하면 이러한 문자열은 모두 부분적으로 일치하는 NAME을 확장하고 마지막 문자열도 LPAR을 읽는 상태로 구문 분석 상태를 진행합니다. 우리가 고려한 어휘의 하위 집합에서 나머지 문자열 "):"은 잘못된 구문이 포함된 시퀀스가 됩니다.
FSM 인덱싱 접근 방식과 관련하여 이는 알고리즘 4가 FSM 상태 0, 1 및 2를 기호 NAME에 대한 하위 집합 "d", "ef", "pass", "", "oo(")에 매핑한다는 의미 FSM, M.
이 그림에서는 허용되는 문법 기호와 전환을 결정하는 기본 파서 상태가 생략되었습니다. 우리는 FSM 접근 방식을 확장하고 나머지 세부 사항을 해결하기 위한 수단으로 푸시다운 오토마타(PDA)를 사용합니다.
4.1 푸시다운 오토마타 공식화
우리는 다음 6-튜플 표현을 사용하여 푸시다운 오토마타를 정의합니다 [Sipser, 1996, 정의 2.13]:
PDA 기반 파서에 대한 인덱싱 접근 방식을 구성하려면 해당 PDA의 알파벳을 통한 CFG 기호 간의 연결과 PDA에서 읽은 기호를 생성하는 어휘 분석 및 스캐닝 단계를 사용해야 합니다.
보다 구체적으로, 파서는 섹션 4에서 암시적으로 설명했듯이 일련의 문자 입력에서 기호를 식별하는 어휘분석기 및 스캐너에 의해 지원됩니다. 허용되는 기호 및 스택 전환을 기반으로 각 구문 분석/PDA 상태에 대해 터미널 기호의 순서가 지정된 목록을 구성할 수 있습니다. 각 상태의 맵 δ로 이는 상태에서 읽은 터미널 기호에 해당하는 각 FSM의 통합인 각 구문 분석 상태에 대해 FSM을 구성할 수 있음을 의미합니다.
그런 다음 스캐닝 단계에서는 구문 분석 프로세스에서 마지막으로 완전히 식별된 기호 이후 읽은 문자에 대해 가능한 터미널 기호 V ⊂ Σ 세트를 식별합니다. 예를 들어, 섹션 4의 Pythonlike CFG에 대한 PDA의 초기 상태 q0에서 문자열 "de"를 스캔하고 렉싱하면 V = {DEF, NAME}이 됩니다. 즉 문자열 "def"를 완성하는 모든 어휘 문자열에 대해 DEF입니다. –다음에는 NAME FSM에서 읽지 않은 문자열(예: "def ") 및 해당 FSM에서 읽은 다른 문자열에 대한 NAME(예: "default")이 옵니다. 스캐너의 단계와 LLM의 샘플링 단계는 결국 단일 터미널 기호 v ∈ V가 결정될 때까지 세트 V를 감소시킵니다.
각 구문 분석 상태에 대해 결합된 FSM을 사용하여 V의 각 문자열에 알고리즘 3을 적용함으로써 PDA 상태, 해당 FSM 상태 및 잠재적 터미널 기호로 구성된 파서 구성을 결정할 수 있습니다.
알고리즘 3의 단계와 유사하게 PDA 상태 q ∈ Q 및 파서 구성의 터미널 기호 세트 V를 읽을 PDA 스택 값을 결정하기 위해 PDA 전환 맵의 사전 이미지를 사용할 수 있습니다.
이 맵에서 제공하는 스택 값은 가능한 파서 구성에서 시작하여 V의 각 문자열에 대한 성공적이고 완전한 구문 분석을 허용하는 PDA를 통해 경로(있는 경우)를 찾는 데 필요합니다. LALR(1) 파서의 REDUCE 작업에 해당하는 파서 상태 및 터미널 조합의 경우 이러한 파서 구성은 Γ의 스택 최상위 값 이상으로 구성됩니다. 이는 어휘 문자열에 수반되는 REDUCE 작업에 대한 모든 유효한 접두사에 해당하는 하위 스택으로 구성됩니다. 궁극적으로, 어휘 문자열의 완전한 구문 분석을 허용하는 각 파서 구성은 PDA용 색인의 항목으로 추가되며, 이 경우 색인은 파서의 구문에 대한 쿼리를 허용하기 위해 트리 데이터 구조여야 합니다. 가치를 쌓으세요.
이 문서는 CC 4.0 라이선스에 따라 있습니다.
L O A D I N G . . . comments & more!
About Author
Writings, Papers and Blogs on Text Models@textmodels
We publish the best academic papers on rule-based techniques, LLMs, & the generation of text that resembles human text.
