"Converting a standard grammar with recursion and alternations into a regular expression: A step-by-step

A grammar is considered regular if it follows either a right-linear or left-linear pattern. According to this tutorial, this type of grammar possesses a unique property:

Regular grammars have a special characteristic: through the substitution of every nonterminal (excluding the root) with its corresponding righthand side, the grammar can be simplified to a single production for the root, containing only terminals and operators on the right-hand side... The resulting expression comprising terminals and operators can be further condensed into a more concise form known as a regular expression.

In an attempt to explore this concept further, I decided to convert the regular EcmaScript grammar for IdentifierName into regular expressions:

IdentifierName ::
    IdentifierStart
    IdentifierName  IdentifierPart

Let's assume that the definitions for IdentifierStart and IdentifierPart are limited to the following:

IdentifierStart ::       IdentifierPart ::
    A                        A                 
    B                        C
    C                        &
    $                    
    _

However, I'm facing some confusion in proceeding with this task due to the presence of both recursion and alternation within the grammar for IdentifierName. Any suggestions or assistance?

My main focus lies on understanding the methodology rather than solely obtaining the resulting regexp, which has been demonstrated by @Bergi as [ABC$_][AC&]*.

javascriptecmascript-nextcompiler-construction

Answer №1

The tutorial referenced here introduces unconventional definitions in its explanation.

Instead of adhering to the standard definition of a regular grammar as one that is either left-linear or right-linear, the tutorial opts for a model based on repetition operators akin to those seen in regular expressions or EBNF. Under this framework, a grammar is considered regular if it solely employs these repetition operators without recursion. Consequently, converting such a "regular grammar" into a regex involves simply substituting non-terminals with their corresponding definitions. However, according to this non-traditional viewpoint, the JavaScript specification's grammar for identifiers falls short of being classified as regular due to its recursive elements necessitating a preliminary substitution process.

This departure from convention raises concerns regarding the validity and practicality of the definitions presented. While regular grammars can indeed be transformed into regular expressions, the methodology outlined in the tutorial may not be universally applicable. A more robust approach involves converting the grammar into a finite automaton before utilizing established algorithms for conversion.

In practice, manually performing this conversion often entails examining the language described by the grammar (e.g., "words beginning with an IdentifierStart symbol followed by zero or more IdentifierPart symbols") and crafting a regular expression accordingly. This intuitive method, sometimes referred to as the "look really hard at the problem until you see the solution"-algorithm, remains a prevalent strategy in manual conversions despite its theoretical simplicity.

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

Can a client receive a response from server actions in Next.js 13?

I'm currently developing a Next.js application and I've created an action in app/actions/create-foo-action.js. In this server action, I am attempting to send a response back to the client. import { connectDB } from "@utils/database" imp ...

javascriptnext.jsserver-side-renderingnext.js13server-action

Sorting the output with gulp and main-bower-files (gulp-order is not functioning)

Hello, I'm a Java engineer diving into the world of Javascript for the first time. Apologies in advance if my information is lacking or incorrect! I am currently working on a gulp build script and utilizing bower to manage dependencies for my JS fron ...

javascriptjqueryangularjsgulpbower

Dividing a set of dates into intervals

