"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

Adjust the dimensions of the bootstrap dropdown to match the dimensions of its textbox

The second textbox features a bootstrap dropdown with extensive content that is overflowing and extending to other textboxes below it. I am looking for a way to resize the dropdown to fit the size of its corresponding textbox. UPDATE: I want the dropdown ...

javascripthtmlcssbootstrap-5

Using PHP to iterate through an array and output the values within a

Hey there! I have a question about incorporating PHP foreach and echo into JavaScript to make it dynamic. Here is the current static JavaScript code: <script type="text/javascript"> $(document).ready(function(){ $('input[type="checkbox"]&ap ...

javascriptphp

What strategies can I use to reduce the amount of event listeners assigned to buttons in jquery?

Currently, I am utilizing jquery 1.6.2 for my project. On one of the pages, I have a structure that resembles the following: <div id="section1"> <fieldset> <ul> <li> <input type="radio" name ...

javascriptjquery

Removing a faded out div with Vanilla JavaScript

I am struggling with a JS transition issue. My goal is to have the div automatically removed once it reaches opacity 0. However, currently I need to move my mouse out of the div area for it to be removed. This is because of a mouseleave event listener that ...

javascripthtmlcss

Omitting a specific item from the OrderBy function in an AngularJS table

My table is sorted by the properties "age" and "name", but I also have a row counter (counterR) that displays the number of rows in the table. I want to exclude the counter from being affected by the sorting because I want it to remain static and always o ...

javascriptangularjs

What is the best way to create a fully clickable navbar item for the Bootstrap dropdown feature?

I'm struggling to make a button in a navbar fully clickable for the dropdown to open. Even when I try adding margin instead of padding, it only makes things worse. Can someone help me figure out what mistake I'm making here? Essentially, my goal ...

javascriptjqueryhtmlcsstwitter-bootstrap

Issue encountered: Inability to implement asynchronous functionality within a forEach loop while making an API request

When making a GET API call, the code looks like this router.get('/review', async (req, res) => { try { const entity = await Entity.find(); const entityId = []; Object.keys(entity).forEach((key) => { entityId.push(entity[ ...

javascriptnode.jsmongodbexpress

What is causing the Access-Control-Allow-Origin error when using axios?

I have a simple axios code snippet: axios.get(GEO_IP) .then(res => res) .catch(err => err); In addition, I have configured some default settings for axios: axios.defaults.headers["content-type"] = "application/json"; axios.defaults.headers.common. ...

javascriptreactjsxmlhttprequestaxios

Is three too much for the Javascript switch statement to handle?

I'm a beginner in Javascript and am working on a project to create a fun program involving astrological signs, planets, and houses to generate a story. I have included three switch statements within one function to accomplish this. I'm encounter ...

javascript

Uploading images simultaneously while filling out a form

Currently, I have a form that requires users to fill it out and upload an image. However, there is a delay of up to 30 seconds when the user hits "Submit" due to the image size being uploaded. I'm interested in finding a way to initiate the image upl ...

phpjavascriptjqueryajaxforms

An error arises when using the command window.close()

I have encountered an issue with this code where it closes all Safari windows but works fine in Internet Explorer. What should I do? Is there an alternative method for closing the current opened window in every browser? <input type='button' v ...

javascriptwindow

Obtaining the calculated background style on Firefox

Back when my userscript was only functional on Chrome, I had a setup where I could copy the entire background (which could be anything from an image to a color) from one element to another. This is how it looked: $(target).css('background', $(so ...

javascriptjquerycssgoogle-chromefirefox

Transitioning NodeJS from local development to a live website

After successfully creating a site using NodeJS with one-page HTML/jQuery, everything is functioning properly on localhost. However, I am facing issues when trying to put the site online at www.xxxx.com. I already have a registered .com domain, but I am un ...

javascriptnode.jsnginxnpmweb-hosting

Positives and negatives images for accordion menu

I have successfully created an accordion list using HTML, CSS, and JavaScript. However, I would like to enhance it by adding a plus and minus picture in the left corner of the heading. Is there a way to achieve this functionality? I have two images that I ...

javascripthtmlcssaccordion

Incorporate Live Data into Google Charts Using Ajax Response for a Dynamic Visualization

I am struggling to successfully load a responsive Google Line Chart after an Ajax call. I have attempted to place the entire Google Chart code within the success part of the Ajax call, but it does not seem to work as expected. Below is my current Ajax code ...

javascriptphpjqueryajaxgoogle-visualization

Issue encountered with Cheerio while using Node.js

When attempting to parse code using cheerio and request on Node Js, I am encountering an error undefined. After thorough checking, it became apparent that the error lies within cheerio rather than the request component. Here is a snippet of my parsing code ...

javascriptnode.jsrequestcheerio

Error message: The Slick Carousal encountered an unexpected problem - TypeError:undefined is not a function

I'm having an issue with a script for a Slick Carousel inside of some Ajax Tabs. I keep encountering the Uncaught TypeError: undefined is not a function error, but I'm unsure what exactly it's pointing to. $(document).ready(function(){ ...

javascriptjqueryajaxcarouseltypeerror

Experiencing an unexpected wait before the requestAnimationFrame?

Surprisingly, Internet Explorer is actually performing the way I want it to in this case :-) I developed a function for SVG animations using requestAnimationFrame (for simplicity, I left out the value calculations here ... but my initial test involved an ...

javascriptcssanimationsvgrequestanimationframe

The fixed positioned div with jQuery disappears when scrolling in Firefox but functions properly in Chrome, IE, and Safari

Click here to see a div located at the bottom of the right sidebar that is supposed to behave as follows: As you scroll down the page, the div should change its class and become fixed at the top of the screen until you reach the bottom of the parent el ...

javascriptjqueryhtmlcssfirefox

Encountering difficulties in compiling Dynamic HTML with the $compile function

I'm attempting to incorporate dynamic HTML into my code with the following lines: var el = $compile('<a ng-controller=\"tableController\" ng-click=\"open\">...ReadMore</a>')($scope); But I'm encounterin ...

javascripthtmlangularjsdynamic-html