Что это? Ищете правильную терминологию, что здесь происходит
Рассмотрим следующую грамматику, которая имеет явный недостаток в том, что касается генераторов синтаксического анализатора:
"Start Symbol" = <Foo>
"Case Sensitive" = True
"Character Mapping" = 'Unicode'
{A} = {Digit}
{B} = [abcdefABCDEF]
{C} = {A} + {B}
Integer = {A}+
HexNumber = {C}+
<ContextA> ::= '[' HexNumber ']'
<ContextB> ::= '{' Integer '}'
<Number> ::= <ContextA> | <ContextB>
<Foo> ::= <Number> <Foo>
| <>
Причина, по которой эта грамматика имеет недостатки, заключается в том, что сканер не может различить терминалы [Integer;HexNumber], (Является 1234 целое или шестнадцатеричное число?!).
В продуктах, написанных в этом примере, это становится бесполезным для битов, но могут быть грамматики, где контекст продукций прояснит, ожидается ли целое или шестнадцатеричное число, и сканер все равно откажется сотрудничать.
Таким образом, сканер должен знать состояние анализатора, чтобы иметь возможность принять правильное решение в отношении шестнадцатеричного или целочисленного токена.
Теперь вопрос по терминологии. Что это делает эту... эээ... грамматику? Лексер? затем? Контекстно-зависимый лексер? Или кто-то скажет, что это контекстно-зависимая грамматика, хотя это явно проблема сканера? Используется ли другая терминология для описания таких явлений?
2 ответа
Контекстно-зависимый означает что-то совсем другое.
Если бы вы использовали более формальную нотацию, вы бы увидели, что ваша оригинальная грамматика была неоднозначной, как сказал Игнасио Васкес-Абрамс, и ваша отредактированная грамматика могла бы нормально обрабатываться LR(1) (или даже LL(1)) генератор парсеров. Вот беспроблемная грамматика зубров:
%start number
%%
digit : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
hex : digit
| 'a' | 'b' | 'c' | 'd' | 'e' | 'f'
| 'A' | 'B' | 'C' | 'D' | 'E' | 'F'
decnum: digit | decnum digit
hexnum: hex | hexnum hex
number: '[' decnum ']'
| '{' hexnum '}'
Конечно, для создания сканера не принято использовать зубров, но это, безусловно, возможно.
Я думаю, что проблема, которую вы рассматриваете, заключается в следующем: если мы создадим сканер, используя flex, это будет выглядеть так:
[[:digit:]]+ { yylval.string = strdup(yytext); return DECNUM; }
[[:xdigit:]]+ { yylval.string = strdup(yytext); return HEXNUM; }
Flex не может вернуть неоднозначный токен, поэтому в случае, когда (следующая часть) ввод 1234flex должен возвращать либо DECNUM, либо HEXNUM. Первое самое длинное ("максимальное количество") правило означает, что любой шаблон, который будет первым в гибком определении, победит в случае токена, который может быть проанализирован в любом случае. Это подразумевает, что шаблон DECNUM должен стоять первым, потому что в противном случае он был бы невозможен для запуска (и в этом случае flex выдаст предупреждение).
Но теперь есть небольшая проблема для грамматики, потому что, когда грамматика ожидает HEXNUM, она должна быть готова найти DECNUM. Это не проблема, если грамматика однозначна. Нам нужно создать только пару нетерминалов:
decnum: DECNUM { $$ = strtol($1, NULL, 10); free($1); }
hexnum: DECNUM | HEXNUM { $$ = strtol($1, NULL, 16); free($1); }
Это не создаст двусмысленности или даже конфликта сдвига / уменьшения, который еще не существует в грамматике.
Если вы хотите попробовать это, вам нужно объявить некоторые типы в вашем прологе зубров:
%union {
char* string;
long integer;
}
%token <string> HEXNUM DECNUM
%type <integer> hexnum decnum