Я предполагаю, что это какой-то вариант популярного языка "без кофеина", часто используемого во вводных курсах CS.
Мне не совсем понятно, почему CUP сообщает только о двух конфликтах, так как на самом деле есть четыре конфликтав вашей грамматике.Возможно, версия, которую вы вставили, не является версией, сгенерировавшей сообщение об ошибке, которое вы включили в свой вопрос.
Конфликты, о которых сообщается в сообщении об ошибке, являются результатом использования вами правой рекурсии для обоих списков объявлений переменныхи список операторов, которые составляют блок операторов.
Обычная мудрость скажет вам, что правильной рекурсии следует избегать всякий раз, когда это возможно, поскольку она использует неограниченный объем стека синтаксического анализатора.Левая рекурсия, напротив, использует постоянный объем стека синтаксического анализатора.Это хорошее эмпирическое правило, но большую часть времени выбор между левой и правой рекурсией будет продиктован синтаксисом.Так, например, если вы пишете грамматику для арифметических выражений без использования объявлений предшествования, вы будете использовать левую рекурсию для левоассоциативных операторов (а это почти все из них) и правую рекурсию для праворекурсивных операторов (таких как операторы присваивания)в C, C ++ и Java).
Списки элементов обычно могут быть записаны в любом случае, так как они, как правило, будут свернуты в вектор, а не останутся в виде двоичного дерева, поэтому в обычном случае будет оставлена рекурсия:
x_list ::= x_list x_element |
// EMPTY
;
Вы также увидите несколько вариантов вышеуказанного шаблона.Например, если список элементов не может быть пустым, первая продукция будет x_list: x_element.Вам также придется вносить изменения, если элементы должны сопровождаться или отделяться токеном, поэтому вы часто будете видеть такие вещи, как:
// In the language this comes from, statements are *always* followed by
// a semicolon. Most languages don't work that way, though.
statement_list ::= statement_list statement T_SEMICOLON |
// EMPTY
;
// Parameter lists (and argument lists) are either empty or have the items
// *separated* by commas. Because the comma is only present if there are at
// least two items, we need to special-case the empty list:
parameter_list ::= T_OPAREN T_CPAREN |
T_OPAREN parameters T_CPAREN
;
parameters ::= parameter |
parameters T_COMMA parameter
;
Хотя я написал все это как левую рекурсию,Я также мог бы использовать правильную рекурсию в этих конкретных случаях.Но есть небольшая разница между леворекурсивным и праворекурсивным синтаксическим анализом, что также влияет на порядок выполнения действий синтаксического анализатора.Рассмотрим разницу между:
id_list ::= id_list ID | id_list ::= ID id_list |
// EMPTY // EMPTY
; ;
Оба они принимают a b c, но принимают их по-разному: ε •
•3 •3
/ \ / \
•2 c a •2
/ \ / \
•1 b b •1
/ \ / \
ε a c ε
Поскольку синтаксический анализатор является восходящим в обоихВ некоторых случаях действия парсера всегда выполняются, начиная снизу.Это приведет к тому, что первый (леворекурсивный) синтаксический анализатор выполнит действия в порядке ввода, а второй выполнит действия справа налево.
Во всяком случае, возвращаясь к проблеме.По сути, у вас есть следующая грамматика, которая выведет возможно пустую последовательность объявлений, за которой следует возможно пустая последовательность операторов:
StatementBody ::= OBRACE VariableDeclarations Statements CBRACE
VariableDeclarations ::= VariableDeclaration VariableDelarations | // EMPTY
Statements ::= Statement Statements | // EMPTY
Принимая во внимание дерево разбора, полученное выше, оба Statements и Declarations необходимо эффективно завершить с пустым производством.Другими словами, прежде чем парсер сможет сдвинуть первый токен в Statements, он должен уменьшить пустой нетерминал VariableDeclarations.А это значит, что ему нужно точно знать, какой токен будет первым токеном в Statements.
К сожалению, это невозможно, потому что и Statement, и VariableDeclaration могут начинаться с ID.Поэтому, если синтаксический анализатор только что достиг конца VariableDeclaration и токен предпросмотра - ID, он не может определить, следует ли переключиться на синтаксический анализ Statements или продолжить анализ VariableDeclarations.
Примечание.что ситуация не улучшится, если мы изменим оба этих списка на левую рекурсию, потому что в этом случае парсер должен будет уменьшить пустой нетерминал Statements в одной и той же точке.Единственный способ избежать угадывания парсером места вставки пустого нетерминала - поместить оба пустых нетерминала на концах StatementBody.Другими словами, VariableDeclarations должен быть леворекурсивным, чтобы пустой VariableDeclarations был в начале, а Statements должен быть праворекурсивным, чтобы пустой Statements был в конце:
StatementBody ::= OBRACE VariableDeclarations Statements CBRACE
VariableDeclarations ::= VariableDeclarations VariableDelaration | // EMPTY
Statements ::= Statement Statements | // EMPTY
Это не совсем работает, хотя, потому что (по другим причинам) парсер должен знать, анализирует ли он Statement или VariableDeclaration, начиная с ID, посмотрев на токенсразу после ID.И там он столкнется со следующим недетерминизмом:
b [ ] a; // Declaration
b [ 3 ] = a; // Assignment
Эти две возможности невозможно различить, пока не будет замечен третий маркер.Но парсер должен знать один токен ранее, чтобы он мог решить, превратить b в Lvalue.
Разрешение этого конфликта более раздражает.Я считаю, что обычный подход заключается в том, чтобы заставить лексический сканер выполнять работу, возвращая [ ] как один токен.Конечно, это решает проблему - с этим изменением одна открытая скобка всегда означает, что анализатор смотрит на выражение, в то время как пара [ ] всегда означает объявление.Но это неудобно в сканере;в частности, сканер должен иметь возможность обрабатывать что-то вроде
[ /* A comment */
/* Another comment */ ]
как один [ ] токен.(Мы надеемся, что никто не будет писать такой код, но он допустим.)
И это приводит нас к третьему конфликту с уменьшением сдвига, который является результатом различия между точечными присваиваниями и точечными вызовами:
a . b ( 3 ) ;
a . b = 3 ;
Это гораздо более простая проблема, и ее можно решить, внимательно посмотрев на справочную грамматику для Decaf.С вашей грамматикой, вызов должен соответствовать производственному ID DOT ID OPAREN ..., в то время как назначение будет соответствовать Lvalue DOT ID.Другими словами, когда DOT - это запрос, анализатор должен решить, следует ли уменьшить a до Lvalue.Этого можно избежать, сделав две правые стороны более похожими.