아래의 과제는 공식 파서 이론에 익숙해야합니다. 용어의 의미를 모르기 때문에 질문의 내용을 모르는 경우 문맥없는 문법과 첫 번째 / 팔로우 세트는 많은 대학 과정에서 다룹니다.

이 Stanford 코스 , 특히 유인물 08 및 09 (7 페이지부터)를 추천 할 수 있습니다 . 나는 또한 이 유인물에서 치트 시트 를 추출 했습니다 . 이 도전을 시도하는 사람은 이것을 읽어 보는 것이 좋습니다 .

문맥이없는 문법이 주어지면 모든 비 터미널의 다음 세트를 찾는 프로그램이나 함수를 작성하십시오. 비공식적으로, 다음의 비 터미널 집합은 터미널과 $유효한 입력에서 터미널 뒤에서 찾을 수있는 입력 끝을 의미합니다.

입력은 인쇄 가능한 단일 ASCII 문자열 또는 인쇄 가능한 ASCII 행 배열로 제공됩니다. $입력의 끝을 나타 내기 위해 (리터럴 출력 또는 문자열을 문자열 등으로 사용하여) 적절한 형식으로 세트를 출력 할 수 있습니다 . 아래 형식에 따라 입력이 항상 유효하다고 가정 할 수 있습니다.

문맥 자유 문법은 매우 단순화 된 방식으로 제공됩니다. 모든 라인에는 단일 생산이 포함됩니다. 모든 프로덕션은 공백으로 구분 된 기호 목록입니다. 터미널은 아포스트로피 (예 :)로 묶인 문자열입니다 '**'. 간단히하기 위해 터미널에는 공백이 없다고 가정 할 수 있지만 프로그램에서 허용하면 좋을 것입니다. 비 터미널은 공백 또는를 포함하지 않는 문자열 일 수 있습니다 $. 빈 생산물 (일반적으로 ε로 표시됨)은 왼쪽 비 터미널 만 포함하는 선입니다. 첫 번째 줄은 시작 기호를 정의하는 프로덕션입니다.

예를 들어 다음 문법은 다음과 같습니다.

S → aSa | bSb | ε

다음과 같이 제공됩니다.

S 'a' S 'a'
S 'b' S 'b'
S

입력 / 출력 예 :

In:
S 'a' S 'a'
S 'b' S 'b'
S

Out:
S {'a', 'b', $}

In:
S A B C
A 'a'
A C 'b'
A
B C
B 'd' A
B
C 'e'
C 'f'

Out:
S {$}
A {'d', 'e', 'f'}
B {'e', 'f'}
C {'b', 'e', 'f', $}

In:
Start Alice Bob
Alice Charlie 'a'
Alice
Bob Bob 'a' Alice Charlie
Bob '!!!'
Charlie 'b'
Charlie

Out:
Start {$}
Alice {'a', '!!!', 'b', $}
Bob {'a', $}
Charlie {'a', $}

바이트 단위의 최단 코드가 이깁니다.

답변

perl -M5.010 follow.pl
E T e
e '+' T e
e
T F t
t '*' F t
t
F '(' E ')'
F 'id'
^D

F ')'
F #
t ')'
t #
T ')'
T #
F '+'
t '+'
T '+'
F '*'
e ')'
e #
E ')'
E #

#!/usr/bin/perl -0n
s/'.*?'/~$&/eg;s% (?=(\w.*\n))%$_.=">$1"%reg;/\s/;$_.=">$` #\n";s%^((\w+)\K ?\S*).*%$s{$1}++||"\$a.=s/ $2\\b/$&/rg"%eemgr,s%^(\w+ ).*?(\w+)$%"\$a.=s/>$1/>$2 /rg"%eermg,$_.=$a,s%>.*\xd8\K .*%%g,s%.+\n%$&x!/\n$&/g%eg until$$_++;s/\xd8.*?\xd8/~$&/eg;say/>(\w+ \W\S*\n)/g