如何解决lua解析器语法中的shift/reduce、reduce/reduce冲突

Question

我正在尝试通过

happy

编写一个lua解析器。

我的

Parser.y

的语法来自https://www.lua.org/manual/5.4/manual.html#9如下

{
module Parser where
import Lexer
}

%name parse
%tokentype { Token }
%error { parseError }

%token
  -- whitespace
  -- $white+       ;

  -- comment
  -- "--" [^\n]*   ;

  -- keyword
  -- https://www.lua.org/manual/5.4/manual.html#3.1
  -- and       break     do        else      elseif    end
  -- false     for       function  goto      if        in
  -- local     nil       not       or        repeat    return
  -- then      true      until     while
  "and"           { TokenAnd }
  "break"         { TokenBreak }
  "do"            { TokenDo }
  "else"          { TokenElse }
  "elseif"        { TokenElseif }
  "end"           { TokenEnd }

  "false"         { TokenFalse }
  "for"           { TokenFor }
  "function"      { TokenFunction }
  "goto"          { TokenGoto }
  "if"            { TokenIf }
  "in"            { TokenIn }

  "local"         { TokenLocal }
  "nil"           { TokenNil }
  "not"           { TokenNot }
  "or"            { TokenOr }
  "repeat"        { TokenRepeat }
  "return"        { TokenReturn }

  "then"          { TokenThen }
  "true"          { TokenTrue }
  "until"         { TokenUntil }
  "while"         { TokenWhile }

  -- https://www.lua.org/manual/5.4/manual.html#3.1
  -- Other tokens
  -- +     -     *     /     %     ^     #
  -- &     ~     |     <<    >>    //
  -- ==    ~=    <=    >=    <     >     =
  -- (     )     {     }     [     ]     ::
  -- ;     :     ,     .     ..    ...
  '+'             { TokenAdd }
  '-'             { TokenMinus }
  '*'             { TokenMutiply }
  '/'             { TokenDevide }
  '%'             { TokenModulus }
  '^'             { TokenPower }
  '#'             { TokenLength }

  '&'             { TokenBitwiseAnd }
  '~'             { TokenBitwiseNot }
  '|'             { TokenBitwiseOr }
  "<<"            { TokenLeftShift }
  ">>"            { TokenRightShift }
  "//"            { TokenFloorDivision }

  "=="            { TokenEquals }
  "~="            { TokenNotEquals }
  "<="            { TokenLessThanEquals }
  ">="            { TokenGreaterThanEquals }
  '<'             { TokenLessThan }
  '>'             { TokenGreaterThan }
  '='             { TokenAssign }

  '('             { TokenLeftParentheses }
  ')'             { TokenRightParentheses }
  '{'             { TokenLeftBrace }
  '}'             { TokenRightBrace }
  '['             { TokenLeftBracket }
  ']'             { TokenRightBracket }
  "::"            { TokenDoubleColon }

  ';'             { TokenSemicolon }
  ':'             { TokenColon }
  ','             { TokenComma }
  '.'             { TokenDot }
  ".."            { TokenConcat }
  "..."           { TokenVararg }

  -- integer
  -- https://www.lua.org/manual/5.4/manual.html#3.1
  Integer         { TokenInteger $$ }

  -- float
  -- https://www.lua.org/manual/5.4/manual.html#3.1
  Float           { TokenFloat $$ }

  -- identifier
  Name            { TokenIdentifier $$ }
  LiteralString   { TokenString $$ }

