Sitelet https://github.com/gpuweb/gpuweb/pull/2735
Skip to content

Describe WGSL's context-aware tokenization - #2735

Merged
kdashg merged 1 commit into
gpuweb:mainfrom
dneto0:issue-2127-context-aware-tokenization
May 31, 2022
Merged

Describe WGSL's context-aware tokenization#2735
kdashg merged 1 commit into
gpuweb:mainfrom
dneto0:issue-2127-context-aware-tokenization

Conversation

@dneto0

@dneto0 dneto0 commented Apr 5, 2022 •
edited
Loading

Copy link
Copy Markdown
Contributor

Also remove parsing conflict between type constructor and function call,
by refactoring the grammar.

Fixes: #2717

Edit: Fix the issue number.

@dneto0 dneto0 added the wgsl WebGPU Shading Language Issues label Apr 5, 2022
mehmetoguzderin
mehmetoguzderin requested changes Apr 5, 2022
View reviewed changes
Comment thread wgsl/extract-grammar.py Outdated
@dneto0
dneto0 force-pushed the issue-2127-context-aware-tokenization branch from 791ac4c to 7afb019 Compare April 5, 2022 20:24
mehmetoguzderin
mehmetoguzderin approved these changes Apr 5, 2022
View reviewed changes

@mehmetoguzderin mehmetoguzderin left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

WGSL is about to be conflict-free! I really like this way of representing callables which comes with the benefit of no more conflicts. Thanks for building this change!

