Действия Midrule (MRA) заставляют синтаксический анализатор принимать ранние решения по синтаксическому анализу.В этом случае, например, парсер должен выполнить MRA до while в do ... while, но когда он видит while, слишком рано знать, завершает ли этот while команды doили запускает команду while.
Без MRA нет проблем (возможно, в зависимости от остальной части вашей грамматики), поскольку он может продолжать сдвигать токены, пока не увидит либо do, либо enddo.
Следует избегать MRA, если в этом нет крайней необходимости.[Примечание 1] В большинстве случаев, когда MRA кажутся заманчивыми, оказывается, что вы пытаетесь сделать слишком много внутри синтаксического анализатора.Часто лучше ограничить синтаксический анализатор созданием абстрактного синтаксического дерева (AST) или созданием сегментов трехадресного кода (TAC) в базовых блоках внутри структуры графа потока управления, а не в виде монолитного массива команд.[Примечание 2] Эти промежуточные структуры данных упрощают базовые алгоритмы (такие как заполнение целей ветвления) и являются основой для множества более сложных и чрезвычайно полезных алгоритмов, которые производят более быстрый и меньший код.(Обычное исключение подвыражений, устранение мертвого кода, постоянное свертывание и т. Д. И т. Д.)
Но даже если вы решили использовать подход, который, кажется, выигрывает от MRA, вы обнаружите, что он частоЛучше избегать их, перемещая действия в нетерминал, которому они следуют, или используя явный маркер нетерминал (то есть пустой нетерминал, единственная цель которого состоит в том, чтобы выполнить действие).Эти стратегии часто создают более читаемые грамматики, и во многих случаях, в том числе и в этой, реорганизация решает конфликты уменьшения-уменьшения.
Бизон эффективно превращает MRA в маркеры - вы можете увидеть это в отчете по грамматикес опцией -v - но истинные маркеры имеют то преимущество, что их можно использовать более одного раза.В отличие от этого, каждый MRA отличается (в реализации зубров), даже если действия идентичны по символам.Например, в упрощенной грамматике в вашем вопросе bison генерирует девять различных нетерминалов маркера, все с одним и тем же действием: {std::cout<<"D";}.В результате бизон жалуется на конфликт «уменьшить-уменьшить», потому что он не может выбрать между двумя разными маркерами, которые оба делают одно и то же.Очевидно, что в этом случае нет основного конфликта, и замена действия явным маркером позволит полностью избежать проблемы, не требуя серьезной операции.
Например, вот очень упрощенная грамматика, которая (непосредственно) создает трикодОбратите внимание на использование маркера new-label, который вставляет метку (и имеет номер метки в качестве семантического значения):
%{
#include <stdarg.h>
#include <stdio.h>
void yyerror(const char*);
int yylex(void);
int pc = 0; /* Program counter */
int label = 0; /* Current label */
int temp = 0; /* Current temporary variable */
void emit_label(int n) { printf("%10s_L%d:\n", "", n); }
void emit_stmt(const char* fmt, ...) {
va_list ap;
va_start(ap, fmt);
printf("/* %3d */\t", pc++);
vprintf(fmt, ap);
putchar('\n');
va_end(ap);
}
%}
%token T_DO "do" T_ENDDO "enddo" T_ENDWHILE "endwhile" T_WHILE "while"
%token ID NUMBER
%%
program
: statements
/* Inserts a label.
* The semantic value is the number of the label.
*/
new-label
: %empty { $$ = label++; emit_label($$); }
/* Parses a series of statements as a block, preceded by a label
* The semantic value is the label preceding the block.
*/
statements
: new-label
| statements statement
statement
: while-statement
| do-statement
| assign-statement
assign-statement
: ID '=' expr { emit_stmt("%c = _t%d", $1, $3); }
while-statement
: new-label "while" condition-jump-if-false "do" statements "endwhile"
{ emit_stmt("JUMP _L%d", $1, 0); emit_label($3); }
do-statement
: "do" statements new-label "while" condition-jump-if-false "enddo"
{ emit_stmt("JUMP _L%d", $2, 0); emit_label($5); }
/* Semantic value is the label which will be branched to if the condition
* evaluates to false.
*/
condition-jump-if-false
: compare { $$ = label++; emit_stmt("IFZ _t%d, _L%d", $1, $$); }
compare
: expr '<' expr { $$ = temp++; emit_stmt("_t%d = _t%d < _t%d", $$, $1, $3); }
expr: term
| expr '+' term { $$ = temp++; emit_stmt("_t%d = _t%d + _t%d", $$, $1, $3); }
term: factor
| term '*' factor { $$ = temp++; emit_stmt("_t%d = _t%d * _t%d", $$, $1, $3); }
factor
: ID { $$ = temp++; emit_stmt("_t%d = %c", $$, $1); }
| NUMBER { $$ = temp++; emit_stmt("_t%d = %d", $$, $1); }
| '(' expr ')' { $$ = $2; }
Этот код создает больше меток, чем ему действительно нужно.Архитектура прямого вывода заставляет печатать эти метки, но что действительно важно, так это то, что позиция в сгенерированном коде сохраняется как семантическое значение нетерминала (возможно), представляющего заголовок базового блока.Постоянное выполнение этого означает, что конечные действия имеют доступ к необходимой информации.
Стоит отметить тот факт, что маркер new-label используется перед обоими экземплярами while.Только в одном случае метка, которую он создает, действительно необходима, но невозможно определить, какая продукция в конечном итоге будет успешной.
Приведенный выше код не совсем удовлетворителен по ряду причин.Для начала, поскольку он настаивает на немедленном выписывании каждой строки, невозможно вставить заполнитель для оператора перехода.Следовательно, маркер, который вставляет условные переходы, всегда переходит вперед (то есть он компилирует переход к метке, которая еще не была определена), в результате чего конечный тест выполняется, в то время как конструкция заканчивается кодом, подобным (source: ... do ... while a < 3 enddo)
_L4:
/* ... Loop body omitted */
/* 23 */ _t16 = a
/* 24 */ _t17 = 3
/* 25 */ _t18 = _t16 < _t17
/* 26 */ IFZ _t18, _L6
/* 27 */ JUMP _L4
_L6:
вместо чуть более эффективного
_L4:
/* ... Loop body omitted */
/* 23 */ _t16 = a
/* 24 */ _t17 = 3
/* 25 */ _t18 = _t16 < _t17
/* 26 */ IFNZ _t18, _L4
Это можно исправить, сохранив TAC в массиве, а не распечатав его, а затем добавив метки в ветви.(Это изменение на самом деле не влияет на грамматику, потому что все это делается в финальных действиях.) Но было бы сложнее реализовать классическую предтестовую оптимизацию, которая превращает:
_L1:
/* 2 */ _t1 = a
/* 3 */ _t2 = 0
/* 4 */ _t3 = _t1 < _t2
/* 5 */ IFZ _t3, _L2
/* ... Loop body omitted */
/* 14 */ JUMP _L1
в
_L1:
/* 2 */ JUMP _L2
/* ... Loop body omitted */
_L2:
/* 12 */ _t1 = a
/* 13 */ _t2 = 0
/* 14 */ _t3 = _t1 < _t2
/* 15 */ IFNZ _t3, _L1
(Переупорядочивание базовых блоков часто позволяет сохранить ветви; в целом, проще вывести базовые блоки в оптимальном порядке, чем строить их в текстовом порядке, а затем перемещать их.)
Примечания
MRA, конечно, не должны использоваться для попыток отследить синтаксический анализатор, поскольку (как в этом случае) они существенно меняют природу синтаксического анализа.Если вы хотите отследить ваш анализатор, выполните действия, описанные в разделе руководства для зубров, по трассировочным анализам (и прочитайте оставшуюся часть главы об отладке синтаксических анализаторов.)
Стиль создания TAC с помощью операторов печати восходит к тем ранним дням вычислений, когда память была настолько дорогой и настолько ограниченной, что компиляцию приходилось выполнять в несколько этапов, каждый из которых записывал свой результат во «внешнее хранилище» (например, на бумажную ленту).), чтобы его можно было последовательно прочитать для следующего прохода.Подавляющее большинство настоящих программистов еще не родились, когда этот стиль написания компиляторов перестал быть необходимым, но удивительное количество учебных ресурсов все еще начинаются, сознательно или нет, с этой базовой архитектуры.Браузер, который вы используете для чтения этого ответа, без колебаний использует два гигабайта (виртуальной памяти) для его отображения.В этом контексте кажется глупым беспокоиться об использовании нескольких сотен килобайт временного хранилища для хранения AST при компиляции программы на том же компьютере.