如何处理Happy+Alex解析器中标识符与关键字的冲突问题

示例输入输出 #

IN:  select TOP [1]
OUT: Select TOP (ConstInt 1)

IN:  select MIN [AVG(2,3)]
OUT: Select MIN (Function "AVG" [ConstInt 2,ConstInt 3])

IN:  select TOP [MIN(2,3)]
OUT: Parse error. Unexpected token TokAssumption "MIN"

问题原因 #

该语法允许MIN同时作为select后的**预设关键字（assumption）**和函数名。在最后一个示例中，MIN被词法分析器优先识别为预设关键字TokAssumption，但此时它处于表达式上下文，本应被解析为对应函数名的TokIdentifier，最终导致解析错误。

疑问与思路 #

最简单的解决方式是让预设关键字和函数名不重叠，但在我实际要修复的解析器中这无法实现。

我的直觉是通过解析器的monadic动作检查前瞻token：当前瞻token为(时，将当前token词法分析为TokIdentifier。这个思路是否正确？有没有更优的处理这类情况的方法？

相关代码 #

Parser.hs（Happy解析器代码）

{
module Parser (
  parser,
  L.runAlex
) where

import Data
import qualified Lexer as L
}

%name parser algexpr
%tokentype { L.Token }
%error { parseError }
%monad { L.Alex } { >>= } { pure }
%lexer { lexer } { L.EOF }

%token

'('       { L.TokLParen }
')'       { L.TokRParen }
'['       { L.TokLSquare }
']'       { L.TokRSquare }
','       { L.TokComma }
'select'  { L.TokSelect }
int       { L.TokConstInt $$ }
ident     { L.TokIdentifier $$ }
ass       { L.TokAssumption $$ }

%%

commaSep(p)
  : commaSep_(p) { reverse $1 }
commaSep_(p)
  : {- empty -} { [] }
  | p { [$1] }
  | commaSep_(p) ',' p { $3 : $1 }

algexpr :: { AlgExpr }
  : 'select' assumption '[' expr ']' { Select $2 $4 }

assumption :: { Assumption }
  : ass { read $1 }

expr :: { Expr }
  : int { ConstInt $1 }
  | ident '(' commaSep(expr) ')' { Function $1 $3 }

{
parseError :: L.Token -> L.Alex a
parseError tok = do
  (L.AlexPn _ line column, _, _, _) <- L.alexGetInput
  L.alexError $ "Parse error. Unexpected token " <> show tok <> " at line " <> show line <> ", column " <> show column

lexer :: (L.Token -> L.Alex a) -> L.Alex a
lexer = (=<< L.alexMonadScan)
}

Lexer.hs（Alex词法分析器代码）

{
module Lexer (
    Alex
  , AlexPosn (..)
  , alexGetInput
  , alexError
  , runAlex
  , alexMonadScan
  , Token (..)
) where

}

%wrapper "monad"

$digit = 0-9
$alpha = [a-zA-Z]
@ident = $alpha [$alpha $digit _]*

tokens :-

<0> $white+     { skip }

<0> "("       { tok TokLParen }
<0> ")"       { tok TokRParen }
<0> "["       { tok TokLSquare }
<0> "]"       { tok TokRSquare }
<0> ","       { tok TokComma }

<0> select    { tok TokSelect }

<0> MAX       { tokS TokAssumption }
<0> MIN       { tokS TokAssumption }
<0> TOP       { tokS TokAssumption }

<0> $digit+   { tokInt }
<0> @ident    { tokS TokIdentifier }

{
data Token
  = TokLParen
  | TokRParen
  | TokLSquare
  | TokRSquare
  | TokComma
  | TokAssumption String
  | TokSelect
  | TokConstInt Int
  | TokIdentifier String
  | EOF
  deriving (Eq, Show)

alexEOF :: Alex Token
alexEOF = pure EOF

tok :: Token -> AlexAction Token
tok ctor _ _ = pure ctor

tokS :: (String -> Token) -> AlexAction Token
tokS f (_, _, _, str) len = pure $ f $ take len str

tokInt :: AlexAction Token
tokInt (_, _, _, str) len = pure $ TokConstInt $ read $ take len str

}

Data.hs

module Data( AlgExpr(..), Expr(..), Assumption(..) ) where

data AlgExpr = Select Assumption Expr
             deriving (Eq,Show)

data Expr = ConstInt    Int
          | Function    String [Expr]
          deriving (Eq,Show)

data Assumption = MAX | MIN | TOP
                deriving (Eq,Show,Read)

内容的提问来源于stack exchange，提问作者swingbit