DEV Community: Lorenzo Felletti

How to Create a Bluetooth LE Scanner for Android

Lorenzo Felletti — Thu, 31 Aug 2023 17:37:15 +0000

Creating a Bluetooth LE scanner for Android is not too complicated. What you need is some understanding of the Android architecture and of Java/Kotlin.

The most difficult part of building such an app would be…managing the permissions, or even finding what are the required permissions (at least for me).

What You Need to Follow This Tutorial

Android Studio installed on your computer
A BLE enabled smartphone for testing running Android 12 (or later)
A basic understanding of Kotlin (or Java, at least)
A (very) basic understanding of how to create a UI in Android

Creating the Project

I will assume that you already know how to create a project in Android Studio, so create a new project, choose Empty Activity, and name it whatever you like, I named mine SimpleBleScanner. Also, select API 31 as the Minimum SDK.

I know that requiring Android 12 could be a bit too tight of a requirement, but this choice was made to be able to experiment with the latest features.

Anyway, if you have the necessity to use an earlier version of the SDK, I think you won’t have to change much of the code.

Managing the Permissions

First, we are going to declare in the Manifest (AndroidManifest.xml) all the permissions we will use in the application. In particular, for Bluetooth LE scanning, the minimum required permissions are the following:

<uses-permission android:name="android.permission.BLUETOOTH_ADMIN" />
<uses-permission android:name="android.permission.BLUETOOTH_CONNECT" />
<uses-permission android:name="android.permission.BLUETOOTH_SCAN" />
<uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" />
<uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />

As weird as it might sound, access to coarse and fine location is required in order to use BLE.

Next, inside the package containing the MainActivity, I chose to create another package named permissions, in which to put all the permission utilities.

Inside this newly created package, create two Kotlin objects named PermissionsUtilities and BleScanRequiredPermissions. These two objects will help us in managing the permissions without writing too much code inside the MainActivity.

BleScanRequiredPermissions will contain only the array of the permissions we are going to require for our app.

val permissions = arrayOf(
    Manifest.permission.BLUETOOTH_SCAN,
    Manifest.permission.ACCESS_COARSE_LOCATION,
    Manifest.permission.ACCESS_FINE_LOCATION,
    Manifest.permission.BLUETOOTH_ADMIN,
)

PermissionsUtilities, on the other hand, is a more complex object, containing all the utility functions to manage permissions in our application.

Anyway, the focus of the article is not on permissions handling, so I will go fast on this part. Feel free to check the permissions package by yourself if interested.

The main functions of this module are:

/**
* Checks for a set of permissions. If not granted, the user is asked to grant them.
*
* @param activity The activity that is requesting the permissions
* @param permissions The permissions to be checked
* @param requestCode The request code to be used when requesting the permissions
*/
fun checkPermissions(activity: Activity, permissions: Array<out String>, requestCode: Int)

/**
* Checks whether a set of permissions is granted or not
*
* @param context The context to be used for checking the permissions
* @param permissions The permissions to be checked
*
* @return true if all permissions are granted, false otherwise
*/
fun checkPermissionsGranted(context: Context, permissions: Array<out String>): Boolean

/**
* Checks the result of a permission request, and dispatches the appropriate action
*
* @param requestCode The request code of the permission request
* @param grantResults The results of the permission request
* @param onGrantedMap maps the request code to the action to be performed if the permissions are granted
* @param onDeniedMap maps the request code to the action to be performed if the permissions are not granted
*/
fun dispatchOnRequestPermissionsResult(
    requestCode: Int, grantResults: IntArray,
    onGrantedMap: Map<Int, () -> Unit>,
    onDeniedMap: Map<Int, () -> Unit>
)

/**
* Checks whether a permission is granted in the context
*
* @param context The context to be used for checking the permission
* @param permission The permission to be checked
*
* @return true if the permission is granted, false otherwise
*/
private fun checkPermissionGranted(context: Context, permission: String): Boolean

/**
* Checks the results of a permission request
*
* @param grantResults The results of the permission request
*
* @return true if all permissions were granted, false otherwise
*/
private fun checkGrantResults(grantResults: IntArray): Boolean

Otherwise, you could check this article about a permission management library I made, and try to use it instead… Android Permissions Made Easy.

Scanning for devices

To manage the scanning, we will create a new package named blescanner, containing two sub-packages named model and adapter.

The model the classes modeling the BleDevice and the BleScanCallback, while the adapter will contain the BleDeviceAdapter, used as adapter for the RecyclerView showing the results of the scan.

//BleDevice.kt
data class BleDevice(val name: String) {
    companion object {
        fun createBleDevicesList(): MutableList<BleDevice> {
            return mutableListOf()
        }
    }
}

// BleDeviceAdapter.kt
class BleDeviceAdapter(private val devices: List<BleDevice>) : RecyclerView.Adapter<BleDeviceAdapter.ViewHolder>() {
    inner class ViewHolder(itemView: View) : RecyclerView.ViewHolder(itemView) {
        val deviceNameTextView: TextView = itemView.findViewById<TextView>(R.id.device_name)
    }

    override fun onCreateViewHolder(parent: ViewGroup, viewType: Int): ViewHolder {
        val context = parent.context
        val inflater = LayoutInflater.from(context)
        val deviceView = inflater.inflate(R.layout.device_row_layout, parent, false)
        return ViewHolder(deviceView)
    }

    override fun onBindViewHolder(holder: BleDeviceAdapter.ViewHolder, position: Int) {
        val device = devices[position]
        val textView = holder.deviceNameTextView
        textView.text = device.name
    }

    override fun getItemCount(): Int {
        return devices.size
    }
}

Other than these three classes, we will create a BleScanManager, that will manage the scanning.

The BleScanManager class contains various members to manage the scanning state and what to do before/after the scanning.


class BleScanManager(
    btManager: BluetoothManager,
    private val scanPeriod: Long = DEFAULT_SCAN_PERIOD,
    private val scanCallback: BleScanCallback = BleScanCallback()
) {
    private val btAdapter = btManager.adapter
    private val bleScanner = btAdapter.bluetoothLeScanner

    var beforeScanActions: MutableList<() -> Unit> = mutableListOf()
    var afterScanActions: MutableList<() -> Unit> = mutableListOf()

    /** True when the manager is performing the scan */
    private var scanning = false

    private val handler = Handler(Looper.getMainLooper())

    /**
     * Scans for Bluetooth LE devices and stops the scan after [scanPeriod] seconds.
     * Does not checks the required permissions are granted, check must be done beforehand.
     */
    @SuppressLint("MissingPermission")
    fun scanBleDevices() {
        fun stopScan() {
            scanning = false
            bleScanner.stopScan(scanCallback)

            // execute all the functions to execute after scanning
            executeAfterScanActions()
        }

        // scans for bluetooth LE devices
        if (scanning) {
            stopScan()
        } else {
            // stops scanning after scanPeriod millis
            handler.postDelayed({ stopScan() }, scanPeriod)
            // execute all the functions to execute before scanning
            executeBeforeScanActions()

            // starts scanning
            scanning = true
            bleScanner.startScan(scanCallback)
        }
    }
}

