2

我正在为具有以下类型的语言开发一个快乐的解析器，还有更多。

type :: { ... }
type :
    'void'                { ... }
  | type '*'              { ... } {- pointer    -}
  | type '(' types ')'    { ... } {- function   -}
  | ...                           {- many more! -}

types :: { ... }
    {- empty -}           { ... }
  | types ',' type        { ... }

该语言的调用语法显然不明确。

callable :: { ... }
callable :
    type                   operand    { ... }    {- return type -}
  | type '(' types ')' '*' operand    { ... }    {- return and argument types -}

type当采用函数指针的类型时，第二条规则与第一条规则的含义不同。

可以通过为不是函数指针的类型添加特殊规则来消除歧义。除非这样做并复制所有类型定义以产生类似的东西

callable :: { ... }
callable :
    typeThatIsNotAFunctionPointer operand    { ... }
  | type '(' types ')' '*'        operand    { ... }

我如何指定仅当替代方案失败时替代方案type operand才合法？type '(' types ')' '*' operand

关于堆栈溢出有很多关于为什么语法有歧义的问题（我发现至少有 7 个），还有一些关于如何消除歧义的问题，但没有关于如何指定如何解决歧义的问题。

不受欢迎的解决方案

我知道我可以将类型的语法重构为一个巨大的复杂混乱。

neverConstrainedType :: { ... }
neverConstrainedType :
    'int'                 { ... }
  | ...                   {- many more! -}

voidType :: { ... }
voidType :
    'void'

pointerType :: { ... }
pointerType :
    type '*'              { ... } {- pointer    -}

functionType :: { ... }
    type '(' types ')'    { ... } {- function    -}

type :: { ... }
type :
    neverConstrainedType  { ... }
  | voidType              { ... }
  | pointerType           { ... }
  | functionType          { ... }

typeNonVoid :: { ... }    {- this already exists -}
typeNonVoid : 
    neverConstrainedType  { ... }
  | pointerType           { ... }
  | functionType          { ... }

typeNonPointer :: { ... }
typeNonPointer :
    neverConstrainedType  { ... }
  | voidType              { ... }
  | functionType          { ... }

typeNonFunction :: { ... }
typeNonFunction :
    neverConstrainedType  { ... }
  | voidType              { ... }
  | functionType          { ... }

typeNonFunctionPointer :: { ... }
typeNonFunctionPointer :
    typeNonPointer        { ... }
  | typeNonFunction '*'   { ... }

然后定义callable为

callable :: { ... }
callable :
    typeNonFunctionPointer                    operand    { ... }
  | type                   '(' types ')' '*'  operand    { ... }
4

1 回答 1

2

基本上你有所谓的转变/减少冲突。您可以谷歌“解决移位/减少冲突”以获取更多信息和资源。

解决移位/减少冲突的基本思想是重构语法。例如，这个语法是模棱两可的：

%token id comma int
A : B comma int
B : id     
  | id comma B

可以通过将其重构为来消除移位/减少冲突：

A : B int
B : id comma
  | id comma B

在你的情况下，你可以尝试这样的事情：

type : simple               {0}
     | func                 {0}
     | funcptr              {0}

simple : 'void'             {0}
       | simple '*'         {0}
       | funcptr '*'        {0}

func : type '(' type ')'    {0}

funcptr : func '*'          {0}

这个想法是这样的：

  • simple匹配任何不是函数或函数指针的类型
  • func匹配任何函数类型
  • funcptr匹配任何函数指针类型

也就是说，我在发现的语法中尝试做的许多事情最好通过在创建解析树后对其进行分析来完成。

于 2015-01-14T20:19:01.320 回答