공식 문법에서 문장을 어떻게 생성합니까?

StackOverflow https://stackoverflow.com/questions/603687

문제

문법에서 문장을 생성하는 일반적인 방법은 무엇입니까?

나는 파서와 반대되는 알고리즘을 원합니다.즉, 문맥 자유 형식 문법(예: LL)이 주어지면 해당 문법에 맞는 임의의 문장을 생성하고 싶습니다.나는 사용한다 문장 여기서는 유효한 텍스트 본문을 의미하므로 실제로 전체 프로그램이 될 수 있습니다(문법상 정확하다면 말이 안 되더라도).

예제 문법:

program   : <imports> NEWLINE? <namespace>
imports   : ("import" <identifier> NEWLINE)* 
namespace : "namespace " <identifier> NEWLINE "{" <classes> "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)*
...

생성된 예시 프로그램:

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}
도움이 되었습니까?

해결책

이 작업을 수행하기위한 "일반적인"알고리즘이 있다는 것을 모르겠습니다. 무작위 프로그램 생성은 유전자 프로그래밍에 사용되므로 문법 기반 GP 시스템을 찾고 프로그램 생성을 어떻게 처리하는지 확인할 수 있습니다. 의사 코드와 같은 재귀 규칙 생성 알고리즘을 수행합니다.

void GenerateRule(someRule)
{
  foreach (part in someRule.Parts)
  {
    if (part.IsLiteral) OutputLiteral(part);
    if (part.IsIdentifier) Output(GenerateIdentifier(part)));
    if (part.IsRule) GenerateRule(part.Rule);
  }
}

이것은 모든 부품에서 일부 데이터 구조로 읽은 것으로 가정합니다. 또한 반복을 처리해야합니다 (발생하는 횟수를 무작위로 생성) 및 선택 규칙 (동전이 있는지 확인하여 존재하는지 확인).

편집 : 아, 규칙에 둘 이상의 옵션이 있다면, 당신은 함께 갈 옵션 중 하나를 선택하고 같은 방식으로 처리합니다. 따라서 일부 규칙이 (문자 적 | 변수) 인 경우 두 가지 중에서 무작위로 선택합니다.

다른 팁

다음은 Python 예제를 사용하는 것입니다. NLTK:

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

이 예는 책.생성된 문장은 구문론적으로 정확하지만 여전히 완전히 횡설수설합니다.

솔루션은 문법의 유도 구조를 따라야합니다. 다음 각각에 대해 무작위 발언을 어떻게 생성합니까?

  • 말단 기호
  • 비 말단 기호
  • 오른쪽 순서
  • 오른쪽의 선택
  • 오른쪽의 별 폐쇄

문법을 나타내는 데 사용하는 데이터 구조를 기록하면 이렇게하면 훨씬 더 명확 해집니다. 상호 재귀 생성기 기능 세트의 구조는 데이터 구조를 매우 밀접하게 반영합니다.

무한 재귀를 다루는 것은 약간의 사악입니다. 가장 쉬운 방법은 발화 스트림을 생성하고 깊이 컷오프를 유지하는 것입니다. 또는 Haskell과 같은 게으른 언어를 사용하는 경우 생성 할 수 있습니다. 모두 당신이 좋아하는 것만 큼 많은 유한 한 사람들 (원래 질문보다 까다로운 문제이지만 매우 재미있는 발언).

내 머리 꼭대기에서 :

