Context-free grammar to Sublime-syntax file

Overview

Context-free grammar to Sublime-syntax file

This project produces sublime-syntax highlighting files from a description of a context-free grammar.

It implements a "Generalised Recursive Descent Parser" as described in Generalised recursive descent parsing and follow-determinism by Adrian Johnstone and Elizabeth Scott. It's essentially a non-deterministic LL(1) parser. If the grammar happens to be LL(1) then no backtracking will happen and it's just an LL(1) parser. If the grammar is not LL(1), then alternatives will be tried in sequence, backtracking until one succeeds.

IMPORTANT: The grammar must be non-left-recursive, and also must be follow-determined. If the grammar is left-recursive then the program will complain and alert the user, but I don't know an algorithm to detect whether the grammar is follow-determined. IF THE GRAMMAR IS NOT FOLLOW-DETERMINED, THEN THE LANGUAGE RECOGNIZED BY THE GENERATED SYNTAX WILL SIMPLY NOT MATCH THE INPUT GRAMMAR.

A grammar is follow-determined if whenever a nonterminal X produces both and y <...> , then y is not in the follow set of X. Intuitively, a grammar is follow-determined whenever a single lookahead token is enough to tell us whether it's okay to pop out of the context for X or if we should keep going within X. (i.e. if we've just consumed the prefix and need to decide whether to finish with X or to keep consuming, then the presence or absence of the next token in the follow set of X had better be enough to tell us which option to take, because once we pop out of X then we can't backtrack to try other options anymore.)

Implementation

Sublime syntax files allow one to define contexts; within each context one can match against any number of regular expressions (including lookaheads) and then perform actions like pushing other contexts onto the context stack, pop out of the context, set the scope of the consumed tokens (i.e. instruct Sublime Text that a token is e.g. a function definition and highlight it appropriately), and others. One can also set a branch point and try multiple branches in sequence; if an action taken is to fail that branch point, then the syntax engine backtracks and tries the next branch in the sequence.

See the Wikipedia page on LL parsers for more details on how LL parsers work in general. What I do here is always indicate "success" by pop: 2; i.e. popping twice out of the current context, and failure by pop: 1. Contexts for a given production are pushed onto the stack interleaved by a pop2! context which always pops 2 contexts off the stack. Therefore a failure, which pops once, moves into the "always pop 2" stream until it hits a failure context (to backtrack and try a different branch) or pops all the way out of the current stack.

TO-DO:

  • Detect whether the input grammar is follow-determined. This may be undecidable for all I know.
  • Accept a convenient text description of a grammar rather than require constructing a Python object by hand. Benjamin Schaaf's sbnf is a project with essentially the same goals as this one, and has a very nice syntax for defining grammars so it'd be nice to allow inputs in that format.
  • Also add other conveniences from sbnf such as a prototype context, and embedding other grammars.
Owner
Haggai Nuchi
https://humantoanimal.com
Haggai Nuchi
python based clash stars made by grade 7 and 5

clash_stars python based clash stars made by grade 7 and 5 How to play: PLAYER ONE (LEFT PLAYER) Move: W,A,S,D Shoot: SHIFT PLAYER TWO (RIGHT PLAYER)

5 Oct 22, 2021
A simple solution for water overflow problem in Python

Water Overflow problem There is a stack of water glasses in a form of triangle as illustrated. Each glass has a 250ml capacity. When a liquid is poure

Kris 2 Oct 22, 2021
Script to use SysWhispers2 direct system calls from Cobalt Strike BOFs

SysWhispers2BOF Script to use SysWhispers2 direct system calls from Cobalt Strike BOFs. Introduction This script was initially created to fix specific

FalconForce 101 Dec 20, 2022
My repository for the Advent of Code, starting from 2021

Advent of Code This is my repository for the Advent of Code (https://adventofcode.com/), starting from 2021. File Structure Inside each year folder, s

Yu-Ting 6 Dec 15, 2021
Build Xmas cards with user inputs

Automatically build Xmas cards with user inputs

Anand 9 Jan 25, 2022
Badge-Link-Creater 'For more beautiful profiles.'

Badge-Link-Creater 'For more beautiful profiles.' Ready Badges Prepares the codes of the previously prepared badges for you. Note Click here for more

Mücahit Gündüz 9 Oct 19, 2022
tgEasy | Easy for a Brighter Shine | Monkey Patcher Addon for Pyrogram

tgEasy | Easy for a Brighter Shine | Monkey Patcher Addon for Pyrogram

Jayant Hegde Kageri 35 Nov 12, 2022
Extract continuous and discrete relaxation spectra from G(t)

pyReSpect-time Extract continuous and discrete relaxation spectra from stress relaxation modulus G(t). The papers which describe the method and test c

3 Nov 03, 2022
flake8 plugin which checks that there is no use of sleep in the code.

flake8-sleep flake8 plugin which checks for use of sleep function. installation Using Pypi: pip install flake8-sleep flake8 codes Code Description SLP

1 Nov 26, 2021
A test repository to build a python package and publish the package to Artifact Registry using GCB

A test repository to build a python package and publish the package to Artifact Registry using GCB. Then have the package be a dependency in a GCF function.

1 Feb 09, 2022
ChainJacking is a tool to find which of your Go lang direct GitHub dependencies is susceptible to ChainJacking attack.

ChainJacking is a tool to find which of your Go lang direct GitHub dependencies is susceptible to ChainJacking attack.

Checkmarx 36 Nov 02, 2022
A python package to adjust the bias of probabilistic forecasts/hindcasts using "Mean and Variance Adjustment" method.

Documentation A python package to adjust the bias of probabilistic forecasts/hindcasts using "Mean and Variance Adjustment" method. Read documentation

1 Feb 02, 2022
Python implementation for Active Directory certificate abuse

Certipy is a Python tool to enumerate and abuse misconfigurations in Active Directory Certificate Services (AD CS). Based on the C# variant Ce

Oliver Lyak 1.3k Jan 09, 2023
A service to display a quick summary of a project on GitHub.

A service to display a quick summary of a project on GitHub. Usage 📖 Paste the code below with details filled in as specified below into your Readme.

Rohit V 8 Dec 06, 2022
Meaningful and minimalist release notes for developers

Managing manual release notes is hard. Therefore, everyone tends to generate release notes from commit messages. But, you won't get a meaningful release note at the end.

codezri 31 Dec 30, 2022
A Python library that helps data scientists to infer causation rather than observing correlation.

A Python library that helps data scientists to infer causation rather than observing correlation.

QuantumBlack Labs 1.7k Jan 04, 2023
MDAnalysis tool to calculate membrane curvature.

The MDAkit for membrane curvature analysis is part of the Google Summer of Code program and it is linked to a Code of Conduct.

MDAnalysis 19 Oct 20, 2022
Render to print for blender 2.9+

render_to_print_blender_addon ** render2print: Blender AddOn for Blender 2.90.0+ ** Calculates camera parameters to allow printing a rendered image to

5 Nov 19, 2021
Python implementation of the Lox language from Robert Nystrom's Crafting Interpreters

pylox Python implementation of the Lox language from Robert Nystrom's Crafting Interpreters. https://craftinginterpreters.com. This only implements th

David Beazley 37 Dec 28, 2022