My goal is to organize this array of objects into smaller arrays based on consecutive dates. These bookings span the next couple of years and I need to break them down efficiently. [ { state: 'BOOKED', date: 2017-01-01T23:00:00.000Z }, { state ...

javascriptarraysnode.jsdatesplit

What is the best way to embed a variable within a Directive HTML block for seamless access by the Controller?

I am facing a challenge with my custom directive that inserts an HTML block onto the page. The issue is to have a variable within this block that can be manipulated based on an ng-click function in my controller. This is what my directive looks like: .di ...

javascriptangularjsangularjs-directiveangularjs-scope

The generation of the npm bin script is not working as expected on Windows operating systems

I'm working on developing an NPM package for command line use. I've set up npm's bin in my package.json to specify the JS file to be executed. Here is a snippet from my package.json: "name": "textree", "bin": { "textree": "./src/cli.js" ...

javascriptnode.jsnpmcommand-line-interface

Storing the result of parsing JSON data into a global variable

$(function() { var countFromData = 0; getReminder(); alert(countFromData); }); function getReminder() { $.getJSON("<?=base_url()?>home/leavereminder", {}, function(data) { ...

javascriptjqueryjson

Tips for reading user input in a terminal using node.js

Before deploying my code to the server, I'm looking to conduct some local node testing. How can I take terminal input and use it as an input for my JavaScript script? Is there a specific method like readline that I should be using? ...

javascriptnode.jsterminal

What is the process for implementing the sticky table header jQuery plugin?

I am looking to implement a sticky header on all tables in my web application, which is built on PHP. As the amount of data continues to grow, search results are fetching more records that may not be visible. I am primarily a PHP programmer and do not have ...

javascriptjqueryhtml

The Express application remains silent unless a port is specified for it to

Having recently started working with Node, I encountered an issue with Express. My application is only listening to localhost:PORT and I want it to also listen to just localhost. Here is the code snippet: ** var app = require('../app'); var debu ...

javascriptnode.jsexpress

Ways to access a particular property of a child component object from the parent component

Is there a way to access a child component's "meta" property from the parent component without using the emit method? I am aware of the solution involving an emit method, but I'm curious if there is a simpler approach to achieving this. // Defau ...

javascriptvue.jsvue-router

Integrate JavaScript code with HTML pages

After creating a basic HTML structure that I am proud of, I encountered some challenges with getting the Javascript to function properly. I am new to working with Javascript and received some initial assistance, but unfortunately, it is no longer working. ...

javascriptjqueryhtmljsonajax

Unable to locate module: Unable to locate the file './Header.module.scss' in '/vercel/path0/components/Header'

I encountered an error while attempting to deploy my next application on Vercel. I have thoroughly reviewed my imports, but I am unable to pinpoint the issue. Module not found: Can't resolve './Header.module.scss' in '/vercel/path0/comp ...

javascriptreactjsnext.jsvercel

The issue of receiving a 500 error when making a POST request in node.js

I have created my own unique REST API that utilizes an NLP API internally. I need to post data on their URL, but unfortunately I am encountering an error that is causing my API to return a 500 error to the frontend. Below is a snippet of my server.js code ...

javascriptnode.jsexpressneedle.js

I have expanded the CSSStyleDeclaration prototype, how do I access the 'parent' property?

I have developed some custom methods for CSSStyleDeclaration and implement them like this: A_OBJECT.style.method() ; The code structure is quite simple: CSSStyleDeclaration.prototype.method = function () { x = this.left; ..... etc } Here's my que ...

javascriptcss

Exporting JSON data to an Excel file using an array of objects with embedded arrays

I am currently developing a fitness application that allows users to create workout routines and download them as an excel file. The data is structured as an array of objects, with each object representing a workout date and containing details of the exerc ...

javascriptreactjsjsonxlsx

EdgeDriver with Selenium and Java can be interrupted by a modal window dialog box, causing the test script to pause its execution

I am in the process of creating a test script for our web application to test the upload functionality of a profile picture using Microsoft Edge and EdgeDriver. However, I am facing an issue where the script stops running completely after initiating the cl ...

javascriptjavaeclipseseleniumselenium-edgedriver

What is the best location to specify Access-Control-Allow-Origin or Origin in JavaScript?

After researching, I found out that I need to set my Access-Control-Allow-Origin or Origin tags. But the question is: where do I actually add these? The suggestions were to use them in the header section. I couldn't find any detailed explanation on t ...

javascriptphpjquerycross-domain

Retrieve information from a JSON file within a Vue.js application rather than entering data manually

I am venturing into the world of Vue.js for the first time. I have created an app that currently relies on manually added data within the script. Now, I am looking to enhance it by fetching data from a JSON file, but I'm unsure about how to proceed wi ...

javascriptvue.jsvuejs2axiosvue-component

Using JavaScript drag and drop feature to remove the dragged element after a successful drop operation

Trying to figure out how to remove a dragged element from the DOM after a successful drop using the native JavaScript drag and drop API. After attempting to listen for the drop event, it seems that it only fires on the element being dropped onto and does ...

javascripthtmldrag-and-drop

Convert the button element to an image

Can someone please explain how to dynamically change a button element into an image using javascript when it is clicked? For instance, changing a "Submit" button into an image of a check mark. ...

javascripthtmlvue.js