%%
 -- https://www.lua.org/manual/5.4/manual.html#9

  -- chunk ::= block
  Chunk : Block { ChunkBlock $1 }

    -- block ::= {stat} [retstat]
  Block : StatList Retstat { BlockStatListRetstat $1 $2 }
        | StatList          { BlockStatList $1 }
  StatList : Stat { StatListSingle $1 }
           | Stat StatList { StatListCons $1 $2 }

    -- stat ::=  ';' | 
    --   varlist '=' explist | 
    --   functioncall | 
    --   label | 
    --   break | 
    --   goto Name | 
    --   do block end | 
    --   while exp do block end | 
    --   repeat block until exp | 
    --   if exp then block {elseif exp then block} [else block] end | 
    --   for Name '=' exp ',' exp [',' exp] do block end | 
    --   for namelist in explist do block end | 
    --   function funcname funcbody | 
    --   local function Name funcbody | 
    --   local attnamelist ['=' explist] 
  Stat : ';' { StatSemicolonEmpty }
       | Varlist '=' Explist { StatAssignment $1 $3 }
       | Functioncall { StatFunctionCall $1 }
       | Label { StatLabel $1 }
       | "break" { StatBreak }
       | "goto" Name { StatGoto $2 }
       | "do" Block "end" { StatDo $2 }
       | "while" Exp "do" Block "end" { StatWhile $2 $4 }
       | "repeat" Block "until" Exp { StatRepeat $2 $4 }
       | "if" Exp "then" Block ElseIfList ElseBlock "end" { StatIf $2 $4 $5 $6 }
       | "for" Name '=' Exp ',' Exp ',' Exp "do" Block "end" { StatForNumeric $2 $4 $6 $8 }
       | "for" Name '=' Exp ',' Exp "do" Block "end" { StatForNumericSimple $2 $4 $6 }
       | "for" Namelist "in" Explist "do" Block "end" { StatForEach $2 $4 $6 }
       | "function" Funcname Funcbody { StatFunction $2 $3 }
       | "local" "function" Name Funcbody { StatLocalFunction $3 $4 }
       | "local" Attnamelist '=' Explist { StatLocalAttribNameList $2 $4 }
       | "local" Attnamelist { StatLocalAttribNameListSimple $2 }
  ElseIfList : { EmptyElseIfList }
             | "elseif" Exp "then" Block ElseIfList { ElseIfListAppend $2 $4 $5 }
  ElseBlock : { EmptyElseBlock }
            | "else" Block { ElseBlock $2 }

    -- attnamelist ::=  Name attrib {',' Name attrib}
  Attnamelist : Name Attrib { AttnamelistCons $1 $2 }
              | Name Attrib ',' Attnamelist { AttnamelistAppend $1 $2 $4 }

    -- attrib ::= ['<' Name '>']
  Attrib : '<' Name '>' { AttribName $2 }
         |              { AttribEmpty }

    -- retstat ::= return [explist] [';']
  Retstat : "return" Explist ';' { ReturnStat $2 }
          | "return" Explist     { ReturnStat $2 }
          | "return" ';'         { ReturnStatEmpty }
          | "return"             { ReturnStatEmpty }

    -- label ::= '::' Name '::'
  Label : "::" Name "::" { LabelName $2 }

    -- funcname ::= Name {'.' Name} [':' Name]
  Funcname : Name { FuncnameDot $1 }
           | Name FuncnameDotList ':' Name { FuncnameColon $1 $2 $4 }
           | Name FuncnameDotList           { FuncnameDotListOnly $1 $2 }
  FuncnameDotList : '.' Name { FuncnameDotSingle $2 }
                  | FuncnameDotList '.' Name { FuncnameDotListAppend $1 $3 }

    -- varlist ::= var {',' var}
  Varlist : Var { VarListSingle $1 }
          | Var ',' Varlist { VarListCons $1 $3 }

    -- var ::=  Name | prefixexp '[' exp ']' | prefixexp '.' Name 
  Var : Name { VarName $1 }
      | Prefixexp '[' Exp ']' { VarBracket $1 $3 }
      | Prefixexp '.' Name { VarDot $1 $3 }

    -- namelist ::= Name {',' Name}
  Namelist : Name { NameListSingle $1 }
           | Name ',' Namelist { NameListCons $1 $3 }

    -- explist ::= exp {',' exp}
  Explist : Exp { ExpListSingle $1 }
          | Exp ',' Explist { ExpListCons $1 $3 }

    -- exp ::=  nil | false | true | Numeral | LiteralString | '...' | functiondef | 
    --   prefixexp | tableconstructor | exp binop exp | unop exp 
  Exp : "nil" { ExpNil }
      | "false" { ExpFalse }
      | "true" { ExpTrue }
      | Float { ExpFloat $1 }
      | Integer { ExpInteger $1 }
      | LiteralString { ExpString $1 }
      | "..." { ExpVararg }
      | Functiondef { ExpFunctionDef $1 }
      | Prefixexp { ExpPrefix $1 }
      | Tableconstructor { ExpTable $1 }
      | BinopExp { ExpBinop $1 }
      | UnopExp { ExpUnopExp $1 }

    -- prefixexp ::= var | functioncall | '(' exp ')'
  Prefixexp : Var { PrefixVar $1 }
            | Functioncall { PrefixFunctionCall $1 }
            | '(' Exp ')' { PrefixExp $2 }

    -- functioncall ::=  prefixexp args | prefixexp ':' Name args 
  Functioncall : Prefixexp Args { FunctionCall $1 $2 }
               | Prefixexp ':' Name Args { FunctionCallMethod $1 $3 $4 }

    -- args ::=  '(' [explist] ')' | tableconstructor | LiteralString 
  Args : '(' Explist ')' { ArgsExpList $2 }
       | Tableconstructor { ArgsTable $1 }
       | LiteralString { ArgsString $1 }

    -- functiondef ::= function funcbody
  Functiondef : "function" Funcbody { FunctionDef $2 }

    -- funcbody ::= '(' [parlist] ')' block end
  Funcbody : '(' Parlist ')' Block "end" { Funcbody $2 $4 }

    -- parlist ::= namelist [',' '...'] | '...'
  Parlist : Namelist ',' "..." { ParlistVararg $1 }
          | "..." { ParlistOnlyVararg }

    -- tableconstructor ::= '{' [fieldlist] '}'
  Tableconstructor : '{' Fieldlist '}' { TableConstructor $2 }

    -- fieldlist ::= field {fieldsep field} [fieldsep]
  Fieldlist : Field { FieldListSingle $1 }
            | Field Fieldsep Fieldlist { FieldListCons $1 $2 $3 }
            | Field Fieldsep { FieldListLast $1 $2 }

    -- field ::= '[' exp ']' '=' exp | Name '=' exp | exp
  Field : '[' Exp ']' '=' Exp { FieldExpKey $2 $5 }
        | Name '=' Exp { FieldNameKey $1 $3 }
        | Exp { FieldExp $1 }

    -- fieldsep ::= ',' | ';'
  Fieldsep : ',' { FieldsepComma }
           | ';' { FieldsepSemicolon }

    -- binop ::=  '+' | '-' | '*' | '/' | '//' | '^' | '%' | 
    --   '&' | '~' | '|' | '>>' | '<<' | '..' | 
    --   '<' | '<=' | '>' | '>=' | '==' | '~=' | 
    --   and | or
  BinopExp : Exp Binop Exp { BinopExpExp }
  Binop : '+'   { Plus }
        | '-'   { BinaryMinus }
        | '*'   { Multiply }
        | '/'   { Divide }
        | "//"  { FloorDiv }
        | '^'   { Power }
        | '%'   { Mod }
        | '&'   { BitwiseAnd }
        | '~'   { BitwiseNot }
        | '|'   { BitwiseOr }
        | ">>"  { ShiftRight }
        | "<<"  { ShiftLeft }
        | ".."  { Concat }
        | '<'   { LessThan }
        | "<="  { LessThanEqual }
        | '>'   { GreaterThan }
        | ">="  { GreaterThanEqual }
        | "=="  { Equals }
        | "~="  { NotEquals }
        | "and" { And }
        | "or"  { Or }

    -- unop ::= '-' | not | '#' | '~'
  UnopExp : Unop Exp { UnopExp }
  Unop : '-'    { UnaryMinus }
       | "not"  { Not }
       | '#'    { Length }
       | '~'    { BitwiseNot }

