거기에 너무 많은 정보가 있지만 이건 정말 내게 멍청한 놈을 도움이되지 않습니다. 문맥없는 언어와 푸시 다운 자동화에 관한 많은 기사를 읽었습니다. 이제 특정 사물이 코드에서 어떻게 보일지 이해하려고합니다. 우리에게 다음과 같은 생성 규칙을주기CFG 제작 규칙은 코드에서 어떤 모습입니까?
L = {am bn | m >= n}
:
S -> B |^
B -> aBb | A
A -> aA | a
정확히 어떻게이 의사 코드에서처럼 보일 것이다
우리가 같은 언어를 정의 가정 수 있습니다? 나는 모든 생산 규칙이 S1으로 정의 된 1 개의 상태이거나 그것들 모두가 개별 상태라고 가정한다. 어쨌든 나는 모르고 누군가가 나를 어떻게 이해하는지 도울 수 있다면 좋을 것이다.
우리는 입력의 문자를 분석하고 입력에 따라 규칙 중 하나가 PDA 스택에 기호를 적용하는 것에 따라 적용된다는 것을 알고 있습니다.
CFG를 실제 구문 분석을 수행하는 코드 조각으로 변환하는 데는 여러 가지 방법이 있으며, 각각의 장단점이 있습니다.
CYK 알고리즘, Unger 알고리즘 및 Earley의 알고리즘과 같은 일부 알고리즘은 임의의 CFG와 문자열을 입력으로 받아 들일 수 있으며 동적 프로그래밍을 사용하여 해당 문자열에 대한 구문 분석 트리를 결정할 수 있습니다. 이러한 알고리즘의 작동은 문자를 한 번에 하나씩 처리하면서 값 표를 채워서 작동하므로 일반적인 푸시 다운 자동화와 유사하지 않습니다.
일부 구문 분석 알고리즘, 특히 LR (1) 및 일반 LR 파서 제품군은 파싱 스택을보다 직접적으로 유지 관리하고 유한 상태 컨트롤을 사용하여 파서를 구동합니다. LR (1) 파서는 모든 CFG를 처리 할 수는 없지만 결정 론적 CFG 만 처리 할 수는 있지만 GLR 파서와 같은 변형은 기본적으로 여러 스택을 병렬로 실행하여 모든 문법을 처리 할 수 있습니다. 컴파일러 생성 도구 인 bison과 yacc은이 패밀리에서 파서를 생성합니다. 입력 파일의 작동 방식을 살펴보면 CFG가 소프트웨어로 인코딩되는 방법을 알 수 있습니다.
LL (1) 파서와 간단한 역 추적 파서는 하향식으로 작동하며 일반적으로 스택 (종종 런타임 호출 스택)을 사용하여 입력 문자열을 구문 분석합니다. 그들은 모든 문법을 다룰 수는 없습니다. ANTLR 파서 생성기는이 패밀리에 파서를 생성합니다.
Packat 파서는 어떤 순서로 우선 순위를 지정하는지 수정 된 CFG를 사용하여 작동합니다. 이러한 파서를 사용하는 코드는 문법의 모양을 밀접하게 반영하는 경향이 있습니다. 파서 결합 자 (parser combinators)는 구문 분석 논리가 CFG와 매우 흡사하게 보이는 또 다른 현대 기술입니다.
컴파일러 과정을 수강하거나 Grune 및 Jacobs의 "Parsing Techniques : A Practical Guide"사본을 가져 오는 것이 좋습니다. 자세한 내용을 알고 싶다면이 안내서를 참조하십시오.
구체적으로 코드에서 수행하기를 원하십니까? 구체적으로 말하십시오. CFG는 언어를 기술합니다. 코드가 파스 트리를 출력하도록 하시겠습니까? 코드가 해당 언어의 문자열을 인식하도록 하시겠습니까? 또는 그들을 생성? 그것들을 생성한다면, 어떤 것들이 있습니까? 당신은 그들 모두를 생성 할 시간이 없다. – Patrick87
프로덕션 규칙은 m> n 인 문자열 만 생성하므로 평등이 불가능합니다. 패트릭 (Patrick)이 말했듯이 알고리즘을 원한다면 정확히 어떤 문제에 대해 지정해야한다. –
@PeterLeupold ok 오늘 내 질문을 업데이트하겠습니다. 당신 말이 맞아요, 많은 정보가 빠졌고 제 예를 편집 할 것입니다. – Asperger