The constructor will take as input a BluetoothManager, a scan period (set to a default value if omitted), and a list of actions to do before and after the scanning. The list of actions is nothing but a list of functions that will be invoked before/after the scanning start.

The Handler is used to schedule the stopping of the scan after the scan period time.

The companion object of the BleScanManager will contain the default value of the scan period, and a function to execute the list of actions.

companion object {
    const val DEFAULT_SCAN_PERIOD: Long = 10000

    private fun executeListOfFunctions(toExecute: List<() -> Unit>) {
        toExecute.forEach {
            it()
        }
    }

The last lines to complete the BleScanManager are the following

private fun executeBeforeScanActions() {
    executeListOfFunctions(beforeScanActions)
}

private fun executeAfterScanActions() {
    executeListOfFunctions(afterScanActions)
}

The Main Activity

The main activity will contain the code that “connects” all the modules we created so far:

the module managing the permissions
the BLE scan manager
the adapter for the RecyclerView

The code is pretty straightforward, the only two methods are the onCreate and the onRequestPermissionResult.

class MainActivity : AppCompatActivity() {
    private lateinit var btnStartScan: Button
    private lateinit var btManager: BluetoothManager
    private lateinit var bleScanManager: BleScanManager
    private lateinit var foundDevices: MutableList<BleDevice>

    @SuppressLint("NotifyDataSetChanged", "MissingPermission")
    @RequiresApi(Build.VERSION_CODES.S)
    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        // RecyclerView handling
        val rvFoundDevices = findViewById<View>(R.id.rv_found_devices) as RecyclerView
        foundDevices = BleDevice.createBleDevicesList()
        val adapter = BleDeviceAdapter(foundDevices)
        rvFoundDevices.adapter = adapter
        rvFoundDevices.layoutManager = LinearLayoutManager(this)

        // BleManager creation
        btManager = getSystemService(BluetoothManager::class.java)
        bleScanManager = BleScanManager(btManager, 5000, scanCallback = BleScanCallback({
            val name = it?.device?.address
            if (name.isNullOrBlank()) return@BleScanCallback

            val device = BleDevice(name)
            if (!foundDevices.contains(device)) {
                foundDevices.add(device)
                adapter.notifyItemInserted(foundDevices.size - 1)
            }
        }))

        // Adding the actions the manager must do before and after scanning
        bleScanManager.beforeScanActions.add { btnStartScan.isEnabled = false }
        bleScanManager.beforeScanActions.add {
            foundDevices.clear()
            adapter.notifyDataSetChanged()
        }
        bleScanManager.afterScanActions.add { btnStartScan.isEnabled = true }

        // Adding the onclick listener to the start scan button
        btnStartScan = findViewById(R.id.btn_start_scan)
        btnStartScan.setOnClickListener {
            // Checks if the required permissions are granted and starts the scan if so, otherwise it requests them
            when (PermissionsUtilities.checkPermissionsGranted(
                this,
                BleScanRequiredPermissions.permissions
            )) {
                true -> bleScanManager.scanBleDevices()
                false -> PermissionsUtilities.checkPermissions(
                    this, BleScanRequiredPermissions.permissions, BLE_PERMISSION_REQUEST_CODE
                )
            }
        }
    }

    @RequiresApi(Build.VERSION_CODES.S)
    override fun onRequestPermissionsResult(
        requestCode: Int, permissions: Array<out String>, grantResults: IntArray
    ) {
        super.onRequestPermissionsResult(requestCode, permissions, grantResults)

        dispatchOnRequestPermissionsResult(
            requestCode,
            grantResults,
            onGrantedMap = mapOf(BLE_PERMISSION_REQUEST_CODE to { bleScanManager.scanBleDevices() }),
            onDeniedMap = mapOf(BLE_PERMISSION_REQUEST_CODE to { Toast.makeText(this,
                    "Some permissions were not granted, please grant them and try again",
                    Toast.LENGTH_LONG).show() })
        )
    }

    companion object { private const val BLE_PERMISSION_REQUEST_CODE = 1 }
}

The latter is used to manage what to do “after” requesting the permissions to the user, while the former sets the ground for the application by setting the RecyclerView adapter, creating the BleScanManager, and setting the onClickListener for the button to start the scan.

Right after the BleScanManager is created, we add to it before/afterScanActions the code to enable/disable the scan button — because we want to disable the scan button while we’re performing it.

The onClickListener to start the scan checks first that the required permissions are granted, and, if so, it proceeds to start the scan, otherwise it starts permissions request flow.

The GUI

The GUI will be very (very) simple, just a Button to start the scanning, and a RecyclerView to show the scanning results.


<?xml version="1.0" encoding="utf-8"?>
<androidx.constraintlayout.widget.ConstraintLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    tools:context=".MainActivity">

    <Button
        android:id="@+id/btn_start_scan"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="@string/btn_start_scan_text"
        app:layout_constraintBottom_toBottomOf="parent"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.498"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toTopOf="parent"
        app:layout_constraintVertical_bias="0.844" />

    <TextView
        android:id="@+id/lbl_scan_results"
        android:layout_width="163dp"
        android:layout_height="19dp"
        android:layout_marginTop="28dp"
        android:clickable="false"
        android:gravity="center"
        android:text="@string/tw_scan_results_title"
        android:textSize="16sp"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toTopOf="parent" />

    <androidx.recyclerview.widget.RecyclerView
        android:id="@+id/rv_found_devices"
        android:layout_width="375dp"
        android:layout_height="516dp"
        app:layout_constraintBottom_toTopOf="@+id/btn_start_scan"
        app:layout_constraintEnd_toEndOf="parent"
        app:layout_constraintHorizontal_bias="0.444"
        app:layout_constraintStart_toStartOf="parent"
        app:layout_constraintTop_toBottomOf="@+id/lbl_scan_results"
        app:layout_constraintVertical_bias="0.0" />
