Recursiva Descendência Parsing - De LL (1) Up

Question

A seguinte "Expressão da calculadora" seguinte (BNF) pode ser facilmente analisada com o analisador de descecente recursivo trivial, que é Preditivo 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+

Porque é sempre o suficiente ver o próximo token para saber a regra para escolher. No entanto, suponha que eu adicione a seguinte regra:

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

Com o objetivo de interagir com a calculadora na linha de comando, com variáveis, como esta:

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

É verdade que não posso usar um pastor preditivo simples (1) para analisar <command> as regras ? Tentei escrever o analisador para isso, mas parece que preciso saber mais tokens para a frente. A solução para usar tracktracking é ou posso implementar LL (2) e sempre procurar dois tokens para a frente?

Como os geradores de analisador RD lidam com esse problema (ANTLR, por exemplo)?

Answer 1

O problema com

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

é quando você "vê" <id> Você não pode dizer se é o começo de uma atribuição (segunda regra) ou é um "<factor>"Você só saberá quando lerá o próximo token.

Afaik Antlr é ll (*) (e também é capaz de gerar analisadores de pacote de rato se não me engano), por isso provavelmente lidará com essa gramática, considerando dois tokens ao mesmo tempo.

Se você puder brincar com a gramática, sugiro adicionar uma palavra -chave para a tarefa (por exemplo let x = 8) :

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

ou use o = Para significar avaliação:

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

Answer 2

Eu acho que existem duas maneiras de resolver isso com um analisador de descida recursiva: usando (mais) lookahead ou por retrocesso.

Olhe para frente

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

Voltando

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

Answer 3

O problema é que a gramática:

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

não é um procedimento mutuamente recursivo. Para um analisador decente recursivo, você precisará determinar um equivalente não recursivo.

O Rdentato Post mostra como consertar isso, assumindo que você pode brincar com a gramática. Este PowerPoint explica o problema com um pouco mais de detalhes e mostra como corrigi -lo:http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3a%2f%2fxml.cs.ncccu.edu.tw%2fcoursessssssos%2fcompiler%2fccu.edu.tw%2fcoursesssessssos mão de b mão 2FCC262fcp262fcp2622fcloresslides%2fclflcomsl. 26topdownparsing.ppt & ei = -yLASPRWGAPHAK5YDCQBQ & USG = AFQJCNGAFRODJXOXKGJEWDMQ8A8594VN0Q & SIG2 = NLYKQVFAKMQY_57137XZRQ

Answer 4

Antlr 3 Usa um analisador "ll (*)" em oposição a um analisador LL (k), para que ele pareça até chegar ao final da entrada, se precisar, sem voltar atrás, usando um autômato finito determinado especialmente otimizado (DFA) .