Online grammar editor

[mingodad]

I've just added /src/Language/Futhark/Parser/Parser.y to https://mingodad.github.io/parsertl-playground/playground/ an Yacc/Lex compatible online editor/tester (select Futhark parser (partially working) then click Parse to see a parser tree for the content in Input source).

While doing so I found that the token Bang ("!...") appears twice on the precedence declarations:

• First time here

  futhark/src/Language/Futhark/Parser/Parser.y

  Line 171 in 4add83b

  %left '`' '!...'

• Second time here

  futhark/src/Language/Futhark/Parser/Parser.y

  Line 179 in 4add83b

  %left '<=...' '>=...' '>...' '<' '<...' '==...' '!=...' '!...' '=...'

Also I'm not sure how the lexer is supposed to differentiate between NATLIT here

futhark/src/Language/Futhark/Parser/Lexer.x

Line 93 in 4add83b

@declit { \s -> decToken (NATLIT (nameFromBS s)) s }

and INTLIT here

futhark/src/Language/Futhark/Parser/Lexer.x

Line 135 in 4add83b

@declit { decToken INTLIT }

[athas]

The lexer picks the first rule that matches, so the second one is redundant.

I suspect the same is the case for the fixity declarations, but I really don't know.

I'll fix it. Thanks for noticing.

[athas]

Actually, for the fixity declaration I think the last one is probably the one that counts, as else I don't think the parser would have worked correctly. And the cause of the mistake is probably when we removed ! as a prefix operator.

[mingodad]

Also when giving the converted grammar to bison-3.8.2 we get this:

bison-nb futhark.g.y
>bison-nb futhark.g.y
futhark.g.y: warning: 35 reduce/reduce conflicts [-Wconflicts-rr]
futhark.g.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples
futhark.g.y:354.11-24: warning: rule useless in parser due to conflicts [-Wother]
  354 | 	| Atom ".." Exp2
      |           ^~~~~~~~~~~~~~

Converted grammar:

%token assert charlit def do doc else entry f16lit f32lit f64lit false floatlit for hole i16lit i32lit i64lit i8lit
%token if import in include intlit let local loop match module natlit open stringlit then true type
%token u16lit u32lit u64lit u8lit val while
//%token "#[" ']' '}' ')' "\\" '~' "'" "'~" "'^" '!' '?' '.' '_'

%left bottom
%left typeprec ifprec letprec caseprec enumprec sumprec
%left ',' case id constructor '(' '{'
%right ':' ":>"
%right "..." TWO_DOTS_LT TWO_DOTS_GT ".."
%left '`'
%right "->"
%left with
%left '='
%left PipeRight
%right PipeLeft
%left LogOr
%left LogAnd
%left Bang Leq Geq Greater '<' Less Equal NotEqual Equ
%left Band Xor '^' Bor '|'
%left ShiftL ShiftR
%left Plus Minus '-'
%left Times '*' Divide Mod Quot Rem
%left Pow
%left juxtprec
%left '[' INDEXING indexprec
%left top

%start Prog

%%

Doc:
	  doc
	;

Prog:
	  Doc Doc Dec_ Decs
	| Doc Dec_ Decs
	| Dec_ Decs
	| %empty
	;

Dec:
	  Dec_
	| Doc Dec_
	;

Decs:
	  Decs_
	;

Decs_:
	  %empty
	| Decs_ Dec
	;

Dec_:
	  Val
	| TypeAbbr
	| SigBind
	| ModBind
	| open ModExp
	| import stringlit
	| local Dec
	| "#[" AttrInfo ']' Dec_
	;

SigExp:
	  QualName
	| '{' Specs '}'
	| SigExp with TypeRef
	| '(' SigExp ')'
	| '(' id ':' SigExp ')' "->" SigExp
	| SigExp "->" SigExp
	;

TypeRef:
	  QualName TypeParams '=' TypeExpTerm
	;

SigBind:
	  module type id '=' SigExp
	;

ModExp:
	  ModExp ':' SigExp
	| "\\" ModParam maybeAscription_SimpleSigExp "->" ModExp
	| import stringlit
	| ModExpApply
	| ModExpAtom
	;

ModExpApply:
	  ModExpAtom ModExpAtom %prec juxtprec
	| ModExpApply ModExpAtom %prec juxtprec
	;

