Это правда;Нелегко найти примеры грамматик выражений, которые разрешают неоднозначность, не используя объявления приоритетов.Возможно, это связано с тем, что декларации предшествования в данном конкретном случае использования чрезвычайно удобны и, вероятно, более удобочитаемы, чем написание однозначной грамматикиРезультирующий синтаксический анализатор обычно также немного более эффективен, потому что он избегает цепочек сокращений единиц, наложенных обычным однозначным стилем грамматики.
Обратная сторона этого удобства состоит в том, что это не помогает ученику достичьпонимание того, как на самом деле работают грамматики, и без этого понимания очень трудно применить декларации предшествования к менее четким приложениям.Таким образом, упражнение, которое породило этот вопрос, безусловно, стоит.
В одном месте вы найдете грамматики однозначных выражений в спецификациях (некоторых) языков программирования, поскольку однозначная грамматика не зависит от точной природыалгоритм, используемый генераторами синтаксических анализаторов для разрешения конфликтов синтаксического анализа.Эти примеры, как правило, довольно сложны, потому что в реальных языках программирования обычно много операторов.Тем не менее, пример грамматики C в каталоге примеров jison показывает стандартную модель грамматик арифметических выражений.Следующий фрагмент значительно упрощен, но большинство произведений просто скопированы и вставлены из оригинала.(Я удалил много операторов, большинство уровней приоритета и некоторые сложности, связанные с такими вещами, как выражения приведения и особенный оператор запятой, которые, безусловно, здесь не актуальны.)
primary_expression
: IDENTIFIER
| CONSTANT
| '(' expression ')'
;
postfix_expression
: primary_expression
| postfix_expression INC_OP
| postfix_expression DEC_OP
;
unary_expression
: postfix_expression
| '-' unary_expression
| INC_OP unary_expression
| DEC_OP unary_expression
;
/* I added this for explanatory purposes. DO NOT USE IT. See the text. */
exponential_expression
: unary_expression
| unary_expression '^' exponential_expression
multiplicative_expression
: exponential_expression
| multiplicative_expression '*' exponential_expression
| multiplicative_expression '/' exponential_expression
| multiplicative_expression '%' exponential_expression
;
additive_expression
: multiplicative_expression
| additive_expression '+' multiplicative_expression
| additive_expression '-' multiplicative_expression
;
expression
: additive_expression
;
C не имеетоператор возведения в степень, поэтому я добавил оператор с правильной ассоциативностью и более высоким приоритетом, чем умножение, что будет служить для пояснительных целей.Однако, ваше задание, вероятно, хочет, чтобы оно также имело более высокий приоритет, чем унарное отрицание, чего я не делал.Поэтому я не рекомендую использовать вышеупомянутое напрямую.
В вышеприведенной модели следует отметить, что каждый уровень приоритета соответствует нетерминалу.Эти нетерминалы связаны в упорядоченную цепочку, используя единичные производства.Мы можем видеть эту последовательность:
выражение ⇒ аддитивное_выражение ⇒ мультипликативное_выражение ⇒ экспоненциальное_выражение ⇒ унарное_выражение ⇒ postfix_expression ⇒ primary_expression
, которое соответствует * порядку старшинства этой грамматики.*
Другим интересным аспектом грамматики является то, что левоассоциативные операторы (все они, кроме возведения в степень) реализованы с леворекурсивными производствами, в то время как правоассоциативные операторы реализованы с праворекурсивным производством.Это не совпадение.
Это базовая модель, но стоит потратить несколько минут, чтобы попытаться понять, как она на самом деле работает, потому что она оказывается довольно простой.Давайте посмотрим на одно производство для умножения и посмотрим, сможем ли мы понять, почему это означает, что возведение в степень связывается более тесно, а сложение - менее плотно:
multiplicative_expression: multiplicative_expression '*' exponential_expression
Это производство говорит, что multiplicative_expression состоит* с multiplicative_expression слева и exponential_expression справа.
Теперь, что это значит для 2 + 3 * 4 ^ 2?2 + 3 - это additive_expression, но из цепочки единичных производств видно, что multiplicative_expression не производит additive_expression.Таким образом, грамматика не включает в себя возможность того, что 2 + 3 - это фраза, соответствующая левой стороне *.Тем не менее, вполне законно, что 3 (CONSTANT, то есть primary_expression) анализируется как левый операнд умножения.
Между тем, 4 ^ 2 является exponential_expression, и наше производство ясно указывает, что exponential_expression может быть сопоставлено справа от *.
A simiАргумент lar, исследующий сложение и экспоненциальное выражение выражений, показал бы, что 3 * 4 ^ 2 (a multiplicative_expression) может находиться справа от оператора +, в то время как ни 2 + 3 * 4 (additive_expression) или 3 * 4 (a multiplicative_expression) могут находиться в левой части оператора возведения в степень.
Другими словами, эта простая грамматика точно и однозначно определяет, каким должно быть выражениеразлагаются.Существует только одно возможное дерево разбора:
expression
|
add
|
+--------+----------------+
| | |
| | mult
| | |
| | +-------+---------------+
| | | | |
| | | | power
| | | | |
| | | | +-------+-------+
| | | | | | |
add | mult | unary | power
... | ... | ... | ...
| | | | | | |
primary | primary | primary | primary
| | | | | | |
2 + 3 * 4 ^ 2
Надеюсь, это поможет.