Это можно сделать, но это некрасиво.
Если бы вы использовали bison, вы могли бы просто использовать парсер GLR, который позволил бы вам справиться с двусмысленностью. (Хотя вам все равно придется что-то делать, чтобы справиться с двусмысленностью, поскольку наивная грамматика неоднозначна.) В противном случае вам придется перепрыгнуть через несколько обручей, чтобы устранить неоднозначность в грамматике. анализируемый с фиксированным просмотром вперед (4 токена), что означает наличие грамматики LALR (1). Эту грамматику можно даже создать механически, поскольку мы знаем, что такое предварительный просмотр, но автоматически созданная грамматика будет довольно раздутой. Выполнение этого вручную утомительно, но результаты немного более управляемы (но все же раздуты).
Суть алгоритма исключения опережающего просмотра состоит в том, чтобы отложить сокращение на k токенов (где k - количество исключаемых опережений). Это делается путем сохранения последних значений k semanti c для каждого нетерминального элемента, чтобы отложенное сокращение имело значения semanti c, необходимые для получения его (отложенного) значения semanti c. К счастью, нам нужно делать это только для продуктов, которые требуют дополнительного просмотра, если мы можем определить, какие это производства. (Нет эффективного алгоритма для этого в целом, и хуже того, если k неизвестно, но часто это более или менее очевидно.)
В этом случае то, что мы в основном хотим Избегайте того, что list, a уменьшается до list, element, а затем до list, прежде чем a получит шанс объединиться со следующим , b. (Нам также нужно избегать уменьшения list, a, b до list, element_multiple, но мы вернемся к этому позже.)
Мы делаем это, создавая нетерминал list plus a, который удерживает list и a. Если за этим нетерминальным будет следовать , b, тогда нам все равно нужно будет придерживаться этого b, что мы и делаем с нетерминальным list plus a plus b.
С другой стороны. стороны, если за list plus a следует (скажем) , c, тогда нам придется сделать эквивалент обратного уменьшения исходного list, a до list, а затем уменьшить это list, c до list.
И есть еще одна возможность, а именно, что за list plus a следует другой a. В этом случае мы сначала уменьшаем задним числом исходные list и a, а затем создаем новые list plus a.
Итак, вот реализация.
Поскольку я никогда использовал GPPG или C#, я написал это на ванильном C, используя bison. Я надеюсь, что все это достаточно базовое c, чтобы вы могли перевести его на свой целевой язык.
Во-первых, (простые) структуры данных:
struct List {
List* prev;
Element elt;
};
struct OneHold {
List* prev;
char held;
};
struct TwoHold {
List* prev;
char held1;
char held2;
};
}
OneHold и TwoHold используются для хранения значений semanti c до тех пор, пока они действительно не понадобятся.
Итак, объявление типа semanti c и грамматика:
%union {
char token;
OneHold one_hold;
TwoHold two_hold;
List* list;
}
%token <token> 'a' 'b' 'c' 'd' 'e' 'f' 'g' 'h' ...
%%
start : expr { print_list($1); putchar('\n'); free_list($1); }
%type <list> expr;
expr : list
| lista { $$ = push_single($1.prev, $1.held); }
| listab { $$ = push_seqab($1.prev, $1.held1, $1.held2); }
%type <list> list;
list : nota { $$ = push_single(NULL, $1); }
| list ',' nota { $$ = push_single($1, $3); }
| lista ',' notab { $$ = push_single(push_single($1.prev, $1.held), $3); }
| listab ',' notac { $$ = push_single(push_seqab($1.prev, $1.held1, $1.held2),
$3);
}
| listab ',' 'c' { $$ = push_seqabc($1.prev, $1.held1, $1.held2, $3); }
%type <one_hold> lista;
lista : 'a' { $$ = (OneHold){ .prev = NULL, .held = $1}; }
| list ',' 'a' { $$ = (OneHold){ .prev = $1, .held = $3}; }
| lista ',' 'a' { $$ = (OneHold){ .prev = push_single($1.prev,
$1.held),
.held = $3};
}
| listab ',' 'a' { $$ = (OneHold){ .prev = push_seqab($1.prev,
$1.held1,
$1.held2),
.held = $3};
}
%type <two_hold> listab;
listab : lista ',' 'b' { $$ = (TwoHold){ .prev = $1.prev,
.held1 = $1.held,
.held2 = $3};
}
%type <token> letter nota notab notac;
letter : 'd' | 'e' | 'f' | 'g' | 'h' ...
nota : 'b' | 'c' | letter
notab : 'c' | letter
notac : 'b' | letter