저는 현재 LL (1) 형식으로 논쟁 할 수 있기를 희망하는 BNF 문법을 사용하고 있습니다. 그러나, 나는 방금 변경을 끝내고 오늘 3 번째로 손으로 문법에 대한 새로운 FIRST와 FOLLOW 세트를 계산했고, 나는 그것에 지쳤다. 더 좋은 방법이 있어야합니다!FIRST 및 FOLLOW 세트를 자동으로 계산하기위한 유용한 도구는 무엇입니까?
누구나 문법이 주어지면 모든 비 단말기에 대해 첫 번째 및 팔로우 세트를 자동으로 계산하는 도구를 제안 할 수 있습니까?
1 년 전 제가 참석 한 대학에서 학기 프로젝트를 진행했습니다. 여기서 우리는 프로그래밍 언어를 작성해야했습니다. 그룹으로서 우리는 파서를 처음부터 손으로 쓸 수 있기를 원했기 때문에 그렇지 않으면 파서를 작성하는 것이 완전히 비현실적이었을 것이므로 LL (1) 문법을 목표로해야했습니다.
물론 우리 출발점은 LL (1)과 거리가 멀었습니다. 그래서 우리도 그것을 배치해야했습니다. 이를 위해 AtoCC 패키지의 kfgEdit 도구를 사용했습니다. 당신이하는 일은 당신의 규칙을 입력하는 것입니다, 그리고 그것은 그것이 LL (1) 문법인지를 한 번의 클릭으로 확인할 수 있습니다.
경고의 좋은 단어 : 도구는 받아 들일 수있는 것에 대해 약간 까다 롭습니다. 실제 문법에 자주 EBNF를 사용하기 때문에 작성할 수 있습니까? * 및 +는 토큰이 표시되어야하는 횟수를 나타냅니다. 이는 지원되지 않습니다. 그룹화는 지원되지 않습니다. 아주 오래 걸리는 것을 발견 할 수 있습니다. LL (1)에 도달 한 후에는 "재배치"를하고 싶을 것입니다.
물론 당신이 다루는 문법의 유형에 따라, 이것은 당신에게별로 문제가되지 않을 수도 있습니다. 상당히 제한된 구조 (프로 시저, 함수, 기본 내장 된 기본 유형 및 배열, ifs, 단일 루프 구조로 우리는 대신 자신을 생각해 냈습니다.)를 사용하여 일종의 Pascal/C 하이브리드를 만들었습니다. 표준 3 ...), LL (1) 문법 - 아마 2, 아마도 그것을 논쟁하는 데 적어도 일주일이 걸렸습니다. 이것은 약 4 개월의 합계가 아니므로 거기에 많은 시간을 보냈습니다.
LL (1) 문법이 반드시 필요한 경우에는 다음과 같은 상황이 발생하면 분명히 버튼을 눌러야하지만 yacc/bison이나 SableCC와 같은 파서 생성기를 사용할 수 있다면 당신은 장기적으로 볼 때 그 경로를 따라 가기가 훨씬 쉽다는 것을 알게 될 것입니다. 그건 당신이 그 길을 따라 가야한다는 것을 의미하지는 않습니다. 실제로 손으로 모든 것을 쓰는 것이 통찰력을 제공한다는 것을 알았습니다. 그렇지 않으면 얻지 못할 가능성이 있습니다. 그러나 현재 상황과 다른 상황에서 그 통찰력을 얻는 것이 더 나을 수도 있습니다. .
tl; dr 버전 : AtoCC 패키지의 kfgEdit를 사용하십시오.
재귀 적 파싱 구문 분석의 경우 ANTLR을 살펴볼 가치가 있습니다. 그러나, 당신의 질문에 대한 정확한 대답을 제공하는지 모르겠습니다 - 주어진 문법에 대해 FIRST와 FOLLOW 세트를 찾으십시오.
필자는 ANTLR (또는 ANTLRWorks)의 실제 분석 기능을 상기하지 않습니다. 문법에서 파서를 생성하는 데 문제가 있는지를 알려줄 수는 있지만 IIRC는 LL (1) 형식의 문법을 여전히 마사지하려고 할 때 도움이되지 않습니다. –
DMS Software Reengineering Toolkit에는 FIRST 및 FOLLOW 세트를 계산하는 파서 생성기가 있습니다. 또한 생성하는 L (AL) R 상태 기계를 검사 할 수 있습니다.
그러나 합법적 인 문맥 자유 문법이있는 경우 LL 모양으로 "논쟁 할 필요가 없습니다. DMS 파서 생성기는 문맥없는 문법으로부터 GLR 파서를 생성합니다.
kfgEdit는 모든 비 단말기에 대한 첫 번째 세트를 계산하지만 가능한 충돌이 발생할 수있는 위치에 따라 일부 후속 세트 만 계산합니다. 즉, 문법 논쟁에서 여전히 귀중한 것이 었습니다. 감사! – Zxaos