Необязательный префикс в грамматике LBNF/BNFC без конфликтов сдвига/уменьшения

Я пытаюсь написать грамматику LBNF/BNFC для C-подобного языка. В C есть много возможных модификаторов, которые вы можете писать или не писать перед объявлением (например, inline, const, volatile и т. д.).

Я пытаюсь написать свою грамматику для повторного использования кода и сделать полученный Haskell AST удобным для использования. Грамматика для типов может выглядеть так:

rule TypeName ::= "bool" | "int" | "double" | "void" | Id ;

Type. Type ::= TypeQualifier TypeName;

ConstModifier.    TypeModifier ::= "const" ;
VolatileModifier. TypeModifier ::= "volatile" ;
NoModifier.       TypeModifier ::= ;

А для объявления функции это может выглядеть так:

Fun. Fun ::= FunModifier Type Id "(" [Param] ")" ";" ;

InlineModifier. FunModifier ::= "inline" ;
NoFunModifier.  FunModifier ::= ;

Проблема в том, что я получаю массу конфликтов сдвига/уменьшения, а иногда даже уменьшения/уменьшения из-за этих необязательных префиксов. Альтернативная грамматика, которая позволяет избежать этих конфликтов, может выглядеть так:

NotInlinedFun. Fun ::= Type Id "(" [Param] ")" ";" ;
InlinedFun.    Fun ::= "inline" Type Id "(" [Param] ")" ";" ;

or

NotInlinedFun. Fun ::= FunRest
InlinedFun.    Fun ::= "inline" FunRest;

FunRest.   FunRest ::= Type Id "(" [Param] ")" ";" ;

что приводит к такому Haskell AST:

data Fun = AFun FunRest | BFun FunRest | CFun FunRest
data FunRest = FunRest Type Id [Param]

вместо более привлекательного

data Fun = Fun Modifier Type Id [Param]
data Modifier = A | B | C

Вы можете видеть, как это может быстро привести к комбинаторному взрыву правил или AST Haskell, который будет неудобен в использовании.

Как лучше всего избежать этих конфликтов?


ebnf grammar bnf happy bnfc
person Grisu47    schedule 30.04.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Когда вы ничего не видите перед int, вы не знаете, является ли это ничто отсутствием модификатора переменной или отсутствием модификатора функции, именно потому, что вы еще не знаете, относится ли int к переменной или к возвращаемому значению. функции. Так что, если синтаксический анализатор работает только с одним токеном просмотра вперед, вы должны избегать принуждения его к принятию решения.

Создание нетерминала из ничего — это форма принуждения синтаксического анализатора решать, какое ничто исследуется, так что этого тоже следует избегать. Но это не единственный пример; если бы вы включили, например, static, вы бы обнаружили, что попытка классифицировать его как модификатор переменной или модификатор функции приведет к тому же конфликту (уменьшение/уменьшение).

Но в любом случае настоящая грамматика C более тонкая. Например, следующее является законным:

static inline const int* extract(int arg);

Так и это:

/* The second const is irrelevant to this discussion. */
volatile const unsigned char* const reg = 0x01A4;

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

long long very_wide;

В других случаях это не так:

inline inline int f(void);

Хотя эти ограничения можно было бы выразить в виде контекстно-свободной грамматики, я никогда не видел, чтобы это делалось; как вы говорите, экспоненциальный взрыв неуправляем. Фактическая грамматика C, как описано в стандарте C, не пытается сделать это; он просто позволяет объявлению содержать произвольный порядок возможно повторяющихся спецификаторов-объявлений (см. 6.7), а затем заставляет семантический анализ различать правильные и неправильные последовательности.

person rici    schedule 01.05.2019