Contextual Language Parsing
Lessons learned while implementing a parser and interpreter for DMN FEEL
Nico Rehwaldt 2022
Language Parser
A tool (or human) that understands the meaning behind (written) text.
if (!fs.existsSync(inputFile)) {
console.log('Created %s', inputFile);
fs.copyFileSync(__dirname + '/template.md', inputFile);
}
How do computers parse language?
Tokenization
Produce (terminal) symbols from the input.
Parsing
Match symbols against grammar to produce a syntax tree.
There exists many strategies to do this: Top-down (Earley) or bottom up (LR parsing, PEG).
Grammar Defines Interpretation
a + b
# can be arithmetic operation (a) + (b)
# or name (a,+,b)
# depending on <grammar>
Language Classes
Chomsky hierarchy defines different classes of languages.
Most sane (programing-) languages are context free.
Context sensitive languages on the other end 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>
Context Sensitivity
Let's take OR as an example.
XOR
Live or death?
Öhm...
Classic OR
What do you want for dinner? Noodles, potatoes, soup or just buns?
Yes.
Human language is context sensitive
FEEL is context sensitive
{
foo: true,
bar: "NOPE",
if foo then bar: 100,
x: if foo then bar
}
Implications
- Parsing is context senstivie
- Tokenizing is context sensitive
- Tokenize, parse and interpret at the same time