1
ANTLR 대 BISON이 아닌 금속 질문에 대한 코드화 된 페달입니다.
또한 이진 형식을 구문 분석하기위한 것입니다. 어휘 분석은 없습니다.접두어 인코딩에 LL (1) 파서가 더 효율적이고 후위에 대해 LR (1)이 더 효율적입니까?
A
답변
1
엄격한 사전 (또는 사후) 순서 식을 구문 분석하는 비용은 하향식 또는 상향식 기술을 사용하여 간단합니다. 어휘 분석조차도 다른 작업에 비하면 정말 작아 보입니다. 작은 속도 차이는 알고리즘 전략보다는 구현 세부 사항의 결과 일 것입니다.
프리 - 오더 또는 포스트 오더 표현에 대해 토큰 미리보기가 필요 없기 때문에 LR (1) 파서를 사용하는 것은 의미가 없습니다. LR (0)은 괜찮을 것입니다. 유용한 LR (0) 파서 생성기를 찾지는 못하지만 파서를 손으로 쓰고 싶다면 그 사실이 작업을 단순화합니다.
0
지금 당장은 LL (1)과 LR (1)을 무시하고 일반적으로 고유 한 구문 분석 코드를 사용하여 이러한 종류의 표현식을 구문 분석합니다. 이전에 구문 분석되고 평가 된 하위 표현식의 스택을 유지 한 다음 상위 2 개 항목을 스택에서 꺼내서 병합하거나 (다른 연산자를 읽은 경우) 병합하거나 스택에 무언가를 푸십시오 (숫자를 읽는 경우).
실제로 스택을 구현할 수있는 몇 가지 방법이 있습니다. 스택을 명시 적 스택 데이터 구조로 만들 수 있습니다. 여기서는 왼쪽에서 오른쪽으로 입력을 가로 질러 스캔하고 적절하게 푸시하고 팝합니다. 이것은 LR (1) 구문 분석기가 작동하는 방식과 가장 비슷합니다. 이동 (밀기) 및 축소 (터지는) 측면에서 생각할 것이기 때문입니다. 재귀 적 알고리즘을 사용하여 호출 스택을 명시 적 스택 대신 사용할 수도 있습니다.이 스택은 LL (1) 구문 분석이 작동하는 방식에 더 가깝습니다.
이 경우 LL (1)과 LR (1) 구문 분석 모두 원시 성능에 신경 쓰면 총 잔인한 것처럼 보입니다. 그들은 다양한 종류의 일반 문법을 처리 할 수 있도록 설계되었으며, 테이블의 오버 헤드가 사용자의 작업을 방해 할 수 있습니다. 두 가지 다른 방법 (명시 적 스택/상향식 대 내재적 인 스택/하향식)으로 코드를 작성하고 실제로 두 가지 중 어느 것이 더 빨리 끝나는 지 확인하십시오.
+0
감사합니다. 이것은 구문 분석 대기 시간이 중요한 금속에 대한 페달입니다. 내 직관에 따르면 LL은 접두사에 더 좋고 LR은 접미어에 더 좋습니다. 하지만 당신이 제안하는대로, 나는 둘 다 쓰고 테스트 할 것입니다. 실제로 LL/pre, LL/post, LR/pre, LR/post 및 test 네 가지 경우 모두를 테스트 할 것입니다. – Olsonist
+0
사실, 호출 스택은 최신 x86에서 명시 적 HW 지원을 제공합니다. 그것은 내가 생각하지 못했던 탁월한 재귀 적 (recursive-decent) 테이블에 이점을 준다. – Olsonist
0
이 문서, LL and LR Parsing Demystified, 나의 직관 백업 :
폴란드어 직접 각각 LL과 LR 구문 분석에, 내보기에, 해당 역 폴란드 표기법.
스택 오버 플로우에 오신 것을 환영합니다! 나는 당신의 문제를 추측 할 수있는 한 귀하의 질문을 편집했습니다. 그러나 주제에 대한 지식을 가진 많은 사람들이 그것을 볼 수 있도록 더 많은 설명을 추가하십시오. P 행운을 빌어 요! – manetsus
바이너리 형식을 가지고 있어도 여전히 토큰을 식별해야합니다 (예 : 프로토콜에 따라 리틀 엔디안 또는 빅 엔디 언 바이트 순서로 4 바이트 정수를 추출해야 함). 어휘 분석과 도덕적으로 동일합니다. 그리고 대부분의 경우, 토큰을 구문 형식으로 결합하는 비교적 간단한 비용 ("구문 분석")보다 더 많은 사이클이 소요됩니다. – rici