병렬 또는 병렬 HTML 파서가 있습니까?

Question

HTML 파싱은 강력한 의존성 때문에 병렬 처리가 어렵습니다.

하나의 HTML 문서가 병렬로 구문 분석되고 단일 DOM 트리가 최종적으로 생성 될 수 있도록 병렬 HTML 파서가 존재하거나 디자인되어 있습니까?

이전 HTML 버전 또는 최신 HTML5 일 수 있습니다.

Answer 1

HTML의 "강력한 종속성"은 구문 분석 할 수있는 다른 언어의 강력한 종속성보다 구문 분석의 관점에서 크게 다르지 않습니다. 진짜 문제는 파일의 한 부분을 파싱하는 것이 일반적으로 왼쪽 컨텍스트에 의존한다는 것입니다. 병렬 구문 분석기의 문제점은 왼쪽 컨텍스트를 얻는 방법입니다.

병렬 구문 분석기를 작성하는 방법, 텍스트를 청크로 분리하고, 개별적으로 구문 분석하고, 함께 결합하는 방법에 대해 general theory이 있습니다. McKeeman의 논문 (참고)은 N 프로세서의 경우 85N의 속도 향상을 주장했습니다.

나는 중앙에서 만나는 양 끝에서 파일을 구문 분석 할 것을 제안한 종이를 기억하는 것 같습니다. 오른쪽 파서가 왼쪽 컨텍스트를 생성했습니다. 왼쪽 파서는 오른쪽 문맥을 생성했습니다. 너는 문법을 뒤집어서에 의하여 양 지향성 스캐닝을 상대적으로 쉽게 할 수 있고, 앞뒤 문법을 파서 발전기에 공급할 수있다. 함께 붙이기 위해서는 참조 된 논문에 기술 된 기술이 필요합니다.

DMS 소프트웨어 리엔지니어링 툴킷에는 파이프 라이닝을 사용하여 구문 분석에서 렉싱 단계를 분리하고 전체 HTML4 파서를 사용할 수있는 GLR 파서가 있습니다. (DMS는 병렬 기반을 기반으로하며, 병렬로 개별 파일을 구문 분석하는 것은 비교적 쉽습니다.) HTML4 파서는 언어 방언에 대한 DMS의 지원을 사용하여 HTML5로 확장 될 가능성이 큽니다.

일반적으로 하나의 프로그램 (또는 HTML) 파일 만 구문 분석하는 경우 이러한 병렬 처리는 전반적인 성능에 많은 영향을주지 않으므로별로 중요하지 않습니다. 대부분의 파서는 꽤 빠르며 시간은 주로 개개인의 문자를 처리하기위한 노력으로 처리됩니다. 파일을 여러 조각으로 나누면 속도가 많이 빨라지고 은 개의 덩어리를 개별적으로, 싱할 수 있습니다. 특히 HTML 파일의 대부분이 공백을 낭비하고 있습니다.

개의 HTML 파일을 처리해야한다면 파일 당 하나의 스레드를 분석하는 것이 더 나을 것입니다. 그런 다음 각 스레드에서 꽤 전통적인 파서 기술을 사용할 수 있습니다.