합성 문법

Question

미니 언어 포함을 지원하는 많은 프로그래밍 언어가 있습니다. PHP는 HTML 안에 내장되어 있습니다. XML은 JavaScript 내에 내장 될 수 있습니다. Linq는 C# 내에 임베드 될 수 있습니다. 정규식은 Perl에 내장 될 수 있습니다.

// JavaScript example 
var a = <node><child/></node> 

대부분의 프로그래밍 언어는 다른 미니 언어로 모델링 할 수 있습니다. 자바는, 예를 들어, 적어도 네 가지의 미니 언어로 나눌 수 수 :

• 유형 선언의 langauge (패키지 지시, 수입 지시, 클래스 선언)
• 멤버 선언 언어 (액세스 한정자를, 메소드 선언, 회원은
• ) 할 수 있다는 진술 언어 (제어 흐름, 순차적 실행)
• 식 언어 (리터럴, 할당, 비교, 연산)

을 바르 네 가지 별개의 문법으로이 네 가지 개념 언어를 구현하는 것은 필자가 복잡한 파서 및 컴파일러 구현에서 일반적으로 볼 수있는 스파게티즘을 줄이기위한 것입니다.

(ANTLR, JavaCC 및 사용자 지정 반복적 파서를 사용하여) 이전에는 여러 가지 다른 종류의 언어에 대한 파서를 구현했으며 언어가 실제로 복잡해지면 하나의 huuuuuuge 문법으로 끝납니다. 파서 구현은 정말 못 생겼다.

이러한 언어 중 하나에 대한 파서를 작성하는 경우, 구문 분석기를 구성 가능한 파서의 모음으로 구현하고 이들 사이에서 제어를 앞뒤로 전달하는 것이 좋습니다.

까다로운 것은 종종 포함 된 언어 (예 : Perl)가 포함 된 언어 (예 : 정규식)에 대한 고유 한 종점 센티널을 정의한다는 것입니다. "|"

이 코드에서

my $result ~= m|abc.*xyz|i; 

는 메인 펄 코드는 비표준 말단을 정의 : 여기에 좋은 예입니다 정규 표현식의 경우. regex 파서를 perl 파서와 완전히 별개로 구현하는 것은 정말 어렵습니다. 정규 표현식 파서는 부모 파서와상의하지 않고 표현식 종단을 찾는 방법을 모르기 때문입니다.