@dneto0 dneto0 mentioned this pull request Apr 5, 2022
Closed
alan-baker
alan-baker reviewed Apr 5, 2022
View reviewed changes
Comment thread wgsl/index.bs Outdated
"title":"Context-Aware Scanning for Parsing Extensible Languages",
"authors": [
"Eric R. Van Wyk",
"August C. and Schwerdfeger"

@alan-baker alan-baker Apr 5, 2022

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think the "and" is a typo? When I check the link the author info doesn't include it.

Suggested change
"August C. and Schwerdfeger"
"August C. Schwerdfeger"

@dneto0 dneto0 Apr 6, 2022

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I badly translated the Bibtex info from the ACM site. Thanks!

@dneto0 dneto0 mentioned this pull request Apr 6, 2022
Merged
@dneto0
dneto0 force-pushed the issue-2127-context-aware-tokenization branch from 556dcdb to 9ea228f Compare April 7, 2022 15:52
@dneto0

dneto0 commented Apr 7, 2022

Copy link
Copy Markdown
Contributor Author

Landed the grammar update separately as #2737, then rebased

@dneto0 dneto0 added this to the V1.0 milestone Apr 7, 2022
@github-actions

github-actions Bot commented Apr 7, 2022

Copy link
Copy Markdown
Contributor

Previews, as seen when this build job started (9ea228f):
WebGPU | IDL
WGSL
Explainer

@kdashg kdashg mentioned this pull request Apr 12, 2022
Closed
@dneto0 dneto0 mentioned this pull request Apr 19, 2022
Closed
@dneto0
Describe WGSL's context-aware tokenization
b4dc640 
WGSL is LALR(1).

Tokenization is context-aware.  The tokenizer either yields the
longest token in the lookahead of the current parser state, or
it fails.

Fixes: gpuweb#2717
@dneto0
dneto0 force-pushed the issue-2127-context-aware-tokenization branch from 9ea228f to b4dc640 Compare May 27, 2022 14:24
@dneto0

dneto0 commented May 27, 2022

Copy link
Copy Markdown
Contributor Author

WIP PR #2754 adds a grammar analyzer:

  • it reads Treesitter's JSON representation of the WGSL grammar
  • can construct (and emit) an LALR(1) parse table. See Add WGSL grammar analyzer #2754 (comment) for a snapshot.
  • The parse table includes the list of lookahead tokens for each parser state.

LALR(1) parser table construction succeeds with the current version of the grammar. That is, WGSL is a LALR(1) language.

Formally, parsing treats tokenization as an oracle. The fact that most parsers treat tokenization as completely independent of parsing is only a strong tradition. This PR spells out the interdependence needed to parse WGSL: the tokenizer must yield the longest 'token candidate' that also appears in the lookahead of the current parse state. If there is none, then parsing fails.

mehmetoguzderin
mehmetoguzderin approved these changes May 27, 2022
View reviewed changes

@mehmetoguzderin mehmetoguzderin left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this PR improves the explanation a lot, the text captures all the details with good references. Thank you!

@kdashg

kdashg commented May 31, 2022

Copy link
Copy Markdown
Contributor
WGSL meeting minutes 2022-05-24
  • DN: Have gotten far enough with LALR(1) to generate some conflicts. First is actually valid in way grammar structured. Module scoped decl has attr <var> and we have attr <function> but in 2 separate rules. In top level mod decl see @ don’t know if var or func. Refactor of rules should make that go away. So, finding things that are diagnosed as not right. Another batch to look at still. Close to confident the language is well behaved and will post on bug.
  • KG: That’s exciting
  • DN: Got compile from 1h to 20seconds.
  • KG: Will let continue to find/ fix issues. Is the meta idea that we burn through and narrow down what is context aware tokenization?
  • DN: Yes, PR up to describe context away which says ask for token which is valid and parse in an LALR derivation. There is an obvious way to implement in top-down, ask next if valid yaa, else cut down to next shortest token. Should line up with the same resolution. Once script is done, but into CI.

@dneto0

dneto0 commented May 31, 2022

Copy link
Copy Markdown
Contributor Author

FYI. I have an updated grammar dump at #2754 (comment)
I fixed a transitive closure problem in the analyzer. It doesn't change the overall conclusion.

@kdashg

kdashg commented May 31, 2022 •
edited
Loading

Copy link
Copy Markdown
Contributor
WGSL meeting minutes 2022-05-31 
* David’s LALR(1) analyzer verifies that WGSL’s grammar is LALR(1)
* PR updated with refined wording.
  • DN: At point where have grammar analyzer which verifies WGSL is LALR(1). Can dump from every parser state what tokens to expect otherwise it’s a parse error. All that’s working and confident and can say rule in PR, tokenization is interleaved, gives rule saying token candidate says anything starting from here that is any valid WGSL token and you take the longest one valid at that parser state. Give term and filter by what exists. For recursive descent, take longest token, see if works, otherwise split to shorter and try. Continue until find, if fail all that then failure.
  • KG: cool. Provides proof that our system should work. Is this something for CI?
  • DN: Yes, current 2min on macbook, lots of stringing and hashing. Now switching to IDs and things to make fast. Will make part of CI (hoping for < 2s). 568 states, 400 reductions. Not that big of a language.
  • JB: Moz produced table driven parser for JS at one point which required lots of tokenization hacks. Was in python and was fast.
  • DN: Wrinkles are nested comment blocks. Fact identifiers and keywords has a bit of precedence. (If looks like keyword is keyword).
  • KG: Any actionalable things?
  • DN: Land PR as it describes interleaving. Can then add << and >> back and then verify still LALR(1) (which I believe we will be)
  • KG: When removing << and >> we added buildings, do we keep them?
  • DN: Tink we should remove
  • MM: No content using them.
  • BC: Tint never implemented. Not aware of any implementation which actually did this.
  • KG: Ask as someone may want to use builtin instead of << or >>. Can request if they want.
  • MM: Can’t have ternary inside second part of thing between <> for a vector type or array type. (e.g. array<i32, 3 > 4 ? 5 : 6>) If wanted to add that then probably want the rust thing and require {} in that situation. If not doing anything special (array<f32, 17>) then don’t need {}’s.
  • DN: Right now, no general expression in that slot of the template. Special grammar rule called ??? expression which jumps far enough into hierarchy. Would have to put it in the right spot to make it available.
  • JB: Rust only resorts to {} because () have meaning at the type level. So WGSL can use ().
  • KG: Resolve to do all the things. Merge PR, revert operator removal Remove shift tokens and add shift built-in functions #2713. Remove the builtins.

@kdashg
kdashg merged commit 861362a into gpuweb:main May 31, 2022
github-actions Bot added a commit that referenced this pull request May 31, 2022
@dneto0 @github-actions
Describe WGSL's context-aware tokenization (#2735)
99ab17e 
SHA: 861362a
Reason: push, by @kdashg

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
@kdashg kdashg mentioned this pull request May 31, 2022
Closed
github-actions Bot added a commit that referenced this pull request May 31, 2022
@dneto0 @github-actions
Describe WGSL's context-aware tokenization (#2735)
4aa7f37 
SHA: 861362a
Reason: push, by @kdashg

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
github-actions Bot added a commit that referenced this pull request May 31, 2022
@dneto0 @github-actions
Describe WGSL's context-aware tokenization (#2735)
0bd224f 
SHA: 861362a
Reason: push, by @kdashg

Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com>
@dneto0 dneto0 mentioned this pull request Jun 9, 2022
Merged
jdarpinian pushed a commit to jdarpinian/gpuweb that referenced this pull request Aug 12, 2022
@dneto0 @jdarpinian
Describe WGSL's context-aware tokenization (gpuweb#2735)
e9e9fad 
WGSL is LALR(1).

Tokenization is context-aware.  The tokenizer either yields the
longest token in the lookahead of the current parser state, or
it fails.

Fixes: gpuweb#2717
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@mehmetoguzderin mehmetoguzderin mehmetoguzderin approved these changes
@alan-baker alan-baker alan-baker approved these changes
@jimblandy jimblandy Awaiting requested review from jimblandy
@litherum litherum Awaiting requested review from litherum

Assignees

No one assigned

Labels

wgsl WebGPU Shading Language Issues

Projects

None yet

Milestone

Milestone 0

Development

Successfully merging this pull request may close these issues.

WGSL parsing assumes context-aware tokenization

4 participants

@dneto0 @kdashg @mehmetoguzderin @alan-baker