Разбор рекурсивного спуска - от LL (1) и выше - PullRequest
Новая
       27

Разбор рекурсивного спуска - от LL (1) и выше

8 голосов
/ 24 сентября 2008

Следующая простая грамматика «выражения калькулятора» (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) и всегда смотреть на два токена вперед?

Как генераторы синтаксических анализаторов RD справляются с этой проблемой (например, ANTLR)?

Ответы [ 4 ]

6 голосов
/ 24 сентября 2008

проблема с 

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

заключается в том, что когда вы «видите» <id>, вы не можете сказать, является ли это началом назначения (второе правило) или это «<factor>». Вы узнаете только когда прочитаете следующий токен.

AFAIK ANTLR - это LL (*) (и, если я не ошибаюсь, он также может генерировать парсеры из rat-pack), поэтому он, вероятно, будет обрабатывать эту грамматику с учетом двух токенов одновременно.

Если вы можете поиграть с грамматикой, я бы предложил добавить ключевое слово для назначения (например, let x = 8): 

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

или используйте = для обозначения оценки: 

<command>   :=  "=" <expr>
            |   <id> "=" <expr>
5 голосов
/ 13 октября 2010

Я думаю, что есть два способа решить эту проблему с помощью синтаксического анализатора рекурсивного спуска: либо используя (больше) lookahead, либо возвращаясь назад.

Lookahead 

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();
    }
}
2 голосов
/ 24 сентября 2008

Проблема в том, что грамматика: 


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

не является взаимно-рекурсивной процедурой. Для рекурсивного приличного парсера вам нужно определить нерекурсивный эквивалент.

В посте rdentato показано, как это исправить, при условии, что вы можете играть с грамматикой. Это powerpoint описывает проблему более подробно и показывает, как ее исправить: 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_57137XzrQ

1 голос
/ 24 сентября 2008

ANTLR 3 использует синтаксический анализатор "LL (*)" в отличие от синтаксического анализатора LL (k), поэтому он будет смотреть вперед, пока не достигнет конца ввода, без необходимости возврата , используя специально оптимизированные детерминированные конечные автоматы (DFA).

...