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

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

0 голосов
/ 30 апреля 2019

Я пытаюсь написать грамматику 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] ")" ";" ;

или 

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

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

, что приводит к AST на Haskell, например: 

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

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

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

1 Ответ

1 голос
/ 01 мая 2019

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

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

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

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), а затем вынуждает семантический анализ различать правильные и неправильные последовательности.

...