Bison에서 문법의 왼쪽 인수 분해가 필요합니까?

Question

나는 bison을 사용하여 파서를 만들고 있습니다. 필자는 바이슨에서 사용할 때 문법을 그대로 두는 것이 여전히 필요한지 물어보고 싶다. 필자는 들소에게 왼쪽 정렬되지 않은 문법을 주려고했는데 경고 나 오류를주지 않았고 파서에 준 예제 구문도 허용했지만 구문 분석기가 모든 입력에 정확하지 않을 수도 있습니다. .

Answer 1

왼쪽 인수 분해는 문법에서 LL 충돌을 제거하는 방법입니다. Bison은 LALR을 사용하기 때문에 왼쪽 재귀 또는 다른 LL 충돌에 문제가 없습니다 (실제로 스택 요구 사항을 최소화하므로 왼쪽 재귀가 바람직합니다). 따라서 왼쪽 인수 분해가 반드시 필요하거나 바람직하지 않습니다.

왼쪽 분해율은 아무 것도 깨뜨리지 않습니다. bison은 왼쪽 인수 분해 문법과 왼쪽 인수 분해 인수를 처리 할 수 ​​있지만 왼쪽 인수 분해 문법을 분석하는 데 더 많은 리소스 (메모리)가 필요할 수 있습니다 , 일반적으로 그렇게하지 마십시오.

편집 당신은 LL-VS-LR 일을 구문 분석하는 방법과 문법의 구조는 각에 미치는 영향에 대한 혼동이 될 것으로 보인다.

LL 파싱은 구문 분석 스택의 시작 심볼로 시작하고 각 단계에서 스택 상단의 비 터미널을 일부 규칙의 오른쪽에있는 심볼로 바꿉니다. 그건 아닌 터미널. 스택 맨 위에 터미널이있을 때, 터미널은 입력의 다음 토큰과 일치해야합니다. 그러면 팝업하여 입력을 소비합니다. 목표는 모든 입력을 소비하고 빈 스택으로 끝나는 것입니다.

LR 구문 분석은 맨 아래입니다. 빈 스택으로 시작하고 각 단계에서 입력에서 스택으로 소비 (소비)하는 토큰을 복사하거나 맨 위에있는 일련의 기호를 바꿉니다. 스택에 규칙의 왼쪽에있는 단일 기호가있는 일부 규칙의 오른쪽에 해당합니다. 목표는 모든 입력을 소비하고 스택의 시작 기호 만 남겨 두는 것입니다.

오른쪽에 같은 기호로 시작하는 동일한 비 터미널에 대한 다른 규칙은 LL 구문 분석에서 큰 문제입니다.이 비 터미널을 규칙 중 하나의 기호로 바꾸고 다음 몇 가지와 일치시킬 수 있습니다 토큰을 입력 할 수 있으므로 수행 할 작업을 미리 알 필요가 있습니다. 그러나 LR 구문 분석의 경우 아무런 문제가 없습니다. 입력에서 스택으로 토큰을 이동 (이동)하고 나중 토큰을 얻을 때 어떤 오른쪽 측면과 일치하는지 결정합니다.

LR 구문 분석은 동일한 토큰으로 시작하는 규칙 대신 오른쪽에 동일한 토큰이있는 끝 규칙에 문제가있는 경향이 있습니다. John Levine의 저서에는 "cart_animal :: = HORSE"및 "work_animal :: = HORSE"규칙이 있으므로 HORSE 기호를 이동 한 후 "cart_animal"또는 "work_animal"중 하나로 축소 할 수 있습니다 . 컨텍스트가 "AND"토큰 뒤에 올 수 있으므로 다음 토큰이 "AND"일 때 줄이기/감소 (LR) 충돌이 발생합니다.

Answer 2

사실, 그 반대가 사실입니다. LALR (1) 파서 생성자가 생성 한 구문 분석기는 왼쪽 재귀를 지원할뿐만 아니라 실제로 보다 나은을 왼쪽 재귀로 처리합니다. 역설적이게도, 오른쪽 문법에서 재귀를해야 할 수도 있습니다.

오른쪽 재귀 작업; 그러나 구문 분석되는 재귀 구문의 크기에 비례하여 구문 분석 스택 공간을 발생시키는 감소를 지연시킵니다.이런 리스프 - 스타일리스트 작성 예컨대

:

list : item { $$ = cons($1, nil); } 
    | item list { $$ = cons($1, $2); } 

파서 스택리스트의 길이에 비례한다는 것을 의미한다. 가장 오른쪽의 item에 도달 할 때까지 감소가 일어나지 않으며, 다음으로 일련의 축소가 발생하여 cons 호출 순서로 오른쪽에서 왼쪽으로 목록을 작성합니다.

코드가 아닌 데이터 구문 분석을 시작하고 데이터가 커질 때까지이 문제가 발생할 수 있습니다. 당신이 왼쪽 재귀이를 수정하면 작업이 "당신이가는대로 감소"되기 때문에

, 당신은 일정한 금액 파서 스택의 목록을 구축 할 수 있습니다 :

이

list : item  { $$ = cons($1, nil); } 
    | list item { $$ = append($1, cons($2, nil)); } 

(지금은 성능이 append 목록의 꼬리를 검색하는 데 문제가 있는데, 그 이유는 파싱과 관련이없는 여러 가지 해결책이 있기 때문입니다.