ModExpAtom:
	  '(' ModExp ')'
	| QualName
	| '{' Decs '}'
	;

SimpleSigExp:
	  QualName
	| '(' SigExp ')'
	;

ModBind:
	  module id ModParams maybeAscription_SigExp '=' ModExp
	;

ModParam:
	  '(' id ':' SigExp ')'
	;

ModParams:
	  ModParam ModParams
	| %empty
	;

Liftedness:
	  %empty
	| '~'
	| '^'
	;

Spec:
	  val id TypeParams ':' TypeExp
	| val BindingBinOp TypeParams ':' TypeExp
	| TypeAbbr
	| type Liftedness id TypeParams
	| module id ':' SigExp
	| include SigExp
	| Doc Spec
	| "#[" AttrInfo ']' Spec
	;

Specs:
	  Specs_
	;

Specs_:
	  Specs_ Spec
	| %empty
	;

SizeBinder:
	  '[' id ']'
	| INDEXING id ']'
	;

SizeBinders1:
	  SizeBinder SizeBinders1
	| SizeBinder
	;

TypeTypeParam:
	  "'" id
	| "'~" id
	| "'^" id
	;

TypeParam:
	  '[' id ']'
	| INDEXING id ']'
	| TypeTypeParam
	;

TypeParams:
	  TypeParam TypeParams
	| %empty
	;

LocalFunTypeParams:
	  '[' id ']' TypeParams
	| TypeTypeParam TypeParams
	| %empty
	;

BinOp:
	  Plus
	| Minus
	| Times
	| '*'
	| Divide
	| Mod
	| Quot
	| Rem
	| Equal
	| NotEqual
	| Less
	| Leq
	| Greater
	| Geq
	| LogAnd
	| LogOr
	| Pow
	| Xor
	| '^'
	| Band
	| Bor
	| '|'
	| ShiftR
	| ShiftL
	| PipeLeft
	| PipeRight
	| '<'
	| Bang
	| Equ
	| '`' QualName '`'
	;

BindingBinOp:
	  BinOp
	| '-'
	| '!'
	;

BindingId:
	  id
	| '(' BindingBinOp ')'
	;

Val:
	  def BindingId TypeParams FunParams maybeAscription_TypeExp '=' Exp
	| entry BindingId TypeParams FunParams maybeAscription_TypeExp '=' Exp
	| def FunParam BindingBinOp FunParam maybeAscription_TypeExp '=' Exp
	| let BindingId TypeParams FunParams maybeAscription_TypeExp '=' Exp
	| let FunParam BindingBinOp FunParam maybeAscription_TypeExp '=' Exp
	| def '(' Pat ',' Pats1 ')' '=' Exp
	| let '(' Pat ',' Pats1 ')' '=' Exp
	;

TypeAbbr:
	  type Liftedness id TypeParams '=' TypeExp
	;

TypeExp:
	  '(' id ':' TypeExp ')' "->" TypeExp
	| TypeExpTerm "->" TypeExp
	| '?' TypeExpDims '.' TypeExp
	| TypeExpTerm %prec typeprec
	;

TypeExpDims:
	  '[' id ']'
	| '[' id ']' TypeExpDims
	| INDEXING id ']'
	| INDEXING id ']' TypeExpDims
	;

TypeExpTerm:
	  '*' TypeExpTerm
	| TypeExpApply %prec typeprec
	| SumClauses %prec sumprec
	;

SumClauses:
	  SumClauses '|' SumClause %prec sumprec
	| SumClause %prec sumprec
	;

SumPayload:
	  %empty %prec bottom
	| TypeExpAtom SumPayload
	;

SumClause:
	  Constr SumPayload
	;

TypeExpApply:
	  TypeExpApply TypeArg
	| TypeExpAtom
	;

TypeExpAtom:
	  '(' TypeExp ')'
	| '(' ')'
	| '(' TypeExp ',' TupleTypes ')'
	| '{' '}'
	| '{' FieldTypes1 '}'
	| SizeExp TypeExpTerm
	| QualName
	;

Constr:
	  constructor
	;

TypeArg:
	  SizeExp %prec top
	| TypeExpAtom
	;

FieldType:
	  FieldId ':' TypeExp
	;

FieldTypes1:
	  FieldType
	| FieldType ',' FieldTypes1
	;

TupleTypes:
	  TypeExp
	| TypeExp ',' TupleTypes
	;