</androidx.constraintlayout.widget.ConstraintLayout>

Other than the activity_main.xml we will need another layout file to define the layout of a RecyclerView row.


<?xml version="1.0" encoding="utf-8"?>
<LinearLayout
    xmlns:android="http://schemas.android.com/apk/res/android"
    android:orientation="horizontal"
    android:layout_width="match_parent"
    android:layout_height="wrap_content"
    android:paddingTop="10dp"
    android:paddingBottom="10dp"
    >
    <TextView
        android:id="@+id/device_name"
        android:layout_width="0dp"
        android:layout_height="wrap_content"
        android:layout_weight="1"
        />
</LinearLayout>

Conclusions

This is all to create a simple Bluetooth LE scanner app in Android.

The results will look something like this

The application's UI while performing a scan

As you can see, the app is very simple on the UI side, this because I wanted to focus more on the functionality. If you want, feel free to fork the repo and improve the application’s UI, or extend its functionalities.

This is all for this article, I hope you enjoyed reading it and that you found it useful. Let me know with a comment!

Cover image by Zarak Khan on Unsplash

Load Environment on Directory Change

Lorenzo Felletti — Mon, 21 Aug 2023 08:34:08 +0000

Change `gcloud` context, `az` login, Kubernetes context, set environment variables, and more just changing directory

During a typical day at work, I often need to change between two, or even three different repos, each with its relative gcloud, or az, or whatever configuration, its Kubernetes context, and so on.

At the beginning, I find it really frustrating and time-consuming to backward-search in history the commands I needed to run to be able to perform my tasks.

Out of frustration, I decided that I needed to find a way to be able to automate this boring task, and I came up with a simple solution that both saves me a lot of time when I need to switch context, but also helps me to track the steps needed to reach a certain configuration, in case I need to replicate it on another project.

After some stack-overflowing, I created these very simple zsh functions (portable to bash with little to no effort), to load hidden scripts on directory change. In particular, the two functions are named cda (that stands for cd and activate, or whatever), and sayonara (that means goodbye in Japanese):

# sourcing hidden files on cd
function cda() {  
        local -a PATHS; PATHS=('.', '.vscode' '.idea')  
        builtin cd "$@" || return  

        for p ("$PATHS[@]"); do  
                local hidden="${p}/.hidden.env"  
                if [[ -f "$hidden" ]]  
                then  
                        source $p  
                fi  
        done  
}

# Cleaning up when leaving, sourcing actions to do (like deactivate venv)  
function sayonara() {  
        local -a PATHS; PATHS=('.', '.vscode' '.idea')  

        for p ("$PATHS[@]"); do  
                local hidden="${p}/.hidden.out.env"  
                if [[ -f "$hidden"]]  
                then  
                        source $p  
                fi  
        done  

        if [[ "$#" -gt 0 ]] && local dest=("$@") || local dest=".."  

        builtin cd $dest || return  
}  
alias sayo="sayonara"

The command sayonara was also aliased with sayo for the sake of brevity.

Why not Just Overriding `cd`?

I could have named the cda function cd and I could have sourced hidden files completely transparently to the user (I am only taking into account the cda function now, as the other is used more rarely), and initially this was the case. In fact, the cda function is written in a way that supports exactly this — note that I do not use cd but builtin cd instead, otherwise an infinite loop would be caused — but this can cause you problems if you have multiple shells opened, and you visit different directories with a hidden env file.

Let’s suppose, for example, that you need to work in dir1 with the hidden environment env1 and you’re working on this, but you need to visit code in dir2 with hidden env env2. With the hidden env being sourced on cda, you cda in dir1, and “only” cd in dir2, and you have no problems. But, if instead you named the function cd, when you cd in dir1 env1 is sourced, but, when you move to dir2, env2 will be sourced, potentially overriding some configurations of env1 (like the Kubernetes context, or the gcloud configuration).

Thus, for this problem, I preferred to give up on the dream of writing cd and having the right configuration always ready to use, and “settled” for the still very good solution of cda-ing into a directory when I want its environment to be activated, and cd-ing into it when I just want to visit it.

Android Permissions Made Easy

Lorenzo Felletti — Mon, 12 Dec 2022 23:45:09 +0000

One library to rule them all

Handling the permission requests in Android is not as straightforward as I thought it should be, especially for beginners. Thus, I decided to write a small library to help in managing them.

The library is very simple to use:

choose a request code for each group of permissions you are going to ask altogether, and define an array containing those permissions (for example, if the application has a button enabling Bluetooth, and a view showing the user location on a map, you would create a BLUETOOTH_REQUEST_CODE = 1 and a LOCATION_REQUEST_CODE = 2, and define two arrays BLUETOOTH_PERMISSIONS = arrayOf(...), and LOCATION_PERMISSIONS = arrayOf(...))
create in the Activity that you want to request the permissions a PermissionManager

private val permissionsManager = PermissionManager(this)

Using the provided DSL, build an appropriate dispatcher
where you want to check or grant the permissions, call the manager’s checkRequestAndDispatch method

permissionManager.checkRequestAndDispatch(BLUETOOTH_REQUEST_CODE)

override the Activity’s onRequestPermissionsResult and add to it the line

permissionManager.dispatchOnRequestPermissionsResult(requestCode, grantResults)

enjoy!

The Dispatcher’s DSL

The DSL to build the dispatcher has a few functions that helps to create the dispatcher in a human-readable way. The following is an example:

    permissionManager.buildRequestResultsDispatcher {  
        withRequestCode(BLUETOOTH_REQUEST_CODE) {  
            checkPermissions(BLUETOOTH_PERMISSIONS)  
            doOnGranted {  
                Log.d(TAG, "Bluetooth permission granted")  
                // something ...  
            }  
            doOnDenied {  
                Log.d(TAG, "Bluetooth permission denied")  
                // something else ...  
            }  
        }  
        withRequestCode(LOCATION_REQUEST_CODE) {  
            checkPermissions(LOCATION_PERMISSIONS)  
            doOnGranted {  
                Log.d(TAG, "Location permission granted")  
                // something ...  
            }  
            doOnDenied {  
                Log.d(TAG, "Location permission denied")  
                // something else ...  
            }  
        }  
    }

Inside buildRequestResultsDispatcher, you can define as many as you want withRequestCode(requestCode) blocks, each containing the permissions to check (checkPermissions) and the behavior to dispatch in case all the permissions are granted (doOnGranted), or some were not (doOnDenied).

