재귀 적 하강 대 재귀 적 상승 파싱

Question

내 자신 만의 사용자 정의 파서를 작성하는 경우 재귀 적 상승 파서를 작성하고 있는지 어떻게 알 수 있습니까? 나는 확실히 LALR 구문 분석의 O (n) 복잡성에 관심이 있으며 (필자는 이미 LALR 문법을 가지고있다.) 나중에 LL 파서를 대신 작성했다는 것을 알기를 원하지 않는다.

편집 : 필자는 자동 테이블 구동 파서 만 보았고 한 쌍의 간단한 예제 재귀 파서를 만들었습니다. 아무 것도 원격으로 손으로 구성 할 수있는 것처럼 보이지 않았습니다. 따라서 실제 알고리즘을 가진 규칙을 다루기 위해 "명백한"코드를 연관시키는 것은 다소 어렵습니다. 나는 매우 왼쪽 또는 그것에 대해 바로 거기에 아무것도

std::vector<std::wstring> RecursiveParseNameOrQualifiedName(Iterator& begin, Iterator end) { 
    std::vector<std::wstring> retval; 
    retval.push_back(begin->Codepoints); 
    CheckedIncrement(begin, end); // The only place that can legitimately expect end of input is namespace contents. 
    while(begin->type == Wide::Lexer::TokenType::Dot) { 
     CheckedIncrement(begin, end); 
     if (begin->type != Wide::Lexer::TokenType::Identifier) 
      Wide::ParserExceptionBuilder(*begin) << L"Expected 'identifier' after '.'"; 
     retval.push_back(begin->Codepoints); 
    } 
    return retval; 
} 

로 번역 한 예를

name_or_qualified_name = identifier *('.' identifier); 

에 대한

당신이 비교적 간단한 규칙의 코드를 가지고가는 경우. 그것은 분명히 유용하고 중요한 정보입니다. 나는 그것을보고 있지 않습니다. 여기에서 유일한 명백한 사실은 재귀 적이라는 것입니다.

편집 : 죄송합니다. 나쁜 예입니다. 어때 이런 식으로 :

void RecursiveParseUsing(Iterator& begin, Iterator end, Wide::Parser::NamespaceAST* current_namespace) { 
    auto new_using = std::unique_ptr<Wide::Parser::UsingAST>(new Wide::Parser::UsingAST()); 
    // expect "begin" to point to a using 
    CheckedIncrement(begin, end); 
    // Must be an identifier, at least 
    if (begin->type != Wide::Lexer::TokenType::Identifier) 
     Wide::ParserExceptionBuilder(*begin) << L"Expected 'identifier' after 'using'"; 
    CheckedIncrement(begin, end); 
    switch(begin->type) { 
    case Wide::Lexer::TokenType::Dot: { 
     begin--; // back to identifier 
     new_using->original_name = RecursiveParseNameOrQualifiedName(begin, end); 
     current_namespace->unnamed_contents.push_back(std::move(new_using)); 
     break; } 
    case Wide::Lexer::TokenType::Equals: { 
     begin--; // back to Identifier 
     new_using->new_name = begin->Codepoints; 
     begin++; // Back to equals 
     begin++; // The token ahead of equals- should be "identifier" 
     new_using->original_name = RecursiveParseNameOrQualifiedName(begin, end); // The only valid next production 
     // this should be left at the one past the name 
     current_namespace->contents[new_using->new_name] = std::move(new_using); 
     break; } 
    case Wide::Lexer::TokenType::Semicolon: { 
     begin--; // Identifier 
     new_using->original_name.push_back(begin->Codepoints); 
     begin++; // Semicolon 
     current_namespace->unnamed_contents.push_back(std::move(new_using)); 
     break; } 
    default: 
     Wide::ParserExceptionBuilder(*begin) << L"Expected '.', '=' or ';' after 'identifier' when parsing 'using'."; 
    } 
    if (begin->type != Wide::Lexer::TokenType::Semicolon) 
     Wide::ParserExceptionBuilder(*begin) << L"Expected ';' after 'identifier'"; 
    CheckedIncrement(begin, end); // One-past-the-end 
} 

Answer 1

LL 및 LALR 모두 O (n)이므로 중요하지 않습니다.

그러나 모든 재귀 적 파서는 LL이 아닙니다. 그것들은 한 번의 생산을 시도하는 어떤 형태의 역 추적을 사용하지 않고 가능한 모든 생산이 다 소모되거나 성공적인 분석이 발견 될 때까지 다른 생산을 시도하는 것이 효과가 없을 때 –을 사용합니다.

LL 또는 LALR 파서 –을 작성하는지 여부를 어떻게 알 수 있느냐에 따라 수행중인 구성 방법을 알고 있어야합니다.

편집 추가 : 재귀 적 강하와 재귀 상승 사이의 한 가지 특징은 절차의 역할입니다. 재귀 적 강하에는 각 비 터미널마다 절차가 있습니다. 재귀 상승에서 각 LR 상태에 대한 절차가 있습니다. 후자를 가지려면 미리 LR 자동 장치를 구성해야합니다 (이 작업을 너무 자주 수행하지 않으면 즉시 수행 할 수 있습니다. –).이 경우에는이 질문을하지 않아도됩니다. 첫 번째 코드 예제는 재귀 적 디센트처럼 보입니다. 두 번째 코드 샘플이 문법과 어떻게 관련되어 있는지 알려주지 않으므로 알려주지 않습니다.