LBNF, объявление / определение функции C, уменьшите уменьшить конфликт
Я пытаюсь представить в LBNF, что объявления функций C / C ++ имеют следующую (приблизительную) форму (<sym> обозначает optionallity, а [rule] является списком с нулевым или большим количеством значений):
type ident ( [type <id>] );
В то время как определения функций имеют вид:
type ident ( [type id] ) { [stmt] }
В настоящее время у меня есть следующие LBNF:
entrypoints Program ;
Program. Program ::= [TopDef] ;
FnDef. TopDef ::= Type Ident "(" [Arg] ")" Block ;
FnDecl. TopDef ::= Type Ident "(" [Par] ")" ";" ;
separator nonempty TopDef "" ;
Param. Par ::= Type ;
NParam. Par ::= Type Ident ;
separator Par "," ;
Arg. Arg ::= Type Ident;
separator Arg "," ;
-- Types ---------------------------------------------------
Int. Type ::= "int" ;
--- more types...
separator Type "," ;
Что вызывает уменьшение / уменьшение конфликтов, как и ожидалось.
Есть ли способ решить эту проблему в парсере / лексере?
Я мог бы решить это с помощью следующей грамматики:
FnDef. TopDef ::= Type Ident "(" [Arg] ")" Block ;
FnDecl. TopDef ::= Type Ident "(" [Arg] ")" ";" ;
separator nonempty TopDef "" ;
Arg. Arg ::= Type Ident;
Arg. Arg ::= Type;
separator Arg "," ;
А затем проверьте в программе проверки типов, что в определениях функций есть идентификаторы для каждого аргумента, но это кажется менее удовлетворительным …
Как это обычно обрабатывается на языке, подобном C?
Решение
То, как вы упоминаете, что вы считаете неудовлетворительным, на самом деле обычно так и делается.
Но вы можете создать LALR (1) грамматику, которая является точной. Вот полная спецификация бизонов без конфликтов:
%token TYPE ID
%%
prog :
| prog decl ';'
decl : TYPE ID def_list block
| TYPE ID def_list ';'
| TYPE ID dec_list ';'
block : '{' prog '}'
def_list : '(' ')'
| '(' type_ids ')'
dec_list : '(' type_opt_ids ')'
type_opt_id: type_only
| type_id
type_ids : type_id
| type_ids ',' type_id
type_opt_ids
: type_only
| type_ids ',' type_only /* SEE BELOW */
| type_opt_ids ',' type_opt_id
type_id : TYPE ID
type_only : TYPE
Ключ заключается в том, чтобы не заставлять анализатор принимать решение. Так как он проходит по списку параметров, он может продолжать сокращать type_opt_ids до тех пор, пока он не поразит анонимный параметр. Если он ударяет один, это уменьшает type_ids и продолжается для остальных параметров, независимо от того, являются ли они анонимными или нет. В конце концов, определение позволяет type_ids но декларация (явно) принимает либо.
Чтобы заставить это работать, семантический тип для type_id а также type_only должно быть одинаковым, так как оба type_ids а также type_opt_ids должны быть списки этого типа. В противном случае вам нужно будет конвертировать type_ids в type_opt_ids в производстве отмечен /* SEE BELOW */
(Я извиняюсь за то, что не преобразовал это в ваш формализм, но я хотел проверить его с помощью зубров, чтобы убедиться, что он на самом деле не конфликтует. Это должно быть достаточно просто для преобразования.)
Обратите внимание, что C ++ рад разрешить определения функций без имен параметров, а C — нет. С другой стороны, C допускает определения функций без типов или с объявлениями типов между списком имен параметров и телом. Но это побочный вопрос, правда.
Другие решения
Других решений пока нет …