The `checkRequestAndDispatch` Method

This method does two things:

it checks if the permissions were already granted, and if so it dispatches the same action associated in the dispatcher to the doOnGranted for the given request code
otherwise, it asks for the permissions that are not granted; and it would be the overridden onRequestPermissionsResult to dispatch the appropriate action after the permission request.

How To Use The Library

The library is deployed on Jitpack, and you can easily add it to your project by adding to your settings.gradle:

    dependencyResolutionManagement {  
        ...  
        repositories {  
            ...  
            maven { url 'https://jitpack.io' }  
        }  
    }

And to your module level build.gradle:

    dependencies {  
        ...  
        implementation 'com.github.lorenzofelletti:permissions:0.4.2'  
    }

The showRationaleDialog Function

It is recommended that you also manage the shouldShowRequestPermissionRationale, so since version 0.3.0 it is possible to do it. Two DSL functions are defined to do this:

rationale — suitable for the cases when you need the maximum configurability, but you should manage “manually” some things, such as calling permissionManager.checkRequestAndDispatch again if needed with the comingFromRationale flag set to true
showRationaleDialog — suitable in all the cases when what you want is to show a dialog with a message. In that case, everything is already set up to function properly, you don’t have to do anything but choosing the message.

An example of the latter is:

    permissionManager.buildRequestResultsDispatcher {  
        withRequestCode(LOCATION_REQUEST_CODE) {  
            checkPermissions(LOCATION_PERMISSIONS)  
            showRationaleDialog("Location permissions are needed for this feature.")  
            doOnGranted {  
                // something ...  
            }  
            doOnDenied {  
                // something else ...  
            }  
        }  
    }

The library is still very young and new features may be added in the future, as well as the existing features may be modified.

Please let me know your opinion on this simple library and if you want any feature added to it.

Cover image by Mark König on Unsplash

How to Build a RegEx Engine in Python (Part 7: The Backtracking System)

Lorenzo Felletti — Mon, 12 Dec 2022 23:27:05 +0000

In this article, we will complete our regex engine with the backtracking system.

This article is the seventh part of my series on how to build a regular expression engine, so if this is the first article you read, I advise you to read the previous ones and then come back to this one.

The backtracking feature was one of the most difficult to implement and is by far the most interesting feature of this project.

Before coming up with the final and (hopefully) correct version of the backtracking system, I implemented a couple of “partially correct” solutions, each of them not working in some edge cases.

To find out all these bugs, testing was crucial, and mainly unit testing. If you don’t already use unit tests in your projects, I strongly suggest you start using them.

When to Backtrack?

To figure out when it is proper to backtrack, and when it is not, is not a trivial task, but it is the first thing you have to sort out when implementing backtracking.

First, you have to understand what your engine can or cannot already do, to not implement the same feature twice.

For example, our engine so far can already do some backtracking: in case of an or (OrNode), if the left branch fails it tries to match the right branch, so we don’t have to implement this in our backtracking system.

When trying to match a regular expression to a given string, let’s call it test string, and you have an engine requiring backtracking (as we saw in part 6) you have to operate these steps:

Start from index 0 of the test string, and the leftmost leaf of the AST representing the regex
Read the first character of the test string and the leftmost leaf of the AST
Do they match? If yes, move on (index 1 or the test string, next leaf in the AST), if not try to backtrack
If backtracking fails, then you have a complete fail: the test string does not match the regex.

Backtracking is possible if:

I matched an element more times than the minimum number of times it has to be matched(e.g. we have an A to be matched 1+ times, and we matched it more than once)
An element B is matched the minimum number of times, but a previous element A is matched more than the minimum number of times.

Groups Sweet Groups!

Our match_group function walks the AST going down a level every time a non-leaf node is encountered, by calling itself recursively.

So, from a match_group function call point of view, “the world is flat” — what it does is just to iterate through its children, children that are all at the same depth in the AST.

The only difference is that a leaf node is encountered there isn’t another function call to get to the new state, while when a non-leaf is found, another match_group is called, and at the end of its execution, the upper level gets the new state.

For a single match_group there is no tree, just a list of elements to iterate through.

And we can exploit this to make our backtracking system also “flat”, meaning that it takes care of only one level.

So, we will define a “flat” backtracking system, and every “level” (i.e. match_group) will have its own.

In doing this, we greatly simplify the backtracking system responsibility, but without losing generality, because the call stack will take care of executing the operations in the right order. In a way, the “depth management” part of our system comes “for free”, thanks to the call stack.

How to Backtrack?

Thanks to the fact that our engine works with groups, we don’t have to create “global” backtracking, but just a system capable of handling backtracking inside a group.

To backtrack, we have to store somewhere the information about the explored path(s), and we also need a strategy to explore all the possible paths.

The information to store is pretty simple:

An array (that we will use as a stack — called backtrack_stack) containing one element for every visited node.

Each element of the array, representing a visited node, must contain the following information:

the visited node(you don’t even need the whole node, but only its index in the children array — the aforementioned array on which match_groupoperates)
how many times have you matched a node
the minimum amount of times it must be matched
an array of how many characters were consumed each time it was matched.

That’s it, this is all the information we need to store in the backtrack stack every time we visit a node.

A backtrack stack will be created for each match_group invocation, tracking only the path explored for sibling nodes.

Let’s Backtrack

Now, with the backtrack stack so defined and the backtracking rules I described earlier, we can state that:

When there is a request for backtracking and the element on top of the stack is matched more times than the minimum, the last consumption must be removed from its consumption list and the consumed characters of the test string updated as follows: test_str_consumed_characters -= last_consumption
When there is a request for backtracking and the element on top of the stack is already matched the minimum number of times, the element should be removed and the consumed characters of the test string updated as follows: foreach consumption in consumed_list_of_the_element: test_str_consumed_characters -= consumption
When there is a request for backtracking on an empty backtrack stack, all the possible paths have been explored and the request must cause the failure of the match (i.e. regex and test string doesn’t match).

By applying these simple three rules in our code, and exploiting the recursion of match_group, we cover all the possible backtracking cases we can encounter, and we obtain the full-fledged RegEx Engine that was our goal to build.

Conclusion

With this article we finished building the RegEx Engine we wanted to build, thus this article concludes this series.

However, if one day I will want to deepen aspects of this project I didn’t so far, I cannot rule out that I will write other articles about this topic, but for now, the series is complete enough in my opinion.

Let me know if you liked this series of articles, or if you have any suggestions or doubts about the topics discussed here.