SizeExp:
	  '[' Exp ']'
	| '[' ']'
	| INDEXING Exp ']'
	| INDEXING ']'
	;

FunParam:
	  ParamPat
	;

FunParams1:
	  FunParam
	| FunParam FunParams1
	;

FunParams:
	  %empty
	| FunParam FunParams
	;

QualName:
	  id
	| QualName '.' id
	;

Exp:
	  Exp ':' TypeExp
	| Exp ":>" TypeExp
	| Exp2 %prec ':'
	;

Exp2:
	  IfExp
	| LoopExp
	| LetExp %prec letprec
	| MatchExp
	| assert Atom Atom
	| "#[" AttrInfo ']' Exp %prec bottom
	| BinOpExp
	| RangeExp
	| Exp2 ".." Atom
	| Atom ".." Exp2
	| '-' Exp2 %prec juxtprec
	| '!' Exp2 %prec juxtprec
	| Exp2 with '[' DimIndices ']' '=' Exp2
	| Exp2 with INDEXING DimIndices ']' '=' Exp2
	| Exp2 with FieldAccesses_ '=' Exp2
	| "\\" FunParams1 maybeAscription_TypeExpTerm "->" Exp %prec letprec
	| ApplyList
	;

ApplyList:
	  Atom ApplyList %prec juxtprec
	| Atom %prec juxtprec
	;

Atom:
	  PrimLit
	| Constr
	| charlit
	| intlit
	| natlit
	| floatlit
	| stringlit
	| hole
	| '(' Exp ')'
	| '(' Exp ',' Exps1 ')'
	| '(' ')'
	| '[' Exps1 ']'
	| '[' ']'
	| id
	| Atom '.' id
	| Atom '.' natlit
	| Atom '.' '(' Exp ')'
	| Atom INDEXING DimIndices ']'
	| '{' Fields '}'
	| SectionExp
	;

NumLit:
	  i8lit
	| i16lit
	| i32lit
	| i64lit
	| u8lit
	| u16lit
	| u32lit
	| u64lit
	| f16lit
	| f32lit
	| f64lit
	;

PrimLit:
	  true
	| false
	| NumLit
	;

Exps1:
	  Exps1_
	;

Exps1_:
	  Exps1_ ',' Exp
	| Exp
	;

FieldAccesses:
	  '.' FieldId FieldAccesses
	| %empty
	;

FieldAccesses_:
	  FieldId FieldAccesses
	;

Field:
	  FieldId '=' Exp
	| id
	;

Fields:
	  Fields1
	| %empty
	;

Fields1:
	  Field ',' Fields1
	| Field
	;

LetExp:
	  let SizeBinders1 Pat '=' Exp LetBody
	| let Pat '=' Exp LetBody
	| let id LocalFunTypeParams FunParams1 maybeAscription_TypeExp '=' Exp LetBody
	| let id INDEXING DimIndices ']' '=' Exp LetBody
	;

LetBody:
	  in Exp %prec letprec
	| LetExp %prec letprec
	| def
	| type
	| module
	;

BinOpExp:
	  Exp2 Plus Exp2
	| Exp2 Minus Exp2
	| Exp2 '-' Exp2
	| Exp2 Times Exp2
	| Exp2 '*' Exp2
	| Exp2 Divide Exp2
	| Exp2 Mod Exp2
	| Exp2 Quot Exp2
	| Exp2 Rem Exp2
	| Exp2 Pow Exp2
	| Exp2 ShiftR Exp2
	| Exp2 ShiftL Exp2
	| Exp2 Band Exp2
	| Exp2 Bor Exp2
	| Exp2 '|' Exp2
	| Exp2 LogAnd Exp2
	| Exp2 LogOr Exp2
	| Exp2 Xor Exp2
	| Exp2 '^' Exp2
	| Exp2 Equal Exp2
	| Exp2 NotEqual Exp2
	| Exp2 Less Exp2
	| Exp2 Leq Exp2
	| Exp2 Greater Exp2
	| Exp2 Geq Exp2
	| Exp2 PipeRight Exp2
	| Exp2 PipeLeft Exp2
	| Exp2 '<' Exp2
	| Exp2 Bang Exp2
	| Exp2 Equ Exp2
	| Exp2 '`' QualName '`' Exp2
	;

