9

次の単純な「電卓式」文法（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

<command>単純なLL（1）予測パーサーを使用してルールを解析できないというのは本当ですか？そのためのパーサーを作成しようとしましたが、今後さらにトークンを知る必要があるようです。バックトラッキングを使用するソリューションですか、それともLL（2）を実装して、常に2つのトークンを先読みすることができますか？

RDパーサジェネレータがこの問題を処理する方法（たとえば、ANTLR）？

4

4 に答える 4

7

の問題

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

つまり、「見た」とき<id>、それが代入の始まりなのか (2​​ 番目の規則) なのか、" <factor>" なのかわかりません。次のトークンをいつ読み取るかだけがわかります。

AFAIK ANTLR は LL(*) です (私が間違っていなければ、rat-pack パーサーも生成できます) ため、一度に 2 つのトークンを考慮してこの文法を処理する可能性があります。

文法で遊ぶことができる場合は、割り当てにキーワードを追加することをお勧めします (例: let x = 8) :

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

または を使用し=て評価を示します。

<command>   :=  "=" <expr>
            |   <id> "=" <expr>
于 2008-09-24T17:58:02.943 に答える
5

再帰下降パーサーを使用してこれを解決するには、2つの方法があると思います。1つは（もっと）先読みを使用する方法、もう1つはバックトラックを使用する方法です。

先のことを考える

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();
    }
}
于 2010-10-13T11:06:09.073 に答える
2

問題は、文法が次のとおりであることです。


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

相互再帰的な手続きではありません。再帰的なまともなパーサーの場合、非再帰的なパーサーを決定する必要があります。

rdentato の投稿では、文法をいじることができると仮定して、これを修正する方法を示しています。このパワーポイントでは、問題をもう少し詳しく説明し、修正方法を示しています: http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3A%2F%2Fxml.cs. nccu.edu.tw%2Fcourses%2Fcompiler%2Fcp2006%2Fslides%2Flec3-Parsing%26TopDownParsing.ppt&ei=-YLaSPrWGaPwhAK5ydCqBQ&usg=AFQjCNGAFrODJxoxkgJEwDMQ8A8594vn0Q&sig2=nlYKQVfakmqy_57137XzQr

于 2008-09-24T17:50:49.653 に答える
1

ANTLR 3は、LL（k）パーサーではなく、「LL（*）」パーサーを使用するため、特別に最適化された決定性有限オートマトン（ DFA）。

于 2008-09-24T18:05:25.217 に答える