재귀 하강 파싱 - LL (1) UP에서

Question

다음과 같은 간단한 "계산기 표현"문법 (BNF)은 예측 LL (1) 인 사소한 재귀 사구 파서와 쉽게 구문 분석 할 수 있습니다.

<expr>      :=  <term> + <term>
            |   <term> - <term>
            |   <term>
<term>      :=  <factor> * <factor>
                <factor> / <factor>
                <factor>
<factor>    :=  <number>
            |   <id>
            |   ( <expr> )
<number>    :=  \d+
<id>        :=  [a-zA-Z_]\w+

선택해야 할 규칙을 알기 위해 다음 토큰을 보는 것으로 항상 충분하기 때문입니다. 그러나 다음 규칙을 추가한다고 가정합니다.

<command>   :=  <expr>
            |   <id> = <expr>

명령 줄의 계산기와 상호 작용하기 위해 다음과 같은 변수와 함께.

calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49

간단한 LL (1) 예측 파서를 구문 분석 할 수 없다는 것이 사실입니까? <command> 규칙? 파서를 쓰려고했지만 더 많은 토큰을 알아야 할 것 같습니다. 역 추적을 사용하는 솔루션입니까, 아니면 LL (2)을 구현하고 항상 두 개의 토큰을 앞으로 볼 수 있습니까?

Parser Generator 가이 문제를 처리하는 방법 (예 : ANTLR)?

Answer 1

문제

<command>   :=  <expr>
            |   <id> = <expr>

당신이 "볼 때" <id> 당신은 그것이 할당의 시작인지 (두 번째 규칙) 또는 ""인지 알 수 없습니다.<factor>". 당신은 다음 토큰을 읽을 때만 알게 될 것입니다.

Afaik Antlr은 ll (*)입니다 (실수하지 않으면 쥐 팩 파서를 생성 할 수 있습니다). 따라서 두 개의 토큰을 한 번에 고려 하여이 문법을 처리 할 것입니다.

문법으로 연주 할 수 있다면 과제에 대한 키워드를 추가하는 것이 좋습니다 (예 : let x = 8) :

<command>   :=  <expr>
            |   "let" <id> "=" <expr>

또는 사용하십시오 = 평가를 의미하려면 :

<command>   :=  "=" <expr>
            |   <id> "=" <expr>

Answer 2

재귀 적 출신 파서로이를 해결하는 방법에는 두 가지가 있다고 생각합니다.

봐

command() {
    if (currentToken() == id && lookaheadToken() == '=') {
        return assignment();
    } else {
        return expr();
    }
}

역 추적

command() {
    savedLocation = scanLocation();
    if (accept( id )) {
         identifier = acceptedTokenValue();
         if (!accept( '=' )) {
             setScanLocation( savedLocation );
             return expr();
         }
         return new assignment( identifier, expr() );
    } else {
         return expr();
    }
}

Answer 3

문제는 문법입니다.

<command>   :=  <expr>
            |   <id> = <expr>

상호 추방 절차가 아닙니다. 재귀 적 괜찮은 파서를 위해서는 비수체 동등한 동등한 것을 결정해야합니다.

Rdentato Post의 문법으로 연주 할 수 있다고 가정 할 때이 문제를 해결하는 방법을 보여줍니다. 이 PowerPoint는 문제를 좀 더 자세히 설명하고 수정 방법을 보여줍니다.http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3A%2F%2FXML.cs.ncccu.edu.tw%2fcourses%2Fcompiler%2FCP2006%2FFslides%2FLEC3-PARSURTENT 26topdownparsing.ppt & ei = -ylasprwgapwhak5ydcqbq & usg = afqjcngafrodjxoxkgjewdmq8a8594vn0q & sig2 = nlykqvfakmqy_57137xzrq

Answer 4

antlr 3 LL (k) 파서와는 달리 "ll (*)"파서를 사용하므로, 특별 최적화 된 결정적인 유한 automata (DFA)를 사용하여 배송없이 입력의 끝에 도달 할 때까지 미리 살펴 봅니다. .