Грамматика: разница между сверху вниз и снизу вверх? (Пример) - PullRequest
Новая
       38

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

7 голосов
/ 06 июля 2010

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

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

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

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

    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

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

Может лиВы говорите, что это грамматика сверху вниз или грамматика снизу вверх (или ни то, ни другое)?

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

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

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

1 Ответ

5 голосов
/ 21 июля 2010

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

С нижними и нижними частями дело в том, что у него есть специальные угловые шкафы, которые трудно реализовать при обычном взгляде. Я, наверное, думаю, что вам следует проверить, есть ли у него проблемы, и изменить грамматику.

Чтобы понять вашу грамматику, я написал правильный 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;

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

...