SectionExp:
	  '(' '-' ')'
	| '(' Exp2 '-' ')'
	| '(' BinOp Exp2 ')'
	| '(' Exp2 BinOp ')'
	| '(' BinOp ')'
	| '(' '.' FieldAccesses_ ')'
	| '(' '.' '[' DimIndices ']' ')'
	;

RangeExp:
	  Exp2 "..." Exp2
	| Exp2 TWO_DOTS_LT Exp2
	| Exp2 TWO_DOTS_GT Exp2
	| Exp2 ".." Exp2 "..." Exp2
	| Exp2 ".." Exp2 TWO_DOTS_LT Exp2
	| Exp2 ".." Exp2 TWO_DOTS_GT Exp2
	;

IfExp:
	  if Exp then Exp else Exp %prec ifprec
	;

LoopExp:
	  loop Pat LoopForm do Exp %prec ifprec
	| loop Pat '=' Exp LoopForm do Exp %prec ifprec
	;

MatchExp:
	  match Exp Cases
	;

Cases:
	  Case %prec caseprec
	| Case Cases
	;

Case:
	  case Pat "->" Exp
	;

Pat:
	  "#[" AttrInfo ']' Pat
	| InnerPat ':' TypeExp
	| InnerPat
	| Constr ConstrFields
	;

ParamPat:
	  id
	| '(' BindingBinOp ')'
	| '_'
	| '(' ')'
	| '(' Pat ')'
	| '(' Pat ',' Pats1 ')'
	| '{' CFieldPats '}'
	| PatLiteralNoNeg
	| Constr
	;

Pats1:
	  Pat
	| Pat ',' Pats1
	;

InnerPat:
	  id
	| '(' BindingBinOp ')'
	| '_'
	| '(' ')'
	| '(' Pat ')'
	| '(' Pat ',' Pats1 ')'
	| '{' CFieldPats '}'
	| PatLiteral
	| Constr
	;

ConstrFields:
	  InnerPat
	| ConstrFields InnerPat
	;

CFieldPat:
	  FieldId '=' Pat
	| FieldId ':' TypeExp
	| FieldId
	;

CFieldPats:
	  CFieldPats1
	| %empty
	;

CFieldPats1:
	  CFieldPat ',' CFieldPats1
	| CFieldPat
	;

PatLiteralNoNeg:
	  charlit
	| PrimLit
	| intlit
	| natlit
	| floatlit
	;

PatLiteral:
	  PatLiteralNoNeg
	| '-' NumLit %prec bottom
	| '-' intlit %prec bottom
	| '-' natlit %prec bottom
	| '-' floatlit
	;

LoopForm:
	  for VarId '<' Exp
	| for Pat in Exp
	| while Exp
	;

DimIndex:
	  Exp2
	| Exp2 ':' Exp2
	| Exp2 ':'
	| ':' Exp2
	| ':'
	| Exp2 ':' Exp2 ':' Exp2
	| ':' Exp2 ':' Exp2
	| Exp2 ':' ':' Exp2
	| ':' ':' Exp2
	;

DimIndices:
	  %empty
	| DimIndices1
	;

DimIndices1:
	  DimIndex
	| DimIndex ',' DimIndices1
	;

VarId:
	  id
	;

FieldId:
	  id
	| natlit
	;

maybeAscription_SimpleSigExp:
	  ':' SimpleSigExp
	| %empty
	;

maybeAscription_SigExp:
	  ':' SigExp
	| %empty
	;

maybeAscription_TypeExp:
	  ':' TypeExp
	| %empty
	;

maybeAscription_TypeExpTerm:
	  ':' TypeExpTerm
	| %empty
	;

AttrAtom:
	  id
	| intlit
	| natlit
	;

AttrInfo:
	  AttrAtom
	| id '(' ')'
	| id '(' Attrs ')'
	;

Attrs:
	  AttrInfo
	| AttrInfo ',' Attrs
	;

%%

[mingodad]

Also the token typeprec appears twice on the precedence declarations:

• First time here

  futhark/src/Language/Futhark/Parser/Parser.y

  Line 166 in 6dcd54b

  %left typeprec

• Second time here

  futhark/src/Language/Futhark/Parser/Parser.y

  Line 167 in 6dcd54b

  %left ifprec letprec caseprec typeprec enumprec sumprec

[mingodad]

See also haskell/happy#260