Грамматика: разница между сверху вниз и снизу вверх? (Пример)

Question

Это следующий вопрос из грамматики: разница между сверху вниз и снизу вверх?

Из этого вопроса я понимаю, что:

• сама грамматика не сверху вниз или снизу вверх, парсер
• Есть грамматики, которые могут быть проанализированы одним, но не другим
• (спасибо Джерри Коффин

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

    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 

Будет ли это читаться парсером сверху вниз и снизу вверх?

Не могли бы вы сказать, что это грамматика сверху вниз или грамматика снизу вверх (или нет)?

---

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

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

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

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: digits digits, Неясно, где начинаются первые цифры, а заканчиваются вторые. Я бы реализовал правило как

digits:
    '0' |
    digit |
    digits digit;

Другая проблема number: '0' | digit digits; Это конфликтует с digits: '0' а также digits: digit;, На самом деле это дублируется. Я бы изменил правила на (удаление цифр):

number:
    '0' |
    digit |
    digit zero_digits;

zero_digits:
    zero_digit |
    zero_digits zero_digit;

zero_digit:
    '0' |
    digit;

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

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

zero_digits:
    zero_digit |
    zero_digit zero_digits;

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