Грамматика: различие между вершиной вниз и вверх дном? (Пример)

Question

Грамматика: различие между вершиной вниз и вверх дном? (Пример)

Это - развить вопрос от Грамматики: различие между вершиной вниз и вверх дном?

Я понимаю от того вопроса что:

сама грамматика не является нисходящей или восходящей, синтаксический анализатор
существуют грамматики, которые могут быть проанализированы одним, но не другим
(спасибо гроб Jerry

Таким образом для этой грамматики (все возможные математические формулы):

    E -> E T E
    E -> (E)
    E -> D

    T -> + | - | * | /

    D -> 0
    D -> L G

    G -> G G    
    G -> 0 | L

    L -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Это было бы читаемо вершиной вниз и восходящим синтаксическим анализатором?

Вы могли сказать, что это - вершина вниз грамматика или восходящая грамматика (или ни один)?

Я спрашиваю, потому что у меня есть вопрос о домашней работе, который спрашивает:

"Запишите нисходящие и восходящие грамматики для языка, состоящего из всех..." (различный вопрос)

Я не уверен, может ли это быть корректно, так как кажется, что нет такой вещи как нисходящая и восходящая грамматика. Кто-либо мог разъясниться?

7

grammar topdown bottom-up

задан Community 23 May 2017 в 12:04

1 ответ

Другие вопросы по тегам:

grammar topdown bottom-up

Похожие вопросы:

score 5 · Accepted Answer

Эта грамматика глупа, поскольку объединяет лексирование и синтаксический анализ в одно целое. Но хорошо, это академический пример.

Суть «снизу вверх» и «сверху вниз» заключается в том, что в них есть особые угловые случаи, которые трудно реализовать с обычным 1 взглядом вперед. Думаю, тебе стоит проверить, нет ли у него проблем, и поменять грамматику.

Чтобы понять вашу грамматику, я написал правильный EBNF

expr:
    expr op expr |
    '(' expr ')' |
    number;

op:
    '+' |
    '-' |
    '*' |
    '/';

number:
    '0' |
    digit digits;

digits:
    '0' |
    digit |
    digits digits;

digit:
    '1' | 
    '2' | 
    '3' | 
    '4' | 
    '5' | 
    '6' | 
    '7' | 
    '8' | 
    '9';

Мне особенно не нравится правило цифры: цифры цифры . Непонятно, где начинается первая цифра и заканчивается вторая. Я бы реализовал правило как

digits:
    '0' |
    digit |
    digits digit;

Другая проблема - число: '0' | цифра цифры; Это конфликтует с цифрами: '0' и цифрами: цифра; . По сути, дублируется. Я бы изменил правила на (удаление цифр):

number:
    '0' |
    digit |
    digit zero_digits;

zero_digits:
    zero_digit |
    zero_digits zero_digit;

zero_digit:
    '0' |
    digit;

Это делает грамматику LR1 (леворекурсивной с одним взглядом вперед) и контекстной. Это то, что вы обычно отдаете генератору синтаксического анализатора, например, bison. А поскольку bison находится снизу вверх, это допустимый ввод для парсера снизу вверх.

Для нисходящего подхода, по крайней мере, для рекурсивного приличного, левая рекурсия представляет собой небольшую проблему. Вы можете использовать откат, если хотите, но для этого вам нужна грамматика RR1 (правый рекурсивный взгляд вперед). Для этого поменяйте местами рекурсии:

zero_digits:
    zero_digit |
    zero_digit zero_digits;

Я не уверен, что это ответит на ваш вопрос. Я считаю, что вопрос плохо сформулирован и вводит в заблуждение; а я пишу парсеры зарабатывая на жизнь ...