Contextual Language Parsing - Vol 2.

(Ab)using Lezer to build context sensitivity into lezer-feel.

Nico Rehwaldt 2022

Recap ⬇️

Context Sensitivity

Context sensitive languages require full context for parsing.

Grammar + Context Defines Interpretation

a + b

# can be arithmetic operation (a) + (b)
# or name (a,+,b)
# depending on <grammar> + <context>

Lezer

• Language parsing toolkit for the editing use-case
• Forgiving (handles broken input)
• Quick (re-evaluates partially)
• Embeddable + customizable
• Supported natively in CodeMirror 6

Technical Details

• A LR(1) parser, a type of shift-reduce parser
• Options to handle ambiguity through GLR parsing (needs to be explicitly flagged in the grammar)

Foundation for FEEL* language support

• lezer-feel - FEEL grammar
• lang-feel - Language definitions for CodeMirror 6
• feelin - FEEL interpreter written in JavaScript

Provides some powerful utilities

• Grammar Driven
• External Tokens + context tracking

External Tokenization

• Be able to parse the token steam ourselves (programmatically) and produce tokens

  input -> token(s)
  

Context Tracking

• Track internal parse state as the parser operates

  context + (shift/reduce symbol) -> new context
  

• Information can be fed into tokenizer to implement contextual parsing

What is Contextual in FEEL?

• Names (vs. expressions)
• Expressions (may be eagerly cut)

Demo + Code Review

import {
  parser,
  trackVariables
} from 'lezer-feel';

const contextTracker = trackVariables({
  'if foo then bar': 1
});

const contextualParser = parser.configure({
  contextTracker
});

// recognizes <if foo then bar> as a <VariableName>
contextualParser.parse('if foo then bar');

Summary

• We use context tracking and external tokenization to implement context sensitive language parsing
• We interpret as we parse to maintain the context

Benefits

Handling context sensitivity at the core (language level) simplifies downstream jobs styling, interpreting, and introspection.

Thanks

❤️