How to Build a RegEx Engine in Python (Part 6: the engine)

Lorenzo Felletti — Mon, 12 Dec 2022 23:23:58 +0000

It is finally time to write about the engine of the regex engine we’re building.

As we already saw, the parser produces an AST as a result of the parsing of a regular expression.

Now, the engine has to check whether a given string matches or not a regex.

To do so, the engine uses the AST representation of the regex, which extracts the fundamental features/elements of the regular expression, and tries to “find” if the test string has them.

The Engine

The engine is again a Python class, having a fundamental method match, which is a closure containing the engine and all the needed auxiliary methods.

Match signature:

def match(self, re: str, string: str)

Match Semantic

The semantic we will give to the match method is the following:

it returns on the first occurrence of the regex in the string
if there is no match, it tries again shifting the input string one character to the right (that is, moving the string one character to the right) until it reaches the end of the string.

That is, if the input string is abac and the regex is c, on the first attempt abac won’t match c, so match tries again, but shifting abac one character to the right this time, so tries to match bac with c, resulting in another fail, so it tries again with ac and c (failing), and, lastly, it tries c with c, resulting in a match, thus returning true.

The match function so far.

How To Match

match_group is the most important method of the engine.

It works by iterating through an AST node’s children, and by calling itself recursively when a GroupNode is found or, with some differences, when an OrNode is found.

If an OrNode is found, it checks if the left children (the one in position 0) matches, if it doesn’t, it tries the right one.

When a leaf node is found (ElementNode, …) it tries to match it.

After every match, the str_i (the index of the string) is increased of the matched characters.

The string index is set to position 0 (or the first position to consider more in general) at the beginning, and is kind of a “global variable”, but local to the match function.

The mechanism of the recursive calls makes it easy to manage the “point in the tree” and “point in the string” considered. It also allows you to think of each group as a separate entity, making it easier to follow mentally the code execution.

Obviously, this isn’t the whole engine, because as stated in the first article, we will need a backtracking system to assure to explore all the possible paths to match the string.

A little problem

In fact, the semantic of leaf nodes and groups is to match them to the most characters possible by default, and while this is convenient most of the time, there are some edge cases in which this won’t lead to a correct answer.

Let’s examine this example:

If you have a regex a+ab and a test string aab:

