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
Google Scholar App Using Python

Google Scholar App Watch the tutorial video How to build a Google Scholar App | Streamlit #30 Demo Launch the web app: Reproducing this web app To rec

Chanin Nantasenamat 4 Jun 05, 2022
Python script to preprocess images of all Pokémon to finetune ruDALL-E

ai-generated-pokemon-rudalle Python script to preprocess images of all Pokémon (the "official artwork" of each Pokémon via PokéAPI) into a format such

Max Woolf 132 Dec 11, 2022
Absolute solvation free energy calculations with OpenFF and OpenMM

ABsolute SOLVantion Free Energy Calculations The absolv framework aims to offer a simple API for computing the change in free energy when transferring

7 Dec 07, 2022
Developer guide for Hivecoin project

Hivecoin-developer Developer guide for Hivecoin project. Install Content are writen in reStructuredText (RST) and rendered with Sphinx. Much of the co

tweetyf 1 Nov 22, 2021
An kind of operating system portal to a variety of apps with pure python

pyos An kind of operating system portal to a variety of apps. Installation Run this on your terminal: git clone https://github.com/arjunj132/pyos.git

1 Jan 22, 2022
This is sample project needed for security course to connect web service to database

secufaku This is sample project needed for security course to "connect web service to database". Why it suits alignment purpose It connects to postgre

Mark Nicholson 6 May 15, 2022
Python Multilingual Ucrel Semantic Analysis System

PymUSAS Python Multilingual Ucrel Semantic Analysis System, it currently is a rule based token level semantic tagger which can be added to any spaCy p

UCREL 13 Nov 18, 2022
Write a program that works out whether if a given year is a leap year

Leap Year 💪 This is a Difficult Challenge 💪 Instructions Write a program that works out whether if a given year is a leap year. A normal year has 36

Rodrigo Santos 0 Jun 22, 2022
Fast Base64 encoding/decoding in Python

Fast Base64 implementation This project is a wrapper on libbase64. It aims to provide a fast base64 implementation for base64 encoding/decoding. Insta

Matthieu Darbois 96 Dec 26, 2022
LinkML based SPARQL template library and execution engine

sparqlfun LinkML based SPARQL template library and execution engine modularized core library of SPARQL templates generic templates using common vocabs

Linked data Modeling Language 6 Oct 10, 2022
Nicotine+: A graphical client for the SoulSeek peer-to-peer system

Nicotine+ Nicotine+ is a graphical client for the Soulseek peer-to-peer file sharing network. Nicotine+ aims to be a pleasant, Free and Open Source (F

940 Jan 03, 2023
A scuffed remake of Kahoot... Made by Y9 and Y10 SHSB

A scuffed remake of Kahoot... Made by Y9 and Y10 SHSB

Tobiloba Kujore 3 Oct 28, 2022
Improving the Transferability of Adversarial Examples with Resized-Diverse-Inputs, Diversity-Ensemble and Region Fitting

Improving the Transferability of Adversarial Examples with Resized-Diverse-Inputs, Diversity-Ensemble and Region Fitting

Junhua Zou 7 Oct 20, 2022
Reso is a low-level circuit design language and simulator, inspired by things like Redstone, Conway's Game of Life, and Wireworld.

Reso Reso is a low-level circuit design language and simulator, inspired by things like Redstone, Conway's Game of Life, and Wireworld. What is Reso?

Lynn 287 Nov 26, 2022
A new mini-batch framework for optimal transport in deep generative models, deep domain adaptation, approximate Bayesian computation, color transfer, and gradient flow.

BoMb-OT Python3 implementation of the papers On Transportation of Mini-batches: A Hierarchical Approach and Improving Mini-batch Optimal Transport via

Khai Ba Nguyen 18 Nov 14, 2022
A toy repo illustrating a minimal installable Python package

MyToy: a minimal Python package This repository contains a minimal, toy Python package with a few files as illustration for students of how to lay out

Fernando Perez 19 Apr 24, 2022
A simply dashboard to view commodities position data based on CFTC reports

commodities-dashboard A simply dashboard to view commodities position data based on CFTC reports This is a python project using Dash and plotly to con

71 Dec 19, 2022
This repository containing cross-section cut and fill calculations using Python programming language.

cross-section This repository is containing cut and fill calculations for cross-section using Python programming language. This codes is made to calcu

3 Jun 15, 2022
Turn a raspberry pi into a Bluetooth Midi device

PiBluetoothMidSetup This will change serveral system wide packages/configurations Do not run this on your primary machine or anything you don't know h

MyLab6 40 Sep 19, 2022
CEI Natural Disaster Tracking Portal

CEI Natural Disaster Tracking Portal (cc) Climatic Eye of ISCI We are an initiative that conducts studies in the field of Space Science, publishes pro

Baris Dincer 7 Dec 24, 2022