또는 내가 Linq는 식의 포함을 허용 언어를 가졌으나 (C#을이처럼) 세미콜론 (;)으로 종료, 나는이 Linq에 표현식이 대괄호 안에 표시 의무화하고 싶었 말할 수 :

var linq_expression = [from n in numbers where n < 5 select n] 

부모 언어 문법 내에서 Linq 문법을 정의한 경우 브릭 인클로저를 찾기 위해 구문 미리보기를 사용하여 "LinqExpression"에 대한 모호하지 않은 작업을 쉽게 작성할 수 있습니다. 하지만 부모님의 문법은 Linq 사양 전체를 흡수해야합니다. 그리고 그것은 끔찍합니다. 반면에 별도의 자식 Linq 파서는 외국 토큰 유형에 대한 미리보기를 구현해야하기 때문에 중단 할 위치를 파악하는 데 매우 어려움을 겪습니다.

Linq 파서가 부모 파서와 완전히 다른 토큰 화 규칙 세트를 정의하기 때문에 별도의 렉싱/파싱 단계를 사용하는 것이 거의 불가능합니다. 한 번에 하나의 토큰 만 스캔하는 경우 상위 언어의 어휘 분석기로 컨트롤을 다시 전달할시기를 어떻게 알 수 있습니까?

너희들은 어떻게 생각하니?더 큰 부모 langauges 안에 미니 언어를 포함시키기 위해 별개의 분리되고 구성 가능한 언어 문법을 구현하기 위해 오늘날 이용 가능한 최상의 기술은 무엇입니까?

Answer 1

구문 분석은 문제의 한 측면이지만, 각 미니 언어와 관련된 다양한 실행 가능 인터프리터 간의 상호 운용성이 해결하기가 훨씬 어려울 것으로 생각됩니다. 유용하게 사용하려면 각각의 독립적 인 구문 블록이 전체 컨텍스트와 일관되게 작동해야합니다 (또는 최종 동작은 예측할 수 없으므로 사용할 수 없습니다).

그들이 실제로하는 일을 이해하지는 못하지만 더 많은 영감을 얻으려는 흥미로운 곳은 FoNC입니다. 그들은 모든 종류의 서로 다른 연산 엔진이 원활하게 상호 작용할 수있게하는 방향으로 향하는 것처럼 보입니다 (추측하고 있습니다).

Answer 2

이 정확한 문제를 해결하기 위해 노력하고 있습니다. 내 생각을 공유 할 것입니다 :

문법 디버깅하기가 어렵습니다. Bison과 ANTLR에서 몇 가지 디버깅을했는데 꽤 좋지 않았습니다. 사용자가 파서에 문법으로 DSL을 삽입하기를 원한다면, 그것을 만들 수있는 방법을 찾아야한다. 내 접근 방식은 임의의 DSL을 허용하지 않고 두 가지 규칙을 따르는 것만 허용하는 것입니다.

• 파일의 모든 DSL간에 토큰 유형 (식별자, 문자열, 숫자)은 동일합니다.
• 불균형 괄호, 중괄호 또는 대괄호는 현대 파서는 어휘 단계로 분석 한 다음 기존의 문법 규칙을 적용 깰 때문에

첫 번째 제한하는 이유은 허용되지 않습니다. 다행스럽게도, 유니버설 토큰 화기는 이미 작성한 DSL을 수용하지 않더라도 작성하려는 DSL의 90 %에 충분히 적합하다고 생각합니다.

두 번째 제한은 문법을 서로 더 구분할 수있게합니다. 괄호 (괄호, 대괄호)를 그룹화 한 다음 각 그룹을 재귀 적으로 구문 분석하여 두 단계로 파싱 할 수 있습니다. 내장 된 DSL의 문법은 포함 된 대괄호를 통해 벗어날 수 없습니다.

해결책의 또 다른 부분은 매크로를 허용하는 것입니다. 예를 들어 regex("abc*/[^.]")은 나에게 잘 어울립니다. 이렇게하면 매크로 "regex"은 주 언어로 정규식 문법을 작성하는 대신 정규식을 구문 분석 할 수 있습니다. 정규 표현식에 다른 구분 기호를 사용할 수는 없지만 내 마음 속에서 일관성을 측정 할 수는 있습니다.

Answer 3

생각해 보면, 이것은 실제로 재귀 적 파생 구문 분석이 작동하는 방식입니다. 각각의 규칙과 그것이 의존하는 모든 규칙은 미니 문법을 형성합니다. 더 높은 것은 상관 없습니다. 예를 들어, ANTLR로 Java 문법을 작성하고 모든 다른 "미니 언어"를 파일의 다른 부분으로 분리 할 수 ​​있습니다.

"미니 언어"가 많은 규칙을 공유하는 이유는 간단하지 않습니다. 그러나 ANTLR과 같은 도구를 사용하여 서로 다른 파일의 개별 문법을 포함 할 수 있다면 좋을 것입니다. 이렇게하면 논리적으로 분리 할 수 ​​있습니다. 이것이 아마도 구현되지 않은 이유는 아마도 그것이 "외관상의"문제 일 것입니다. 문법 파일 자체와 파싱 자체가 아닌 순수하게 관련되어 있습니다. 또한 코드를 더 짧게 만들지는 않습니다 (약간 더 쉽게 따라갈 수도 있음). 이것이 해결할 수있는 유일한 기술적 인 문제는 이름 충돌입니다.

Answer 4

this podcast를 듣고 싶을 수도 있습니다.스캐너없는 구문 분석은 다른 문법 작성 문제를 해결할 수 있도록 "발명 된"것입니다 (문제는 "유니버설"토크 나이저/스캐너를 작성할 수 없다는 것을 빨리 발견한다는 것입니다).

Answer 5

스캐너없는 일반화 된 LR 구문 분석 SGLR을 살펴보십시오. 다음은 참조 및 URL입니다. 이 파싱 기술은 파싱 테이블의 구성을 매우 간단하게 만듭니다. 특히 SDF와 결합하여.

Martin Bravenboer와 Eelco Visser. 언어 라이브러리에 대한 구문 포함 및 동화 디자인 소프트웨어 공학 모델 : 모델 2007 년 워크샵과 심포지엄, LNCS의 볼륨 (5002), 2008 년

MetaBorg 및 MetaBorg in action

Answer 6

펄 6 특별히 프로그램을 작성하기 위해 만든 DSL을의 집합으로 볼 수있다.

실제로 Rakudo 구현은 정확히 이런 방식으로 구현됩니다.

짝수 문자열은 사용하거나 사용하지 않도록 설정할 수있는 옵션이있는 DSL입니다. 이 작업을하는 것은 기본적으로 가지고

Q 
:closure 
:backslash 
:scalar 
:array 
:hash 
"{ 1 + 3 } \n $a @a<> %a<>" 

qq"{1+2}" eq ｢3｣ 

qq:!closure"{1+2}" eq ｢{1+2}｣ 

는 합성 가능한 문법에서 만들어 질 :

sub circumfix:«:-) :-)» (@_) { say @_ } 

:-) 1,2,3 :-) 

---

는 펄에서 6 개 문법 클래스의 단지 유형 및 토큰은 방법의 유형입니다. 내가 빌드로 구문 분석 트리를 변환하는 편리한 인 행동 클래스를 보여주지 않았다

role General-tokens { 
    token start-of-line { ^^ } 
    token end-of-line { $$ } 
} 
grammar Example does General-tokens { 
    token TOP { 
    <start-of-line> <stuff> <end-of-line> 
    } 
    token stuff { \N+ } 
} 

role Other { 
    token start-of-line { <alpha> ** 5 } 
} 
grammar Composed-in is Example does Other { 
    token alpha { .. } 
} 

say Composed-in.parse: 'abcdefghijklmnopqrstuvwxyz'; 

｢abcdefghijklmnopqrstuvwxyz｣ 
start-of-line => ｢abcdefghij｣ 
    alpha => ｢ab｣ 
    alpha => ｢cd｣ 
    alpha => ｢ef｣ 
    alpha => ｢gh｣ 
    alpha => ｢ij｣ 
stuff => ｢klmnopqrstuvwxyz｣ 
end-of-line => ｢｣ 

참고.