0

在使用快乐解析器编写的函数式语言编译器中，这与 yacc/bison 非常相似，我实现了列表和列表一些核心函数map，concat并且filter，使用以下规则：

Exp:
...
| concat '(' Exp ',' Exp ')'         { Concat $3 $5 }
| map '(' Exp ',' Exp ')'            { Map $3 $5 }
| filter '(' Exp ',' Exp ')'         { Filter $3 $5 }

这很好用，但在大多数函数式语言中没有括号或逗号，所以map(myfun, [1,2,3])我宁愿写map myfun [1,2,3]. 语法中明显的修改如下：

Exp:
...
| concat Exp Exp         { Concat $2 $3 }
| map Exp Exp            { Map $2 $3 }
| filter Exp Exp         { Filter $2 $3 }

但是这个修改包含很多reduce-reduce 冲突。如何在没有逗号和括号的情况下实现函数调用的解析？

我能提取的最小的冲突语法是这样的：

Exp :
    -- Math
     Exp '+' Exp                         { Op $1 Add $3 }
    | Exp '-' Exp                        { Op $1 Sub $3 }

    -- Literals
    | num                                { Num $1 }
    | '-' num %prec NEGATIVE             { Num (-$2) }

    -- Lists
    | map Exp Exp                        { Map $2 $3 }

它产生 4 个减少/减少冲突。删除任何规则也会导致冲突。如果您有兴趣，这里是完整的语法。

4

1 回答 1

1

问题在于，由于函数应用程序中没有标记，基于标记的优先级冲突解决不能很好地工作——当它试图决定一个可能是函数应用程序的转变和一些其他表达式的归约时，前瞻标记是参数表达式开头的任何内容；没有可以使用的“空白”标记。

要解决该问题并使其正常工作，您需要将每个可能是表达式的标记（FIRST(Exp) 中的每个标记）的优先级设置为函数应用程序的优先级。如果这些标记中的任何一个需要其他优先级（例如，任何可能是中缀或前缀的标记），这将变得更加棘手并且可能不起作用。

一个可能更好的替代方法是根本不使用优先规则——相反，用不同的规则为每个优先级别消除语法的歧义：

Exp: Term | Exp '+' Term
Term: Factor | Term '*' Factor
Factor: Primary | Factor Primary
Primary: num | id | '(' Exp ')'
于 2016-10-09T21:23:43.347 回答