재귀 하강 구문 분석 및 추상 구문 트리

Question

주로 학습을 목적으로 재귀 적으로 괜찮은 파서를 하드 코딩하고 있습니다. 몇 가지 문제가 있습니다.

나는 예제로 CSS3 문법에서이 발췌를 사용합니다 :

simple_selector = type_selector | universal; 
type_selector = [ namespace_prefix ]? element_name; 
namespace_prefix = [ IDENT | '*' ]? '|'; 
element_name = IDENT; 
universal = [ namespace_prefix ]? '*'; 

첫째, namespace_prefix이 모두 type_selector 및 universal 내에서 선택적 부분이라고 인식하지 않았다. 따라서 *|* 같은 입력을 입력하면 namespace_prefix 생산과 일치하는 모든 입력에 대해 맹목적으로 고려 되었기 때문에 type_selector이 항상 실패했습니다.

재귀 적으로 괜찮은 점은 이해하기 쉽지만 내 이해는 더 나은 단어가 부족하여 번 반복적 인 재귀을 생산에 적용하기 전에해야한다는 것입니다. 그래서 프로덕션의 서명을 부울 값을 반환하도록 변경했습니다. 이렇게하면 특정 생산품이 성공했는지 여부를 쉽게 알 수있었습니다.

임의의 미리보기를 지원하기 위해 연결된 목록 데이터 구조를 사용하고 프로덕션을 시도하기 위해이 목록을 쉽게 조각 낼 수 있으며 프로덕션이 성공하지 못하면 내 시작 지점으로 돌아갈 수 있습니다. 그러나, 프로덕션을 시도하는 동안, 나는 문서 객체 모델을 구성하려고하는 가변적 인 상태를 따라 가고있다. 생산이 성공할 것인지 아닌지를 알 수있는 방법이 없기 때문에 이것은 실제로 해결되지 않습니다. 그리고 제작이 성공적이지 않으면, 어떻게 든 변경 사항을 취소해야합니다.

내 질문은 여기 있습니다. 중간 구문으로 추상 구문 트리를 사용하고 거기서부터해야합니까? 이 문제를 해결하기 위해 일반적으로하는 일입니까? 그 이유는 주로 문서 객체 모델이 재귀를위한 적절한 트리 데이터 구조가 아닌 것으로 보인다.

Answer 1

저는 CSS에 익숙하지 않지만 일반적으로 할 수있는만큼 모호성을 없애기 위해 문법을 리팩터링합니다.

simple_selector = [ namespace_prefix ]? (type_selector | universal); 
type_selector = element_name; 
namespace_prefix = [ IDENT | '*' ]? '|'; 
element_name = IDENT; 
universal = '*'; 

모든 문법이 같은 간단한 모양 미리 단순화 할 수있는 것은 아닙니다 : 여기에 귀하의 경우, type_selector 보편적 모두의 시작 부분이 될 수 namespace_prefix 생산은 별도의 옵션 제품으로 앞에 꺼내 될 수있다 그러나 이것들에 대해서는 더 복잡한 shift-reduce 파서를 사용할 수 있습니다. 또는 제안대로 - 역 추적 할 수 있습니다. 역 추적의 경우 일반적으로 프로덕션을 구문 분석하고 문법을 통해 경로를 기록하려고 시도합니다. 입력과 일치하는 제작물을 얻은 후에는 녹음 된 경로를 사용하여 해당 제작물에 대한 의미 작업을 실제로 수행합니다.