Disallow `syntax {S} S ::= ...`

Open
#3,839 13 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
4/5
Estimated time
3-5 days
Newbie friendliness
35/100
Issue type
Bug
Clarity
Mostly clear
Activity status
Stale
Tech stack
python
Domain
compilers

Research direction

Start in the frontend validation for syntax productions and compare it with the existing hooked-sort restrictions. Reproduce the shown parameterized-sort examples, including token and function variants, to identify the current unrelated error or crash. Done means these productions receive a deliberate frontend error, with regression coverage for the examples.

Written by the indexing model from the issue text.

Description

Productions syntax {S} S ::= ... where the sort parameter S only appears on the LHS are buggy, and appear to be de-facto unsupported.

At a minimum, they violate restrictions that we place on hooked sorts. For example,

syntax Bool ::= foo()
syntax Bool ::= MyBoolSubsort

is disallowed because you cannot add new constructors or subsorts to hooked sorts, thus

syntax {S} S ::= foo()
syntax {S} S ::= MySubsort

must be disallowed as well. (We don't currently report a nice error here, and instead report unrelated errors or crash depending on the exact example).

We could potentially permit syntax {S} S ::= "new_token" [token] or syntax {S} S ::= foo() [function] as hooked sorts allow token and function productions.

However, I’m unaware of any compelling use cases for this, and they are either unsupported or buggy in practice.

For example,

syntax {S} S ::= "bott1" [token]
               | "bott2" [token]
rule bott1 => bott2

results in

[Error] Internal: Uncaught exception thrown of type NoSuchElementException
(NoSuchElementException: key not found: SortS)

Given these issues, I propose that we just report an error in the frontend on any such production.

Dominant language
Python
Stars
591
Forks
163
No merged PRs in 30d

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from runtimeverification/k

All issues in runtimeverification/k

Similar issues

More Python issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.