2013-10-22 1 views
2

이전에 질문 한 내용을 다시 정리합니다. 목적은 구문 분석에서 우선 순위가 작동하는 방식을 이해하는 것입니다.구문 분석의 우선 순위

a(3).value = 100을 구문 분석하고 싶습니다. .을 읽은 후 다음과 같이 parser.mly이 멈추고 오류를 반환합니다. 내가 argument_list 전용 부품을 이동하는 경우

그러나, 파일의 끝에 (beginend에 의해 KO-globed), 구문 분석은 잘 작동합니다 (따라서는 l_expression 이후).

구문이 구문 분석되는 경우 let_statementdata_manipulation_statement으로 줄어 듭니다. a(3).valuemember_access_expression으로 축소됩니다. a(3)index_expression으로 축소됩니다. 3argument_list으로 줄어 듭니다.

문장을 구문 분석 할 수없는 경우 문장의 시작을 call_statementcontrol_statement으로 줄이려고 시도합니다 ... 오류로 끝납니다.

항상 우선 순위가 무엇이든 상관없이 구문 분석은 항상 성공으로 끝날 수없는 감소를 거부한다고 생각했습니다. 하지만 거기에 그것은 시도하고 실패한 것으로 보이며 다른 가능성을 시도하는 것을 거부했습니다 ...

아무도 명확히 도울 수 있습니까?

statement: 
| control_statement { $1 } 
| data_manipulation_statement { BS_DMS $1 } 

control_statement: | control_statement_except_multiline_if { BS_CSEMI $1 } 
control_statement_except_multiline_if: | call_statement { $1 } 
call_statement: | simple_name_expression argument_list { CSEMI_SNE_AL ($1, $2) } 
data_manipulation_statement: | let_statement { $1 } 
let_statement: | l_expression EQUAL expression { DMS_let (None, $1, $3) } 

simple_name_expression: | name { $1 } 
index_expression: | l_expression LPAREN argument_list RPAREN { IE_LE_AL ($1, $3) } 
member_access_expression: | l_expression DOT unrestricted_name { MAE_LE_UN ($1, $3) } 
literal_expression: | INTEGER { LIE_INT $1 } 

unrestricted_name: | name { UN_N $1 } 
name: | untyped_name { N_UN $1 } 
untyped_name: | IDENTIFIER { UN_I $1 } 

expression: 
| l_expression { E_LE $1 } 
| value_expression { E_VE $1 } 

value_expression: 
| literal_expression { VE_LIE $1 } 
| parenthesized_expression { VE_PE $1 } 

(***** begin argument_list *****) 
argument_list: | positional_or_named_argument_list { AL_PONAL $1 } 

positional_or_named_argument_list: 
| positional_argument_COMMAs required_positional_argument { PONAL_PAs_RPA (List.rev $1, $2) } 
positional_argument_COMMAs: 
    /* empty */ { [] } 
| positional_argument_COMMAs positional_argument COMMA { $2 :: $1 } 

positional_argument: | argument_expression { $1 } 
required_positional_argument: | argument_expression { $1 } 
argument_expression: | expression { AE_expression (None, $1) } 
(***** end argument_list *****) 

l_expression: 
| simple_name_expression { LE_SNE $1 } 
| index_expression { LE_IE $1 } 
| member_access_expression { LE_MAE $1 } 

답변

3

구문 분석이 어떻게 진행되는지에 대한 절대 규칙은 없습니다. 파서에 따라 다릅니다. 대체로 정확한 파서는 "성공으로 끝나지 않을 수있는 감소를 항상 거부해야합니다."하지만 선형 시간의 왼쪽에서 오른쪽 파서로는 일반적으로이를 수행 할 수 없습니다. GLR 파서 (바이슨이 생성 할 수있는)는 문법에 따라 최대 큐빅 시간 내에이를 수행 할 수 있습니다. 대부분의 파싱 연결자 라이브러리와 같은 역 추적 파서가이를 수행 할 수 있지만 알고리즘의 복잡성을 예측하는 것은 쉽지 않습니다. 그러나 당신이 사용하고 있다고 생각하는 * LR (1) 파서는 태그에 기초하여 * LR (1) 문법만을 파싱 할 수 있으며 문법은 그 중 하나가 아닙니다.

LR (1) 파서가 왼쪽에서 오른쪽으로 (L) 입력을 통해 한 번에 하나씩 토큰을 진행합니다. 각 토큰을 읽은 후 입력의 가장 오른쪽 토큰 (R)으로 끝나는 모든 작품을 "축소"(즉, 작품과 일치)합니다. 이렇게하려면 구문 분석 ("구문 분석 스택")과 다음 (1) 토큰 ("미리보기")의 진행 상태를 유지할 수있는 많은 정보를 사용합니다. 그들은 유한 상태 푸시 다운 오토 마톤으로 작업하며, 이상적인 PDA에 대해 다른 근사치를 제공하지만, 중요하지 않은 문법의 목적을 위해 이러한 오토마타를 구성하는 몇 가지 방법이 있습니다. ocamlyacc는 원본 yacc와 마찬가지로 LALR (1) 파서를 생성하지만 LR (1)은 문법이 아니기 때문에 간소화 된 LR (1) 구문 분석기로 파싱 할 수 없습니다.

