Bison: необязательные токены в одном правиле

Я использую GNU Bison 2.4.2 для написания грамматики для нового языка, над которым я работаю, и у меня есть вопрос. Когда я указываю правило, скажем:

statement : T_CLASS T_IDENT  '{' T_CLASS_MEMBERS '}' {
           // create a node for the statement ...
}

Если у меня есть вариант правила, например

statement : T_CLASS T_IDENT T_EXTENDS T_IDENT_LIST  '{' T_CLASS_MEMBERS '}' {
           // create a node for the statement ...
}

Где (из правил гибкого сканера):

"class"                     return T_CLASS;
"extends"                   return T_EXTENDS;
[a-zA-Z\_][a-zA-Z0-9\_]*    return T_IDENT;

(а T_IDENT_LIST — это правило для идентификаторов, разделенных запятыми).

Есть ли способ указать все это только в одном правиле, установив каким-то образом "T_EXTENDS T_IDENT_LIST" как необязательный? я уже пробовал с

 T_CLASS T_IDENT (T_EXTENDS T_IDENT_LIST)? '{' T_CLASS_MEMBERS '}' {
     // create a node for the statement ...
 }

Но Бизон выдал мне ошибку.

Спасибо


grammar flex-lexer bison
person Simone Margaritelli    schedule 19.04.2010    source источник

Ответы (3)


arrow_upward
14
arrow_downward

Короче говоря, нет. Bison имеет дело только с грамматиками LALR(1), что означает, что он использует только один символ просмотра вперед. Вам нужно что-то вроде этого:

statement: T_CLASS T_IDENT extension_list '{' ...

extension_list: 
              | T_EXTENDS T_IDENT_LIST
              ;

Однако есть и другие генераторы синтаксических анализаторов, которые работают с более общими грамматиками. Если память не изменяет, некоторые из них поддерживают необязательные элементы относительно напрямую, как вы просите.

person Jerry Coffin    schedule 19.04.2010
comment
Это было решение написать только одно правило без | :) Спасибо! - person Simone Margaritelli; 19.04.2010
comment
Это не имеет ничего общего с тем, что это LALR(1), так как оба являются LALR(1). Это потому, что входной синтаксис - BNF, а не EBNF. - person Chris Dodd; 06.05.2013
comment
@ChrisDodd: Извините, но неправильно. Проблема здесь в том, что, когда он писал это, его синтаксический анализатор должен был смотреть вперед на три символа, через T_CLASS и T_IDENT, чтобы увидеть, будет ли следующий символ { или T_EXTENDS, чтобы увидеть, какой вариант statement использовать. Это нарушение LALR(1). EBNF выглядит для меня полным отвлекающим маневром - я не вижу ничего, что даже напоминало бы EBNF в этом вопросе. - person Jerry Coffin; 07.05.2013

arrow_upward
1
arrow_downward

Почему бы вам просто не разделить их с помощью оператора выбора (|)?

statement:
  T_CLASS T_IDENT T_EXTENDS T_IDENT_LIST  '{' T_CLASS_MEMBERS '}'
  | T_CLASS T_IDENT  '{' T_CLASS_MEMBERS '}'

Я не думаю, что вы можете сделать это только потому, что это восходящий анализатор LALR (1), вам понадобится что-то другое, например LL (k) (ANTLR?), Чтобы делать то, что вы хотите.

person Jack    schedule 19.04.2010

arrow_upward
0
arrow_downward

Я думаю, что максимум, что вы можете сделать, это

statement : T_CLASS T_IDENT  '{' T_CLASS_MEMBERS '}'
    | T_CLASS T_IDENT T_EXTENDS T_IDENT_LIST  '{' T_CLASS_MEMBERS '}' {
}
person Michael Krelin - hacker    schedule 19.04.2010