Not that bad of a description i guess.
Before I get started talking about everything lexical analysis, I do want to quickly dip my toes into regex; this is because most of my ideas in this post come from how regex works.
Knowing how to use regex (regular expressions) can be super useful in producing awesome programs. I mean I use regex both in my blog and note software to be able to look for the given keyword lines and provide a count.
Recently, I have been looking into compilers and performing lexical analysis and what came across my mind was using regular expressions to match symbols across provided source code to ensure that the usage of certain variables do not produce confusing statements.
For example in python:
if __name__ == "__main__":
# obviously, this isn't an integer
# and python would not give a damn
# because python is type-agnostic anyways...
foo:int = "string"
# yet this works just fine...
print(foo)
The primary idea of regex usage in this case, is doing lexical analysis to point out
“hey this is bad programming practice because you annotate this as an int, but it really should be a string.”
But obviously no one writes code like this. As a matter of fact, most seasoned python developers I’ve seen don’t even provide type annotations… if at all.
I mean sure; in a non-prod environment who gives a shit? But these bad practices sometimes do slip through to production level code. Wouldn’t it be awesome if there were better static analysis tools that actually do look at symbols in our software to track their usage? Well here’s the issue with trying to do that with a language like python: Variable reassignment is the exact same as initialization.
def maybe_this_is_a_bad_language():
"""
Perfectly fine python code for
whatever reason...
"""
# create xyz with the value 32
xyz=32
# change the value
xyz=1
# now change the value to a string
xyz="zxcvbn"
# finally, now set it to none
xyz=None
return xyz
If you have been working with python long enough, you have certainly come across code like this: a single variable somehow changes its type in another function, or some method decides to change the value of any attribute unexpectedly and then you have to spend hours debugging.
Introducing regex. Regex (short form of regular expression) allows you
to parse strings of text and it will allow you to search for matches within a given set of
characters, rules, or text you pass into it. The idea was created by Stephen Cole Kleene
in the 1950’s, but wasn’t widespreadly used until the 1970’s-80’s with the advent of UNIX.
At this point you should be familiar with grep; grep was a CLI utility written by Ken Thompson
that does pattern search using regular expressions. Its name is literally derived from the g/re/p
ed command that performed such regular expression searches.
Using regex, we can track the use of a variable throughout the entirety of a program to see
what it does. grep has so many use-cases it’s actually kind of insane, below is a list of
things I’ve had used grep/regex for:
Ideally what I want to do with regex is use it to track variables, and use regex to essentially look at symbol usage in C programs to be able to convert it over to Rust. Procedure would look something like this:
Given any random .c file (that passes compilation); ensure that you can replicate the functionality of such a program in another language such as Rust. Maintain used data structures.
Ok, this is a very big task because there are several different factors we have to account for:
In addition, the fact that we are able to maintain the same data structures in a program means that it should be slightly easier to parse. For example, let’s look at a static sized buffer:
int main(){
int* cv[10];
return 0;
}
In rust, we can represent that directly as:
fn main()-> i32{
let x: [i32;10] = [0;10]
0
}
This isn’t so bad right? Now let’s look at this code:
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Vectors in C.
typedef struct Vector_u64 {
unsigned long long int *buffer;
size_t length;
size_t capacity;
} Vector_u64;
//! inits the new u64 buffer.
Vector_u64 vec64_new() {
Vector_u64 new;
size_t length = 0;
size_t init_size = 2;
size_t capacity = sizeof(unsigned long long int);
fprintf(stdout, "allocating new buffer...\n");
new.buffer = calloc(capacity, init_size);
if (new.buffer == NULL) {
fprintf(stderr, "failed to allocate memory to the new buffer\n");
exit(1);
}
new.capacity = capacity * init_size;
fprintf(stderr, "Created a new buffer of size %lu\n", new.capacity);
new.length = 0;
return new;
}
//! gets a value from the array
unsigned long long int vec64_get(Vector_u64 *vector, size_t idx) {
if (idx > vector->length) {
// return the last index if anything
return vector->buffer[vector->length - 1];
}
return vector->buffer[idx];
}
//! Reallocates the u64 buffer.
static void vec64_reallocate(Vector_u64 *vector) {
size_t new_size = vector->capacity * 2;
fprintf(stdout, "reallocating new buffer w/ to fit %lu numbers...\n",
(new_size / sizeof(unsigned long long) / 2) + vector->length);
unsigned long long int *new_ptr =
(unsigned long long int *)realloc(vector->buffer, new_size);
if (new_ptr == NULL) {
fprintf(stderr, "failed to reallocate buffer.\n");
exit(1);
}
vector->capacity = new_size;
}
/// shrinks the vector to size
void vec64_shrink(Vector_u64 *vector) {
unsigned long long int *new_buf =
calloc(sizeof(unsigned long long), vector->length);
memcpy(new_buf, vector->buffer, vector->length);
vector->capacity = sizeof(unsigned long long) * vector->length;
vector->buffer = new_buf;
}
void vec64_free(Vector_u64 *vector) { free(vector->buffer); }
/// push a new value to the vector at the last index.
void vec64_push(Vector_u64 *vector, unsigned long long int number) {
size_t current_capacity = (vector->length) * sizeof(unsigned long long int);
if (current_capacity == vector->capacity) {
vec64_reallocate(vector);
}
size_t last_idx = vector->length;
vector->buffer[last_idx] = number;
vector->length += 1;
};
//! pop a value from the array, return the value popped
unsigned long long int vec64_pop(Vector_u64 *vector, size_t idx) {
if (idx > vector->length) {
fprintf(stderr, "failed to pop value; %lu is out of range", idx);
return EXIT_FAILURE;
}
// start
unsigned long long int value = vector->buffer[idx];
if (idx == vector->length - 1) {
vector->buffer[idx] = 0;
vector->length -= 1;
return value;
}
// otherwise, do a left shift
for (size_t i = idx; i < vector->length; i++) {
vector->buffer[i] = vector->buffer[i + 1];
}
vector->length -= 1;
// shrink
size_t half_cap = vector->capacity / 2;
size_t current_cap = vector->length * sizeof(unsigned long long);
if (current_cap == half_cap) {
vec64_shrink(vector);
}
return value;
}
int main(int argc, char *argv[]) {
Vector_u64 newvec = vec64_new();
for (size_t i = 0; i < 128; ++i) {
vec64_push(&newvec, i);
fprintf(stdout, "newvec[%lu] = %llu\n", i, vec64_get(&newvec, i));
}
vec64_pop(&newvec, 63);
fprintf(stdout, "capacity= %lu\n", newvec.capacity);
for (size_t j = 0; j < newvec.length; ++j) {
fprintf(stdout, "\nnewvec[%lu] = %llu\n", j, vec64_get(&newvec, j));
unsigned long long popped = vec64_pop(&newvec, j);
fprintf(stdout, "popped %llu\n", popped);
fprintf(stdout, "newvec[%lu] = %llu\n", j, vec64_get(&newvec, j));
}
fprintf(stdout, "final capacity= %lu\n", newvec.capacity);
vec64_free(&newvec);
return EXIT_SUCCESS;
}
This is one of my implementations of std::vec from the C++ standard library into C for 64-bit integers.
The issue is that there already has a Rust implementation in the standard library right? So how exactly do
we discern between something that already exists– and someone’s implementation of a data structure?.
Now, this isn’t the most beautiful C code– but the idea behind why I shared this code to begin with was to do with the following struct. It’s listed at the very top of the previous code block, but for the sake of demonstative purposes, I changed the name of both the type and fields.
typedef struct x {
unsigned long long int *i;
size_t z;
size_t p;
} x;
The C code has this struct which peaks our interest. We see the following fields associated with their types clearly:
unsigned long long int *: a pointer to a unsigned 64-bit integer.size_t: two fields distinct for keeping track of 2 unnamed values.From this alone, we can probably make an assumption that this is a vector type/dynamically allocated array. This is because arrays almost always contain these fields. However, the question then gets raised:
What matters more implementation details? Or intended results?