CFG에서 생성 할 때 유효한 다음 터미널 집합 확인

Question

문맥 자유 문법에서 임의의 문장을 생성하려고합니다. 각 단계에서 생성 될 다음 비단 말은이 질문과 관련없는 일부 확률 적 기준에 따라 결정됩니다. 내가 갇혀있는 곳에서, 문법과 지금까지 생성 된 부분 문장이 주어지면 문법에 따라 다음 단계에서 생성 될 수있는 비단 말 집합을 어떻게 결정할 수 있습니까?

다음은 BNF 및 부분 생성의 예제 문법입니다. 세웠 죠

<expr> ::= <term> "+" <expr> | <term> 
<term> ::= <term> "*" <factor> | <factor> 
<factor> ::= "(" <expr> ")" | <const> 
<const> ::= "0" | "1" | "2" | "3" | "4" 

지금까지 시퀀스를 생성 : (1 +. 이 경우 생성 될 다음 토큰이 집합 {"(", "0", "1", "2", "3", "4"}에서 나와야한다는 것을 쉽게 알 수 있습니다.

일반 문법 및 부분 생성을 고려하여이 집합을 결정하거나 각 단계에서이 집합을 사용할 수 있도록 문장을 생성하는 알고리즘이 있습니까?

Answer 1

문장을 생성하는 일반적인 방법은 시작 기호로 시작한 다음이 대답과 완전히 관련이없는 샘플링 기준을 사용하여 첫 번째 (또는 마지막) 비단 말을 반복적으로 프로덕션 중 하나로 대체하는 것입니다.

문법이 왼쪽에서 오른쪽으로 해석 가능한 경우 접두사를 구문 분석 한 다음 오류가없는 작업이있는 터미널 중 하나를 선택하기 만하면됩니다. 이를 위해서는 왼쪽에서 오른쪽으로 쓰는 알고리즘이 무엇이든 상관없이 구문 분석 테이블이 필요합니다. 알고리즘이 LALR (k) 인 경우 최종 결과를 초래하는 조치를 줄여야합니다. 이 시나리오를 피하려면 감소 작업을 선택하는 경우 해당 미리보기 기호에 커밋하지 마십시오. 교대를 할 때만 커밋하십시오. (그러나 줄이기 동작에 해당하는 미리보기는 무시할 수 없으므로 미리보기 심볼이 일관되게 선택되도록 전체 세트를 유지해야합니다.)