올바른 LL (1) 문법 작성?

Question

현재 프로그래밍 언어 용 (아주) 작은 인터프리터/컴파일러를 작성하려고합니다. 언어에 대한 구문을 설정 했으므로 언어의 문법을 적어 둘 필요가 있습니다. 나는 약간의 연구 끝에 LL (1) 파서를 사용하는 것이 가장 쉬운 방법이라고 생각하기 때문에 LL (1) 파서를 사용하려고합니다.

본인은이 도메인에 익숙하지 않지만 수집 한 내용에서 BNF 또는 EBNF를 사용하여 구문을 형식화하는 것이 좋습니다. 그러나 모든 문법이 LL (1) 파서를 사용하는 구현에 적합하지는 않습니다. 따라서 LL (1) 형식으로 문법을 작성하는 올바른 방법 (또는 권장)이 무엇인지 궁금합니다.

도움 주셔서 감사합니다. Charlie.

추신 : 저는 하스켈의 파섹 (Parsec) 라이브러리를 사용하여 파서를 작성하려고합니다.

EDIT : 또한 SK-logic에 따르면 Parsec은 무한한 미리보기 (LL (k)?)를 처리 할 수 ​​있지만 질문은 여전히 ​​그 문법 유형을 나타냅니다.

Answer 1

필자는 LR (0) 파서를 사용하여 비슷한 작은 프로젝트를 만들었 기 때문에 전문가는 아닙니다. 일반적인 접근 방법은 다음과 같습니다.

1. 가공을 얻으십시오. 이를 통해 +, -, /, * 등의 규칙과 파생어를 만들고 파서가 작동하는 추상 구문 트리를 생성하는지 확인하십시오. 다른 입력에서 트리를 테스트하고 평가하여 산술이 올바르게 수행되는지 확인하십시오. 단계별로 작업하십시오. 충돌이 발생하면 계속 진행하기 전에 먼저 해결하십시오.

2. if-then-else 또는 case 표현식처럼 작동하는 유사한 구문을 사용하십시오.

3. 문법을 작성하는 언어에 더 많은 영향을받습니다.

은의 definetly (모든 언어에 대한 전체 LL 문법 온라인 불행하게도 나는 1 분에 발견하지 못했지만, LR 문법이 너무 참조로 유용합니다)를 기준으로 다른 프로그래밍 언어 문법을 확인하십시오. 예를 들면 :

Python grammar

물론 LL에 대한 위키 백과에서 몇 가지 작은 예 당신은 아마 이미 체크 아웃 한 Wikipedia LL Parser 문법

ANSI C grammar

.

난 당신이 도움이 물건의 일부를 찾을 희망

Answer 2

문법은 LL (k)는 경우를 결정하기위한 두 알고리즘이있다. 파서 생성기가이를 구현합니다. 가능한 경우 문법을 LL (k)로 변환하기위한 휴리스틱도 있습니다.

하지만 LL로 간단한 언어를 제한 할 필요가 없습니다 (1), 가장 현대적인 파서 생성기 (JavaCC, ANTLR, Pyparsing, 및 기타) LL (K)에있는 K를 처리 할 수 ​​있기 때문이다.

더 중요한 것은 구문 당신은 몇 가지 일반적인 프로그래밍 구조는 않기 때문에 언어에 대한 최고의, 2와 4 사이 k을 필요로 고려하는 것이 매우 가능성이 높습니다.

Answer 3

처음에는 반드시 문법을 LL (1)로하고 싶지는 않습니다. 구문 분석기를 더 간단하게 작성하고 더 나은 성능을 제공 할 수는 있지만 일반적으로 사용되는 언어 (일반적으로 LL (1)이 아닌)보다 언어가 더 장황해질 수 있습니다.

그렇다면 다음 단계는 정신적으로 문법을 단계별로 실행하고 그 시점에서 나타날 수있는 모든 가능성을 상상해보고 첫 번째 토큰으로 구별 할 수 있는지 확인하는 것입니다.

문법 LL을 만들기 위해 주어진 시점에서 나타날 수 있으며이 같은 맥락으로 시작 할 수있는 여러 선택의 경우 (1)

1. , 앞 이야기에서 키워드를 추가 엄지 손가락의 두 가지 규칙이있다 너 선택을 찍은 너.
2. 선택 품목 또는 반복 부품이있는 경우 다음에 선택/반복 부품의 첫 번째 토큰으로 표시 될 수없는 종료 토큰이 있어야 함을 확인하십시오.
3. 가능하면 생산 초기에 옵션 부품을 피하십시오. 처음 두 단계가 훨씬 쉬워졌습니다.