추상적 문제 설명 :파싱되지 않은 AST <O (exp (n))?
I 파싱되면 다시 동일한 AST를 생성하는 AST로부터 토큰 스트림을 생성하는 수단 unparsing, 볼때.
그래서 parse(unparse(AST)) = AST이 있습니다.
이것은 동일한 AST를 생성하는 유효한 구문 분석 트리를 찾는 것과 같습니다.
이 언어는 변형을 사용하여 context freeS-attributed 문법으로 설명됩니다.
따라서, 해석기는 모든 문법 제약이있는 통과 노드를 통해 유효한 '경로'를 찾아야합니다. 이것은 기본적으로 문법 규칙에 노드 AST의 유효한 할당을 찾는 것을 의미합니다. 이것은 일반적으로 constraint satisfaction problem (CSP)이며 구문 분석과 마찬가지로 O (exp (n))에서 backtracking으로 해결할 수 있습니다.
다행히도 구문 분석에 대해서는 GLR (또는 더 나은 문법 제한)을 사용하여 O (n³)에서 수행 할 수 있습니다. AST 구조가 문법 프로덕션 규칙 구조와 너무 가깝기 때문에 런타임이 구문 분석보다 나쁜 구현을 보는 것은 정말 놀랐습니다. XText은 구문 분석을 위해 ANTLR을 사용하고 역 분석을 위해 역 추적합니다.
질문
- 는 컨텍스트 무료 S-속성을 공유하는 모든 파서 및 unparser 필요 문법이나있다가, 예를 들어 더 제약이다인가 구문 분석 기술/파서 구현?
- 나는이 문제가 일반적으로 O (exp (n))가 아니라는 느낌을 가지고있다. 천재가 나를 도와 줄 수 있을까?
- 기본적으로 상황에 맞는 문법입니까?
예 1 : 그래서
Area returns AnyObject -> Pedestrian | Highway
Highway returns AnyObject -> "Foo" Car
Pedestrian returns AnyObject -> "Bar" Bike
Car returns Vehicle -> anyObjectInstance.name="Car"
Bike returns Vehicle -> anyObjectInstance.name="Bike"
나는
AnyObject -> AnyObject -> Vehicle [name="Car"]을 포함하는 AST가 나는 루트 영역이 될 수 있습니다 알고 있다면, 나는 그것을 해결할 수
Area -> Highway -> Car
따라서 (고속도로 보행자) 결정은 하위 트리 결정에 따라 결정됩니다. 리프가 첫눈에 몇 가지 유형 중 하나 일 수 있지만 나중에 올바른 경로를 형성하는 특정 리프가되어야하는 경우 문제는 더욱 심각해집니다.
예 2 :
그래서 S-속성 규칙 그냥 예를 들어, 일부 속성을 할당, 지정되지 않은 객체를 반환하는 경우대서양 표준시를 통과하는 동안 나는 C.
에 "C"를 해결할 수 있습니다 직후
A -> B C {Obj, Obj}
X -> Y Z {Obj, Obj}
B -> "somekeyword" {0}
Y -> "otherkeyword" {0}
C -> "C" {C}
Z -> "Z" {Z}
대서양 표준시가 포함 그렇다면
Obj
/\
"0" "C"
나는
A
/\
B C
에 unparse 수 있습니다 문법에서 생성 할 수있는 모든 제약 조건은 "C"를 누를 때까지 A와 X 두 규칙에 모두 만족합니다. 이는 트리
Obj
|
MagicNumber_42
모두 솔루션
A -> B | C
B -> "map" {MagicNumber_42}
C -> "foreach" {MagicNumber_42}
유효하고 그들이 예컨대, 동일한 의미를 갖고 있다고 생각되는 것을 의미한다. 통 신당.
추가 정보 :
나는 이해할 수 없을 것 같다. 파스 트리의 depth-in-fix traversal은 원래 순서대로 토큰 잎을 방문해야합니다. AST가 파스 트리와 너무 다르므로 이러한 순회를 수행 할 수 있습니까? – phs
예, 구문 분석 트리는 '강력한 형식'이므로 특정 노드를 생성하는 데 사용 된 특정 문법 규칙을 기본적으로 알고 있습니다. 일반적인 AST의 경우이 정보는 손실되어 재구성해야합니다. 그래서 AST를 unparsing하기 위해서는이 AST를 생성하는 유효한 구문 분석 트리를 작성하는 것만으로 충분합니다. 몇 가지 구문 분석 트리가있을 수 있지만이 중 유효한 것이 모두 같은 의미 (구문 설탕)를 가지기 때문에 중요하지 않습니다. 문제는 AST를 통과하는 것이 아니라 방문한 노드에 올바른 문법 규칙 생성 순서를 지정하는 것입니다. –
구문 분석 트리를 AST로 변환하는 변환은 응용 프로그램에 따라 다릅니다. 이것이 반전하려는 단계 인 것처럼 들리므로 특정 응용 프로그램 (언어)에 대해 알려줘야합니다. – phs