parsing - 愉快地解决错误

Question

在正则表达式中，我可以写：

a(.)*b

这将匹配整个字符串，例如

acdabb

我尝试使用 Happy 中的令牌流来模拟这一点。

t : a wildcard b
wildcard : {- empty -} | wild wildcard
wild : a | b | c | d | whatever

但是Happy生成的解析器不识别

acdabb

有没有办法解决这个问题/我做错了吗？

Answer 1

正如您所说，Happy 使用 LALR(1) 解析器，文档中对此进行了说明。您在评论中指出，更改为右递归可以解决问题，但对于新手来说，可能不清楚如何实现。要更改递归，将wilcard wild其重写为wild wildcard，从而生成以下文件：

{
module ABCParser (parse) where
}

%tokentype { Char }

%token a { 'a' }
%token b { 'b' }
%token c { 'c' }
%token d { 'd' }
%token whatever { '\n' }

%name parse t

%%

t 
 : a wildcard b
  { }

wildcard 
  : 
   { }  
  | wildcard wild
     { }

wild 
   : a 
    { }
   | b 
     { }
   | c 
     { }
   | d
     { }
   | whatever
     { }

现在生成一个工作解析器。