the resulting AST will consist of a GroupNode, with three children, all leaves
a first a to be matched [1, +∞[ times
a second a to be matched exactly one time
a final b to be matched exactly one time.

During the execution of our match function as presented, this is what will happen:

match_group is called and start iterating on its children
the first a element is matched as much as possible, so two times aa
then the engine tries to match the second a element, but it fails as now the only left character is a b
false would be returned, but we all know the correct answer is true.

This is because of the semantics we gave to our match function. What we would like the system to do is to “try another way”:

since the first element could accept 1 or more occurrences of the letter a, and it matched two of them, we would like to be able to tell it “hey, please try by matching it one time less”
in this case, the first a would be matched one time, leaving enough room to fit the second a element, and then also the b element, our third and last
this process worked, and so the answer would be true, as it should be.

This process is called backtracking and will be the topic of the next article, for now, let’s ignore the problem.

Conclusion

Overall, we covered pretty much everything we needed to cover to explain the behavior of the match method.

The skeleton of our code will look something like this

match function’s structure.

In the next article, we will cover the interesting topic of backtracking and will complete our regex engine.

How to Build a RegEx Engine in Python (Part 5: Parser conclusion)

Lorenzo Felletti — Mon, 12 Dec 2022 23:17:38 +0000

In this article, we’ll dig rapidly through the code of the parser, which will produce the AST we discussed in the previous article in output.

This will hopefully be the last piece about the parser, and then we’ll move on to the engine and the juicy part, the backtracking system.

So, the parser is contained in the Pyrser class, as we already saw in Part 3, which has the method parse, that takes as input a regular expression in the form of a string, and gives us the corresponding AST in output.

Pyrser structure

Pyrser structure.

We already spoke about the various functions and what is their purpose in previous articles.

Now we will look closer to the code of some of them. I will not explain what each line does, this isn’t the purpose of this series of articles, but I will rather express some final thoughts after.

If you’re not super interested in the code, feel free to skip reading through it.

Parse Regex Sequence

parse_re_seq code.

Parse Group

parse_group code.

Parse Element

parse_el code.

Final Words

In conclusion, the parser was not as hard to code as hard to debug.

When I first coded it I did it quickly and without having a perfectly clear idea in mind of what I wanted in output.

In fact, the parse_re function is indeed a leftover of an error:

in the beginning, the ^ and $ symbols were meant to be “absolute”, meaning that once typed, they would have been applied to every single regex in the sequence
This meant that a regex such as ^a|b$ returned false on test string cb, while it should return true because that b must be at the beginning isn’t specified in the second regex, but this original implementation maintained the “match start” from the other one
This happened because at the beginning I thought that should be the “right” behavior, and I created the RE node of the AST just for this purpose.

I later realized that this behavior was confusing and didn’t make any sense, so I had to figure out a way to change it, possibly maintaining the RE node, because the engine was already coded and using it.

In the end, parse_re remained, completely emptied of any behavior, useless, for the sake of compatibility with the — already working — engine.

Apart from this, the parser and the AST does a really good job overall, and coding a TDRDP parser isn’t so hard once you figured out a good grammar, which is no joke for non-trivial projects.

How to Build a RegEx Engine in Python (Part 4: The AST)

Lorenzo Felletti — Fri, 11 Nov 2022 09:23:43 +0000

In this article, I will present you the process I followed to end up with the final AST of the solution, and which are its strength and flaws (because yes, following my articles you won’t create a perfect solution, sorry).

So, let’s start with the logic blocks I wanted to have to build my AST.

I felt I needed:

a Group block (to group various elements)
an Element block, or more in general a Leaf block (used for elements, wildcards, match start/end, range elements, …)
an Or block, to express the alternative
a Regex block, to express the “single point of entry” (kinda useless, it will turn out)

So, each regex will have a root node called RE, the fancy name I chose for the top-level block acting as a single point of entry.

This node is actually quite useless, but also harmless, and in the next article, I will briefly discuss why it stayed in the final solution.

Having these blocks clear in mind, I created this hierarchy of Python classes:

The base class is the ASTNode, and the RE, Group, and Or nodes directly inherit from it.

All the other nodes will be leaves of our AST, meaning they will not have children nodes, so I created the intermediate class LeafNode (inheriting from ASTNode) from which they all inherit, and that serves as a base class to group them all.

Oops, I made a mistake, and then another (maybe)

I decided on the fly that it would have been good for the RE node to only have one child, so I called this property child.

Following the same idea, the GroupNode has a children property named children, and the OrNode has two properties left and right for its children.

This was making total sense in my mind, until I had to code the engine, in which, as we will see, we want to iterate through the children of these nodes.

You can guess the error now: having all these different names for (basically) the same property is not a good design choice.

You cannot write node.children and move on, you have to check the type of the node, and then access the children using the right field name.

This would make the code more error-prone, uselessly longer, and unnecessarily leads to WET code.

We need to DRY this code, but how? We need to call all these properties with the same name: children.

But the parser is already using the child, children, left, and right properties, and it would be painful to rewrite the code using the newborn property.

This is when I had the “eureka!”:

Just add the children property to every class and handle the mapping under the hood.

A (mostly harmless) flaw

The problem is that, as it is implemented, if someone changes, for example, the right child using the node.right property after the node is created the change is not propagated to the children property, and vice-versa.

This is an error, actually, but I was too lazy to figure out a different solution, and after all, changing a node after its creation doesn’t make much sense, so we can supersede this error.

Conclusion

To conclude, the AST hierarchy we created is good enough to don’t end up being an obstacle to our project, even if it has a couple flaws, not very relevant in our context.

Anyway, it is crucial to notice these flaws, and trying to avoid making the mistakes leading to them next time would be good for sure.

Cover image by Jr Korpa on Unsplash

How to Build a RegEx Engine in Python (Part 3: TDRDP)

Lorenzo Felletti — Sat, 03 Jul 2021 14:49:05 +0000

In the previous articles we spoke about how to define our grammar, how to build the lexer, and a bit about Python strings.

In this article, we will finally begin the parser, the second-hardest part of the project (the first is the engine).

TDRDP

TDRDP stands for Top-Down Recursive Descent Parsing — a useful technique to create a parser.

I won’t get into the details of when and how you can apply this technique, there’s already plenty of good articles about it, explaining it way better than I could.

Anyway, luckily (😉) the grammar we built in the first article supports it.

How to TDRDP

To implement a recursive-descent parser, we have to create a function for each non-terminal symbol of the grammar.

So, in our project, a function to parse the RE non-terminal, one for the GROUP, one for the RANGE_EL and so on.

As you noticed, in the techniques’ acronym appear the infamous word ‘recursive’ (and now you’re all scared).

Now you’re probably curious about where the recursion comes up. Well, it turns out the recursion come up in the functions calls:

Each function can call the functions of the non-terminals that appears in its productions.

For example, our grammar has the production rule RE_SEQ ::= '^'? GROUP ‘$'? ('|' RE_SEQ)? in which two non-terminals appear on the right side, RANGE_EL and RE_SEQ itself. In this case, the function corresponding to the non-terminals RANGE_EL and RE_SEQ itself can be called, hence the recursion.

To use TDRDP, once all these functions are created, we call the top-level production, serving as an entry point, which in our case is the one corresponding to the non-terminal RE and the recursive calls will take care of the entire process of parsing by themselves.

At the end, the function we called will return us the result of the parsing, whether it is a boolean, or something more complex like an AST as it is in our case.

AST

The AST, Abstract Syntax Tree, is a tree representation of something, in our case of the regular expression we are parsing.

Quoting Wikipedia: “The syntax is “abstract” in the sense that it does not represent every detail appearing in the real syntax, but rather just the structural or content-related details. For instance, grouping parentheses are implicit in the tree structure, so these do not have to be represented as separate nodes.”

It is composed of nodes in a hierarchy, with a root node at the top:

every node has one parent, except for the root node
nodes can have zero or more children
if a node does not have children, it is called a **leaf **node.

Abstract Syntax Tree example.

In the above example, we have a regular expression and a possible corresponding AST. The root node is RE, and following the hierarchy to the leaves, you will notice that the leaves have always some letters behind, that are the possible matches for the given element.

You’ll also notice that the left-most leaf letter (A) corresponds to the first letter appearing in the regex, the second with the second, and the right-most leaf with the last one, a range element accepting letters between A and C.

Our goal in the next articles will be to define an AST similar to this, and then to make the parser capable of building it.

Structure of our Parser

Without digging into the details, we can already create a skeleton for our parser.

We’ll start by creating a class called Pyrser (because I’m a funny person) and defining a init method and a parse function, inside which we will define all the functions we need to implement a TDRD parser.

Pyrser structure.

I hope you’re familiar with the concept of closure, because we’re going to use it a lot in our project.

Utilities

Let’s discuss the utilities first.

We will use the first utility function get_range_str when we will parse range elements ([a-m|0-3]) to get the number/letters contained in a given range.

The second utility next_tkn_initializer is a closure returning a function that, when called, set the current token to the next one to parse. Although not fundamental, this function is very convenient, as you will notice.

A function for each non-terminal

As you can see there is a function for each non-terminal of our grammar (except SPECIAL, that was only introduced to denote the special symbols, and QTIFIER that is replaced by parse_curly because the quantifiers ? * + will be parsed inside parse_group for simplicity and the only quantifiers needing a special treatment are only that specified with the curly brace syntax {3} {2,3} {3,} {,3}).

Each function of a non-terminal symbol returns an ASTNode object, we will see how it is done in the next article.

For this article, we won’t go deeper into the actual implementation of the parser because we need a good AST implementation first.

Cover Image by Marius Masalar on Unsplash

How to Make a Bar Chart Race With Python in 2 Minutes

Lorenzo Felletti — Sat, 19 Jun 2021 21:35:41 +0000

How to create a cool bar chart race animation the easiest way.

Prerequisites: having Python installed on your pc or being registered for Google Colaboratory.

Step 0

First create a new directory for the project (if you use Google Colaboratory skip to step 1)

mkdir my_bar_chart_race

Then create a new virtual environment, and activate it

python3 -m venv venv
source venv/bin/activate

Step 1

If you haven’t already, install pandas

pip3 install pandas

Install the library we’ll use to create the bar chart race named, you won’t guess it, bar_chart_race

pip3 instll bar_chart_race

Step 2

Now that we have the necessary libraries installed, let’s load our data.

In this tutorial, we’ll create a bar chart animation of the 2020 MotoGP World Championship’s title race. If you’re not familiar with this sport — that’s bad — don’t worry.
I will sum it up briefly for you to better understand what the data means.

How MotoGP works

MotoGP is the premier class of motorcycle road racing. A championship is held every year and consists of many races (or Grand Prix). After each Grand Prix, each rider gains some points depending on his final position at the GP. At the end of the season, the rider with the most point wins the championship.

The point system in use since 1993 is the following:

The dataset

You can find the dataset here.

Step 3

Now the cool part: coding!

Import the libraries

import pandas as pd
import bar_chart_race as bcr

Load the dataset

df = pd.read_csv('./2020-championship.csv')
df = df.set_index('race')

Let the magic happen

The final result is only one line of code away

bcr.bar_chart_race(df=df, title='2020 MotoGP Championship Race', orientation='h', sort='desc', n_bars=10, steps_per_period=40, period_length=2000)

Ok, we’ve done with the coding. You can save and run the program, and you will obtain as output the bar chart race video.

Done!

Congrats, you’ve finished. As easy as that.

That was just a short introduction to this library. You can unleash your imagination creating much more advanced races with it.

How to Build a RegEx Engine in Python (Part 2.1: Python strings)

Lorenzo Felletti — Tue, 01 Jun 2021 10:12:16 +0000

Intro

Previous episodes recap:

We want to build a RegEx Engine.
In the first episode we briefly spoke about the grammar we want to recognize.
In the second episode we built the lexer (the first of three components we need, the others are the parser, and finally the engine).

This episode is kind of a spin-off, as it isn’t much centered on the RegEx itself, as we will explore Python strings, using the project just as an excuse to learn something new.

Dear Py\thon

Aaagh…Python strings…

The problem with what we created so far is that a string in Python, by default, treats the ‘\’ as an escape.

Thus, in our implementation, the lexer can't read ‘\’, then the following character, and finally decide the meaning of it.

For example, if we escape, for whatever reason, the letter ‘c’ we will get the correct output (an ElementToken with char field = ‘c’), but for the wrong reason. But, if we escape the escape character ‘\’, writing ‘\’, we will note an unexpected behavior:

The scanned tokens vs. the expected ones. The hole between b and c is a ‘\t’, while we wanted a ‘\’.

Why is this happening? Is there a bug in the Lexer implementation we have done so far?

The answer is no, there’s no bug in the implementation.

The problem is that Python escaped the escape character for us, so our lexer read ‘\’ as one character, a backslash, and our lexer will escape the next character.

But, this is not the behavior we wanted. We wanted to escape a backslash, not the character following the escaped backslash.

Luckily, it is not difficult to ‘fix’ this behavior, and we have at least two ways to do this.

First Way

The first way is to simply pass the lexer a raw string instead of a string. To do this it is sufficient to prefix the string with an r:

lexer.scan(r'ab\\tc')

Doing this way, unfortunately, the user must remember to pass a raw string instead of a string to the lexer whenever needed.

Second Way

The problem with the first solution is that the user may forget about this particular and his regex will show unexpected behavior.

Maybe we should prevent it and automatically, and always, interpret the string as raw, thus preventing this strange behavior to ever happen.

To achieve this, we should build a function that “convert” our string representation to raw and call it right away before the lexer does any processing.

To do that, we should do something like this [1]:

def str_to_raw(s):
    raw_map = {8:r'\b', 7:r'\a', 12:r'\f', 10:r'\n', 13:r'\r', 9:r'\t', 11:r'\v'}
    return r''.join(i if ord(i) > 32 else raw_map.get(ord(i), i) for i in s)

In this way, the passed regex is “converted“ to a raw string, and interpreted as raw.

The problem with this approach is that it is extremely hacky, as you should extend raw_map to include every possible escape sequence.

This solution would be very specific on the particular Python implementation, something you should generally avoid whenever possible.

Conclusion

The first solution is most likely the one you want, because of how hacky the second is, but you’re free to implement the solution you prefer or find a better one on your own.

Resources

[1] How to create raw string from string variable in python? — Stack Overflow — Stack Overflow

Cover by Pankaj Patel on Unsplash.

How to Build a RegEx Engine in Python (Part 2: The Lexer)

Lorenzo Felletti — Sun, 23 May 2021 22:08:06 +0000

In the previous article, we spoke about grammar and what we need to complete this project.

It’s now time to finally dig into the coding part.

Set Up The Environment

To set up the environment we first need to create a folder for the project and the virtualenv we’ll use for it.

mkdir pyregex  
cd pyregexpython3 -m venv venv  
source venv/bin/activate

For this project, we will use a couple of python libraries:

pip3 install numpy  
pip3 install autopep8

Autopep8 isn’t needed for the project itself, but I use it to help me with keeping formatting uniform throughout the codebase.

On the other hand, we’ll use NumPy to build the AST.

The Folder Structure

Inside pyregex, we create an src folder where we will place all our code.

The __init__.py files you see are empty files needed by python to navigate through the project.

Building The Lexer

What Is a Lexer

A Lexer (or Scanner) is a component that takes a string as input and outputs a list (array, or whatever) of tokens, i.e. “category of words, logical tokens, of a grammar”.

A brief example:

Input string:

English language lexer output:

The Tokens

Our lexer will have to recognize different types of tokens (character, parenthesis, brackets, escape, …).

To do so we first need to define a hierarchy of tokens types.

In the list above you can see the hierarchy of tokens we’re going to create and a few implemented token classes. (Remember that the complete code is available here).

For many of the tokens, I created first a base class to represent the type and then more specialized ones for the actual char we choose to be the one representing the type.

This wasn’t strictly necessary, but adds not much work and may help you keep the code coherent and makes it easy to overload token types (maybe one day I will want ‘#’ to be an escape too for some reason).

Finally the Lexer

The lexer itself is a quite simple component.

In a file named lexer.py, we create the class Lexer which will implement the scan method that will take a string as input and outputs a NumPy array of the tokens recognized.

To recognize the tokens the Lexer iterate through each character of the input string and assigns it the corresponding token.

As you can see it is pretty straightforward. The only two tricky points are the handling of the escape, ‘^’ and curly brace.

The escape
To handle the escape I created a support variable escape_found which is set to false at the end of each while loop.

When an escape it’s actually found, the variable is set to true and the continue clause immediately after restarting the loop without setting it to false again. Thanks to this, in the next iteration, the variable value would be true, thus triggering the specific condition (if escape_found).

The code specific to the condition is then executed and, since there is no continuity, the end of the loop code is reached and escape_found is set again to false.

The ‘^’
This is by far the most interesting in my opinion because the reality is that, unless you find it as the first character, you can’t be sure if what you found is a negation, like in [^abc] (i.e. match a char that is anything but a, b, or a match start token in a subsequent regex, like in ^abc$|^012$ .

Since this is impossible to tell, in our implementation each ‘^’ after index 0 is recognized by the lexer as a Circumflex (NotToken), and then it will be the parser to have the final word on the question.

The Left curly brace
When a left curly brace ‘{‘ is met, we enter to a kind of “sub-grammar” that recognizes the quantifier {min, max} (with min or max eventually omitted).

Thus, the number of allowed tokens tightens, and it is always good to recognize early badly formatted regexes.

Because, if you can eliminate some grammar errors in the Lexer, which is fairly simple, you won’t have to check for the same error again in the Parser, which is already more complex by itself, reducing (by a tiny bit) the complexity of it.

Conclusion

As you probably noted, the Lexer is a very simple component to design and implement.

Harder times will come as we’ll design and implement the Parser, and even harder with the engine (and the backtracking system above all).

I hope you enjoyed reading this article. For this part I think we did enough, don’t hesitate to ask me questions if something isn’t clear to you, I’ll be glad to answer any questions!

Cover Image by 鏡飛匙 on Unsplash

How to Build a RegEx Engine in Python (Part 1: The Grammar)

Lorenzo Felletti — Sun, 23 May 2021 21:47:59 +0000

In this series of articles, we will follow the steps to build a RegEx Engine in Python. I chose Python over the many alternatives for a few reasons:

It is well integrated with the Linux command line
Because yes.

In a way, I find Python to be a “less verbose version of Java” and a “less confusing version of JavaScript”, which were the other two alternatives I considered.

Please let me explain before get mad at me.

Before starting this project I had no idea how things should be done, how to code the various modules, and so on.

I had to figure everything out by myself.

And, when I don’t know how to do things exactly, I find JS a bit too confusing, it’s just a feeling, not a universal truth, and I find that with Java I can organize my ideas better.

But, since I don’t like how verbose and limiting Java is in some way, but wanted classes, and I love having functions as first-class citizens, Python seemed like the perfect blend to me.

Anyway, it’s now time to start with the project itself.

What We Need

To match a string with a regular expression of our will we need to complete a few steps:

understand the regular expression
create an internal representation of it (so that we can see if a passed string match with it)
match the string with the regex, using the internal representation we built of it.

To complete the first two steps we need two components:

a Lexer (or scanner) to parse the regex in tokens (“words”, generic “pieces of information”). As an example in the sentence “I am beautiful, very beautiful” each word (“I”, “am”, …) is a token of type “word” and the comma is a token of type “punctuation”
a Parser which read all the tokens in sequence and “understands” them, building while doing so an internal representation of the regex (which will be a tree, called Abstract Syntax Tree, AST for the friends).

To accomplish the third step we need to build a component able to take as input the AST built by the Parser and a string, and visiting the tree to match each leaf of the tree with some part of the string (and something more, we will discuss later).

This component is named:

Engine.

The Roadmap

So, now that we know the modules we will have to code, let’s build a roadmap:

define the RegEx grammar we want to recognize
build the lexer
build the parser
build the engine
enjoy.

The Grammar

It’s now time to discuss the grammar we want to recognize.

I assume you know what a formal grammar is and that you understand the EBNF notation, if not, DON’T PANIC, google it.

The regex grammar we will recognize is the following:

Top-level production RE ::= RE_SEQ is indeed useless but is there because I used it in one of the early versions of the project and I was too lazy to remove it later. Anyway, it is completely harmless, I promise, and it will cost you just a couple of lines of code and only one more call on the stack during execution.

The Grammar Explained

The features that the described grammar will be able to implement are the following:

So, valid regexes are:

Examples of recognized regexes.

Conclusion

You can browse the code of the final result here.

I think that can be enough for the first part, more in the next articles of the series.

In the next article, we will set up the environment and start coding, starting from the lexer.

See you soon! I hope you enjoyed this read!

Please feel free to reply if you don’t understand something, need some hints, whatever. I’ll be glad to answer you.

Cover Image by Pankaj Patel on Unsplash

DEV Community: Lorenzo Felletti

How to Create a Bluetooth LE Scanner for Android

What You Need to Follow This Tutorial

Creating the Project

Managing the Permissions

Scanning for devices

The Main Activity

The GUI

Conclusions

Load Environment on Directory Change

Change gcloud context, az login, Kubernetes context, set environment variables, and more just changing directory

Why not Just Overriding cd?

Android Permissions Made Easy

The Dispatcher’s DSL

The checkRequestAndDispatch Method

How To Use The Library

The showRationaleDialog Function

How to Build a RegEx Engine in Python (Part 7: The Backtracking System)

When to Backtrack?

Groups Sweet Groups!

How to Backtrack?

Let’s Backtrack

Conclusion

How to Build a RegEx Engine in Python (Part 6: the engine)

The Engine

Match Semantic

How To Match

A little problem

Conclusion

How to Build a RegEx Engine in Python (Part 5: Parser conclusion)

Pyrser structure

Parse Regex Sequence

Parse Group

Parse Element

Final Words

How to Build a RegEx Engine in Python (Part 4: The AST)

Oops, I made a mistake, and then another (maybe)

A (mostly harmless) flaw

Conclusion

How to Build a RegEx Engine in Python (Part 3: TDRDP)

TDRDP

How to TDRDP

AST

Structure of our Parser

Utilities

A function for each non-terminal

How to Make a Bar Chart Race With Python in 2 Minutes

How to create a cool bar chart race animation the easiest way.

Step 0

Step 1

Step 2

How MotoGP works

The dataset

Step 3

Import the libraries

Load the dataset

Let the magic happen

Done!

How to Build a RegEx Engine in Python (Part 2.1: Python strings)

Intro

Dear Py\thon

First Way

Second Way

Conclusion

Resources

How to Build a RegEx Engine in Python (Part 2: The Lexer)

Set Up The Environment

The Folder Structure

Building The Lexer

What Is a Lexer

A brief example:

The Tokens

Finally the Lexer

Conclusion

How to Build a RegEx Engine in Python (Part 1: The Grammar)

What We Need

The Roadmap

The Grammar

The Grammar Explained

Conclusion

Change `gcloud` context, `az` login, Kubernetes context, set environment variables, and more just changing directory

Why not Just Overriding `cd`?

The `checkRequestAndDispatch` Method