{
parseError :: [Token] -> a
parseError _ = error "Parse error"
}

但是冲突发生了，gammer 说

ambiguity

。

解析
```
not False and True
```
时，两棵语法树都正常，当
```
and
```
到来时，发生了移位/反射冲突。如何修复语法来解决这个冲突？

         ...                     ...
          |                       |
         Stat                    Stat
          |                       |
        BinOp                    UnOp
       /  |  \                  /   \
  UnOp                                BinOp
 /    \                             /  |  \
not False and True          not False and True

我不知道为什么当'('到来时会发生反射/反射冲突。我无法想出一个输入句子，同时有两个语法树，一个有
```
Stat -> Functioncall
```
减少，另一个有
```
Prefixexp -> Functioncall
```
减少到
```
Chunk 
```
。例如
```
foo()
```
可以减少
```
Stat -> Functioncall
```
，但不能减少
```
Prefixexp -> Functioncall
```
。如何修复语法来解决这个冲突？

State 9

    Stat -> Functioncall .                              (rule 8)
    Prefixexp -> Functioncall .                         (rule 63)

    "break"        reduce using rule 8
    "do"           reduce using rule 8
    "else"         reduce using rule 8
    "elseif"       reduce using rule 8
    "end"          reduce using rule 8
    "for"          reduce using rule 8
    "function"     reduce using rule 8
    "goto"         reduce using rule 8
    "if"           reduce using rule 8
    "local"        reduce using rule 8
    "repeat"       reduce using rule 8
    "return"       reduce using rule 8
    "until"        reduce using rule 8
    "while"        reduce using rule 8
    '('            reduce using rule 63
            (reduce using rule 8)

    '{'            reduce using rule 63
    '['            reduce using rule 63
    "::"           reduce using rule 8
    ';'            reduce using rule 8
    ':'            reduce using rule 63
    '.'            reduce using rule 63
    Name           reduce using rule 8
    LiteralString  reduce using rule 63
    %eof           reduce using rule 8

为什么lua的语法是对的？
```
happy
```
和
```
YACC
```
使用
```
LALR
```
。如果
```
lua parser
```
使用 LR(0) 或运算符优先级解析或一些更强大的算法？

Answer 1

您需要设置优先级。有关详细信息，请参阅文档。

我认为在这种情况下会是

%right not
%left and
%left or

对于所有其他中缀运算符，依此类推。

如何解决lua解析器语法中的shift/reduce、reduce/reduce冲突

问题描述投票：0回答：1

1个回答

最新问题

如何解决lua解析器语法中的shift/reduce、reduce/reduce冲突

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1