나는 재귀 적으로 일하고 있습니다 (기본적으로 재귀 적 괜찮은 파서의 반대) 범위로 무엇을 해야하는지에 대한 일부 휴리스틱을 사용합니다.(...): 아마도 무작위로 선택) 옵션 (?: 보다 [], 아래), 반복 ( ''포아송 배포?). 리터럴 ("...")은 출력에 대해 간단하며 서브 톨렌 (`<...> ')은 재귀를 생성합니다.

일종의 완전한 커버리지를 보장하지 않는 한 너무 어렵지 않아야합니다. 그럼에도 불구하고, 그냥 생성합니다 다발 데이터의 도움이 될 것입니다 ...

*] 규칙을 처리 할 때 무한 회귀를 방지하기 위해 시간의 50% 미만의 옵션을 포함시켜야합니다.

 nonterm:  otherstuff <nonterm>?

잘 잡힌다 주각.

반복과 마찬가지로 강력하게 수렴하는 분포를 던지십시오.

입력 문법이 여기와 같이 BNF 형태로 제공되면 먼저 구문 분석해야합니다. 가장 간단한 일은 매핑을 사용하는 것입니다 (name, string), 그런 다음 최고 수준의 토큰으로 시작하십시오 (첫 번째 토큰을 의미 할 수 있습니다 ...).

이것은 당신에게 제공합니다 :

( "프로그램", "u003Cimports> Newline?u003Cnamespace> ")

( "수입", ( "가져 오기"u003Cidentifier> Newline)*)

...

당신은 "프로그램"으로 시작하여 히트 "로 시작합니다.u003Cimports> "그래서 당신은 되풀이되면 ..."Newline? "u003Cnamespace> "너무 재발 ... 돌아 왔을 때 당신은 끝났습니다.

나는 이것이 전에 이루어진 내 자신의 의심을 느낀다. 출력이 필요한 경우 웹을 검색 할 것입니다 ... 아마도 http://portal.acm.org/citation.cfm?doid=966137.966142, 수많은 파서 생성기가 검색 공간을 혼란스럽게하지만 ... 시도해보십시오. 이 종이, 도.

BTW-- 지역 대학에는이 저널에 온라인 구독이있을 것이므로 도서관에서 연결하여 무료로받을 수 있습니다.

당신이 가질 문제는 그래프의 재귀 적 특성이 무한 크기의 올바른 문법을 생성 할 수 있다는 것입니다. 당신은 아마도 당신이 그 노드에 몇 번이나 닿을 수있는 횟수에 대한 수와 한계를 가진 노드 유형의 해시를 설정하는 것과 같은 일을하고 싶을 것입니다. 그런 다음 먼저 심장의 내용을 검색하십시오.

첫 번째 제안은 폭이 큰 첫 번째 검색 일 것입니다. 규칙 그래프를 설정하고이를 통해 검색하십시오. 당신은 가능한 가장 작은 프로그램에서 시작하여 천천히 점점 더 커지는 프로그램을 뱉어 내기 시작할 것입니다. 그러나 문법이 주어진 수의 규칙에 대해 기하 급수적으로 더 많은 프로그램을 뱉어 내고 DFS를 사용하는 프로그램에서 30 개 정도의 토큰을 얻지 못할 것입니다.

깊이의 첫 번째 검색의 문제점은 두 번째로 왼쪽 수반 규칙이있을 때 검색이 무한 루프에 갇히게된다는 것입니다.

또 다른 큰 문제는 구문 적으로 올바른 프로그램이 의미 적으로 올바른 프로그램에서 먼 길이라는 것입니다. 후자의 유형을 생성하는 것은 가장 기본적인 경우를 제외하고는 완전히 불가능할 수 있습니다.

평소와 같이, 나는 바퀴를 재창조하는 것에 대해 조언 할 것입니다. Arm Assembler를 위해이 중 하나를 썼지 만 후회하는 것으로 기록되어 있습니다 (소프트웨어 : 연습과 경험 2007 년 4 월) :

“돌이켜 보면, 상용 표현식 생성기는 비교를위한 랜덤 암 어셈블리 지침을 생성하는 데 사용되어야합니다. 대신 Perl 스크립트가 점진적으로 구축되어 각 ARM 명령 정의를 취하고 인스턴스를 생성했습니다. 그러나 점진적인 사내 접근법의 장점은 간단한 대체가 간단한 버그를 감지했으며 버그 사냥이 점진적으로 진행될 수 있다는 것입니다.”

나는 내가 내 마음을 바꾸게 한 것을 기억하지 못하고 그것이 당신의 특정 요구와 관련이 있을지 의심하지만, 기존의 솔루션을 더 열심히 보는 것이 좋습니다. 이와 같은 것들을 직접 작성하는 데 징계가 덜 필요하지만 항상 예상보다 오래 걸립니다.

답은 아니지만 문법 생성에서 Wikipedia 항목을 확인하십시오.http://en.wikipedia.org/wiki/context-free_grammar_generation_algorithms

사용 된 몇 가지 일반적인 알고리즘을 설명했습니다.

아이디어는 훌륭하지만 (이전에 여러 번 생각했지만) 현실은 일부 샘플 데이터 및/또는 수많은 생성기 제약 조건/노력 한도가 없으면 상당히 큰 일이라는 것입니다.

손으로 샘플을 쓰는 것이 더 쉽게 찾을 수 있습니다. :)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top