LALR (1) 파서가 파싱 할 수 있습니까?

Question

나는 다른 사람의 사이에서 다음과 같은 구조를 가지고 언어에 대한 들소의 파서를 쓰고 :

• 자기 파견 : [identifierarguments]
• 파견 : [expression. identifierarguments]
• 문자열 자르기 : expression [expression, expression] - 파이썬과 유사합니다.

arguments은 쉼표로 구분 된 표현식 목록이며 비어있을 수도 있습니다. 위의 모든 것은 독자적으로 표현 된 것입니다. 제 문제는 [method [other_method]]과 [someString[idx1, idx2].toInt]을 구문 분석하는 방법이나 LALR (1) 파서를 사용하여이 작업을 수행 할 수 있는지 잘 모르는 것입니다.

좀 더 정확히 말하자면 다음 예를 생각해 보겠습니다. [a[b]] (메서드 호출, b 메서드 호출). 상태가 [a에 도달하면 [b]] (룩어 두 번째 [이다), 그것은 a[b,c] 같은 따를 수 있기 때문에 그 자체가 expression로 감소 될 수있는 (expression에 (이미 identifier로 감소 된) a을 절감하고 두 번째 구조를 계속할지 여부를 알 수 없습니다 위에서 arguments의 목록 (이 경우 [b] 등)이 표시 될 것이므로 identifier (계속 이동하십시오)을 유지하십시오.

이 문법을 사용하는 방식 때문에이 시프트/축소 충돌이 발생합니까? 아니면 LALR (1) 구문 분석기로 모든 구문을 구문 분석 할 수 없습니까?

그리고 좀 더 일반적인 질문은 특정 유형의 파서가 언어를 구문 분석 할 수 없다는 것을 어떻게 증명할 수 있습니까?

Answer 1

당신의 문법이 명백하다고 가정하면 (당신이 묘사 한 부분이 나타납니다) %glr-parser을 지정하는 것이 가장 좋습니다. 대부분의 경우 올바른 구문 분석은 소수의 토큰만으로 강제되므로 오버 헤드가 눈에 띄지 않아야하며 장점은 AST의 문법이나 구문을 복잡하게 만들 필요가 없다는 것입니다.

한 가지 단점은 들소가 문법이 모호하지 않은지 확인할 수 없다는 것입니다. 일반적으로 불가능합니다. 증명하기 쉽지 않습니다. 일부 입력이 모호한 것으로 밝혀지면 GLR 파서가 오류를 생성하므로 좋은 테스트 슈트가 중요합니다.

언어가 LR (1)이 아니라는 것을 증명하는 것은 까다 롭습니다. 언어가 아마도 인식 가능이고 LALR (1) 파서 인 경우 불가능할 것으로 생각됩니다. (그러나 전체 문법을 보지 않고 말할 수는 없습니다.) 그러나 구문 분석 (CS 이론 외부)은 유용하도록 올바른 구문 분석 트리를 만들어야하며 LR 문법을 생성하는 데 필요한 수정 사항은 AST post-parse fixup이 필요합니다.제 (서브 세트) 경우

a[b[c],d] 

및

[a[b[c],d]] 

간의 우선 순위의 차이로부터 정확한 AST 스프링을 작성하는 성사는 b는 인수리스트 [c]에 결합 쉼표 낮은 우선 순위를 가지고 ; 결국 b[c] 및 d은 슬라이스의 형제 자매입니다. 두 번째 경우 (메서드 호출)에서 쉼표는 인수 목록의 일부이며 메서드 응용 프로그램보다 훨씬 긴밀하게 바인딩됩니다. b, [c] 및 d은 메소드 응용 프로그램의 형제입니다. 그러나 임의의 긴 입력 (d이 임의의 표현식이 될 수 있기 때문에)까지는 구문 분석 트리의 모양을 결정할 수 없습니다.

"우선 순위"는 공식적으로 정의 할 수 없으며 트리를 조정할 수있는 해킹이 있기 때문에 모든 것이 조금 손 쉬워. LR 속성은 실제로 구성 가능하지 않기 때문에보다 엄격한 분석을 제공하는 것이 실제로 가능합니다. 하지만 상관없이 GLR 파서는 가장 간단하고 강력한 솔루션입니다.

나중에 참조 할 수있는 작은 점 : CFG는 프로그래밍 도구가 아닙니다. 또한 문제의 문법을 명확하게 전달할 목적으로 사용됩니다. Nirmally, 당신이 당신의 언어를 설명하고 싶다면 비공식적으로 설명하려고하는 것보다 명확한 CFG를 사용하는 것이 더 낫습니다. 물론 의미없는 비 터미널 이름이 도움이 될 것이고 몇 가지 예가 결코 상처를주지는 않지만 문법의 본질은 공식적인 설명에 있으며 생략하면 다른 사람들이 "도움이되기"가 더 어려워집니다.