위의 설명에서 나는 LR 구문 분석에 적용되지 않기 때문에 "우선 순위"라는 단어를 사용하지 않았습니다. 우선 순위 파서 (일반적으로 LR 파서보다 강력하지는 않지만 구성하기가 쉽다)와 같은 것들이 있지만 손으로 ​​쓴 파서의 형태를 제외하고는 더 이상 공통적이지 않습니다. (우선 순위 - 문법 파서 생성기가 있는지 확실하지 않지만 일단 LALR (1) 구문 분석이 발견되면 파서 - 생성기 시장이 우선 순위 또는 LL (1) 구문 분석보다 강력하기 때문에 파서 - 생성기 시장을 빠르게 인수했습니다.) 그러나 모호한 문법에 대처하기 위해 초기 단계에서 "우선 순위"가 yacc에 추가되었습니다. 명백하게 쓰여졌을 수도 있지만, 모호한 형태로 더 조밀 한 문법이 있습니다.

LR 파서가 수행 할 작업을 결정할 때 둘 이상의 대안이있을 수 있습니다. 이는 하나 이상의 가능한 감소 ("감소 감소"충돌)가 있거나 사용 가능한 감소가 정확한지 ("shift-reduce"충돌) 명확하지 않기 때문일 수 있습니다. 충돌은 문법이 모호하거나 지정된 미리보기를 사용하여 구문 분석 할 수 없기 때문에 발생합니다.

페티 닉 LR 파서 생성기는 실패를보고합니다. 그러나 실용 파서 생성기는 대안 중 원하는 것이 무엇인지 알아 내려고 시도 할 수 있습니다. 이렇게하는 간단한 방법은 프로그래머가 제공 한 선언 ("우선 순위 선언") 또는 일부 경험적 방법 ("문법 파일에서 처음 나타나는 것을 선호")을 기반으로 다른 대안보다 우선 순위를 하나 부여하는 것입니다.). 그러한 경험적 방법은 파싱이 예상되는 언어를 실제로 파싱하지 않는 파서가 될 수 있다는 점에서 위험합니다. IMHO 파서 생성기는 적어도 그렇게했다고 경고하지 않고 휴리스틱을 적용해야합니다.

이제 실질적인 문제 : 문법이 LR (1)이 아닌 이유.

다음 추출 정보부터 시작하겠습니다.

call_statement: simple_name_expression argument_list 
let_statement: l_expression EQUAL expression 
l_expression: index_expression 
l_expression: simple_name_expression 
index_expression: l_expression LPAREN argument_list RPAREN 

이제 입력 : a (을 고려하십시오. 즉, 토큰 a을 읽었으며 lookahead 토큰은 (입니다. asimple_name_expression으로 줄여야합니다 (단원 제작물을 여러 개 사용했지만 세부 정보는 관련성이 없음). 지금이 시점에서, 파서 상태가 포함됩니다 : (·은 생산에서 현재 "포인트"표시)입니다

call_statement: simple_name_expression · argument_list 
index_expression: l_expression · LPAREN argument_list RPAREN 
l_expression:  simple_name_expression · 

, 우리는 그대로 simple_name_expression을두고 argument_list를 수집하기에 이동하거나 수를 index_expression의 나머지 부분을 수집하기 위해 simple_name_expressionl_expression으로 줄일 수 있습니다. 어떤거야?

적어도 우리가 RPAREN에 도달 할 때까지는 답변을 알 수 없습니다. 다음 토큰은 l_expression (예 : . 또는 LPAREN)까지 확장 될 수 있으므로 답변을 알지 못할 수도 있습니다.이 경우 우리는 계속 스캔을해야합니다. 우리가 해답을 찾을 때 아무 말도 할 수 없기 때문에 한정된 미리보기가 충분하지 않을 수 있으며이 문법은 - 비록 모호하지는 않지만 - 모든 k에 대한 LR (k)가 아닙니다. (우선 순위 발견 방법도 효과가 없을 것입니다.)

지나치게, call_statement에 대한 문법이 원했던 것이 분명하지 않습니다. 그것이 expression로 시작해야 년부터 argument_list( 시작할 수와 expression는 괄호 될 수 있지만 괄호로 시작하지 않는 다음은 합법적 인 call_statement 될 것이다 그래서 :.

print a(3), value 

원한다면 괜찮습니다.