Что это? Ищу правильную терминологию, что здесь происходит

Глядя на следующую грамматику, которая имеет очевидный недостаток в отношении генераторов синтаксических анализаторов:

"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 целым или шестнадцатеричным числом?!).

В продуктах, написанных в этом примере, это становится неактуальным для битов, но могут быть грамматики, где контекст продуктов уточняет, ожидается ли целое или шестнадцатеричное число, и сканер все равно отказывается сотрудничать.

Таким образом, сканеру необходимо знать состояние синтаксического анализатора, чтобы иметь возможность принять правильное решение относительно шестнадцатеричного или целочисленного токена.

Теперь вопрос по терминологии. Что это делает с этой... эээ... грамматикой? Лексер? тогда? Контекстно-зависимый лексер? Или можно сказать, что это контекстно-зависимая грамматика, хотя это явно проблема сканера? Используются ли другие термины для описания таких явлений?


grammar terminology lexical-analysis chomsky-hierarchy
person BitTickler    schedule 16.05.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Контекстно-зависимый означает совсем другое.

Если бы вы использовали более формальную нотацию, вы бы увидели, что ваша исходная грамматика была неоднозначной, как сказал Игнасио Васкес-Абрамс, и ваша отредактированная грамматика могла бы нормально обрабатываться 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 не может возвращать неоднозначный токен, поэтому в случае, когда (следующая часть) ввода равна 1234, flex должен возвращать либо DECNUM, либо HEXNUM. Первое самое длинное («максимальное количество») правило означает, что шаблон, стоящий первым в определении flex, будет иметь преимущество в случае токена, который можно проанализировать любым способом. Это означает, что шаблон DECNUM должен быть первым, потому что в противном случае он не сможет сработать (и в этом случае flex выдаст предупреждение).

Но теперь есть небольшая проблема с грамматикой, потому что, когда грамматика ожидает HEXNUM, она должна быть готова найти DECNUM. Это не проблема, при условии, что грамматика недвусмысленна. Нам нужно только создать пару нетерминалов:

decnum: DECNUM           { $$ = strtol($1, NULL, 10); free($1); }
hexnum: DECNUM | HEXNUM  { $$ = strtol($1, NULL, 16); free($1); }

Это не создаст двусмысленности или даже конфликта сдвиг/свертка, которого еще нет в грамматике.

Если вы хотите попробовать это, вам нужно объявить некоторые типы в прологе bison:

%union {
   char* string;
   long  integer;
}
%token <string> HEXNUM DECNUM
%type <integer> hexnum decnum
person rici    schedule 16.05.2015
comment
Менее формальная нотация, которую я использовал, оказалась грамматикой, которую использует синтаксический анализатор GOLD. Преимущество GOLD в том, что вы можете написать грамматику и напрямую протестировать ее без какого-либо кодирования. Ваше исправление интересно. Тем не менее, это по-прежнему оставляет открытым вопрос, какой будет терминология для этого: «жесткий сканер»? :) Между прочим, я столкнулся с этой проблемой, когда писал грамматику для парсера PGN. Примечание 2. Я немного надеялся, что кто-нибудь упомянет систему генератора парсеров, которая использует другой подход к взаимодействию сканера и парсера. - person BitTickler; 16.05.2015
comment
@BitTickler: я недостаточно знаю о PGN, чтобы оказать какую-либо помощь. Альтернативой архитектуре парсер/сканер является так называемая модель без сканера. Google найдет вам миллион ссылок, многие из которых состоят из очень эмоциональных аргументов. (Лично я не фанат, но все работает.) Как правило, парсеры без сканера можно сделать однозначными, но они редко LR(1) и часто даже не LR(ограниченные), так что в некоторых контекстах терминология будет быть не LR(k) (т.е. все еще поддающимся анализу парсером GLR)... - person rici; 16.05.2015
comment
@BitTickler: ... Когда у вас возникают проблемы с интерфейсом сканера/парсера, это часто происходит из-за того, что у вас есть не простой язык, а скорее составной язык (например, регулярные выражения, встроенные в awk; токенизация регулярных выражений не совместим с токенизацией окружающего языка.). Языковая композиция — это еще один термин, который можно найти в Google, и еще один случай, когда синтаксический анализ без сканера позиционируется как (или часто) решение. Гибкое решение — это начальные условия, что является еще одним методом композиции. - person rici; 16.05.2015

arrow_upward
0
arrow_downward

Эта грамматика может быть описана как неоднозначная.

person Ignacio Vazquez-Abrams    schedule 16.05.2015
comment
Хм... учитывая грамматику, которая различает, какой токен может произойти (не удосужился написать рассматриваемый пример), грамматика не будет двусмысленной, и единственная причина, по которой это не сработает, будет заключаться в том, что используется сканер - в отличие от к бессканерному разбору. Может быть, мне следует отредактировать грамматику, чтобы сделать ее более очевидной. - person BitTickler; 16.05.2015