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

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 (леворекурсивной с одним просмотром вперед) и контекстно-свободной.Это то, что вы обычно передаете генератору синтаксического анализатора, такому как Bison.А поскольку Bison работает снизу вверх, это допустимый вход для парсера снизу вверх.

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

zero_digits:
    zero_digit |
    zero_digit zero_digits;

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