Zulip Chat Archive

Stream: lean4

Topic: using indentation to resolve syntactic ambiguity


Simon Hudon (Mar 19 2022 at 23:25):

I'm building a DSL for writing context free grammars. I have the following syntactic rule and an example:

declare_syntax_cat rules
declare_syntax_cat rule
declare_syntax_cat symbol
syntax (ident <|> strLit) : symbol
syntax ident " ::= " (colGt symbol)* : rule
syntax rule* : rules
syntax(name := grammarCmd) "grammar " ident rules "end " ident : command

grammar foo

  foo ::= "(" foo ")"
  star ::= "." foo
  --   ^
  -- expected 'end'

end foo
-- invalid 'end', insufficient scopes

Clearly, the fact that I can have an identifier on either side of " ::= " makes this grammar ambiguous so I added colGt so that if I have a new line in the middle of a production rule, I have to indent it in order for it to be recognized as the continuation of the same rule. It doesn't seem to work that way. I also tried using notFollowedBy(" ::= ") after ident on the rhs of the production rule and that also doesn't work. How can I resolve this ambiguity?

Leonardo de Moura (Mar 19 2022 at 23:34):

@Simon Hudon colGt is the way to go, but you need to use withPosition to specify the column colGt is going to compare.

declare_syntax_cat rules
declare_syntax_cat rule
declare_syntax_cat symbol
syntax (ident <|> str) : symbol
syntax ident withPosition(" ::= " (colGt symbol)*) : rule
syntax rule* : rules
syntax(name := grammarCmd) "grammar " ident rules "end " ident : command

macro_rules
  | `(grammar $id1:ident $rules:rules end $id2:ident) => `(#print "hello")


grammar foo
  foo ::= "(" foo ")"
  star ::= "." foo

end foo

Simon Hudon (Mar 19 2022 at 23:41):

Ah! Nice! Thank you

Arthur Paulino (Mar 20 2022 at 03:20):

What does "colGt" mean? I keep reading "column greater than" in my mind but I'm not sure that makes sense

Simon Hudon (Mar 20 2022 at 03:34):

Leo just gave me the second part of this puzzle. withPosition marks a relative position and colGt is a match only if it appears at a column greater that the latest position recorded by withPosition


Last updated: Dec 20 2023 at 11:08 UTC